Поиск пути в игре: NavMesh, A* и flow field на 200 агентов

Двести агентов, застрявших у одних ворот

В конце прошлого года я работал над сценой осады: одни ворота замка и 200 экземпляров NavMeshAgent, бегущих к ним. Навигация в игровом ИИ разваливается именно на таких сценах. Запись, которую QA прикладывал к ночной сборке, всегда замирала в одном и том же месте: за пятнадцать метров до ворот около шестидесяти агентов тёрлись друг о друга и мелко дрожали, часть из них пятилась назад. За первые десять секунд во двор за воротами попадали от силы сорок.

Время кадра держалось на 11 мс, пока агенты были далеко, и вырастало до 26 мс, когда они подходили к воротам. Первой догадкой было, что взорвался A*. Профайлер её не подтвердил: NavMesh.CalculatePath в сумме давал 3,2 мс, а собственное внутреннее обновление NavMeshAgent занимало 9,8 мс. То есть узкое место было не в поиске, а в той работе, которую каждый агент делает каждый кадр.

На самом деле одновременно проявлялись две разные проблемы, и их принимали за одну: стоимость расчёта глобального пути и поведение агентов относительно друг друга. Любое обсуждение, которое сваливает их под один заголовок, заходит в тупик, потому что лечатся они в совершенно разных местах. Пока вы их не разделите, вы никогда не поймёте, какая настройка сдвинула какое число. У нас разделение началось с одной привычки: следить в профайлере за строкой поиска и строкой обновления агентов по отдельности.

Куда на самом деле смотрит NavMesh

NavMesh — это треугольная сетка, запечённая из проходимой поверхности сцены и стянутая от каждого края на радиус агента. Область, по которой ходит агент, — это не тот пол, который вы видите во вьюпорте. Когда приходит репорт о застрявшем агенте, первое дело — включить отображение сетки в окне Navigation и измерить, сколько сантиметров прохода реально остаётся в дверном проёме. При стандартном Voxel Size в 0,166 м я не раз видел, как в тесных углах пропадают отдельные полигоны.

Проём наших ворот был 1,6 м, а Agent Radius — 0,5 м, и оставалась единственная полоса шириной 0,6 м: один агент проходит, двое нет. Уменьшить радиус до 0,35 выглядело простым решением, но по всей карте агенты начали залезать в стены. Правильной правкой оказалось расширить ворота до 2,4 м на стороне уровня. Радиус агента — не косметическая настройка, а базовая единица всей навигации.

Вторая классическая ловушка — цель, оказавшаяся вне сетки. SetDestination в этом случае возвращает false, а возвращаемое значение никто не проверяет; или путь приходит со статусом NavMeshPathStatus.PathPartial, и агент доходит до ближайшей достижимой точки и стоит там. Снаружи это выглядит ровно как «застрял». Притягивание каждой цели к сетке через NavMesh.SamplePosition в радиусе 2 м закрыло большую часть таких репортов. Ту же проверку примените к точкам спавна: агент, родившийся вне сетки, потерян с первого кадра.

Разрывы вроде лестниц, ям и дверных проёмов требуют off-mesh links. Расставленные вручную компоненты OffMeshLink ведут себя куда предсказуемее автоматически сгенерированных. При стандартной стоимости 1.0 сто сорок из наших двухсот агентов пытались протиснуться через единственный разрыв в 1,2 м; значение costOverride, выставленное в 5.0, увело большинство на более длинный, но свободный маршрут. Держите оба конца линка на сетке: линк, у которого один конец висит в воздухе, молча игнорируется.

Стоимость A* и иерархический поиск пути

Стоимость A* pathfinding растёт вместе с числом раскрытых узлов. На NavMesh из 41.000 полигонов один запрос с одного края карты на другой занимал 0,35 мс. Двести агентов, спросивших в одном кадре, дали бы 70 мс, но такого рывка вы не увидите: Unity ставит запросы в очередь, путь приходит с опозданием на три-четыре кадра, а агенты всё это время бегут по старому курсу. Симптом — не подвисание, а запоздалый поворот.

Иерархический поиск пути срезает эту стоимость дважды. Карта делится на регионы, переходы между ними записываются в граф порталов; поиск сначала идёт по грубому графу из 30-40 узлов (0,02 мс), а подробный A* работает только до следующего портала. Средний запрос у нас упал с 0,35 мс до 0,06 мс, и полный путь агента больше никогда не считался целиком за один раз. Грубый граф строится один раз на этапе bake и обновляется в рантайме только тогда, когда динамическое препятствие закрывает портал.

Альтернатива, которую мы попробовали и выбросили, — общий кэш путей. Мы округляли цели до ячеек по 4 м и выдавали один путь всем агентам, идущим в ту же ячейку. На статичных целях попадание было 70%, но при погоне за игроком падало до 18%, а логика инвалидации съедала больше, чем кэш экономил. Код мы удалили. Разделение путей окупается только там, где цель стоит на месте десятки кадров.

Одно flow field на всю толпу

Если у 200 агентов одна цель, запускать 200 отдельных поисков бессмысленно. Flow field прогоняет одно распространение стоимости в обратную сторону от цели, а затем записывает в каждую ячейку вектор направления на самого дешёвого соседа. У нас была сетка 128x128 с ячейкой 0,5 м, полная перестройка занимала 4,1 мс. Распространение заполняет все ячейки за один проход, так что стоимость совершенно не зависит от числа агентов.

Важно, что эти 4,1 мс платятся при смене целевой ячейки, а не каждый кадр. Пока игрок бежал, это случалось три-четыре раза в секунду, то есть примерно 14 мс в секунду. Стоимость на агента схлопывается до двух билинейных выборок: 0,004 мс, или 0,8 мс на все 200 агентов. Та же толпа через иерархический A* обходилась в 12 мс.

Граница очевидна: каждая отдельная цель — это ещё одно поле. После трёх-четырёх целей память и стоимость перестроения обгоняют A*. Поэтому мы остались на гибриде: именованные NPC и боссы на A*, симуляция толпы на flow field. Оба варианта стоят на одних и тех же треугольниках NavMesh, отличается только источник направления. Разделение живёт в единственном bool в коде, и дизайнер переключает его прямо на префабе.

Local avoidance — это не глобальная навигация

RVO и производный от него ORCA делают одно: каждый агент считывает позиции и скорости соседей, отсекает полуплоскостями скорости, ведущие к столкновению, и выбирает из оставшегося то, что ближе всего к желаемой скорости. Его горизонт — секунда-другая, и о геометрии уровня он не знает ничего. Это коррекция направления, а не навигация. Оставьте агента с ней наедине, и RVO никогда не доведёт его до цели.

Поэтому ждать глобального решения от local avoidance неверно с самого начала. У П-образной стены двора RVO прижимает агента к стене, а двое встречных агентов встают в клинч. Перевод obstacleAvoidanceType в HighQuality это не чинит, а лишь съедает 6,2 из 9,8 мс на 200 агентов. Понижение до Good дало 3,9 мс без заметной с расстояния камеры разницы.

Настоящий выигрыш оказался в поле avoidancePriority. Пока у всех агентов стоит значение по умолчанию 50, картина остаётся симметричной и никто никому не уступает. Раздача случайного приоритета от 0 до 99 при спавне сократила затор у ворот с 4,2 секунды до 1,1 секунды. Правка в одну строку.

Динамические препятствия и бюджет запросов пути

Для динамических препятствий используется NavMeshObstacle с carving, но carving перепекает тайл на каждое движение. При 12 катящихся по сцене бочках мы видели регулярные всплески по 5,8 мс. Поднятие carvingMoveThreshold до 0,5 м и включение carveOnlyStationary опустило ту же сцену до 0,9 мс. Никогда не делайте препятствием то, что движется непрерывно: это работа local avoidance.

С бюджетом всё просто: зафиксируйте число полных запросов пути на кадр. У нас это 12. Агенты запрашивают с интервалом 0,45 секунды плюс случайное смещение от 0 до 0,15 секунды, потому что без этого джиттера волна спавна складывает все запросы в один кадр. Когда бюджет исчерпан, запрос не отменяется, а сдвигается на следующий кадр, и этого никто не замечает, потому что агент тем временем продолжает идти по текущему пути. Измеряйте бюджет на целевом железе: наши консольные 12 на десктопе спокойно превращаются в 30.

В этой сцене общее время кадра упало с 26 мс до 13,4 мс, а доля поиска пути — с 13 мс до 2,1 мс, и самым дешёвым выигрышем внутри всего этого была однострочная правка приоритета. Порядок работы стройте так: сначала глазами проверьте геометрию NavMesh, затем поставьте бюджет запросов на кадр, затем переведите толпу на flow field, а к настройкам local avoidance прикасайтесь в последнюю очередь. Пойдёте в обратном порядке — часы уйдут в параметры ORCA, а проём в 0,6 метра останется ровно там же, где был. Не меняйте настройку, которую не измерили: все числа здесь пришли из профайлера, ни одно — из догадки.