Искусственный интеллект в DOOM

DOOM — прародитель шутеров от первого лица, определивший целое поколение игр 90-х. Хоть это и не первая игра такого рода, и даже не первая игра id Software, но именно она изменила индустрию. Проект до сих пор изучают не только из-за его известности, но и потому, что он достиг высот в условиях сильных технических ограничений, задолго до появления большинства современных инструментов и стандартов. Под катом перевод статьи о работе искусственного интеллекта в Doom и трюках которые использовали разработчики для создания интересных боевых ситуаций.

DOOM, по своей сути, данжен-кроулер с оружием, в котором игроку предстоит ориентироваться в сложных нелинейных пространствах, находить ключи и активировать переключатели, чтобы найти выход с локации. По пути игроку придется сразиться с несметным количеством демонических созданий: от Зомби-солдат с оружием до Импов с фаерболами, летающих врагов вроде Какодемонов и Потерянных душ, а также здоровяков по типу Пинки и Барона Ада. DOOM II в 1994 году добавил еще больше разнообразия: Рыцари Ада, Ревенанты, Арахнотроны, Манкубусы, Элементали боли и Архивили. Все эти персонажи перемещаются по миру, реагируют на действия игрока и атакуют по собственной внутренней логике. Самое впечатляющее — это то, как игра одновременно обрабатывает пути, проверяет область видимости, столкновения и другие взаимодействия для огромного количества врагов.

Игра использовала все нововведения рынка домашних PC в тот период. Процессоры Intel становились доступнее, оперативная память — дешевле, а переход к Windows 3.1 подтолкнул к широкому распространениею графических ускорителей. Из-за подобных изменений id Software пришлось выбросить большинство наработок своей предыдущей игры (Wolfenstein 3D в 1992 году) и заняться серьезной переработкой кода для достижения высот, о которых игры той эпохи могли только мечтать.

Основная логика

Искусственный интеллект врагов в DOOM — это один из объектов игровой логики известный как thinker. Он отвечает за поведение всех игровых объектов, которым необходимо принимать решения. Оригинальная сборка игры для DOS работает со скоростью 35 кадров в секунду, где каждый кадр обрабатывается логика для всех четырех основных классов thinker’а: 

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

2. Обновление строки состояния в нижней части экрана.

3. Отображение на внутриигровой карте.

4. Рендеринг HUD.

Логика врагов основана на конечном автомате (Finite State Machine) — это простой и эффективный механизм, чтобы определить, выполняет ли персонаж определенное поведение в определенном состоянии, и при каких условиях состояние может смениться. Позже Half-Life популяризировала FSM в шутерах благодаря удобной реализации кодовой базы на C++, а также механизмам, с помощью которых персонажи могут иметь цель и возможность ее выполнить. DOOM работает похожим образом, но ему не хватает некоторых возможностей и бесшовной интеграции — в движке просто нет скриптового языка для гибкой настройки NPC. При этом вся логика написана на C, и в ней реализовано множество хитрых твиков для создания разнообразного дизайна врагов.

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

1. Враги всегда начинают в состоянии SPAWN: бездействуют и ждут события, которое заставит их перейти к активному поведению. Наиболее наглядный пример такого поведения — уровень Entryway в самом начале DOOM II, где при старте уровня враги стоят спиной к игроку, пока тот не привлечет их внимания.

2. Получив сигнал о том, что игрок близко, они переходят в состояние SEE: перемещаются по карте и двигаются к своей цели. 

3. Если ситуация позволяет, враг переходит в состояние MELEE/RANGE и атакует игрока. Затем возвращается к SEE.

4. В состояние PAIN противник переходит только извне, что логично — это должно происходить при получении урона. Затем воспроизводит нужные кадры для рендеринга, звуковые эффекты и возвращается к основной логике. NPC не переходят в состояние PAIN при каждом получении урона, вместо этого смена состояния завязана на шансах заложенных в дизайне врага. 

5. Наконец, противник может умереть двумя способами:

• Есть состояние DIE, когда демон получает общее количество урона, превышающее его начальное здоровье.

• Есть XDIE, когда демон получает урон и его разрывает на части. Это произойдет, если урон превысит оставшееся здоровье противника плюс его начальное здоровье.

  Например, Имп начинает с 60 HP. Если у него осталось 10 здоровья, то при следующей атаке нужно нанести 71 урона, чтобы его разорвало. С Зомби или Зомби-сержантом (20 и 30 HP) это будет легко, а с Какодемоном или Рыцарем Ада (400 и 500 HP) практически невозможно. Но способ тоже есть — с помощью телефрага (то есть телепортироваться во врага и нанести 10 000 урона). Например, в Perfect Hatred, второй миссии эпизода Thy Flesh Consumed DOOM, телефрагом можно убить Кибердемона с 4000 HP.

6. Последнее состояние RAISE. Оно появилось в DOOM II из-за демона Архивиля, который умеет воскрешать других демонов. 

Каждый противник придерживается этих общих состояний, но их индивидуальное поведение отличается. Как же оно определяется и работает?

Определение действий

Для выполнения логики любой агент спавнится с прикрепленным объектом thinker. Каждый thinker — это структура на C с указателем на функцию игровой логики, которую враг должен выполнить, а также дополнительные переменные, которые помогают ей обрести форму. Эта функция помогает каждому демону определить нужное поведение по его текущему состоянию.

Определение каждого врага в DOOM происходит вне кодовой базы. Текстовый файл из проекта импортируется и компилируется в файл 'info' с характеристиками врага и определениями для всех состояний. Затем информация компилируется в struct, который содержит следующие элементы:

• Внутренний ID в игре.

• Количество здоровья, с которым демон спавнится.

• Скорость передвижения.

• Вероятность прерывания состояния PAIN.

• Радиус и высота.

• Специфические свойства NPC.

Например, Импы — это твердые объекты, через них нельзя пройти (MF_SOLID), но можно стрелять (MF_SHOOTABLE) и наносить урон, а их смерть засчитывается в общее количество врагов на уровне (MF_COUNTKILL).  

Кроме того, демоны не всегда впадают в состояние PAIN при получении урона. Вместо этого на них влияет вероятность прерывания этого состояния, которое в кодовой базе называется PAIN chance. Когда враг получает ранение, происходит проверка вероятности: перейдет он в PAIN или нет. Число варьируется от 0 до 256 (1 байт) и настраивается для каждого врага. В случае с Импом и Зомби-сержантом оно равно 200 и 170 соответственно, то есть у первого 79,3% шанс перейти в PAIN, а у второго — 67,6%. 

Хитрость в том, что засчитывается каждое отдельное попадание из оружия. Если ракета считается за одно попадание, то дробовик технически имеет семь отдельных атак из-за своего разброса. Вот почему миниган полезен против Какодемона и Арахнотрона — у обоих PAIN chance 128 (или 50%), поэтому каждая вторая пуля может вызвать состояние PAIN. Это сильно влияет на выбор оружия, ту же систему реализовали в перезапуске серии в 2016 году. 

Некоторые враги имеют низкий PAIN chance. У Кибердемона и Архивиля он однозначный (5,5% и 3,1%), а у Потерянных душ, наоборот, 100%. Технически даже у бочек есть PAIN chance, но он равен 0.

Помимо информации о поведении врага, есть индивидуальные определения действий для каждого состояния FSM. Например, Имп использует действие атаки для обоих состояний ближнего и дальнего боя, а у Зомби-сержанта есть только дальний бой.

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

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

• Длину кадра во внутриигровых тиках.

• Внутриигровое действие в исходном коде, которое он должен выполнить на этом кадре действия.

• Следующий кадр действия, который он должен выполнить.

В случае с атакой Импа получится:

• Отрисовать первые два спрайта по 8 кадров каждый и запустить код, который обеспечивает поворот Импа лицом к игроку.

• Затем отрисовать третий кадр на 6 кадров и запустит функцию TroopAttack, которая разработана специально для импа.

• После завершения третьего кадра переход обратно в основное состояние SEE.

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

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

Самое интересное — переход к состоянию RAISE. Любой противник, которого может воскресить Архивиль, имеет набор действий с теми же кадрами спрайтов что и для смерти, но воспроизводятся они в обратном порядке.

И последнее: для каждого из этих определений действия нужен отдельный кадр анимации, но это скрывает еще одну сложность. Враги в DOOM могут изображаться под 8 различными углами относительно позиции игрока. Поэтому когда используется одно из этих семейств спрайтов, оно всегда извлекает нужный набор спрайтов для этого персонажа, основываясь на его угле относительно игрока. 

У Импа 21 уникальных индекс спрайта, а значит — 168 отдельных спрайтов, чтобы покрыть все 8 углов. Оптимизация здесь в том, что некоторые персонажи симметричны. Поэтому вместо 8 наборов спрайтов есть только 5, и если набор спрайтов для данной ориентации отсутствует, он просто берет зеркальный эквивалент. 

Обзор и движение

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

В состоянии SPAWN противник ждет триггера для перехода в следующий стейт. Этих триггера всего два: когда NPC увидит или услышит врага. Увидев цель, монстр поворачивается к ней. Здесь есть несколько дополнительных проверок, например, является ли цель возможным объектом для атаки. Другими словами, NPC не преследуют все, что издает шум.

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

Но вернемся назад: как враги видят или слышат игрока? Это огромный кусок логики в DOOM, связанный с левел-дизайном. А также один из самых интересных аспектов оптимизации игры. В предыдущих разборах про The Last of Us, Splinter Cell и Alien: Isolation, мы рассказывали о том, как конусы зрения используются для обзора врагов. DOOM появился еще до этого, но он выходил на PC в 90-х, и в нем довольно часто одновременно осматриваются десятки противников. Даже если все они находятся в состоянии SPAWN, каждый вызывает функцию Look() в кодовой базе 35 раз в секунду. Поэтому она должна не только эффективно работать, но и быть оптимизированной.

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

Как сделать, чтобы враг видел игрока и перемещался к нему с наименьшими затратами на просчет пути? Дело в том, что DOOM разбит на фрагменты-секторы с помощью алгоритма двоичного разбиения пространства (BSP, binary space partitioning algorithm). Он позволяет организовать объекты, чтобы те сохраняли пространственную информацию. Так рендерер всегда знает, какие части игровой карты ему нужно отрисовать, отрисовывая только нужный сектор и все примыкающие. Эту оптимизацию добавил Джон Кармак, чтобы повысить производительность рендеринга и не пытаться отрисовать весь уровень.

С ИИ примерно та же история. Карта разбита на секторы, поэтому вы можете записать информацию о том, видит ли один персонаж другого, основываясь на их местоположении. Видимость между секторами в DOOM вычисляется заранее с помощью таблицы REJECT.  При помощи нее мы можем сказать, видит ли персонаж из одного сектора персонажа в другом секторе.

Пример на картинке ниже. Персонаж в секторе A не увидит никого в секторах C и D, но теоретически может заметить в секторе B. Когда они ищут игрока, происходит проверка по таблице REJECT, чтобы понять, а нужно ли вообще проводить проверку видимости.

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

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

Звук

Если враг увидит игрока, он атакует. А что если игрок забегает в комнату и просто стреляет из дробовика? Демоны должны среагировать на шум.

Вот в чем забавная штука. Да, враги в DOOM слышат вас, но не так, как вы думаете. Можно сказать, что они ВИДЯТ звук, так как в функции Look() буквально задается «звуковая цель».

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

Хороший пример: Deimos Lab (E2M4), где вход примыкает к длинному коридору сбоку. Когда игрок убьет всех Импов и Зомби-сержантов у входа, на него вскоре нападут Импы, которые слышали бой за сотни метров.

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

Вражда между противниками

В DOOM демоны могут сражаться друг с другом. Для этого в коде есть такая логика: если NPC атакован и ранен другим персонажем, то он может назначить этого персонажа своей целью (даже если это не игрок). То есть демоны не будут нападать друг на друга без причины, нужно заманить одного врага на линию огня другого и надеяться на френдлифаер.

Есть и исключения: Бароны и Рыцари Ада не могут ранить друг друга, Элементали боли технически не могут быть втянуты в такие бои, потому что извергают Потерянные души (которые затем становятся целью), а Архивиля не могут атаковать в принципе.

Дизайн энкаунтеров

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

Первый прием. В игре есть различные пользовательские действия, которые можно синхронизировать с картой. Если вы когда-нибудь открывали карту, то заметили множество линий: некоторые из них это реальная геометрия, другие — триггеры (игра может определить, когда игрок пересекает нужную часть). Редактор уровней DOOM позволяет выполнять фрагменты кода при входе в нужную часть уровня и добавлять тег, указывающий, какие части карты должны быть затронуты. Так можно устроить засаду — поставить потайную дверь и спрятать несколько врагов, которые находятся в состоянии SPAWN и не слышат никаких звуков.

Однако каждый триггер может иметь только одну функцию, указывающую на один объект. Что делать, чтобы одновременно произошло два события? Отличный пример — ловушка с синим ключом на Toxin Refinery (E1M3). Вы входите в помещение, чтобы взять ключ, но тут же гаснет свет и открывается потайная дверь с Импами внутри. Здесь размещаются два триггера рядом друг с другом, нацеленные на разные объекты. 

В игре более 130 таких функций: открытие и закрытие дверей, поднятие или опускание пола, запирание двери, изменение уровня освещения, телепортация игрока и так далее. 

Другой пример — Military Base, секретный уровень в первом эпизоде DOOM. Там можно стриггерить ловушку, схватив ракетную установку на вершине пентаграммы. Когда игрок переходит через пентаграмму, это не меняет комнату, а убирает небольшую стену, которая защищала телепортатор в маленькой комнате. 

​​

Враги внутри уже активны, им остается зайти в телепорт и оказаться около игрока. Хитрость в том, что есть небольшой незаметный коридор, который соединяет основную комнату с потайной. Именно по нему проходит звук и триггерит демонов, которые затем идут к телепортатору. Такая «звуковая труба» часто встречается в WAD-файлах DOOM и DOOM II.

Второй прием. Существует флаг засады MF_AMBUSH, который устанавливает дополнительную логику к состоянию SEE. Как упоминалось ранее, если демон видит игрока или слышит выстрел, то он принимает это за цель и движется к ней. MF_AMBUSH изменяет логику, чтобы демон игнорировал шум и ждал визуального подтверждения. То есть противник активен, но неподвижен.

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

Отличный пример — Containment Area, вторая миссия игры The Shores of Hell. Многие Импы на этом уровне используют флаг засады, то есть даже когда вы убиваете кого-то рядом с ними, они все равно ждут прямой видимости с игроком.

Вместо заключения

DOOM исполнилось почти 30 лет, а он все еще влияет на индустрию. Игру продолжают портировать практически на все устройства — исходный код находится в открытом доступе уже более 20 лет.

Исходный код движка DOOM на GitHub

Книга Фабиана Сангларда Game Engine Black Book DOOM