В предыдущих статьях я уже немного затронул тему правильного обмана игрока, через койоттайм и подкручивание стрельбы. Смотря на эти случаи, вы наверное заметили, что хороший игровой код довольно часто занимается построением модели мира которая будет достаточно хорошо совпадать с тем, что человек ожидает от игры.
С навигацией в играх приходится хачить не меньше, и приходится разбираться уже не со временем прыжка и физическим состоянием персонажа в понимании игрока, а с набором полигонов, узлов, рёбер и стоимостей и вообще всем тем, что определяет путь NPC на карте. И опять же надо смотреть на ожидания игрока от NPC, а не корректность поведения.
В стратегиях у ботов обычно есть обычно очень простая задача пройти через какие‑нибудь ворота‑узкое место, обойти стену и оказаться во дворе, и пока у нас один солдат, который идёт по пустой карте, никакой особой проблемы не возникает. А стоит вам добавить на карту десять, пятьдесят, сто, двести солдат и одни ворота, через которые физически способны одновременно протиснуться всего несколько юнитов, как выясняется они этого не делают, хотя алгоритме поиска пути (вроде A*) прекрасно отработал. Отработал, то отработал, а солдатики на месте тупят, и выясняется что мы пытаемся заставить его решать задачу, на которую он не рассчитан.
Наши двести NavMeshAgent одновременно получили одну и ту же команду бежать к одним несчастным воротам, они быстро находят маршруты, двигаются по карте, но по мере приближения к воротам пространство начинает становиться теснее и часть из них собираются в пятнадцати метрах от прохода, начинают немного дрожать, а некоторые пятятся назад, пока другие пытаются протиснуться между соседями. Во двор за за это время проходит от силы десяток.
Если мы в этот момент открываем профайлер и смотрим за застрявших солдат, то видим что A* занимает очень много времени, а занимает много времени, потому что каждому NPC нужен путь, значит у нас двести поисков пути, поиск пути тормозит и очевидно, что нужно оптимизировать поиск пути, чтобы он работал быстрее. Неочевидно...
Неочевидно, потому что мы пытаемся решить вопрос глобальной навигации «как мне попасть из точки A в точку B», тогда как поведение толпы определяет другой вопрос «как мне двигаться по этому маршруту, когда рядом со мной ещё несколько десятков таких же персонажей».
Визуально же обе проблемы выглядят одинаково и солдату надо просто доходить до цели, но если перепутать решения, можно потом несколько часов настраивать A*, менять радиусы, перестраивать NavMesh, увеличивать отталкивания и всё равно наблюдать у ворот эту толпу, которая явно знает, куда ей нужно идти, но дойти туда не может.
(Попробовать самому) Можно двигать ширину ворот и количество агентов, и смотреть как работает затор в реальном времени.
Как работает NavMesh
Почему персонаж «застрял» в дверях, когда в редакторе и в игре проход выглядит достаточно широким? NavMesh это не пол, который игрок видит во вьюпорте, а отдельная геометрия, построенная поверх проходимой поверхности с учётом параметров конкретного навмеш‑агента. Поэтому визуально широкий коридор может оказаться довольно узким местом с точки зрения центра NPC, потому что от стен нужно убрать его радиус, чтобы он за эти самые стены не цеплялся (серая область вогруг геометриия, красная это навмеш)
В нашей сцене ширина ворот составляла 1,6 метра, а Agent Radius пол‑метра, и ворота, с точки здения зрения дизайнера и игрока выглядят широкими, чтобы туда проходили аж три NPC, но если посмотреть на это все через алгоритм NavMesh'а, то с каждой стороны нужно оставить по полметра, и для центра агента остаётся всего 0.6 метра, то есть в ворота шириной 1,6 метра, может пройти всего один NPC.
Один агент ещё проходит, два агента рядом уже начинают мешать друг другу, а если подогнать сюда двести персонажей, то мы получим случай, когда навигационная сетка говорит, что путь существует, но система локального движения не способна физически провести по этому пути хотя бы одного.
Можно попробовать уменьшить Agent Radius до 0,35 метра, что очень заманчиво и позволяет решить проблему локально, особенно если смотреть только на эту конкретную дверь, но вместе с ней меняется вся геометрия навигации, и NPC начинают подходить ближе к стенам, клипать в геоиметрию, проходить в места, куда по дизайну уровня они вообще не должны помещаться. Ваша маленькая локальная оптимизация неожиданно сломала половину уровня, и видя эти конкретные проблемы, дизайнер решает не трогать агента, и что делает? Правильно... он делает ворота шире (смотрите на ширину дверей, особенно в старых играх, они не просто так выше и шире были, все это следствия «проблемы ворот»)
Что тоже является хорошим примером почему параметры NavMesh'а нельзя воспринимать как косметические настройки, и почему радиус навмеш‑агенто это не просто «насколько толстым нарисовать кружок вокруг персонажа», а параметр, который определяет, где вообще появляется проходимая область.
Агент застрял
Есть и другая разновидность этой проблемы, когда мы уверены, что персонаж застрял где‑то на маршруте, хотя никакого маршрута у него вообще никогда не было, потому что цель находится за пределами навмеша. Агент стоит на месте, QA говорит, что персонаж застревает, программист открывает профайлер и не находит ничего подозрительного, начинает смотреть A*, потом NavMesh, потом локальное отталкивание, а потом выясняется, что A* вообще не запускался. Программиста здесь винить сложно, а дизайнер эту причину обычно замечает как баг навигации и пишет на это баг.
Другая разновидность проблемы, когда путь существует, но заканчивается на ближайшей достижимой точке, и снаружи такая ситуация опять выглядит как «NPC застрял». В общем случае это заставляет сначала вернуть цель на навмеш, а потом уже с ней работать. Это же объясняет почему NPC не могут заходить в произвольные места, куда может забираться игрок.
(Попробовать самому) Кликать надо в стену, тогда цель либо притянется к ближайшей проходимой точке, либо (если рядом вообще нет прохода) останется на месте
Ещё один способ заставить A* не искать
Разрывы между участками NavMesh тоже являются проблемами, поэтому лестницы, ямы, дверные проёмы и другие места, где навигация не является одной непрерывной поверхностью, требуют OffMeshLink. Что тоже доставляет проблема, потому что сам факт существования нескольких маршрутов ещё не означает, что система выберет тот, который человек считает разумным.
Допустим у нас был разрыв шириной 1,2 метра, через который можно было пройти, и при стандартной стоимости link, равной 1.0, около 140 из 200 агентов пытались туда попасть, хотя на карте существовал более длинный, но менее загруженный маршрут.
Для компьютера если один путь дешевле другого, значит нужно идти по дешёвому пути, а то, что там уже образовалась очередь, в стоимости маршрута часто никак не отражено. Увеличение стоимости линки заставило большинство агентов выбирать другой маршрут, что показывает как работает механизм заполнения переходов, но обычный A* не может догадаться об этом, потому что он оптимизирует только ту стоимость пути, которую ему дали.
(Попробовать самому) Меняйте стоимость перехода через линку, чтобы увидитеть как агенты сами перераспределяются с узкого места на широкий обход.
Когда A* начинает становиться дорогим
Теперь можно наконец поговорить про сам A*, хотя после предыдущих проблем уже становится понятно, что сам алгоритм просто не способен решать часть задач. Алгоритм A* раскрывает узлы и сравнивает стоимости чтобы найти маршрут, а если навмеш содержит 41К полигонов и надо построить путь с одного края карты на другой, то один такой запрос в тестовой сцене в среднем будет затрагивать более трети все полигонов.
Допустим один такой запрос требует 0.35 миллисекунды, то попытка выполнить двести таких запросов одновременно, физические дает 70 миллисекунд. Мы давно научились обходить такие кейсы, и уже лет двадцать реальные системы ставит запросы к навмешу в очередь, а пока путь не готов (что может произойти и через несколько кадров), агент продолжает двигаться по старому маршруту. Проблема не всегда выглядит как фриз, иногда это просто безобидное запаздывание, когда персонаж пару кадров в стену или запаздывает.
Иерархический A*
Если карта состоит из нескольких больших областей, между которыми существует относительно небольшое количество переходов, совершенно необязательно каждый раз заставлять A* исследовать все 41K полигонов, потому что мы заранее знаем довольно много о структуре уровня и можем сначала определить, через какие крупные области вообще нужно пройти.
Для этого карту можно разделить на регионы и построить между ними граф порталов, а затем сначала искать маршрут по этому грубому графу, который может содержать всего несколько десятков узлов, и только после этого запускать подробный поиск внутри тех регионов, через которые действительно проходит маршрут.
Сначала мы получаем что‑то вроде A → B → C, то есть определяем маршрут по крупным регионам, а уже после этого ищем подробный путь Agent → Portal B → Portal C → Target, и тем самым не заставляем каждый запрос заново рассматривать всю карту, хотя для самого агента конечный результат выглядит совершенно так же, будто он построил обычный полный маршрут.
Причём такой грубый граф можно построить один раз во время сборки или загрузки уровня и обновлять только тогда, когда препятствие закрывает один из порталов, и это снова тот же старый принцип оптимизации, который постоянно всплывает в игровых системах. Если информацию можно вычислить заранее, а потом много раз использовать, то вычислять её заново каждый раз обычно довольно глупо.
(Попробовать самому) Переключайте A* и Hierarchical A*, чтобы увидеть open/closed тайлы и разницу во времени поиска.
А что если все идут в одну точку?
А вот тут A* начинает проигрывать любому алгоритму движения толпы, потому что если у нас двести агентов и у всех одна цель, то надо запускать двести независимых поисков пути, даже если большая часть информации о маршруте к этой цели у них будет одинаковой.
Разные стартовые позиции не дают возможности использовать A* как есть, и значительная часть маршрута после некоторой точки становится общей. Получается что мы двести раз решаем одну и ту же задачу только потому, что у нас двести персонажей, поэтому придумали flow field.
Вместо того чтобы для каждого агента отдельно искать путь от него к цели, мы один раз распространяем стоимость от цели назад к толпе, а потом для каждой ячейки сохраняем направление к соседней ячейке с меньшей стоимостью. После чего любой агент, попавший в эту ячейку, просто смотрит на направление и продолжает движение, получается что мы вытащили всю информации, которую нам сгененрировал A* в процессе и сохранили её на какой‑то момент времени, поэтому стоимость построения самого поля практически не зависит от количества агентов.
Для теста я использовал сетку 128×128 с размером ячейки 0.5 метра, полная перестройка поля занимает 4 миллисекунды, но это стоимость изменения самого поля, а не стоимость обработки каждого агента, и при обновлении три‑четыре раза в секунду средняя стоимость перестроения составляла всего 12 миллисекунд в секунду. Для сравнения, та же толпа через иерархический A* обходилась в 12 миллисекунд на каждый запрос.
Это компромисс и он хорош для толпы, а когда у каждого агента появляется собственная цель, и ему вместо одной цели надо следить за тремя или четырьмя, то количество необходимых полей начинает расти, вместе с ним растёт память и стоимость перестроения, и в какой‑то момент оказывается, что мы построили огромную красивую систему только для того, чтобы получить примерно ту же работу, которую обычный A* выполнял намного проще.
Поэтому совершенно нормально использовать гибридную систему, где именованные NPC, боссы и персонажи с индивидуальными задачами используют A*, потому что им действительно нужны отдельные маршруты, а большие группы обычных солдат используют flow field, потому что их главная задача заключается в том, чтобы всем вместе достаточно эффективно двигаться в одном направлении.
(Попробовать самому) Можно переключать бенчмарк A* на 200+ агентов с одним общим полем направлений.
Local avoidance
Но даже после того, как мы нашли правильный глобальный путь, проблема ворот никуда не исчезает, потому что теперь каждый агент знает, куда ему нужно идти, но шестьдесят агентов всё ещё могут одновременно захотеть занять одну и ту же точку пространства. Но опять A* не может решить эту проблему.
Здесь на сцене появляется RVO или производный от него ORCA, которые решают уже совсем другую задачу, когда агент смотрит на позиции и скорости соседей, определяет направления, которые приведут к столкновению, отбрасывает их, выбирая среди оставшихся скорость, максимально похожую на желаемую. Иначе говоря, агента в этот момент не интересует «как мне попасть в город?», а только «как не врезаться в человека передо мной прямо сейчас?».
Поэтому local avoidance нельзя использовать как замену глобальной навигации, и если дать ему только локальное поведение и сказать «ну всё, теперь сам доберись до цели», он вполне может несколько минут идеально избегать всех столкновений и при этом вообще никуда не прийти, особенно если перед ним окажется П‑образная стена. (Попробовать самому)
Когда у всех агентов одинаковый avoidancePriority, например стандартное значение 50, система становится слишком симметричной, и каждый агент считает себя таким же важным, как соседний, каждый пытается избежать столкновения, сосед делает ровно то же самое, и в результате все достаточно умные, чтобы не врезаться друг в друга, но недостаточно наглые, чтобы наконец пройти через ворота. Иногда для толпы полезнее дать агентам небольшой приоритет, и в тестовой сцене случайный avoidancePriority от 0 до 99 сократил время затора у ворот с 4,2 секунды до 1,1 секунды.
И это тоже хороший пример того, почему голый профайлер хуже визуализации поведения, или почему сложный алгоритм тоже может тупить, когда вся эта огромная толпа честно пытается работать по одинаковым правилам. И чтобы решить проблему вместо сложного изменения алгоритма понадобилась всего лишь небольшая асимметрия в поведении. (Попробовать самому) Можно сравнить Uniform и Random приоритеты на одинаковых воротах и толпе.
Динамические препятствия
Теперь добавим в сцену несколько бочек, которые катятся по уровню, и сделаем автоматическую перестройку навмеша вокруг них. Все будет работать, но проблема что перестроение части навигационной сетки дорого, а если препятствие двигается постоянно, то мы фактически просим движок регулярно переделывать NavMesh из‑за объекта, который через полсекунды оказывается в другом месте.
Здесь опять надо понимать, какую задачу решает каждая система и если объект стоит на месте, его имеет смысл учитывать в глобальной геометрии, а если объект постоянно движется, возможно, NavMesh тут вообще ни при чём и заставлять глобальную навигацию реагировать на каждое движение объекта будет как перестраивать карту дорог города каждый раз, когда один автомобиль перестроился в соседний ряд. Потому что для остальных участников движения структура города от этого не изменилась.
(Попробовать самому) Можно таскать препятствие в двух режимах «Every drag move» с «Only on release».
Количество запросов
После всех этих оптимизаций остаётся ещё одна вещь, которую многие забывают сделать. Даже если один запрос пути достаточно дешёвый, это совершенно не означает, что двумстам агентам нужно делать его одновременно, потому что в реальной игре нас интересует не только стоимость одной операции, но и как эти операции влияют на время кадра.
Причина простая, если все агенты появились одновременно и у всех стоит одинаковый интервал обновления, то с большой вероятностью они и обновляться будут тоже одновременно, и вместо равномерной нагрузки мы получим маленькую армию, которая синхронно решит, что прямо сейчас ей всем одновременно нужен новый маршрут, после чего профайлер покажет периодический пик, хотя каждый отдельный запрос сам по себе может быть очень дешёвым.
Если запросов становится больше бюджета, агент совершенно не обязан немедленно пересчитывать путь, потому что он уже находится на каком‑то маршруте и может продолжать движение по старому, пока новый запрос ждёт своей очереди, и игрок, скорее всего, вообще этого не заметит, поскольку для него гораздо важнее плавное движение, чем то, что новый маршрут был рассчитан одним кадром позже, а для движка это означает, что мы можем превратить резкий всплеск работы в более равномерную очередь без какого‑либо заметного изменения самого поведения.
(Попробовать самому) При jitter 0 и unlimited budget виден периодический пик на графике frame time, можно добавлять jitter или budget и смотреть, как спайки превращаются в очередь.
Проблема обычно не там, где мы ищем
В итоге «проблема ворот» оказывается вообще не про ворота и даже не про навигацию, а про довольно типичную ошибку недоценки области знаний, когда мы видим конкретное поведение персонажа и пытаемся найти причину в ближайшем алгоритме, который кажется связанным с этим поведением.
NPC не проходит через ворота, значит надо чинить A*, NPC застрял, значит надо перестраивать NavMesh, толпа дёргается, значит надо улучшать avoidance, а потом оказывается, что A* нашёл маршрут, NavMesh считает проход проходимым, avoidance избегает столкновений и каждый отдельный компонент делает именно то, что от него требуется.
Просто задача, которую мы пытаемся решить, находится вне этих систем и после пересмотра подход часто оказывается, что ворота всё это время были у нас в голове.
