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.
- mpmisko
There has been a lot of progress in this field in the research community. Two good papers:
- Groxx
Red Blob Games has quite a few S-tier posts, highly recommend exploring further if this is at all interesting to you
- tkocmathla
Incredible write-up, as usual. I still fondly remember discovering Red Blob Games' Hexagonal Grids [1] guide while building an implementation of the Tzaar board game [2]. The illustrations are enormously helpful!
- layer8
Finally an interesting article about AI!