A* Demystified - Gabriel Gambetta
The first article in this series presented the generic pathfinding algorithm; every pathfinding algorithm is a slight variation of it. The second article revealed the secret behind the different search algorithms: it all comes down to the choose_node function. It also presented a reasonably simple choose_node that yields an algorithm called Uniform Cost Search. This algorithm is pretty good: it will find the shortest path from the start node to the goal node. However, it’s somewhat wasteful: it considers paths that a human clearly sees as “wrong” - they tend to move away from the goal. Can we avoid this? Imagine we’re running a search algorithm in a special computer which has a chip that can do magic (bear with me). With this awesome chip, we can express choose_node in a very simple way which is guaranteed to produce the shortest path without losing any time exploring partial paths that won’t lead anywhere: Tempting, but magic chips still require somewhat lower level code. This would b