В 2005 году Google показал Google Maps, где карту можно перетаскивать, а не перезагружать страницу, как в MapQuest. Но внимание автора привлекла функция 2007 года: перетаскивание начальной и конечной точек маршрута с мгновенным пересчётом кратчайшего пути. Значит, у Google работал быстрый A* на карте всего мира с миллионами дорог.
Автор уже разбирался в A и обычных оптимизациях, но Google Maps использовал что-то новое. Он стал читать статьи. Почти все они не оправдывали сложности, если карта не очень большая. Исключением оказалась относительно простая техника — differential heuristics. В 2014 году он написал интерактивное руководство по A и включил эту оптимизацию в список тем. Потом он пытался сделать по ней туториал в 2015, 2016, 2018, 2019, 2022 и 2024 годах — но ничего не выходило. В конце концов автор понял: надо перестать писать туториал. Он знает алгоритм, но не настолько хорошо, чтобы учить других.
Тогда он переключился на изучение и эксперименты. Много узнал, пережил взлёты и падения, выяснил, что впереди ещё много неизведанного. По ходу дела нашёл объяснение, которое ему понравилось, и переписал страницу. Раньше эвристика изображалась кучей чисел, теперь он использует две стрелки: одна показывает направление, которое подсказывает эвристика, вторая — правильное направление. Когда они совпадают, A* работает быстрее. Он добавил визуализацию областей, где оптимизация эффективна, и интерактивную диаграмму, где можно двигать точки и наблюдать, как меняются эти области.
Новая страница про differential heuristics опубликована. Автор начал её более десяти лет назад, поэтому там остались следы старого текста и кода. Он считает, что есть куда улучшать, но это первая версия, которую он готов считать выпущенной.