Handling A* pathfinding algorithm data?
Author
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?
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.
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.
Author
I'm using c++, and the pathfinding is for a pacman clone, lol.
I always imagined that the A* nodes are simply positions in a 2d array which would correspond to the map space..
??
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..
??
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!
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!
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.
Author
@ grayaii:
Thanks i'll check out the links :)
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]
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]
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...
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
