Ranked #5 on Hacker News with 73 points and 5 comments.
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.