Pathfinding: A* и NavMesh

Цели урока

• Реализовать A* на сетке с манхэттенской эвристикой
• Понять разницу Dijkstra vs A* и когда каждый подходит
• Использовать NavMeshAgent в Unity для движения NPC
• Построить Flow Field для одновременного pathfinding тысяч юнитов

NPC в игре должен дойти из точки A в точку B, обходя стены, врагов и пропасти. Как сделать это быстро для сотен персонажей одновременно, не разрушив частоту кадров? Pathfinding - одна из ключевых задач game AI.

• **RPG/Shooter NPC:** A* на NavMesh - стандарт в Unity и Unreal Engine
• **RTS (StarCraft, Age of Empires):** Flow Fields - тысячи юнитов без просадок FPS
• **Pac-Man призраки:** простейший BFS - 1980 год, принципы те же
• **Cities: Skylines:** иерархический pathfinding - дороги разного уровня

A* алгоритм

Персонаж стоит на клетке A и должен добраться до клетки B, обходя стены. Наивный обход всех клеток (BFS) работает - но тратит время на клетки, которые явно ведут не туда. **A*** умнее: он оценивает каждую клетку суммой «сколько уже прошли» плюс «сколько примерно осталось» и всегда идёт туда, где эта сумма минимальна.

Формула оценки: `f(n) = g(n) + h(n)`, где `g(n)` - реальная стоимость пути от старта до n, `h(n)` - **эвристика**: оценка расстояния от n до цели. Пока h(n) не переоценивает реальное расстояние (admissible heuristic), A* гарантирует кратчайший путь.

**Эвристики для разных сеток:** манхэттенское расстояние для сетки без диагоналей, евклидово расстояние для сетки с диагоналями, нулевая эвристика (h=0) превращает A* в Dijkstra.

Dijkstra vs A*

Dijkstra всегда находит кратчайший путь - но исследует граф равномерно во все стороны, как расширяющаяся волна. A* добавляет направление: эвристика «подталкивает» поиск к цели. На открытой местности A* исследует в разы меньше вершин. Когда же Dijkstra лучше?

Dijkstra выигрывает, когда нужно найти пути **от одного источника ко всем остальным вершинам** (single-source shortest paths). Например, в RTS: вычислить стоимость пути от базы до каждой клетки карты один раз. A* оптимален для поиска **одного конкретного пути** от A до B.

**Bidirectional A*:** запускать поиск одновременно от старта и от цели навстречу друг другу. Встреча в середине сокращает исследуемое пространство примерно вдвое - важно для больших открытых карт.

NavMesh в Unity/Unreal

3D игровой мир - не сетка клеток. Персонаж идёт по неровному ландшафту, огибает здания, поднимается по лестнице. **NavMesh (Navigation Mesh)** - это полигональная сетка, покрывающая только проходимую поверхность. A* работает на этой сетке, а не на воксельной сетке всего уровня.

Unity запекает NavMesh в Editor: статическая геометрия помечается как Navigation Static, NavMesh Surface компонент задаёт агентский радиус, высоту и step height. Результат - полигональный меш доступных зон, хранящийся как asset.

**Funnel algorithm (SSFA):** после нахождения пути через NavMesh полигоны он содержит «углы» - точки пересечения границ полигонов. Funnel algorithm сглаживает путь, убирая лишние повороты и строя прямые отрезки там, где персонаж может пройти напрямую.

Flow Fields для RTS

В RTS тысячи юнитов одновременно движутся к одной цели. Запускать A* для каждого юнита каждый кадр - нереально. **Flow Field** решает это: один раз считаем Dijkstra от цели, для каждой клетки записываем направление движения к цели. Юниты просто смотрят на направление в своей клетке - O(1).

**Пересчёт Flow Field:** не нужно пересчитывать каждый кадр. Пересчёт нужен только когда меняется цель или меняется карта (разрушение здания). Для RTS с одной базой игрока - пересчёт очень редкий.

Pathfinding в играх

• A*: f(n)=g(n)+h(n), при допустимой эвристике гарантирует кратчайший путь
• Dijkstra = A* с h=0; оптимален для single-source all-targets задач
• NavMesh: полигональная сетка проходимых зон, работает с любой 3D геометрией
• Funnel algorithm сглаживает путь через NavMesh полигоны
• Flow Fields: один Dijkstra от цели, N юнитов используют O(1) lookup

Связанные темы

Pathfinding - часть более широкого инструментария Game AI.

• Steering Behaviors — Flow field задаёт направление, steering задаёт скорость и уклонение
• Behavior Trees — BT решает когда и куда идти, A* решает как дойти
• Procedural Generation — Генерируемые уровни требуют динамического NavMesh

Вопросы для размышления

• Почему переоценивающая эвристика (inadmissible) делает A* быстрее, но может дать неоптимальный путь?
• Как NavMesh агентный радиус влияет на доступные пути и что происходит при узких проходах?
• В каких случаях Flow Field нужно пересчитывать и как минимизировать частоту пересчётов?

Связанные уроки

• alg-13-dfs