Игровой ИИ. FSM.
Продолжаю мой цикл про игровой ИИ. В первой части были расписаны общие понятия для игровых ИИ, и описаны условия для абстрактной модели поведения. В этой части мы обсудим Finite state machine и попробуем расписать ИИ для простого NPC из Doom 2016. Также не забывайте подписываться на мой канал, чтобы не пропустить следующие части.
Конечный автомат
Finite state machine он же (Конечный автомат) одна из самых популярных моделей, используемых в геймдеве. Она встречается почти в любой области геймдева: анимационные системы, VFX, ИИ, рендер, сетевые репликации и т.д.
Конечный автомат представляет собой некую абстрактную модель устройства с сигналом на входе и сигналом на выходе, который в каждый момент времени находится в одном из конечного числа возможных состояний. При этом также определены условия (или функции) переходов между этими состояниями.
Детерминированный конечный автомат(ДКА) - это такой автомат, у которого из одного состояния по определенному сигналу возможен переход только в одно состояние. Такие автоматы встречаются чаще всего в геймдеве.
Недетерминированные конечный автомат(НКА) - автомат, у которого переход из одного состояние в другое определен не единственным образом. Такие автоматы могут находиться в нескольких состояниях одновременно. Любой НКА можно преобразовать в ДКА, но такие преобразования могут вызвать взрывной рост количества состояний ДКА.
Стоит отметить, что переходы между состояниями могут происходить не только по внешним сигналам, но и самопроизвольно.
Визуально представлять конечный автомат принято с помощью ориентированного графа, где вершины графа - это состояния автомата, дуги - переходы из одного состояние в другое, метки на дугах - входные сигналы, по которым происходит переход.
Как можно переложить абстрактную модель на задачи и логику геймдева, в частности для описания поведения ИИ? Один из вариантов - это представить, что входными сигналами могут выступать настройки ИИ, состояние мира, состояние пешки (не путать с состоянием самого автомата, который является внутренней частью автомата и не является входным сигналом). Выходным сигналом будет являться поведение ИИ.
Переход автомата между состояниями соответствует принятию решения ИИ. Как говорилось выше, такое решение может происходить самопроизвольно (например текущие состояние ИИ закончилось), либо как реакция на входной сигнал (например состояние пешки изменилось, и текущее поведение не актуально). Состояния в такой модели будут тождественны поведению. Получившаяся модель отлично позволяет реализовать высокоуровневый ИИ.
Такой подход позволяет реализовать логику принятия решения, но возможно продолжить этот подход для реализации конкретного поведения. Представим, что входные сигналы будут являться объектами, целями данного поведения, настройками ИИ и инструментами, с помощью которых можно выполнить это поведение. Выходными сигналами будут выступать действия или игровые события, имеющие геймплейный смысл. Переходы автомата будут реализовывать правила окончания конкретных действий или событий. Получившаяся модель отлично позволяет реализовать средний уровень ИИ: последовательности действий которые будет совершать ИИ.
Тестовый ИИ
Для того, чтобы проще воспринимать абстрактную модель, применим ее для уже существующего ИИ, реализованного и доступного для примера. Возьмем противника Imp из Doom 2016.
- Бездействовать (Idle): NPC просто стоит на месте или проигрывает набор анимаций (анимации могут быть парными, если рядом есть другой NPC)
- Бродить по локации(Wander): NPC перемещается в рандомной области или по определенному маршруту
- Атаковать в ближнем бою (Melee): NPC атакует игрока с помощью атаки ближнего боя
- Запрыгивать на стены (Jump): NPC находит вертикальную поверхность, на которую запрыгивает.
- Атаковать в дальнем бою (Range Attack): NPC атакует игрока с помощью нескольких маленьких огненных шаров или с помощью одного большого, который требует времени на подготовку.
- Проигрывать анимацию получения урона (Hit Reaction): NPC при критическом уроне стоит несколько секунд, позволяя игроку совершить добивание
- Искать игрока, если он скрылся из зоны видимости (Search): NPC старается занять такую позицию, из которой возможно атаковать игрока
- Проигрывать анимацию смерти (Death): NPC мертв и ни на что не реагирует, находясь в анимации смерти
- Участвовать в добивании (Finisher): NPC проигрывает анимацию жертвы добивания, если игрок применил добивание к нему.
- Проигрывать агрессивное бездействие (Aggressive Idle): NPC проигрывает особые анимации, если игрок погиб, если игрок проигрывает финишер, или если все атаки недоступны (например, они откатываются)
Как говорилось раньше, поведенческая модель должна быть достаточно абстрактной, чтобы не знать о пешке и о том, как она выполняет конкретные действия или поведения. Но при этом она, очевидно, должна соответствовать дизайну и возможностям пешки, которой она управляет.
Простая FSM
Как будет выглядеть высокоуровневый конечный автомат, описывающий поведение Imp? Для начала необходимо выделить, что является поведениями для нашего NPC. Самым простым и высокоуровневым конечным автоматом, описывающим наш NPC, будет следующий пример:
В данном автомате присутствуют всего 3 состояния: состояние покоя, состояние боя и состояние смерти. Условиями перехода из состояния покоя в состояние боя будет сигнал от системы рецепторов о том, что пешка заметила игрока. Условием перехода из состояния смерти будет сигнал от пешки о том, что ее состояние изменилось на мертвый. Такой автомат конечно же описывает некое поведение, и его можно использовать в некоторых играх. Если же состояния сами по себе описывают все условия использования атак и действий, доступных тестовому NPC (что абсолютно валидный подход, но о нем чуть позже), то этот автомат вполне можно использовать в игре.
Добавив несколько дополнительных состояний мы получим менее абстрактный автомат, который наглядно описывает логику принятия решений конкретного NPC.
В данном автомате видно, что рост числа состояний привел к заметному увеличению количества переходов, причем некоторые переходы (например все переходы в состояние Death) обладают одинаковыми условиями. Даже для такой простой модели во время боя для каждого состояния нам надо проверять в среднем около 3 условий перехода. При попытке добавить еще состояния вырастет и количество проверок. Поэтому уже можно выделить первый недостаток простых конечных автоматов: с ростом количества состояний в игровых ИИ будет расти количество переходов и условий переходов. Это ставит разработчика перед выбором - либо страдает производительность (мы обрабатываем каждый переход каждый логический промежуток времени и сильно ограничиваем количество NPC), либо страдает отзывчивость (мы обрабатываем только несколько переходов за один промежуток времени и, тем самым, принятие решений будет занимать дольше времени).
Так как большинство современных движков позволяет работать с конечным автоматом с помощью редактора графов, существует одна удобная особенность, реализованная почти во всех редакторах - Any state (Любой состояние). Это абстрактное состояние, которое является ссылкой на любое состояние и позволяет создавать общие исходящие переходы в одно состояние (например переходы в состояние Death). Используя такое состояние, можно упросить отображение нашего графа, но это не решит проблему количества переходов..
В следующий раз я расскажу про HSM (иерархический конечный автомат) - модель, которая получается, если поместить конечный автомат в состояния другого конечного автомата.