Беги, да не спотыкайся: как устроен ИИ в Death Stranding

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

ИИ-программист Kojima Productions Эрик Джонсон выступил с докладом на GDC 2021, в ходе которого рассказал, как устроен искусственный интеллект в Death Stranding. Большего всего внимания Джонсон уделил вопросам построения навигационной сетки и поиска пути в отрытом мире. Мы выбрали из лекции главное.

Беги, да не спотыкайся: как устроен ИИ в Death Stranding

Окружение Death Stranding наполнено множеством препятствий и труднопроходимых зон, которые представляют из себя проблему не только для игрока, но и для NPC. Для разработчиков было важно, чтобы ИИ адекватно воспринимал все неровности вокруг себя и корректно перемещался по миру, но при этом продолжал представлять опасность для игрока.

В Death Stranding есть несколько типов противников, каждый из которых имеет свои особенности поведения. Есть МУЛы — их цель заключается в том, чтобы отобрать посылки у главного героя, поэтому они не используют огнестрельное оружие. Вторая группировка — террористы, которые пытаются убить Сэма. Они активно пользуются укрытиями и огнестрелом. Третий тип — мини-боссы, во время схваток с которыми ландшафт окружения кардинально преображается. Ещё есть BT, но они малоподвижны, поэтому их можно не рассматривать в контексте перемещения по миру.

Разработка ИИ шла постепенно: сначала авторы добавили врагам базовые функции, чтобы можно было опробовать геймплей, а лишь затем начали думать над тем, как поместить NPC в открытый мир.

Ранний концепт. На этом этапе противники умели искать грузы, а игрок мог тихо вырубать NPC
В 2017 году враги научились реагировать на звук и искать его источник. Сэм умел прятаться в траве, но противники могли отслеживать его грузы
В финальной версии МУЛы выезжают на разведку, если засекают груз Сэма. Тем не менее у игрока остаётся возможность спрятаться, пока NPC ищут его
Если же МУЛы замечают Сэма, то начинают охотиться за ним

Как противники используют навигационную сетку

Для передвижения по миру Death Stranding ИИ использует навигационную сетку (navmesh), состоящую из полигонов. Navmesh покрывает все поверхности, по которым могут передвигаться NPC. Если какой-то участок пространства не покрыт навигационной сеткой, то NPC не сможет зайти на него.

На плоских непрерывных пространствах navmesh достаточно простая
Но большая часть мира в Death Stranding — это пересечённая местность, по которой трудно передвигаться. В таких зонах навигационная сетка получается намного сложнее
Чтобы построить сетку для естественного окружения, нужно намного больше navmesh-полигонов, чем для плоских поверхностей

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

Разработчики стремились сделать так, чтобы NPC учитывали все эти особенности, а также умели преодолевать препятствия и избегать опасные участки.

Чтобы обнаружить препятствие перед собой, NPC используют рейкастинг 
Во время бега NPC проверяют материал, по которому передвигаются — если они цепляют камень, то есть шанс, что они споткнутся
Но NPC стараются избегать камней

Чтобы NPC понимали, где передвигаться безопасно, а где — нет, разработчики поделили все navmesh-полигоны на несколько групп: по голубым передвигаться просто, по жёлтым — сложнее, по красным — ещё сложнее. Соответственно, ИИ умеет распознавать труднопроходимые зоны, поэтому стремится их избегать.

Так выглядит система Placement Painting, которая отмечает полигоны, на которые нежелательно заходить 
Ещё противники могут заходить в воду, хоть это и нежелательно для них

С появлением системы Placement Painting поведение NPC стало более правдоподобным. Но вместе с этим появились и проблемы — поиск пути на столь детализированной навигационной сетке тратит много вычислительных ресурсов.

Как NPC ищут подходящий путь

Для процесса pathfinding разработчики использовали алгоритм A*, который занимается поиском оптимального и наименее трудозатратного маршрута, сравнивая «стоимость» разных путей. Так как в Death Stranding зона для поиска пути может быть очень большой, команда ограничила процесс 500 итерациями.

Так выглядит navmesh фермы — здесь есть заборы и небольшие препятствия, но в основном тут открытые пространства. В ширину эта территория равна 200 метрам
500 итераций достаточно, чтобы найти маршрут через эту зону 
На пересечённой местности всё намного сложнее. 500 итераций хватит лишь на поиск пути в зоне шириной в 25 метров
К тому же в Death Stranding навигационная сетка генерируется в реальном времени. Это дополнительно усложняет поиск пути в открытом мире. Например, цель, к которой стремится NPC может исчезнуть даже до того, как до неё будет проложен маршрут

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

Есть два распространённых способа реализовать это решение — рейкаст и таймер, — но они оба не подходят. Рейкаст не подходит, потому что он реагирует на проблему слишком поздно, поэтому NPC постоянно опаздывал бы с запуском поиска пути. А таймер не подходит, потому что сложно задать универсальный интервал, который был бы эффективным во всех ситуациях. К тому же этот подход слишком ресурсоёмкий, а маршрут получается нестабильным.

Команда использовала таймер на ранних этапах разработки — система перезапускала процесс два раза в секунду и просто направляла NPC к цели, которая была на предыдущем прогоне.

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

Когда МУЛ доходит до жёлтой стрелки, можно увидеть, как его путь внезапно меняется и ведёт его в противоположную сторону. Из-за этого поведение противников выглядело некорректным

Команда поняла, что ей нужна система, которая:

  • сможет итеративно находить путь, чтобы достичь цели (учитывая ограничение в 500 итераций);
  • будет незамедлительно находить проблемы;
  • сможет автоматически пересоздавать путь, но при этом делать это как можно реже.

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

Первая ситуация: ИИ-агент выходит за пределы намеченного пути
Первая ситуация: ИИ-агент выходит за пределы намеченного пути
Вторая ситуация: цель, к которой стремился агент, покидает свой полигон
Вторая ситуация: цель, к которой стремился агент, покидает свой полигон
Третья ситуация: сегмент пути становится недоступен, поэтому агент не может пройти по нему
Третья ситуация: сегмент пути становится недоступен, поэтому агент не может пройти по нему
Четвёртая ситуация: финальная цель переместилась и теперь находится за пределами пути. В такой сиутации маршрут считается до ближайшего к цели тайла
Четвёртая ситуация: финальная цель переместилась и теперь находится за пределами пути. В такой сиутации маршрут считается до ближайшего к цели тайла
Пятая ситуация: цель находится за пределами просчитанного пути, поэтому агент сначала добирается до ближайшего к цели тайла, а потом пересчитывает маршрут
Пятая ситуация: цель находится за пределами просчитанного пути, поэтому агент сначала добирается до ближайшего к цели тайла, а потом пересчитывает маршрут

В результате разработчики создали Event-Based Repathing систему, которая отвечала всем требованиям: она могла реагировать на самые распространённые проблемы, при которых нужно заново искать путь, но при этом делала это не слишком часто, чтобы не забирать вычислительные мощности.

Так система работает на практике. Если нет ошибок, то агент продолжает движение по намеченному маршруту. Если же появляется препятствие, то путь пересчитывается
Когда агент двигается, вокруг него генерируются новые тайлы навигационной сетки. Это позволяет корректно рассчитывать путь NPC даже несмотря на то, что его дальность не слишком большая

Проблемы системы перезапуска поиска пути

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

Иногда NPC подбирали странные пути следования  
При беге NPC не успевал пересчитывать свою траекторию, из-за чего попадал за пределы маршрута. Потом он создавал новый путь, но опять попадал за его пределы. Это могло повторяться бесконечно
Ещё одна проблема возникала в момент, когда NPC наступал на полигон с высокой «стоимостью» — тогда он создавал новый путь и пытался обойти препятствие
Чтобы решить проблему, разработчики снизили «стоимость» прохода по полигону, но увеличили плату за вход на него. В результате агенту сложнее просто взять и поменять свой маршрут
В результате NPC всё ещё избегает труднопроходимых зон, но не меняет направление, если наступает на эти полигоны
Ещё одна проблема приводила к застреванию NPC в цикле пересоздания пути. Она заключалась в том, что в некоторых ситуациях размера подгруженной navmesh не хватало — тайлы просто сбрасывались, когда NPC отходил. Поэтому разработчики увеличили размер сетки 

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

Чтобы спуститься в расщелину, NPC нужно сперва дойти до подходящей точки, находящейся в 100 метрах от него. В такой ситуации для корректного поиска пути потребуется слишком много итераций
Если ИИ всё же найдёт путь в расщелину, то он не сможет из неё выбраться — размер полигонов внизу слишком маленький, поэтому размер зоны поиска не превышает нескольких десятков метров
Если ИИ всё же найдёт путь в расщелину, то он не сможет из неё выбраться — размер полигонов внизу слишком маленький, поэтому размер зоны поиска не превышает нескольких десятков метров
Также в таких условиях NPC вряд ли могли бы найти дорогу на базу после охоты за игроком
Также в таких условиях NPC вряд ли могли бы найти дорогу на базу после охоты за игроком

Чтобы справиться с этим, разработчики использовали технологию движка Decima под названием AI Road Network. Её можно описать как сеть дорог, дополняющих систему поиска пути в Death Stranding: NPC могут переключаться на AI Road Network, если не могут найти маршрут при помощи базовой системы поиска пути.

Так выглядит поиск пути только при помощи навигационной сетки — NPC упирается в стену, потому что не знает, можно ли обойти препятствие
Гибридная система позволяет агенту переключиться на AI Road Network, чтобы дойти до точки, которая находится за пределами его навигационной сетки

Создание навигационной сетки для динамических объектов

В Death Stranding есть ситуации, когда навигационная сетка должна сгенерироваться для динамических объектов. Например, это происходит в моменты столкновения с мини-боссами: из земли появляются здания, на которые может забраться не только игрок, но и противник.

Navmesh генерируется в момент, когда здание только начинает появляться из земли. Вместе с этим создаются точки прыжка для противника, которые показывают ему, с какой стороны можно забраться на здание
Когда мини-босс запрыгивает на здание, оно начинает тонуть. Тогда же исчезает и navmesh на крыше

Динамические объекты встречаются и вне столкновений с мини-боссами. Большинство таких объектов помечаются на навигационной сетке как пропсы.

К динамическим объектам относятся выдвижные барьеры, бочки, ограждения
Транспорт, находящийся в покое, помечается как пропс
Это относится и к постройкам, которые находятся в состоянии возведения
Навигационная сетка для моста генерируется прямо во время строительства

Использование лестниц и укрытий

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

Как на них можно залезать в вертикальном положении
Как на них можно залезать в вертикальном положении
Как с них можно слезать в вертикальном положении
Как с них можно слезать в вертикальном положении
Как на них можно залезать в горизонтальном положении
Как на них можно залезать в горизонтальном положении
Как с них можно слезать в горизонтальном положении
Как с них можно слезать в горизонтальном положении
Когда игрок ставит лестницу, она проверяет точки соприкосновения с поверхностью. В зависимости от этого определяются точки, с которых NPC могут забраться на лестницу
Также NPC могут спрыгивать с лестниц, если это для них безопасно

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

Когда начинается бой, система проводит collision-тест, чтобы найти ближайшие укрытия
Когда система нашла укрытие, NPC проверяет с какой позиции он сможет стрелять в цель, но при этом оставаться защищённым 
Когда система нашла укрытие, NPC проверяет с какой позиции он сможет стрелять в цель, но при этом оставаться защищённым 
За поиск укрытий отвечает ИИ-агент, который анализирует окружение в момент начала перестрелки
Вот так NPC проверяют, находится ли Сэм на линии огня
Когда игрок отдаляется от NPC, они заменяются на низкодетализированные модели. Уровень их интеллекта тоже снижается, но они сохраняют базовые черты поведения: например, продолжают патрулировать определённые маршруты

Джонсон отметил, что некоторые вещи так и не удалось реализовать в Death Stranding. Например, систему bidirectional pathfinding или процедурную расстановку точек для прыжков.

441441
105 комментариев

Ещё несколько моментов. По поводу укрытий.

24
Ответить

Комментарий недоступен

47
Ответить

ИИ просчитывает даже когда игрок далеко. https://twitter.com/Suvitruf/status/1453035100376080392

22
Ответить

Получается гениально

25
Ответить

Комментарий недоступен

22
Ответить

В них на релизе почти 20 лет назад багов не было,только вылеты):

1
Ответить

Достаточно просто сделать костяк. Но на пограничных решениях (лестницы, скалы, лестницы + скалы) происходят разные баги/непредвиденные результаты.
Например, на одной мобильной игре, где есть динозавры с пушками добавили такое поведение: когда динозавр близко, то он бежит на врага и кусает его. В итоге два динозавра бежали друг на друга и начинали бегать кругами) Не помню, но вроде так и не пофиксили этот баг)
Плюс недостаток времени на такие вещи. Как правило, на ИИ мало тратят времени. Хорошо, если есть готовое решение и опыта достаточно. Но скорее всего всё оканчивается на том, заводишь систему, приемлемо работает и идешь делать следующую задачу.
Ну а на ААА проектах может сидеть пару лет и заниматься только ИИ) Он там настолько преисполнится)) Хотя если честно на счёт ААА не знаю) Может они 2-3 месяца ИИ занимаются (если это не одна из главных фичей), а потом идут другие вещи делать.

Ответить