Игровой ИИ. GOAP

В прошлый раз мы закончили с ИИ, основанным на полезности (utilityAI), и сегодня мы начинаем обсуждать новый тип игрового ИИ Goal Oriented Action Planning (GOAP).Также не забывайте подписываться на мой канал, чтобы не пропустить следующие части.

Планирование

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

Состояние Мира

Главным и важным компонентом GOAP является структурированное состояние мира. Наши предыдущие системы ИИ тоже анализировали что происходило в мире (где противник, ранен ли агент, видна ли текущая цель). В случае GOAP состояние мира является не абстрактной концепцией информации, необходимой для работы ИИ, а полноценным объектом в памяти, содержащим информацию о мире в понятном остальному алгоритму формате.

class GOAPWorldState

{

bool bPlayerDead = false;

int AliveAICount = 3;

bool AIHasWeapon = true;

int AmmoAmountInWeapon = 0;

};

Конечно же в реальных системах состояние мира использует контейнеры для записи информации, а не поля, по аналогии с Blackboard. Важно заметить, что состояние мира удобно сделать уникальным для каждого агента. Да, какие-то значения будут одинаковыми (например состояние Игрока) для всех агентов, но часть информации будет иметь смысл относительно конкретного ИИ агента. Такой подход связан с тем, что GOAP перекочевал в геймдев из робототехники, и там схожие алгоритмы работают непосредственно на агенте, который и будет выполнять план, поэтому все остальные агенты как бы не являются ИИ для робота, а являются внешними факторами состояния мира. В геймдеве же очевидно, что планирование и выполнение планов для всех агентов происходит внутри одной программы, а чаще всего внутри одной системы. Поэтому это порождает создание индивидуальных состояний мира для каждого агента, который хочет использовать GOAP.

Цель (Goal)

Цель в GOAP описывается тоже с помощью состояния мира: это набор нескольких полей из состояния мира, значения которых зафиксированы. Например целью может быть поднять предмет, т.е. флаг bHasItem в состоянии мира агента должен иметь значение true. Кроме того у каждой цели есть приоритет или полезность этой цели, т.е. цифровое представление того, насколько эта цель сейчас актуальна для игрока. В роли такого представления могут выступать функции полезности из UtilityBasedAI. В GOAP вместо выбора поведения агент выбирает цель, но для выбора используются аналогичные подходы и алгоритмы как в UtilityBasedAI.

Действия (Action)

Действия в GOAP - это маленькие простые поведения. Чаще всего это комбинации перемещения и либо совершения каких-то действий самим агентом (атака, кувырок, использование способности), либо взаимодействие с каким-то объектом в игровом мире (открыть дверь, поднять оружие, включить тревогу). Кроме самой реализации у действий есть несколько характеристик, необходимых для работы в GOAP.

Первая характеристика - это то, как это действие меняет состояние мира. Чаще всего эта характеристика описывается схожа с целями: это набор полей со значениями из состояния мира, обозначающие изменение состояния мира при выполнении этого действия. Например действие “открыть дверь” описывается полем DoorState = Open.

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

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

Smart Objects

В GOAP используется очень удобная концепция умных объектов(smart objects). В игровом ИИ агентам очень часто приходится взаимодействовать с интерактивными объектами в мире - это могут быть кнопки, двери и т.д. Планы и действия в  GOAP чаще всего не привязаны к конкретному агенту или объекту, действие может быть абстрактным (например подойти и провзаимодействовать с предметом). Поэтому необходим ассет, в котором будет храниться информация о том, как взаимодействовать с предметом (например какую анимацию проигрывать), состояние объекта (дверь открыта или закрыта) и т.д. Роль такого асета выполняют умные объекты. Умные объекты представляют собой структуру, в которой хранится вся информация, необходимая ИИ для взаимодействия с нею. Умные объекты чаще всего содержат в себе простой конечный аппарат (FSM) для описания своего состояния и для проигрывания анимаций и эффектов, связанных с взаимодействием с ним (например анимация открытия двери). В большинстве реализаций также существует удобный интерфейс для получения списка умных объектов в заданном расстоянии или на уровне.

Подход умных объектов позволяет легко добавлять новые сущности в геймплей, не меняя ИИ и не исправляя уже существующие объекты. N.B. умные объекты используются не только в GOAP, но и в других системах принятие решения, а также в других игровых системах: например взаимодействия игрока с объектами на карте.

План

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

Построение плана

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

Давайте рассмотрим пример. У нас существует агент со следующими целями

Также у нашего агента есть набор действия

Давайте наш агент выберет цель Атаковать Врага, и у него на старте есть оружие ближнего боя.

На первом шаге наш граф поиска плана выглядит следующим образом

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

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

Теперь наш план состоит из 3 действий: найти оружие дальнего боя, подойти на расстояние выстрела, и атаковать.
Этот пример хорошо демонстрирует как из простых настроек и действий, генерируется логичное и “умное” поведение.

В следующий раз мы обсудим некоторые особенности работы с GOAP.