Иерархический поиск пути
Разбиение карты на крупные регионы: сначала ищется грубый маршрут между ними, затем он уточняется внутри каждого региона.
Большую карту удешевляет абстракция. Карту делят на кластеры, а в абстрактный граф выносят только входы в кластеры и связи между ними. A* сначала решает маленький граф — через какие регионы идёт путь, — а потом каждый участок уточняется локально. Самый цитируемый вариант — HPA* Ботеа, Мюллера и Шеффера (2004).
Выигрыш велик на разросшихся уровнях: абстрактный поиск затрагивает лишь малую долю узлов. Цена — путь больше не гарантированно кратчайший, он почти оптимален, чего в игре почти всегда достаточно. Метод хорошо сочетается с jump point search внутри кластеров и с навмешем для более точной геометрии.