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

JGO Coder

Medals: 5
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) For each adjacent...
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

 Games published by our own members! Check 'em out!
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: 149
Projects: 1
Exp: 6 years

Java guru wannabe

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

These two threads should be able to help you out

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

 EgonOlsen (45 views) 2018-06-10 19:43:48 EgonOlsen (27 views) 2018-06-10 19:43:44 EgonOlsen (47 views) 2018-06-10 19:43:20 DesertCoockie (210 views) 2018-05-13 18:23:11 nelsongames (127 views) 2018-04-24 18:15:36 nelsongames (126 views) 2018-04-24 18:14:32 ivj94 (867 views) 2018-03-24 14:47:39 ivj94 (128 views) 2018-03-24 14:46:31 ivj94 (779 views) 2018-03-24 14:43:53 Solater (143 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 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