CODEWITHSUNDEEP
path-finding
Anton
Anton

Reputation: 11

A* Star Pathfinding help!

On many A* Start Pathfinding tutorials the last part is always something like this;

Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

I don't really get what I am suppose to do to implement this in my A * star Pathfinding. The current method I am using is the following; I save the path, reverse it, runs the pathfinder again but I get neighboring nodes by checking if they are on the original path list and adding them if they are on the list.

The problem with this method is that I get some strange path sometimes.

Upvotes: 1

Views: 2029

Answers (2)

vdsf
vdsf

Reputation: 1618

You simply need to keep a "came from" map for the nodes you visit.

When you reach your target, you can work your way back to the source node by recursively polling "came from" on the node until the node is the source.

Note that this will give you a reversed path. You simply reverse this path and you got your shortest path from source to target.

You don't have to run your shortest path algorithm again.

Upvotes: 3

Anthony
Anthony

Reputation: 2296

If you haven't already read this, take a look: http://theory.stanford.edu/~amitp/GameProgramming/

That was my resource when I implemented A* for a game. The "parent" square you mentioned isn't a good name. As turbovince mentioned, it's not the "parent" node but rather where you came from. Each node has a reference from whence it came, so when you finally land on the target you should be able to traverse these references back to the origin.

Upvotes: 1

Related Questions