Sign in to follow this  
Waaayoff

Handling A* pathfinding algorithm data?

Recommended Posts

What do people usually use to store data like which node is walkable, in which list is the node (open or closed).. which node is its parent, what is each node's F,G and H values.. stuff like that.. Should i use linked lists? Also, on an unrelated subject, how fast/efficient are linked lists? EDIT: What about Binary trees?

Share this post


Link to post
Share on other sites
What language are you using? What kind of search space are you exploring?

Don't confuse your underlying map with the data you build up during the search. A node in your map graph may be walkable or not, but that doesn't mean your A* node is walkable - they are 2 different concepts, even if you are sneaky and use the same data structure for both. You wouldn't even generate/evaluation an A* node for a place on the underlying map that is unwalkable as that would be pointless.

It's common to use some variant of a priority queue for the open list (as you need quick access to the next best node) and a hash table for the closed list (as you need to quickly find if an node is already in there).

For each node you just create a structure with exactly the values you want. Generally speaking you need to store F, G, and a parent reference, but it really depends on the structures you're using.

Share this post


Link to post
Share on other sites
I'm using c++, and the pathfinding is for a pacman clone, lol.

Quote:
Don't confuse your underlying map with the data you build up during the search. A node in your map graph may be walkable or not, but that doesn't mean your A* node is walkable - they are 2 different concepts, even if you are sneaky and use the same data structure for both. You wouldn't even generate/evaluation an A* node for a place on the underlying map that is unwalkable as that would be pointless.


I always imagined that the A* nodes are simply positions in a 2d array which would correspond to the map space..

??

Share this post


Link to post
Share on other sites
There are bunch of articles out there on the A* (A star) algorithm, and I have to admit it took me quite a while to understand them. At the end I found this article to be very useful (Since I was able to step through the c# source code):
http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527

But you may want to start with this:
http://www.policyalmanac.org/games/aStarTutorial.htm

and this one has a really good explanation too:
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Good luck! For me, it was a tough obstacle to overcome!

Share this post


Link to post
Share on other sites
Quote:
Original post by Waaayoff
I'm using c++, and the pathfinding is for a pacman clone, lol.

Quote:
Don't confuse your underlying map with the data you build up during the search. A node in your map graph may be walkable or not, but that doesn't mean your A* node is walkable - they are 2 different concepts, even if you are sneaky and use the same data structure for both. You wouldn't even generate/evaluation an A* node for a place on the underlying map that is unwalkable as that would be pointless.


I always imagined that the A* nodes are simply positions in a 2d array which would correspond to the map space..

??

if you make the ghosts chase the player using A*,you are dooming the player to never win. ghosts with A* will always get to the player before the player consumes all points.
if you look at the original pacman i think they ghosts just move randomly.

Share this post


Link to post
Share on other sites
@ grayaii:
Thanks i'll check out the links :)

Quote:
Original post by Bru
if you make the ghosts chase the player using A*,you are dooming the player to never win. ghosts with A* will always get to the player before the player consumes all points.
if you look at the original pacman i think they ghosts just move randomly.


I read somewhere that the ghosts behave like this:

Ghost 1: Takes shortest path to the player (this is what A* is for)
Ghost 2: Takes the longest path to the player (no idea how to do this yet)
EDIT: Actually, i think i can do this with A* by simply checking for highest F value instead of Lowest
EDIT2: Nevermind, that way the Ghost would never catch the player.. ever.
Ghost 3: Wanders randomly (easy :P)
Ghost 4: Wanders relatively at the middle of the maze trying to cut off the player when he approaches.

[Edited by - Waaayoff on March 12, 2010 3:30:15 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Bru
if you make the ghosts chase the player using A*,you are dooming the player to never win. ghosts with A* will always get to the player before the player consumes all points.

That's not true, because you keep moving...

Share this post


Link to post
Share on other sites
www.3dbuzz.com have an A* series of videos that they have recently made.
3dbuzz tend to make interesting tutorial videos that are also in depth.

Unfortunately, I think that these videos are for C#, but the differences shouldn't be too large between C++ and C# surely?

Anyway, if you want to have a look, hopefully this helps you.
http://www.3dbuzz.com/vbforum/content.php?150-AI-Programming-Pathfinding-with-Astar

Another unfortunate thing is it seems you have to pay to watch the videos, which is fair enough considering the quality of 3d buzz tutorial videos, but I understand most people don't want to spend money to learn.
So it's up to you really.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this