Игровой ИИ. HSM
Продолжаю мой цикл про игровой ИИ. В первой части были расписаны общие понятия для игровых ИИ, и описаны условия для абстрактной модели поведения. В второй части мы обсудили Finite state machine и попробовали расписать ИИ для простого NPC из Doom 2016.
В этой части мы продолжим знакомство с конечным автоматом, конкретнее иерархическим конечным автоматом. Затем попробуем представить простейшие реализации FSM на с++. Также не забывайте подписываться на мой канал, чтобы не пропустить следующие части.
HSM
Получившийся в прошлой части автомат можно полноценно использовать для ИИ IMP и реализовать большую часть поведения, но добавление еще поведений (а значит состояний) значительно усложнит структуру автомата и повлияет на производительность ИИ. К тому же некоторые решения отданы на реализацию состояниям: например выбор типа дальней атаки или тип небоевого поведения. Такой подход не нарушает тех принципов, которые мы заложили ранее в поведенческую модель, т.к. решение все еще принимает одна система, но, с точки зрения разработки, сложные состояния с условиями и правилами применений могут быть неудобны для реализации.
Взяв за основу конечный автомат, дополним его следующей концепцией: каждое состояние может быть реализовано 2 способами. В первом случае состояние - это обычное состояние автомата, которое может быть тождественно как целому поведению так и простому действию ИИ. Во втором случае состояние является другим конечным автоматом. Причем к этому вложенному автомату применяется то же правило относительно состояний. Получившаяся модель называется Hierarchical State Machine (HSM), или иерархический конечный автомат.
Как будет выглядеть ИИ для Imp описанный с помощью HSM? Первый уровень может быть очень простым, почти как первый автомат, который мы описали для IMP.
Состояния Death и HitReaction будут являться простыми состояниями, которые будут реализовывать простые действия (проиграть заданную в каждом состоянии анимацию). А вот Combat и Idle теперь будут являться конечными автоматами.
Для Idle мы можем собрать простой автомат, который выбирает тип Idle с помощью переходов, условиями которых являются настройки конкретного Imp в игре.
Теперь давайте рассмотрим состояние Combat. Все состояния в данном случае будут являться HSM.
Данный подход позволяет создавать простые переиспользуемые состояния. Пример WanderMove (который описывает простое перемещение к рандомной точке) или MoveTo (который описывает перемещение к заданной точке или цели).
В HSM каждый слой обрабатывается как отдельный автомат. Сначала мы проверяем условия переходов одного состояния, затем переходы состояния, в котором находится вложенная машина, и так до того момента, пока не достигнем состояния, которое не является автоматом. Порядок выполнения проверок (от базового слоя или от самого глубокого слоя) может меняться от реализации к реализации HSM, и особенно не влияет на подход к разработке самих автоматов.
HSM позволяет упростить разработку графов и сократить количество потенциальных багов. Например, автомат в предыдущей секции содержал баг: не был доступен переход из Idle в HitReaction. Как результат - если Imp еще не начал атаку, но уже получил критический урон, вместо того, чтобы перейти в состояние HitReaction, переходил бы сначала в состояние RangeCombat либо MeleeCombat
HSM не уменьшает количество проверок переходов. Например, находясь в состоянии Combat->Ranged мы все равно будем делать 4 проверки условий переходов (две для состояния Combat и две для состояния Ranged). Но HSM позволяет легко приоритизировать - какие проверки совершать чаще, какие - реже, что добавляет простой подход к оптимизации производительности. Например: можно решить, что вложенные состояния отвечают за тонкие действия и сиюминутные решения, поэтому мы будем обрабатывать их каждый кадр, тогда как основной автомат мы можем проверять только каждые 10 кадров, т.к. он отвечает за редкие изменения тактики и поведения.
Является ли HSM все еще детерминированным конечным автоматом или это уже недетерминированный автомат? HSM на мой взгляд все еще является ДКА потому, что не смотря на вложенность в один момент времени в каждой FSM, он может находиться только в одном состоянии. Это состояние является комбинацией всех состояний всех активных FSM, но оно все равно единственное.
Стоит отметить, что подход, который мы использовали для создания FSM с последующим переводом его в HSM, отлично работает на практике. Создавать простейший автомат, затем добавлять новые состояния, посмотреть и проанализировать возможно ли сложить часть автомата в отдельный автомат, и т.д. пока не получим автомат описывающий все поведение NPC.
Состояние и переходы.
Теперь, когда есть некоторое представление о том, как будет выглядеть FSM для нашего IMP, необходимо опуститься на уровень ниже и рассмотреть, как могут быть реализованы состояния и переходы.
Переход представляет из себя объект с двумя ссылками на разные состояния. Первым является состояние, из которого совершается переход. Второе состояние - это цель перехода. Также в переходе должно существовать условие, при выполнении которого должен совершаться переход в целевое состояние. Чаще всего условие реализовано как функция, которая возвращает значение булевого типа, либо как переменная булевого типа, которая изменяется некой логикой. Также, если в движке или в игре существует система событий, имеет смысл изначально задать возможность переходу слушать события и, при получении некоторого события, проставлять в переменную True, чтобы в дальнейшем ИИ совершила переход в новое состояние. Также стоит добавить поле приоритета, чтобы была возможность настроить необходимый переход, если условия для нескольких переходов выполнены одновременно.
struct FSMTransition
{
int32 Priority;
bool bCondition;
public:
FSMTransition() :
Priority(0)
,bCondition(false);
virtual bool DoesTransitionPass() { return bCondition};
FSMState_Base* GetFromState() const { return FromState; }
FSMState_Base* GetToState() const { return ToState; }
void SetFromState(FSMState_Base* State);
void SetToState(FSMState_Base* State);
private:
FSMState_Base* FromState;
FSMState_Base* ToState;
};Пример структуры простейшего перехода
Состояние представляет собой объект с функциями, вызываемыми в момент входа в состояние, выхода из состояния, и функцию тика или обновления, которая вызывается каждый кадр (или каждый раз когда ИИ получает шанс отработать свою логику, если ИИ не обновляется каждый кадр). Кроме того, обычно в состоянии хранятся списки исходящих переходов и иногда ссылки на входящие переходы. Важно понимать, что пока FSM работает, для каждого экземпляра ИИ создается свой экземпляр FSM ( иногда для оптимизации в памяти хранится только активное состояние). Это означает, что состояние может использовать свои поля для выполнения логики поведения, которое описывает. Состоянию нужна внешняя память только для передачи данных между состояниями.
struct FSMState_Base
{
public:
FSMState_Base();
virtual bool StartState();
virtual bool UpdateState(float DeltaSeconds);
virtual bool EndState(float DeltaSeconds,
const FSMTransition* TransitionToTake = nullptr);
private:
const FSMTransition* NextTransition;
TArray<FSMTransition*> IncomingTransitions;
TArray<FSMTransition*> OutgoingTransitions;
};
Пример структуры простейшего состояния
Готовые решения
Реализация полноценной и оптимизированной HSM - это нетривиальная и сложная задача. Поэтому для написания своего ИИ я настоятельно рекомендую пользоваться готовыми решениями. Например для Unreal Engine 5 есть отличный плагин Logic Drive https://logicdriver.com/ , скриншоты из которого использовались в этой статье.
В следующий раз я расскажу про другую популярную модель поведения - Behaviour Tree, или дерево поведения.