Игровой ИИ — исследование и внедрение дерева поведения

машинное обучение

От ярких персонажей The Elder Scrolls до потных игроков в NBA 2K, от коварных врагов в Call of Duty и реалистичных толп в Assassin's Creed. Игровой ИИ существует почти в каждом уголке игры, бесшумно создавая огромный и увлекательный игровой мир. Так как же реализуются эти сложные ИИ? Давайте рассмотрим и реализуем дерево поведения, одну из игровых инфраструктур искусственного интеллекта.

Введение в деревья поведения

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

class BehaviorTree
{
public:
    BehaviorTree(Behavior* InRoot) { Root = InRoot; }
    void Tick()
    {
       Root->Tick();
    }
    bool HaveRoot() { return Root?true:false; }
    void SetRoot(Behavior* InNode) { Root= InNode; }
    void Release() { Root->Release(); }
private:
    Behavior* Root;
};

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

поведение

Поведение — это самая основная концепция дерева поведения.Это базовый класс почти всех узлов дерева поведения.Это абстрактный интерфейс, а такие узлы, как условия действия, являются его конкретной реализацией. Ниже приведена реализация Behavior, без некоторых простых методов оценки состояния Полный исходный код можно найти по ссылке на github в конце текста.

class Behavior
{
public:
    //释放对象所占资源
    virtual void Release() = 0;
    //包装函数，防止打破调用契约
    EStatus Tick();

    EStatus GetStatus() { return Status; }
    virtual void AddChild(Behavior* Child){};
    
protected:
    //创建对象请调用Create()释放对象请调用Release()
    Behavior():Status(EStatus::Invalid){}
    virtual ~Behavior() {}
    virtual void OnInitialize() {};
    virtual EStatus Update() = 0;
    virtual void OnTerminate(EStatus Status) {};

protected:
    EStatus Status;
};

Интерфейс Behavior является ядром всех узлов дерева поведения., и я утверждаю, что методы построения и деструктора всех узлов должны быть защищены, чтобы предотвратить создание объектов в стеке.Все объекты узлов создаются в куче с помощью статического метода Create() и уничтожаются с помощью метода Release()., так как Behavior является абстрактным интерфейсом, он не предоставляет метод Create(). Этот интерфейс удовлетворяет следующему контракту

  • Перед первым вызовом метода Update один раз вызывается функция OnInitialize, отвечающая за инициализацию и другие операции
  • Метод Update() вызывается каждый раз при обновлении дерева поведения и только один раз.
  • Когда поведение больше не находится в рабочем состоянии, вызовите OnTerminate() один раз и выполните другую логику в зависимости от состояния возврата.

Чтобы убедиться, что контракт не нарушен, мы оборачиваем эти три метода в метод Tick(). Tick() реализован следующим образом

//update方法被首次调用前执行OnInitlize方法，每次行为树更新时调用一次update方法
    //当刚刚更新的行为不再运行时调用OnTerminate方法
    if (Status != EStatus::Running)
    {
        OnInitialize();
    }

    Status = Update();
    
    if (Status != EStatus::Running)
    {
        OnTerminate(Status);
    }

    return Status;

Возвращаемое значение Estatus — это значение перечисления, указывающее рабочее состояние узла.

enum class EStatus:uint8_t
{
    Invalid,   //初始状态
    Success,   //成功
    Failure,   //失败
    Running,   //运行
    Aborted,   //终止
};

Действие

Действие — это листовой узел дерева поведения, который представляет конкретную операцию, выполняемую персонажем (такую ​​как атака, отскок, защита и т. д.), и отвечает за изменение состояния игрового мира. Узлы действий могут напрямую наследоваться от узлов Behavior и реализовывать другую логику, реализуя разные методы Update(), получать данные и ресурсы в методе OnInitialize() и освобождать ресурсы в OnTerminate.

//动作基类
class Action :public Behavior
{
public:
    virtual void Release() { delete this; }

protected:
    Action() {}
    virtual ~Action() {}
};

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

состояние

Условие также является конечным узлом дерева поведения, которое используется для проверки информации об игровом мире (например, находится ли враг в пределах досягаемости, есть ли вокруг объекты, на которые можно взобраться, и т. д.), и успешности условия. обозначается статусом возврата.

//条件基类
class Condition :public Behavior
{
public:
    virtual void Release() { delete this; }

protected:
    Condition(bool InIsNegation):IsNegation(InIsNegation) {}
    virtual ~Condition() {}

protected:
    //是否取反
    bool  IsNegation=false;
};

Здесь я реализовал базовый класс условия, IsNegation, чтобы определить, является ли условие обратным (например, если враг виден, можно изменить на то, что враг не виден).

Декоратор

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

//装饰器
class Decorator :public Behavior
{
public:
    virtual void AddChild(Behavior* InChild) { Child=InChild; }
protected:
    Decorator() {}
    virtual ~Decorator(){}
    Behavior* Child;
};

Реализован базовый класс декоратора, давайте реализуем конкретный декоратор, то есть декоратор, который повторяет несколько дочерних узлов, упомянутых выше.

class Repeat :public Decorator
{
public:
    static Behavior* Create(int InLimited) { return new Repeat(InLimited); }
    virtual void Release() { Child->Release(); delete this; }
protected:
    Repeat(int InLimited) :Limited(InLimited) {}
    virtual ~Repeat(){}
    virtual void OnInitialize() { Count = 0; }
    virtual EStatus Update()override;
    virtual Behavior* Create() { return nullptr; }
protected:
    int Limited = 3;
    int Count = 0;
};

Как упоминалось выше, функция Create отвечает за создание узлов, а Release отвечает за освобождение метода Update() следующим образом.

EStatus Repeat::Update()
{
    while (true)
    {
        Child->Tick();
        if (Child->IsRunning())return EStatus::Success;
        if (Child->IsFailuer())return EStatus::Failure;
        if (++Count == Limited)return EStatus::Success;
        Child->Reset();
    }
    return EStatus::Invalid;
}

Логика очень проста, если выполнение не удалось, он немедленно вернется, продолжит выполнение во время выполнения и повторит счетчик + 1, если выполнение успешно.

составное поведение

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

//复合节点基类
class Composite:public Behavior
{  
    virtual void AddChild(Behavior* InChild) override{Childern.push_back(InChild);}
    void RemoveChild(Behavior* InChild);
    void ClearChild() { Childern.clear(); }
    virtual void Release()
    {
        for (auto it : Childern)
        {
            it->Release();
        }

        delete this;
    }

protected:
    Composite() {}
    virtual ~Composite() {}
    using Behaviors = std::vector<Behavior*>;
    Behaviors Childern;
};

Секвенсор

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

//顺序器：依次执行所有节点直到其中一个失败或者全部成功位置
class Sequence :public Composite
{
public:
    virtual std::string Name() override { return "Sequence"; }
    static Behavior* Create() { return new Sequence(); }
protected:
    Sequence() {}
    virtual ~Sequence(){}
    virtual void OnInitialize() override { CurrChild = Childern.begin();}
    virtual EStatus Update() override;

protected:
    Behaviors::iterator CurrChild;
};

Реализация метода Update() выглядит следующим образом.

EStatus Sequence::Update()
{
    while (true)
    {
        EStatus s = (*CurrChild)->Tick();
        //如果执行成功了就继续执行，否则返回
        if (s != EStatus::Success)
            return s;
        if (++CurrChild == Childern.end())
            return EStatus::Success;
    }
    return EStatus::Invalid;  //循环意外终止
}

Селектор

Селектор — это еще одно часто используемое составное поведение, которое выполняет каждое подповедение по очереди до тех пор, пока одно из них не завершится успешно или все не завершатся ошибкой.

Поскольку секвенсор — это просто функция обновления, ниже публикуется только метод обновления.

EStatus Selector::Update()
{
    while (true)
    {
        EStatus s = (*CurrChild)->Tick();
        if (s != EStatus::Failure)
            return s;    
        //如果执行失败了就继续执行，否则返回
        if (++CurrChild == Childern.end())
            return EStatus::Failure;
    }
    return EStatus::Invalid;  //循环意外终止
}

Параллельно

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

//并行器：多个行为并行执行
class Parallel :public Composite
{
public:
    static Behavior* Create(EPolicy InSucess, EPolicy InFailure){return new Parallel(InSucess, InFailure); }
    virtual std::string Name() override { return "Parallel"; }

protected:
    Parallel(EPolicy InSucess, EPolicy InFailure) :SucessPolicy(InSucess), FailurePolicy(InFailure) {}
    virtual ~Parallel() {}
    virtual EStatus Update() override;
    virtual void OnTerminate(EStatus InStatus) override;

protected:
    EPolicy SucessPolicy;
    EPolicy FailurePolicy;
};

Здесь Epolicy — тип перечисления, представляющий условия успеха и неудачи (это успех или неудача, один или все успехи или неудачи)

//Parallel节点成功与失败的要求，是全部成功/失败，还是一个成功/失败
enum class EPolicy :uint8_t
{
    RequireOne,
    RequireAll,
};

Функция обновления реализована следующим образом


EStatus Parallel::Update()
{
    int SuccessCount = 0, FailureCount = 0;
    int ChildernSize = Childern.size();
    for (auto it : Childern)
    {
        if (!it->IsTerminate())
            it->Tick();

        if (it->IsSuccess())
        {
            ++SuccessCount;
            if (SucessPolicy == EPolicy::RequireOne)
            {
                it->Reset();
                return EStatus::Success;
            }
                
        }

        if (it->IsFailuer())
        {
            ++FailureCount;
            if (FailurePolicy == EPolicy::RequireOne)
            {
                it->Reset();
                return EStatus::Failure;
            }        
        }
    }

    if (FailurePolicy == EPolicy::RequireAll&&FailureCount == ChildernSize)
    {
        for (auto it : Childern)
        {
            it->Reset();
        }
        
        return EStatus::Failure;
    }
    if (SucessPolicy == EPolicy::RequireAll&&SuccessCount == ChildernSize)
    {
        for (auto it : Childern)
        {
            it->Reset();
        }
        return EStatus::Success;
    }

    return EStatus::Running;
}

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

void Parallel::OnTerminate(EStatus InStatus)
{
     for (auto it : Childern)
    {
        if (it->IsRunning())
            it->Abort();
    }
}

Монитор

Монитор — это одно из приложений параллелизатора, постоянно проверяющее, выполняется ли определенное условие во время текущего процесса поведения, и немедленно закрывающееся, если оно не выполняется. Просто поместите условие в конец параллелизатора.

Активный селектор

Активные селекторы – это разновидность селекторов. В отличие от обычных селекторов, активные селекторы активно проверяют принятые решения и постоянно проверяют осуществимость действий с высоким приоритетом. Когда это возможно, Ху немедленно прерывает выполнение действий с низким приоритетом ( например, если во время патрулирования будет обнаружен враг, патрулирование будет немедленно прервано, и противник будет немедленно атакован). Его метод Update() и метод OnInitialize реализованы следующим образом.

//初始化时将CurrChild初始化为子节点的末尾
virtual void OnInitialize() override { CurrChild = Childern.end(); }

    EStatus ActiveSelector::Update()
    {
        //每次执行前先保存的当前节点
        Behaviors::iterator Previous = CurrChild;
        //调用父类OnInlitiallize函数让选择器每次重新选取节点
        Selector::OnInitialize();
        EStatus result = Selector::Update();
        //如果优先级更高的节点成功执行或者原节点执行失败则终止当前节点的执行
        if (Previous != Childern.end()&CurrChild != Previous)
        {
            (*Previous)->Abort();    
        }

        return result;
    }

Пример

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

//构建行为树：角色一开始处于巡逻状态，一旦发现敌人，先检查自己生命值是否过低，如果是就逃跑，否则就攻击敌人，攻击过程中如果生命值过低也会中断攻击，立即逃跑，如果敌人死亡则立即停止攻击
    BehaviorTreeBuilder* Builder = new BehaviorTreeBuilder();
    BehaviorTree* Bt=Builder
        ->ActiveSelector()
            ->Sequence()
                ->Condition(EConditionMode::IsSeeEnemy,false)
                     ->Back()       
                ->ActiveSelector()
                     ->    Sequence()
                          ->Condition(EConditionMode::IsHealthLow,false)
                                  ->Back()
                          ->Action(EActionMode::Runaway)
                                ->Back()
                          ->Back()
                    ->Monitor(EPolicy::RequireAll,EPolicy::RequireOne)
                          ->Condition(EConditionMode::IsEnemyDead,true)
                                ->Back()
                          ->Action(EActionMode::Attack)
                                ->Back()
                          ->Back()
                    ->Back()
                ->Back()
            ->Action(EActionMode::Patrol)
    ->End();

    delete Builder;

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

    //模拟执行行为树
    for (int i = 0; i < 10; ++i)
    {
        Bt->Tick();
        std::cout << std::endl;
    }

Результат выполнения следующий, каждый результат выполнения отличается из-за наличия случайных чисел

Реализация конструктора

Построитель использовался при создании дерева поведения выше, теперь я представлю свою собственную реализацию построителя.

//行为树构建器，用来构建一棵行为树,通过前序遍历方式配合Back()和End()方法进行构建
class BehaviorTreeBuilder
{
public:
    BehaviorTreeBuilder() { }
    ~BehaviorTreeBuilder() { }
    BehaviorTreeBuilder* Sequence();
    BehaviorTreeBuilder* Action(EActionMode ActionModes);
    BehaviorTreeBuilder* Condition(EConditionMode ConditionMode,bool IsNegation);
    BehaviorTreeBuilder* Selector();
    BehaviorTreeBuilder* Repeat(int RepeatNum);
    BehaviorTreeBuilder* ActiveSelector();
    BehaviorTreeBuilder* Filter();
    BehaviorTreeBuilder* Parallel(EPolicy InSucess, EPolicy InFailure);
    BehaviorTreeBuilder* Monitor(EPolicy InSucess, EPolicy InFailure);
    BehaviorTreeBuilder* Back();
    BehaviorTree* End();

private:
    void AddBehavior(Behavior* NewBehavior);

private:
    Behavior* TreeRoot=nullptr;
    //用于存储节点的堆栈
    std::stack<Behavior*> NodeStack;
};

BehaviorTreeBuilder* BehaviorTreeBuilder::Sequence()
{
    Behavior* Sq=Sequence::Create();
    AddBehavior(Sq);
    return this;
}

void BehaviorTreeBuilder::AddBehavior(Behavior* NewBehavior)
{
    assert(NewBehavior);
    //如果没有根节点设置新节点为根节点
    if (!TreeRoot)
    {
        TreeRoot=NewBehavior;
    }
    //否则设置新节点为堆栈顶部节点的子节点
    else
    {
        NodeStack.top()->AddChild(NewBehavior);
    }

    //将新节点压入堆栈
    NodeStack.push(NewBehavior);
}

BehaviorTreeBuilder* BehaviorTreeBuilder::Back()
{
    NodeStack.pop();
    return this;
}

BehaviorTree* BehaviorTreeBuilder::End()
{
    while (!NodeStack.empty())
    {
        NodeStack.pop();
    }
    BehaviorTree* Tmp= new BehaviorTree(TreeRoot);
    TreeRoot = nullptr;
    return Tmp;
}
``
在上面的实现中，我在每个方法里创建对应节点，检测当前是否有根节点，如果没有则将其设为根节点，如果有则将其设为堆栈顶部节点的子节点，随后将其压入堆栈，每次调用back则退栈，每个创建节点的方法都返回this以方便调用下一个方法，最后通过End（）表示行为树创建完成并返回构建好的行为树。

那么上面就是行为树的介绍和实现了，下一篇我们将对行为树进行优化，慢慢进入第二代行为树。
注：由于现在网速太慢，github明日上传
Категории