Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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 2267 times)
0 Members and 1 Guest are viewing this topic.
Offline 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!
Offline 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.

Offline 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.  Wink 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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.

Offline 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...

Offline Mike

JGO Wizard


Medals: 76
Projects: 1
Exp: 6 years


Java guru wanabee


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

These two threads should be able to help you out Smiley

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 Smiley
State of Fortune | Discussion thread @ JGO
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (16 views)
2014-09-21 02:42:18

BurntPizza (13 views)
2014-09-21 01:30:30

moogie (13 views)
2014-09-21 00:26:15

UprightPath (24 views)
2014-09-20 20:14:06

BurntPizza (27 views)
2014-09-19 03:14:18

Dwinin (40 views)
2014-09-12 09:08:26

Norakomi (71 views)
2014-09-10 13:57:51

TehJavaDev (96 views)
2014-09-10 06:39:09

Tekkerue (49 views)
2014-09-09 02:24:56

mitcheeb (70 views)
2014-09-08 06:06:29
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!