В предыдущих статьях я уже немного затронул тему правильного обмана игрока, через койоттайм и подкручивание стрельбы. Смотря на эти случаи, вы наверное заметили, что хороший игровой код довольно часто занимается построением модели мира которая будет достаточно хорошо совпадать с тем, что человек ожидает от игры.

С навигацией в играх приходится хачить не меньше, и приходится разбираться уже не со временем прыжка и физическим состоянием персонажа в понимании игрока, а с набором полигонов, узлов, рёбер и стоимостей и вообще всем тем, что определяет путь 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 избегает столкновений и каждый отдельный компонент делает именно то, что от него требуется.

Просто задача, которую мы пытаемся решить, находится вне этих систем и после пересмотра часто оказывается, что ворота всё это время были у нас в голове.

Комментарии (13)


  1. Void-Cowboy
    08.10.2026 06:48

    а потом игрок сильно быстро вращает камерой, оптимизатор "упрощает" на мгновение и вот уже маршрут перерестроен

    как по мне с играми на таких толпах проблема скорее в коллизиях с другими механиками чем в просто перемещениях

    все же логику "застреваний" можно и простыми условиями развязать, а вот всякое на стыке сложнее всего отлавливать и фиксить (и зачастую часть все равно в релиз улетает)


  1. mynameco
    08.10.2026 06:48

    была статья, где рассказывалось как делали навигацию для старкрафт 2. там толпы проходили через толпы. там сетка, мелкая и агент резервирует точки перед собой.


  1. azTotMD
    08.10.2026 06:48

    Я тут, возможно, какие-то крамольные мысли скажу, но я со своей колокольни сужу.

    потому что каждому NPC нужен путь, значит у нас двести поисков пути

    Не смотрели на мурмурацию? Это когда рой птиц движется как одно целое. Там вроде совсем простые правила - двигайся за впереди идущим, но не подходи слишком близко. Причем правила локальные, не нужно выделять каких-то лидеров.

    NPC застрял

    а это происходит потому, что у него нет обратной связи. Он пытается идти, но никак не реагирует на то, что координаты не меняются.

    Зачем вообще нужен этот А*? Ну ладно там для стратегий со статической картой, ок. В RPG то его зачем тащить?

    на ожидания игрока от NPC, а не корректность поведения

    движение по алгоритму кратчайшего пути - это некорректное поведение. Никто так не ходит. Мы так не ходим. Мы идём либо по уже знакомой дороге, либо примерно оценивая направление. Причем если нам локально встретится возмущение - дерево поперек привычной дороги мы без проблем обходим. Я бы скорее ожидал, что NPC будет совершать случайные блуждания как-то реагируя на то, что ему встретится (побеседовал с другим нпц, сорвал цветов). Если уж по сюжету нужно, чтобы НПЦ добрался до какого-то места, то пусть дойдет хоть как-нибудь, а не оптимальным способом.


    1. ardraeiss
      08.10.2026 06:48

      движение по алгоритму кратчайшего пути - это некорректное поведение. Никто так не ходит. Мы так не ходим.

      Очень даже ходим, причём массово. Те самые "тут толпами срезают через газон, потому что дизайнеры благоустройтва не кратчайший путь проложили, а со странной загогулиной" тропинки по паркам и дворам - это результат сокращения маршрута. Это даже сильнее нежелания лезть на более грязный, чем плиточка, газон оказывается. И из этого существует практика ландшафтного дизайна - сперва соорудить садик, а потом, спустя несколько недель-месяцев, когда люди натопчут тропинки, эти тропинки и проложить полноценно с дренажом.


    1. Skigh
      08.10.2026 06:48

      движение по алгоритму кратчайшего пути - это некорректное поведение. Никто так не ходит. Мы так не ходим.

      Моделировать "как ходим мы" для сотен агентов одновременно - современных компьютеров не хватит.


      1. azTotMD
        08.10.2026 06:48

        ну это, если через ЛЛМ делать, можно ведь и поэффективнее найти способы


  1. ardraeiss
    08.10.2026 06:48

    Вспомнилось, что проблема прохождения несогласованной толпой не самых широких ворот и в реальности существует, только чуть иная - когда барано-козы ломятся в открытый для них проход, толпясь и толкаясь, и мешают сами себе. Там не вопрос пасфайндинга, там именно "где два барана пройдут бок о бок без задержек - там они толчею учиняют и время теряют".

    На примерах в статье нечто похожее видно, где агенты/неписи толпятся у входа, куда двое одновременно проходят рядышком, но только если согласованно. А без согласования толпятся трое-четверо, пролезает время от времени один и прёт по плюс-минус центру, не давая другим.


    1. Ndochp
      08.10.2026 06:48

      В общем моделируешь армию - учи ходить строем.


  1. Deosis
    08.10.2026 06:48

    В зомби-шутере баг превращается в фичу


  1. Error1024
    08.10.2026 06:48

    Не имею отношения к геймдеву, но ваши статьи про игровую индустрию и плюсы - прекрасны, спасибо что продолжаете писать их, в эпоху ИИ слопа в топах статей.


  1. ElvenSailor
    08.10.2026 06:48

    а в принципе, не факт, что мобам в толпе вообще нужно взаимодействовать друг с дружкой, => мы можем их сделать проходящими через друг дружку => навигация сильно упрощается. Выглядит порой комично, но есть жанры, где это ок.

    В Lineage2 помню, вообще специально сделали так, что если мобяра застрял - он может телепортнуться. Зело их видимо, забодали маги, которые паравозы фармили со скалы :)


  1. master_program
    08.10.2026 06:48

    А можно выложить исходные коды? Так то прикольно NavMesh Sandbox , то хотелось бы покопаться во внутренностях.


    1. dalerank Автор
      08.10.2026 06:48

      без проблем. https://github.com/dalerank/article_pathfinding, там для всех трех статей примеры. Плюсовые не могу ибо они c игровых проектов, а JS аналоги все выложил