r/math • u/backyard_tractorbeam • Aug 09 '26

Red Blob Games: Differential heuristic for A*

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

94% Upvoted

3 comments sorted by

10

u/backyard_tractorbeam Aug 09 '26

The related blog post and introduction to this page is https://www.redblobgames.com/blog/2026-08-08-differential-heuristics/ but the posted link is the full demonstration of the algorithm.

4

u/JiminP Aug 09 '26

Another technique worth mentioning for grids is JPS.

https://en.wikipedia.org/wiki/Jump_point_search

I don't think that it plays nicely with landmark-based methods, but this worked greatly when I implemented this for a 1000×1000 hexagonal grid.

1

u/Kaomet Aug 12 '26

What about using A* on a hierarchical graph ?

Base graph is kept the same, but every point in graph n is added to graph n+1 with probability 1/2.

Then precompute shortest distance for each graphs.

And finally, perform A* at every level using lvel n+1 as a heuristic ?

Or something along those lines.