CODEWITHSUNDEEP
c#algorithmpath-finding
Jesse
Jesse

Reputation: 562

A* Pathfinding.. Saving the path

I'm stuck with my pathfinding program. Currently it can find the correct path but I'm unable to draw the path only. I did a little variation on only going horizontal & vertical.. No diagonal. So only using G cost and no H or F costs.

Using this tutorial

It says: 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.

Q: How can I find the parent square and work my way back?

Currently I print my closed list nodes and getting this: enter image description here

Upvotes: 1

Views: 666

Answers (1)

Patashu
Patashu

Reputation: 21793

When you do an A* pathfind, each tile should also store what tile was its parent (e.g. what tile discovered the best path to me). This way, when you first find a path that reaches the ending, you reconstruct the path as follows:

  • Add the ending tile to the path.
  • Add the ending tile's parent to the path.
  • Add the ending tile's parent's parent to the path...

... Until you're at the start.

If this doesn't work (gives you not the best path), you're probably not letting the first path to a tile be overriden by a better path OR you used a heuristic that's too overconfident and the actual fastest path was never tested because it found a path to the ending already and assumed by the heuristic and by A*'s greedy nature no other path is faster.

Upvotes: 4

Related Questions