Навигационная сетка (Navmesh)
Упрощённая полигональная карта тех мест игрового мира, где персонаж действительно может пройти.
Альтернатива — регулярная сетка, но она быстро становится дорогой: большой уровень с разрешением в метр даёт миллионы узлов для поиска. Навигационная сетка покрывает ту же территорию несколькими сотнями выпуклых полигонов — выпуклых затем, чтобы между любыми двумя точками внутри одного полигона можно было идти по прямой без дополнительных проверок. A* ищет путь по полигонам, а не по клеткам, а результат потом сглаживается в проходимую линию.
Сетки почти всегда строятся автоматически по геометрии уровня: воксельная разметка отмечает, где уклон проходим, а высота достаточна. Recast & Detour Микко Мононена (2009) — открытая эталонная реализация, лежащая в основе и Unity, и Unreal. Связи между полигонами могут иметь стоимость или тип — так моделируются прыжки, лестницы и двери, доступные не всем персонажам.