Red Blob Games: How Google Maps' 2007 drag-and-drop routes led to a decade-long quest to explain differential heuristics
In 2007, Google Maps added a feature that let users drag route endpoints and instantly see recalculated paths. This hinted at a fast A* pathfinding optimization that author Amit Patel had never encountered. After studying the technique—differential heuristics—he spent over a decade trying to write a tutorial, failing repeatedly because he didn't understand it deeply enough. Switching to experimentation, he finally found a clearer explanation and released an interactive guide with new visualizations, including arrows showing heuristic mismatches and regions of improvement.
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.
- plomme
Very good write up, as always, from Red Blob. It turned my high-level assumption on Google Maps pathfinding upside down. I thought, recalling algorithms class, that Google Maps worked so fast due to "optimal substructure" of shortest-path finding. That is that the shortest path from A-C through B also produces the shortest paths from A-B and B-C, and that for most of any given path you could route through some number of precalculated "midpoint" paths. Reading this turns it upside down in the sense that landmarks go behind the target, and not in the middle of the route! Very handy tool.
- simonw
Discussed here five days ago: https://news.ycombinator.com/item?id=49079995
(Honestly though this is such a cool piece of work it deserves a second conversation, that one only hit 40 comments.)
- inigyou
Good article and demonstrations. I was a bit confused about the colors - at least once the text talks about blue tiles being the ones that don't need to be checked because of the landmark, but they are actually green, and the blue ones are the ones that weren't checked anyway. I am not colorblind.
Many of your maps consist of rooms connected at a few points. Have you considered running pathfinding first through the graph of rooms and then through each room individually? You could even precompute all paths through a room from one portal to another, but you probably don't need to, but you would need to precompute how costly they are. This is probably about the same pathfinding cost as putting a landmark in each room.