Improving A* Heuristics with Landmarks
Improving Heuristics for A* Pathfinding
A* pathfinding can be sped up by improving the heuristic function, not just the priority queue or map representation. The key idea is to precompute distances to a set of landmarks and use the triangle inequality to derive a lower bound for any goal. This 'differential heuristic' works best when landmarks are placed strategically, often on the map's outer edges. Multiple landmarks, placed manually or automatically, can significantly reduce the search space. Implementation is simple: run Dijkstra's algorithm from each landmark and modify the heuristic to take the maximum of the base heuristic and the landmark-based bounds.
It’s impractical to precalculate all costs to all locations, but if we’ve precalculated the costs to a specific location, we can use that to estimate the cost to a different location.
- simonw
> I learned about this technique in 2007, then tried writing it up in 2015. I realized that I didn’t understand it enough to be able to explain it. I studied it off and on in 2016, 2018, 2019, 2022, 2024, and 2026. I abandoned and restarted this page many times. And by 2026 I think I understand it well enough to write this page.
Outstanding.
- lokar
It uses df as an example, but it (unlike the others) has the problem that the set of valid paths between any two points can be constantly changing.
- LPisGood
Usually I would not point out a typo, but this one makes it difficult to grasp the magnitude of potential improvements:
> the number of nodes A* has to explore decreases from 12693 to 12693