Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (565) Games in Android Showcase (151) games submitted by our members Games in WIP (605) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Getting started with A* :x  (Read 2503 times) 0 Members and 1 Guest are viewing this topic.
StonePickaxes

JGO Coder

Medals: 4
Projects: 2

Nathan Kramber

 « Posted 2012-05-23 02:11:27 »

So I recently implemented basic mouse movement into my game, and I put in VERY basic path finding. I knew that this wouldn't work for the final game, and I had already heard of A*, so I thought I would look into it.

However, I can't seem to find a good explanation of how it works and how to implement it.

Any chance I could get a good explanation (or get linked to one) from you guys?

Thanks.
-Nate

p.s. You can see said game here.

Check out my website!
UprightPath
 « Reply #1 - Posted 2012-05-23 03:01:43 »

Beep, boop, da-be-da-boop.

Ahem! A* is probably not what you want to start out, with you don't already understand how to do Dijkstra's and all of that.

Anyway, what A* star does is...
1) Keeps track of visited nodes and the 'best cost' to get to that node. (Typically called the closed list).
2) Keeps track of nodes that can be visited during the next iteration, sorted by (And this is important) the distance from your start to that node plus a guess as to how far it is away from the goal.

Then, the algorithm works as follows:
1) Put the starting node in the 'open' queue.
2) Pop the top off your open queue.
3) Put it in the closed list.
4) Check if it's the goal. If you haven't reached it yet, set it as the best, otherwise check if it's the best (Meaning least ground covered).
4.1) If it's not the goal, get all of its adjacent nodes.
5.1) Check if getting to that node would take longer than your current best path. If it does discard it, otherwise...
5.2) Then, check whether it's in the closed list. If it is, check if it'd be a shorter path to get to it.*** If it is, compute the 'expected distance' then add it to the open list.
5.3) If it's not in the closed list, compute the 'expected distance' then add it to the open list.
6) If there's a node in the open list, go back to 2.
7) The best path is your best path.

*** Depending on how you want to implement it, and how "good" your guess of distance remaining is, you might be able to skip this part.

The guess depends on your map and various other stuff. Typically, you use something like a Manhattan distance (Think adding the opposite and adjacent sides of the right angle formed by the line between the two positions) or the Euclidean distance (Straight line distance). These are 'good' for a given value of good.

If you want some real code for this, give me a poke and I'll write up something.

Longarmx
 « Reply #2 - Posted 2012-05-23 05:18:55 »

Yes please! I have also been looking around for a couple of weeks and have started multiple time to try to implement this but I cant. I understand how the theory works its just the actual code that screws me up.  I would really enjoy it if you could come up with a little example.

Thanks,
Longarmx

krasse
 « Reply #3 - Posted 2012-05-23 11:22:47 »

Also, a priority queue is a good data structure for A* when you select nodes to expand (depending on heuristic and current cost).
I use a binary heap for this.

UprightPath
 « Reply #4 - Posted 2012-05-23 17:19:00 »

Well, since (More than one) person asked for it, here's a link to my rather basic A* pathfinder.

It's not very well implemented, 'cause I did it in like thirty minutes, however Here. It's currently just a basic 'one cost' tile thing, which makes it rather trivial and it's not really commented, but...

Mike

« JGO Spiffy Duke »

Medals: 142
Projects: 1
Exp: 6 years

Java guru wannabe

 « Reply #5 - Posted 2012-05-23 18:00:09 »

http://www.java-gaming.org/topics/pathfinding-for-beginners/23981/view.html
http://www.java-gaming.org/topics/introduction-to-pathfinding/25158/view.html

Mike

My current game, Minecraft meets Farmville and goes online
State of Fortune | Discussion thread @ JGO
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 theagentd (11 views) 2015-03-27 23:08:20 wxwsk8er (52 views) 2015-03-20 15:39:46 Fairy Tailz (46 views) 2015-03-15 21:52:20 Olo (28 views) 2015-03-13 17:51:59 Olo (30 views) 2015-03-13 17:50:51 Olo (37 views) 2015-03-13 17:50:16 Olo (43 views) 2015-03-13 17:47:07 ClaasJG (56 views) 2015-03-10 11:36:42 ClaasJG (41 views) 2015-03-10 11:33:01 Pippogeek (47 views) 2015-03-05 14:36:23
 LiquidNitrogen 23x BurntPizza 21x KevinWorkman 21x basil_ 21x EgonOlsen 17x theagentd 16x Roquen 16x princec 12x Riven 11x Varkas 10x SHC 9x Ashedragon 8x Ecumene 7x nsigma 7x wessles 7x phu004 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org