摘要：另外，當并行器滿足條件提前退出時，所有正在執行的子行為也應該立即被終止，我們在函數中調用每個子節點的終止方法監視器監視器是并行器的應用之一，通過在行為運行過程中不斷檢查是否滿足某條件，如果不滿足則立刻退出。將條件放在并行器的尾部即可。

從上古卷軸中形形色色的人物，到NBA2K中揮灑汗水的球員，從使命召喚中詭計多端的敵人，到刺客信條中栩栩如生的人群。游戲AI幾乎存在于游戲中的每個角落，默默構建出一個令人神往的龐大游戲世界。
那么這些復雜的AI又是怎么實現的呢？下面就讓我們來了解并親手實現一下游戲AI基礎架構之一的行為樹。

行為樹是一種樹狀的數據結構，樹上的每一個節點都是一個行為。每次調用會從根節點開始遍歷，通過檢查行為的執行狀態來執行不同的節點。他的優點是耦合度低擴展性強，每個行為可以與其他行為完全獨立。目前的行為樹已經可以將幾乎任意架構（如規劃器，效用論等）應用于AI之上。

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）是行為樹最基礎的概念，是幾乎所有行為樹節點的基類，是一個抽象接口，而如動作條件等節點則是它的具體實現。
下面是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接口是所有行為樹節點的核心，且我規定所有節點的構造和析構方法都必須是protected，以防止在棧上創建對象，所有的節點對象通過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來標識條件是否取反（比如是否看見敵人可以變為是否沒有看見敵人）

裝飾器（Decorator）是只有一個子節點的行為，顧名思義，裝飾即是在子節點的原有邏輯上增添細節(如重復執行子節點，改變子節點返回狀態等)

//裝飾器
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;
    Behaviors Childern;
};

順序器(Sequence)是復合節點的一種，它依次執行每個子行為，直到所有子行為執行成功或者有一個失敗為止。

//順序器：依次執行所有節點直到其中一個失敗或者全部成功位置
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;  //循環意外終止
}

選擇器（Selector）是另一種常用的復合行為，它會依次執行每個子行為直到其中一個成功執行或者全部失敗為止

由于與順序器僅僅是Update函數不同,下面僅貼出Update方法

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,
};

update函數實現如下

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 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地址