Проблема ворот

22 минуты назад Прокомментировать Просмотры: 6

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

С навигационными системами приходится изощряться не меньше. Только вместо таймингов прыжков и физических состояний мы имеем дело с полигонами, узлами, связями и весами — всем тем, из чего складывается маршрут NPC. И здесь снова приоритетом выступают не столько математические правила, сколько психология восприятия игрока.

В стратегических играх перед ботами обычно стоит банальная задача: проскочить в узкий дверной проем, одолеть преграду и высыпать во внутренний двор. Если по пустой карте шествует одинокий боец, никаких сложностей не возникает. Но стоит выпустить на поле сотню-другую солдат при единственных воротах, куда физически помещаются лишь двое-трое, как начинается коллапс. Алгоритм поиска (например, A*) отработал безупречно, однако юниты беспомощно толпятся на месте, сталкиваясь с задачей, к которой они изначально не приспособлены.

Двести агентов NavMesh одновременно получают приказ рвануть к злосчастному проходу. Они мгновенно настраивают маршруты, бегут, но по мере сужения пространства толпа сбивается в пятнадцати метрах от цели. Люди начинают судорожно дергаться, пятиться и толкаться, пока внутрь просачивается от силы парочка бойцов.

Заглянув в этот момент в профайлер и обнаружив затор, мы видим, что львиную долю времени отъедает A*. Задержка логична: каждый NPC запрашивает собственный путь, таких запросов целая сотенная армия, все начинает тормозить. Казалось бы, вывод очевиден — надо ускорить поиск пути. Но это ловушка…

Заблуждение кроется в том, что мы пытаемся разрешить проблему макро-навигации («как добраться из точки A в точку B»), в то время как поведение толпы диктуется микро-задачей («как лавировать по готовому маршруту, когда бок о бок с тобой теснится толпа сослуживцев»).

Визуально обе ситуации выглядят одинаково — боец просто обязан дойти до цели. Но если перепутать методы, можно часами крутить параметры A*, менять радиусы, перепекать NavMesh, настраивать силы отталкивания и всё равно наблюдать у входа неорганизованную массу, которая прекрасно понимает куда идти, но сделать шаг не может.

(Проверить интерактив) Можно на лету менять ширину прохода и численность отряда, наблюдая формирование пробок.

Как устроен NavMesh

Почему же персонаж «вязнет» в дверях, хотя глазом видно, что проем более чем просторный? Дело в том, что NavMesh — это невидимая подложка под ногами, а отдельная сетка поверх геометрии уровней, сгенерированная с учетом габаритов конкретного агента. Именно поэтому коридор, казавшийся широким во вьюпорте, для центра NPC превращается в игольное ушко: от стен необходимо отступить на радиус персонажа, чтобы исключить застревания (серый контур — отступы от стен, красный — сам навмеш).

В нашем примере ширина ворот равна 1,6 м при радиусе агента в полметра. Дизайнеру и игроку кажется, что сюда запросто протиснутся трое. Однако расчеты NavMesh безжалостно отнимают по 50 сантиметров с каждого края, оставляя для центра NPC скромные 0,6 метра. Фактически в такие ворота сможет протиснуться лишь один боец.

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

Соблазнительно уменьшить радиус агента до 0,35 метра, решив проблему точечно. Но это повлечет перестройку всей геометрии навигации: персонажи начнут липнуть к стенам, проваливаться в текстуры и проникать туда, куда по задумке разработчиков ступать не должны. Локальная правка рушит половину уровня. В итоге левел-дизайнер предпочитает не трогать настройки агента, а… правильно, делает дверные проемы шире. Именно отсюда берет корни архитектурная гигантомания в старых видеоиграх — исполинские ворота и коридоры обусловлены банальной «проблемой ворот».

Вот почему параметры навигационной сетки — это не просто косметические цифры. Радиус агента определяет не толщину нарисованного кругляша, а границы самой проходимой зоны.

Агент застрял

Бывает и другой сценарий: мы уверены, что юнит застопорился посреди пути, хотя никакого маршрута у него изначально не существовало, так как конечная точка задана вне пределов навмеша. Персонаж стоит в ступоре, тестировщики оформляют баг-репорт, а программист в недоумении шерстит профайлер. Он проверяет A*, затем сетку, следом систему отталкивания, пока не выясняет, что поиск пути даже не стартовал. Винить кодера трудно, а для геймдизайнера это выглядит как классический сбой навигации.

Схожая коллизия возникает, когда маршрут находится, но обрывается у ближайшей доступной точки, внешне выглядя как все то же «застревание». Логика требует сначала проецировать цель на навмеш и лишь затем строить к ней путь. Именно поэтому NPC лишены возможности залезать в произвольные укромные места, доступные игроку.

(Попробовать в деле) Кликните по стене: цель либо прилипнет к ближайшему проходу, либо (при их отсутствии) агент останется на месте.

Еще один способ ввести A* в ступор

Разрывы в NavMesh тоже добавляют головной боли. Лестницы, провалы, дверные коробки — все участки, где навигация прерывается, требуют использования OffMeshLink. И здесь кроется подвох: наличие множества дорог вовсе не гарантирует, что движок выберет вариант, кажущийся разумным человеку.

Возьмем разрыв шириной 1,2 метра с дефолтным весом линка 1.0. Примерно 140 из 200 бойцов попрутся именно туда, игнорируя более длинный, но свободный обходной путь.

Для машины дешевый путь — закон, невзирая на то, что там уже образовалась давка. Повышение стоимости перехода заставляет солдат переключиться на альтернативу, демонстрируя процесс перераспределения потоков. Однако стандартный алгоритм A* об этом не догадается сам, так как он слепо оптимизирует те веса, которые ему задали.

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

Когда A* начинает тормозить

Теперь можно обсудить производительность самого A*. Хотя после вышесказанного очевидно, что алгоритм просто не создан для решения некоторых задач. Метод перебирает узлы и сопоставляет веса. Если навмеш насчитывает 41 тысячу полигонов, а проложить путь нужно из одного конца карты в другой, единичный запрос на тестовом полигоне захватит больше трети всей сетки.

Допустим, на один такой расчет уходит 0,35 миллисекунды. Попытка запустить две сотни подобных запросов одновременно обернется просадкой в 70 миллисекунд. Игровая индустрия научилась справляться с этим лет двадцать назад: запросы выстраиваются в очередь, а пока путь не готов (на что уходит пара кадров), агент продолжает шагать по устаревшему маршруту. Геймплейно это выглядит не как фриз, а как легкое запаздывание — персонаж может секунду потыкаться носом в преграду.

Иерархический A*

Если карта поделена на крупные сектора, соединенные небольшим числом проходов, нет смысла заставлять A* сканировать все 41K полигонов. Логичнее заранее просчитать структуру уровня и сперва определить ключевые зоны макро-уровня.

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

Схема выглядит как цепочка регионов A -> B -> C, после чего ищется конкретный трек Agent -> Portal B -> Portal C -> Target. Это избавляет систему от необходимости перелопачивать всю карту целиком, хотя для самого агента итоговый результат неотличим от классического поиска.

Подобный верхнеуровневый граф создается на этапе компиляции или загрузки уровня и обновляется лишь при блокировке порталов. Старый добрый принцип: предварительно посчитанные данные глупо вычислять заново в рантайме.

(Пощупать руками) Переключайтесь между обычным и иерархическим A*, чтобы оценить разницу в тайлах и скорости расчета.

Что если все движутся к одной цели?

Здесь классический A* капитулирует перед алгоритмами перемещения толпы. Имея две сотни юнитов с единым пунктом назначения, придется инициировать 200 независимых поисков, даже при идентичности большей части маршрутов.

Разница стартовых позиций мешает использовать A* напрямую, хотя финальные отрезки путей совпадают. Мы занимаемся сизифовым трудом, решая одну задачу двести раз. Спасением становится векторное поле (Flow Field).

Вместо индивидуального поиска путей мы однократно распространяем веса от цели в обратную сторону по всей толпе. Для каждой ячейки сетки фиксируется вектор направления на соседний тайл с наименьшим весом. Попав в ячейку, агент просто считывает направление. Мы один раз аккумулируем всю информацию, которую генерировал A*, поэтому затраты на построение поля практически не зависят от численности отряда.

Для тестов я взял сетку 128×128 с шагом 0,5 метра: полная перестройка поля занимает 4 миллисекунды. Это стоимость обновления самой матрицы, а не каждого юнита. При частых апдейтах (3–4 раза в секунду) нагрузка составляла всего 12 мс в секунду. Для сравнения, аналогичная толпа на иерархическом A* съедала 12 мс на каждый отдельный запрос!

Конечно, это компромисс. Метод хорош для масс, но как только у каждого бойца появляются личные задачи или меняются приоритеты, количество полей растет, раздувая потребление памяти и усложняя пересчет. Разумнее применять гибридный подход: боссы, именные NPC и одиночки используют A*, а солдатская массовка управляется векторными полями.

(Попробовать) Можно протестировать бенчмарк A* для 200+ агентов, управляемых общим векторным полем.

Локальное избежание столкновений (Local Avoidance)

Даже после прокладки идеального глобального маршрута «проблема ворот» не исчезает: шестьдесят бойцов одновременно стремятся занять одну точку пространства. И здесь A* снова бессилен.

На арену выходят RVO или его производная ORCA. Они решают иную задачу: анализируя скорости и позиции соседей, алгоритм отсекает векторы столкновений, подбирая оптимальную скорость для продолжения движения. Иными словами, юнита больше не волнует глобальная цель «как дойти до города», его заботит лишь вопрос «как не задеть соседа в эту секунду».

Поэтому локальный avoidance нельзя рассматривать как замену глобальной навигации. Оставшись без путеводной нити, агент будет виртуозно уворачиваться от всех вокруг, но никуда не придет, уперевшись в банальный тупик-стену (интерактивный пример).

Когда у всех агентов выставлен одинаковый приоритет (скажем, стандартные 50), система становится симметричной. Каждый считает себя равным соседу, уступает дорогу, но в итоге никто не проявляет напористости для преодоления заветного проема. Небольшая асимметрия творит чудеса: случайный разброс avoidancePriority от 0 до 99 сократил время простоя у ворот с 4,2 до 1,1 секунды.

Это наглядный пример того, почему сухие цифры профайлера уступают визуальному анализу, а сложнейший код пасует перед простейшим единообразием правил. Проблема решилась не переписыванием алгоритмов, а добавлением поведенческой асимметрии (оценить в демо, сравнив Uniform и Random приоритеты).

Динамические препятствия

Добавим на уровень катящиеся бочки с авто-перепеканием навмеша. Все работает, но процесс запекания фрагментов сетки — удовольствие дорогое. Заставлять движок пересчитывать геометрию из-за объекта, который через полсекунды сменит позицию, неэффективно.