0

So when you have the A* Algorithm that correctly finds the path and now you have the Closed list. How do you determine the Shortest path from that closed list?

I've been looking for answers for this for weeks but I just don't understand. I've looked like every video and wiki page.

What I have understood so far is that you have to somehow mark the best neighbor node and use that? I made a question about this 2 weeks ago this is the answer I got. "You should save the block you came from for every block visited, that way you can reconstruct the path".

But I don't understand if you save every block you came from that will just lead you to the same path that is the closed list? Also what I tried was when the path is done and you have the closed list follow the end to the start choosing the nodes in the closed list that have the lowest G Cost.

But that doesn't work because there are spots where the best Path is not the lowest G Cost. So like in this GIF I have my algorithm get the path and I have the closed list. How do I get the Fastest path from that like in this video?

enter image description here

Gilbert Le Blanc
  • 50,182
  • 6
  • 67
  • 111
  • 2
    What you are looking for is the concept of [backtracking](https://en.wikipedia.org/wiki/Backtracking). The exact implementation of backtracking depends on the concrete implementation of A* used. If you, for example, store for each node the distance to the target, you can reverse the path from the target to the start by looking at the neighbors of the target and choose one whichs distance is 1 to the target. Then select this node, look at its neighbors, choose one which distance is 2 and so on and so forth... until you arrive at the start. – Turing85 Aug 01 '20 at 10:30
  • @Turing85 Yeah but if you do it like that so it would choose the neighbor that is closest to the target then this would happen --> https://imgur.com/a/247EnRY This is what it should be like --> https://imgur.com/a/1QTh7NZ –  Aug 01 '20 at 11:41
  • 1
    Read carefully. I said that if you store the minimum distance to the target in each node and select them accordingly when backtracing, that you reconstruct the shortest path. This is not what would happen. – Turing85 Aug 01 '20 at 11:42
  • @Turing85 "for example, store for each node the distance to the target".What is the "Target" You are referring here. Is it the current node or the Start node if you are backtracing backwards i dont really understand –  Aug 01 '20 at 12:15
  • 1
    Please take a look at the question linked by @Spektre. – Turing85 Aug 01 '20 at 12:21
  • I have i still dont get it. All the videos i watch just are like "Save the node where the current node came from" Then backtrace it through those nodes but it makes no sense ur making another copy of the closed list. I understand everything about this algorithm except the backtracing part ive tried for weeks to understand it but i just cant –  Aug 01 '20 at 14:07
  • For more help post [mre] including test data. – c0der Aug 01 '20 at 15:09

0 Answers0