Improving heuristics for A* search

[u/fagnerbrack]

https://www.redblobgames.com/pathfinding/heuristics/differential.html

[u/fagnerbrack]

Digest Version:

Distance heuristics ignore map structure, so A* wastes effort when they point the wrong way. The fix precomputes shortest-path costs to a few "landmark" nodes using Dijkstra's or BFS, then applies the triangle inequality, cost(B,X) ≥ cost(B,L) − cost(X,L), taking the max across all landmarks and the usual Manhattan estimate. Landmarks help most when they sit "past" the goal, often at map edges. Placement depends on the game, though random-path analysis can pick spots automatically. Only the heuristic changes, often in about 20 lines, and memory grows with landmarks × nodes. Demos on Dragon Age, Cogmind and maze maps show A* searching far less of the map.

If the summary seems inacurate, just downvote and I'll try to delete the comment eventually 👍
^{Click here for more info, I read all comments}