In 2005 Google showed off Google Maps, which lets you drag the map around instead of reloading the page like MapQuest and others used. That’s the feature that got everyone’s attention. But what got my attention was a feature they added in 2007 where you could drag the start/end points on a route[1], and it would recalculate the shortest path as you dragged. That means they had fast A* pathfinding[2] on the entire world, which had millions of roads. How did they do it?
I had already studied A* and the common optimizations, but Google Maps was using optimizations I hadn’t learned about. I started reading papers. My reaction to almost all of them was “this complexity isn’t worth it unless your map is very large”. There was one technique however that was relatively simple, and I wanted to explore it further.
In 2014 I wrote my interactive guide to A* pathfinding. I made a list of additional topics I wanted to cover, including graphs, heuristics, optimizations, data structures, and so on. One of these topics was the optimization I had learned about in 2007: differential heuristics (although it didn’t get that name until later).
I tried writing a tutorial about it in 2015 but I couldn’t find an explanation I liked. I tried again in 2016, 2018, 2019, 2022, 2024. I finally realized that I needed to stop trying to write a tutorial. Although I understood the algorithm, I didn’t understand it well enough to teach it.
I needed to understand it better. So I switched to learning and experimentation mode. I learned a lot. I went through some ups and downs. I learned that there’s still more to learn. Along the way I found an explanation I was happier with, and I rewrote the page again.
-
I had previously shown the heuristic as lots of numbers. I switched to using two arrows. One is the direction the heuristic suggests and one is the correct direction. When they are in alignment, the heuristic makes A* run faster.
Arrows showing heuristic mismatches -
I added visualizations showing the regions in which the optimization was effective, combined with an interactive diagram where I can move the points around to see how those regions change.
Visualizing the improved areas
Here’s my new page about Differential Heuristics. I started over ten years ago so there are remnants of old text and code still there. I think there’s still plenty of room for improvement, but this is the first version I’m considering “released”.