Продолжаю мой цикл про игровой ИИ. В предыдущей части мы закончили с FSM. В этой части мы поговорим про Дерево поведения (Behavior Tree). Также не забывайте подписываться на мой канал, чтобы не пропустить следующие части.

Дерево Поведения

В прошлый раз мы разобрали Конечный автомат, и выделили основной его минус: быстрый рост сложности графа при росте количества состояний. И если с точки зрения проектирования и разработки эту проблему частично можно решить используя иерархический конечный автомат, то производительность всегда будет страдать при росте числа состояний. Дерево поведения (Behavior Tree или BT) является попыткой решить эту проблему.

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

Из данного определения можно выделить несколько особенностей:

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

Выбран (Selected) - мы активно проверяем поддерево растущее из этого узла, либо сам этот узел.
Выполнятся (Running) - этот узел активно выполняется:например персонаж куда-то идет или совершает действие.
Провал (Failed) - этот узел не доступен для текущего состояния ИИ или игры и не может выполниться. Например: попытка дойти до цели, до которой нет пути, или стрельба из разряженного оружия
Успех (Complete) - этот узел закончил выполнения и завершил свое действие. Например: персонаж закончил следование по маршруту, или завершил атаку.
Ошибка (Error) - попытка проверки этого узла вызвала состояние, несовместимое с обычным условием обхода дерева. Например: у дерева нет агента, который будет совершать действие. Этот статус существует не во всех реализациях Behavior Tree, его основное отличие от статуса Провала в том, что статус Провала ожидаемый (у нас могут кончиться патроны во время стрельбы, но не может исчезнуть оружие).

Пример логики обхода простого Behavior Tree. Желтый цвет выбранный узел, Красный узел вернул статус ошибки, Синий узел выполняется, зеленый узел вернул статус успеха.

Некоторые действия и узлы могут быть в состоянии “Выполнятся”, т.е. во время обхода дерева мы можем найти узел, который сразу не может ответить стоит ли нам продолжать обход. В таком случае мы останавливаем текущий обход. Возникает вопрос: в следующий тик ИИ захотим ли мы продолжить обход дерева и откуда нам его начинать? Существует два ответа на этот вопрос..

Первый способ: мы начинаем обход дерева с начала, и если более ранние узлы решат перейти в статус “Выполняется”, мы прерываем текущее поведение. Если же таких узлов нет - мы доходим до узла, на котором остановились в прошлый кадр, и опрашиваем его снова.

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

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

N.B. Наличие статуса “Выполняется” это как раз то, что отличает дерево поведения (Behavior Tree) от дерева решений (Decision trees) - последнее принимает решения, но не отвечает за выполнения поведения. (Подробно расписанное отличие вот тут https://gamedev.stackexchange.com/questions/51693/difference-between-decision-trees-behavior-trees-for-game-ai)

Виды узлов

Узел Действия

Узел Действия является конечным узлом, не содержит потомков, представляет собой некоторое действие или атомарное поведение, которое необходимо совершить Агенту. Кроме статусов “Успех” или “Неудача” может возвращать статус “Выполняется”, так как большинство действий Агента требуют времени, и их статус может быть непонятен в момент обхода дерева. К таким узлам также относятся узлы, которые совершают действия исключительно внутри ИИ (например записывают что-то в память или находят подходящую цель для действия). В этих случаях статус “Выполняется” чаще всего не используется, так как статус таких действий можно определить сразу.

Управляющий узел

Управляющий узел - это узел, который контролирует правила обхода дерева, но не содержит в себе какого-то действия или поведения. Его статусы чаще всего собираются из статусов растущего из него поддерева в зависимости от конкретного типа узла. Чаще всего, если кто-то в поддереве находится в статусе “Выполняется”, то контролирующий узел возвращает такой статус.

В большинстве реализаций дерево поведения содержит следующие управляющие узлы:

Селектор (Selector)

Это управляющий узел, который последовательно опрашивает узлы-потомки, и если хотя бы один из них возвращает статус “Успех”, то такой же статус возвращает и Селектор. Если же все потомки вернули статус “Неудача”, то и селектор возвращает “Неудачу”.

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

Последовательность (Sequence)

Это управляющий узел, который последовательно опрашивает узлы-потомки, и если один из них возвращает статус “Неудача”,то вся последовательность возвращает “Неудачу”. Если же все узлы вернули “Успех”, то и последовательность возвращает “Успех.

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

Параллельный узел (Parallel)

Этот управляющий узел параллельно запускает своих потомков. Статусы и условия выполнения могут отличаться от реализации и настроек. Например в Unreal Engine 5 существует реализация Simple Parallel, в котором успех или неудача определяется левым узлом, а продолжительность выполнения определяется в зависимости от настройки либо обоими узлами, либо основным. Также в данной реализации после завершения правого узла мы его перезапускаем и перезапускаем обход по нему. Но это исключительно пример реализации, почти любой подход можно реализовать для параллельных узлов и найти для него применения.

Пример параллельного узла, пока мы двигаемся к локации раз в пять секунд стрелять из оружия

Активный Селектор (Active Selector)

Активный селектор - это разновидность селектора, способного прерывать потомка, который находится в статусе “Выполняется”, если более приоритетное поведение стало доступным. Активный селектор - одна из реализаций старта обхода с начала, о котором говорилось ранее. Он встречается не во всех версиях Behavior Tree, например в Unreal Engine 5 вместо Активного Селектора используются декораторы с прерыванием (О декораторах я расскажу подробно в следующей части).

Корневой узел.

Корневой узел является корнем дерева, с которого мы совершаем обход, это всегда управляющий узел, его тип определяется исключительно реализацией: это может быть селектор, это может быть последовательность, а может быть особый управляющий узел только с одним потомком, как в Unreal Engine 5.

В следующий раз я расскажу про то как в дереве поведения организована память (Blackboard) и про способы изменения обхода деревьев в зависимости от условий и состоянии ИИ (Decorator и Services).