{"id":3842,"url":"\/distributions\/3842\/click?bit=1&hash=4c67e91a2a588f03561899c61c4eabfeb37008500c6498f3b9533b2e8845d454","title":"\u041e\u0431\u043e\u0436\u0430\u0435\u0442\u0435 \u043a\u043e\u043f\u0430\u0442\u044c\u0441\u044f \u0432 \u0434\u0430\u043d\u043d\u044b\u0445? ","buttonText":"\u0412\u0430\u043c \u0441\u044e\u0434\u0430","imageUuid":"11cfcef6-3125-52d0-8ef8-49fb205d3efe","isPaidAndBannersEnabled":false}
Gamedev
Владимир Семыкин

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

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

ИИ-программист Kojima Productions Эрик Джонсон выступил с докладом на GDC 2021, в ходе которого рассказал, как устроен искусственный интеллект в 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 вряд ли могли бы найти дорогу на базу после охоты за игроком

Чтобы справиться с этим, разработчики использовали технологию движка 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, они заменяются на низкодетализированные модели. Уровень их интеллекта тоже снижается, но они сохраняют базовые черты поведения: например, продолжают патрулировать определённые маршруты

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

0
104 комментария
Написать комментарий...
Andrey Apanasik

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

Но из-за того, что алгоритм работает по требованию, бывают случаи, когда npc ещё не успел подобрать укрытие.

Чтобы эту проблему решить, в самом начале боя специальный менеджер в фоне постепенно начинает прогонять объекты и помечает их как возможные для укрытия 🤔
Ответить
Развернуть ветку
Легкий ихтиандр

Так, Андрей, хвтатит пиарить твиттер этого ноунейма.

Ответить
Развернуть ветку
Andrey Apanasik

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

Там буквально вся карта живёт своей жизнью.

А когда игрок вызывает ивенты для пропуска времени, то перемотка и для npc срабатывает.
Ответить
Развернуть ветку
3 комментария
Vahe

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

Ответить
Развернуть ветку
Названый жар

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

Ответить
Развернуть ветку
Александр Кобяков

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

Ответить
Развернуть ветку
9 комментариев
Иван Лашин

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

Ответить
Развернуть ветку
1 комментарий
Артём Афанасенко

Веревка - для лохов, боласган - выбор мастеров. Вообще люблю нападать на лагеря МУЛов, особенно когда Сэм научился отбивать их эхолокацию. Кого в стелсе, кого пушкой, кого на их же собственной машине сбиваю. Веселуха. Потом собираю ресурсы и давай строить дороги :)

Ответить
Развернуть ветку
leet

Незабываемо в первый раз стащить у МУЛов грузовик, когда у Сэма еще нет возможности делать свои и развозить грузы с кайфом. Ну, конечно, если дороги есть :D

Ответить
Развернуть ветку
8 комментариев
Qu Be
кого на их же собственной машине сбиваю. Веселуха.

D:

Ответить
Развернуть ветку
Remus Croft

Боласган тупо делает всё дальнейшее оружие ненужным.

Ответить
Развернуть ветку
5 комментариев
zedalert

Программисты: создают сложный AI, навигационные карты, тестируют это годами.
Я: залезаю на недоступную для NPC поверхность - NPC стоят внизу на одном месте и ловят все выстрелы.

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

Ответить
Развернуть ветку
Роман Китов

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

Ответить
Развернуть ветку
1 комментарий
Labanshee

Пользуясь темой, подскажите, пожалуйста. А в Death Stranding поставки имеют завершение? То есть возможно ли сделать все поставки из одной базы, и больше они там появляться не будут, или же это бесконечный процесс?

Ответить
Развернуть ветку
DarkPrince9507

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

Ответить
Развернуть ветку
17 комментариев
Ivan Orlov

У каждой базы определённый набор заданий (с нумерацией). Если ты его уже делал, это будет отмечено, но ничто не мешает повторить его, если например заказ даёт тебе ресурсы для строительства.
Однако есть проблема на некоторых базах, если за ней закреплено очень много заказов. Но там есть прикол - берёшь все задания, но на этапе подготовки передумываешь. В итоге список пополняется квестами, которые встали в освободившуюся очередь доступных квестов.
Суммарно в игре 500 миссий.

Ответить
Развернуть ветку
5 комментариев
Konstantin Hmm

Тебе уже ответили, но дополню, квест можешь считать выполненным если взял особую доставку и по завершению получил оценку S [НЕВЕРОЯТНО В КВАДРАТЕ], а посмотреть количество всех заказов что там будут через браслет, на карте.

Ответить
Развернуть ветку
Ruz Leon

Просто спустя время появятся повторные.

Ответить
Развернуть ветку
3 комментария
Семён Камалов

Как минимум для Старейшины поставки имеют значения. Не будешь привозить ему лекарства, Старейшина умрёт

Ответить
Развернуть ветку
2 комментария
Yura

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

Ответить
Развернуть ветку
Artfullash

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

Ответить
Развернуть ветку
Артём Афанасенко

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

Ответить
Развернуть ветку
Chesheer

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

Ответить
Развернуть ветку
Qu Be

По кд к ним хожу что бы дорогу строить.

Ответить
Развернуть ветку
Приятный Мурод
Пересечённая местность оказалась головной болью не только для игроков

но ведь для игрока там все максимально лояльно сделано, два курка/два кнопки мыши - и ты не падаешь нигде

Ответить
Развернуть ветку
leet

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

Ответить
Развернуть ветку
9 комментариев
danila

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

Ответить
Развернуть ветку
Str1X

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

Ответить
Развернуть ветку
1 комментарий
Владислав Румянцев

Еще хороший(а может и нет) и не затратный способ поиска пути для NPC. Это выход на траекторию гл.персонажа непесью. Гл.персонаж будет всегда выбирать оптимальный путь, траектория записывается во временный буфер, а NPC будет повторять. А включать алгоритм заново поиска только если гл.персонаж сделал ошибку, т.е. не оптимально выбрал путь. Ошибся, проиграл. После просчета оптимального пути NPC, опять выходит на траекторию гл.персонажа. Выложил бы видео как болванка догоняет болванку, но недоработанные болванки персонажей пугают людей больше чем алгоритм)). Вообще многие траектории движения можно сохранять для постоянного использования для NPC просчитав один раз. Это сильно сокращает затратность ресурсов. Траектории можно делать с временным отклонением, например если NPC нужно задержать. Рассчитывать постоянно поиск, особенно если много NPC будет накладно.

Ответить
Развернуть ветку
RusUpdate

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

Ответить
Развернуть ветку
Thomas Anderson

в Directors Cut мулов тоже научили стрелять. в их лагерях установили турели и теперь, как только они вас засекают - бегут к этим турелям и мочат. поэтому в лагеря приходилось пробираться исключительно по стелсу

Ответить
Развернуть ветку
Last Waltz

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

Ответить
Развернуть ветку
Pavloleg

ИИ-программист? Кодзима там технологической сингулярности успел достичь, пока мы тут с нейронами балуемся?

Ответить
Развернуть ветку
alex nika

Полезно, спасибо

Ответить
Развернуть ветку
neofic

Я, честно говоря, в легком шоке от того на сколько круто они заморочились! Эти наработки скорее всего можно будет как то использовать в будущем и для реального передвижения по пересеченной местности. Или может кто знает - реальные роботы ушли уже дальше чем НПС в этой игре?

Ответить
Развернуть ветку
Михаил Кузнецов

Надеюсь они когда-нибудь расскажут как работает их система асинхронного мультиплеера с расстановкой объектов \ прокладыванием тропинок

Ответить
Развернуть ветку
Павел

Тоже пытаюсь найти по этому поводу инфу, но нигде так и не нашёл.

Ответить
Развернуть ветку
Кумыс Камин

Ответственно заявляю что у открытого мира игры очень сильно не раскрыт его потенциал.Да да.Посему и теплится надежда на 2ю часть где ВОЗМОЖНО это исправят.(Хотя кого я обманываю,Кодзиме сан это нахрен не нужно)(Было бы нужно и в 1й бы сделал).(Наверное).

Ответить
Развернуть ветку

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

Развернуть ветку
Konstantin Hmm

Как я и предполагал, в игре ИИ умный только тогда, когда вы УБЕГАЕТЕ.
В потасовках нпс останавливаются на месте, в стелсе вообще смех, чего не ожидаешь от Кодзимы, не слышат как душат их союзников в метре друг от друга.

Ответить
Развернуть ветку
Георгий Авакян

Автор хорош!

Ответить
Развернуть ветку
Remus Croft
сложности поиска пути на карте высот
все МУЛы сидят на равнинах

ммм

Ответить
Развернуть ветку
Странник1986

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

Ответить
Развернуть ветку
Читать все 104 комментария
null