Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (684) Games in Android Showcase (196) games submitted by our members Games in WIP (751) 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 3023 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.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: 148
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.

 orrenravid (228 views) 2016-07-16 03:57:23 theagentd (296 views) 2016-07-11 14:28:54 Hydroque (383 views) 2016-07-06 05:56:57 Hydroque (533 views) 2016-07-03 08:52:54 GrandCastle (403 views) 2016-07-01 09:13:47 GrandCastle (396 views) 2016-07-01 09:09:45 CopyableCougar4 (449 views) 2016-06-25 16:56:52 Hydroque (422 views) 2016-06-22 02:17:53 SwampChicken (387 views) 2016-06-20 13:22:57 SwampChicken (306 views) 2016-06-20 13:22:49
 Archive 30x Slyth2727 24x Brynn 23x EgonOlsen 22x orangepascal 22x TritonDreyja 21x orange451 20x DavidBVal 19x Spasi 18x Opiop 11x princec 11x LiquidNitrogen 11x Phased 11x Longor1996 10x ziozio 10x KaiHH 10x
 Making a Dynamic Plugin Systemby Hydroque2016-06-25 00:13:25Java Data structures2016-06-13 21:22:09Java Data structures2016-06-13 21:20:42FPS Camera Tutorialby Hydroque2016-05-22 05:40:58Website offering 3D Models specifically for games for freeby vusman2016-05-18 17:23:09Website offering 3D Models specifically for games for freeby vusman2016-05-09 08:50:56Website offering 3D Models specifically for games for freeby vusman2016-05-06 11:10:21Website offering 3D Models specifically for games for freeby vusman2016-04-29 12:56:17
 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