CODEWITHSUNDEEP
path-findinga-star
Nathaniel G.M.
Nathaniel G.M.

Reputation: 433

A* (a-star) issues finding shortest path - specific example

A* Issue

In this example (please see picture), the Manhattan heuristic delays the path because of the unwalkable block west of the destination block.

My question is how can I fix this? Do I need to keep checking the blocks on the open list (the gray blocks) even after I found the destination? I might as well use dijkstra if I have to do that. Do I have to live with an imperfection like this if I go with a-star or is there a solution?

I have done my research on it and implemented my own algorithm that works exactly as the tutorials / articles on the web have explained, but I keep running into specific instances like this where a* fails to find the shortest path.

Upvotes: 2

Views: 412

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86006

Your heuristic needs to be admissible but is not. Use Diagonal or Euclidean distance instead.

Upvotes: 1

Related Questions