Search code examples
algorithmmathpath-findinga-star

will a star always return the least cost path?

I have been implementing a star recently on one of my pathfinding visualisers. A common thing that i have noticed is that while it does return the shortest path, it sometimes fails to return the least cost path. Now i am unsure as to if, this is due to some implementation error or if this is not a characteristic of the algorithm on a whole. For reference, these are the outputs of the a star and dijkstras algo respectively: enter image description here

dijkstar

So, why is this the case? (PS:the weights are 10, normal cost is 1 for any direction of movement and, the grey patches are walls)

Solution

  • A* may not return the least cost path, that is correct. This is a feature of A* though, not a disadvantage. To answer your question,

    Why is it the case?

    A* has a heuristics function that allows the algorithm to sacrifice accuracy for much higher performance by significantly reducing the area of search. This can be seen in your image too, where the Dijkstra's area of search is much wider. A* is often more useful in real-time games, where you don't necessarily need the lowest-cost path, as long as it is "good enough". Refer to this article for more examples. I find it explains A* very clearly in simple language.

    As to what is "good enough", you define this using the heuristics function. Using different function will result in different behavior, allowing you to tune the algorithm to be optimal for your needs (depending on your playing field and accuracy requirement). You can also remove the heuristics, in which case it becomes simply the Dijkstra's algorithm. Refer to this article from the same site for some examples of heuristics.