Ориентиры делают A* быстрее: меньше узлов, но пересчёт при смене карты

Обычная эвристика A вроде Manhattan distance не видит стен, поэтому часто толкает алгоритм не в ту сторону и заставляет исследовать лишние узлы. Решение — улучшить эвристику с помощью ориентиров (landmarks): нескольких заранее выбранных вершин карты. Идея опирается на неравенство треугольника. Если заранее посчитать расстояние от каждого узла до ориентира L, то для любого пути из старта B в цель X получается нижняя оценка cost(B,X) ≥ cost(B,L) - cost(X,L). Чем точнее эта оценка, тем меньше узлов A перебирает. Один ориентир полезен только для целей, лежащих между стартом и ориентиром или за ним, поэтому нужно несколько ориентиров. Для каждого из них запускают поиск кратчайших путей — Dijkstra, а для единичных весов достаточно BFS — и сохраняют стоимости в массив. Затем в эвристике берут максимум из обычного расстояния и всех разностей cost(B,L_i) - cost(X,L_i). Кода добавляется немного, сам A* менять не нужно. Расстановка ориентиров зависит от карты: для статичных карт их можно подобрать в редакторе, для процедурных — проанализировать случайные пути. Автор проверил метод на картах из Dragon Age, Cogmind и лабиринтах — интерактивные демо показывают, сколько узлов удаётся не исследовать (синие зоны). Например, в лабиринте четыре ориентира дают заметный выигрыш. У метода есть нюанс: если карта меняется (сломали стену), эвристика может стать неоптимальной или просто медленнее, пока не пересчитают таблицу расстояний. В конце автор перечисляет связанные работы: Goldberg и Harrelson (2004), Hotz (1994), Thorup и Zwick (2005), Ng и Zhang (2002), Rayner и другие (2011), Goldenberg и другие (2011). Сам он изучал эту технику с 2015 года и наконец смог объяснить.