Setting up A* Pathfinding
Author
I have been looking up, and working on, psudocode to write a pathfinder using A*. A lot of the places I have looked tie linked lists into it. I would like to know how I would use a linked list to create an A* pathfinder.
My steup:
1. Load the Maze
2. Place all the numbers for the maze into an array[30][30];
loop
3. A* stuff that I kind of understand...
4. If(if current->next->solution == true)
5a. Solved
5b.Top of Loop
Could someone explain the concept of A* a little more and show how I would use a linked list in this?
Thanks for your time.
For the record lists are one of the worst ways to implement the queues in a A* algorithm, that said, it's is also one of the simplest ways to do it too, so since you don't really fully understand A* i guess it will do for now =).
And since your map is small, i'm assuming this from the array[30][30], a list might actually perform pretty good.
About A*, i am not going to explain it here, it would probably be a little extensive and since i don't have the gift of teaching, i'de probably not be able to explain A* as good as some of the articles right here in Gamedev.
Check out Artificial Intelligence in the Articles section, i think you'll find good help there.
Cheers
And since your map is small, i'm assuming this from the array[30][30], a list might actually perform pretty good.
About A*, i am not going to explain it here, it would probably be a little extensive and since i don't have the gift of teaching, i'de probably not be able to explain A* as good as some of the articles right here in Gamedev.
Check out Artificial Intelligence in the Articles section, i think you'll find good help there.
Cheers
You might want to check these...
http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.policyalmanac.org/games/binaryHeaps.htm
http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#S5
http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.policyalmanac.org/games/binaryHeaps.htm
http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#S5
Author
Ive been reading some of the stuff you ahve showed me and I have a less general question...
"Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too. For each of these squares, save point A as its “parent square”. This parent square stuff is important when we want to trace our path. It will be explained more later."
struct open
{
int cost;
open *parent;
open *next;
};
in some function:
{
current->parent = previous;
}
//I really dont think this will work, because each parent has several "children" so the node before it will not neccesarily be the parent...
Is that how I would define the parent pointer? or would that just point to the next node like next does? If I cant define it like that how would I?
"Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too. For each of these squares, save point A as its “parent square”. This parent square stuff is important when we want to trace our path. It will be explained more later."
struct open
{
int cost;
open *parent;
open *next;
};
in some function:
{
current->parent = previous;
}
//I really dont think this will work, because each parent has several "children" so the node before it will not neccesarily be the parent...
Is that how I would define the parent pointer? or would that just point to the next node like next does? If I cant define it like that how would I?
You shouldn't point back to a node in the open list, eventualy those nodes will be removed from the open list, the parent's node job is to allow to find the full path when you reach the destiny.
The A* puts the adjacent(of the current one) squares on the open list, then choses the one that's the most likely to be in the correct path, and puts it's adjacent squares in the open list and so on. When you reach the end, you'll want to return the FULL PATH.
What do you have when you are at the end? The end node, you know just the end node.
How do you know the path you traveled till you got there? You put the end node in a array(or some other structure), check out it's parent, and put the parent in the same array, and check the parent's parent, and put it in the array and so on until you get to the beggining node.
When this is finished you have put the intire path in a array(or some other structure), that you can return for the user of the funtion to use in wich way he sees fit.
Cheers
The A* puts the adjacent(of the current one) squares on the open list, then choses the one that's the most likely to be in the correct path, and puts it's adjacent squares in the open list and so on. When you reach the end, you'll want to return the FULL PATH.
What do you have when you are at the end? The end node, you know just the end node.
How do you know the path you traveled till you got there? You put the end node in a array(or some other structure), check out it's parent, and put the parent in the same array, and check the parent's parent, and put it in the array and so on until you get to the beggining node.
When this is finished you have put the intire path in a array(or some other structure), that you can return for the user of the funtion to use in wich way he sees fit.
Cheers
Author
Aye, I learned that later, after I posted. But HOW do you find out which node is the parent, is what I was tryign to ask. And would you store it as a pointer? and int? what?
Forgot about it, sorry.
A pointer to a closed list element.
The nodes you travel are stored there.
A pointer to a closed list element.
The nodes you travel are stored there.
For the sake of optimization, you might want to use a priority queue of pointers instead of a linked list and a bit/bool vector to signal the closed nodes.
If you need to keep two full lists and still maintain their pointers, then you might want to combine both node types into one class (if you're using C++) and build your lists to be of pointers to that class. In such case, whether the node was closed or open at the time you pointed to it wouldn't matter.
Depending on what you actually keep in your nodes, you may want to have two derived classes for the concrete objects.
If you need to keep two full lists and still maintain their pointers, then you might want to combine both node types into one class (if you're using C++) and build your lists to be of pointers to that class. In such case, whether the node was closed or open at the time you pointed to it wouldn't matter.
Depending on what you actually keep in your nodes, you may want to have two derived classes for the concrete objects.
Author
Well, I have not really looked into priority queues or vectors yet so...I'll go look those up and get back to you :D
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
