Jump to content
  • Advertisement
Sign in to follow this  
Betrayer_of_Code

Setting up A* Pathfinding

This topic is 5388 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Forgot about it, sorry.
A pointer to a closed list element.
The nodes you travel are stored there.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!