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

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

行為樹是一種樹狀的數(shù)據(jù)結(jié)構(gòu)，樹上的每一個節(jié)點都是一個行為。每次調(diào)用會從根節(jié)點開始遍歷，通過檢查行為的執(zhí)行狀態(tài)來執(zhí)行不同的節(jié)點。他的優(yōu)點是耦合度低擴展性強，每個行為可以與其他行為完全獨立。目前的行為樹已經(jīng)可以將幾乎任意架構(gòu)（如規(guī)劃器，效用論等）應(yīng)用于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;
};

上面提供了行為樹的實現(xiàn)，行為樹有一個根節(jié)點和一個Tick（）方法，在游戲過程中每個一段時間會調(diào)用依次Tick方法，令行為樹從根節(jié)點開始執(zhí)行。

行為（behavior）是行為樹最基礎(chǔ)的概念，是幾乎所有行為樹節(jié)點的基類，是一個抽象接口，而如動作條件等節(jié)點則是它的具體實現(xiàn)。
下面是Behavior的實現(xiàn)，省略掉了一些簡單的判斷狀態(tài)的方法完整源碼可以參照文尾的github鏈接

class Behavior
{
public:
    //釋放對象所占資源
    virtual void Release() = 0;
    //包裝函數(shù)，防止打破調(diào)用契約
    EStatus Tick();

    EStatus GetStatus() { return Status; }
    virtual void AddChild(Behavior* Child){};
    
protected:
    //創(chuàng)建對象請調(diào)用Create()釋放對象請調(diào)用Release()
    Behavior():Status(EStatus::Invalid){}
    virtual ~Behavior() {}
    virtual void OnInitialize() {};
    virtual EStatus Update() = 0;
    virtual void OnTerminate(EStatus Status) {};

protected:
    EStatus Status;
};

Behavior接口是所有行為樹節(jié)點的核心，且我規(guī)定所有節(jié)點的構(gòu)造和析構(gòu)方法都必須是protected，以防止在棧上創(chuàng)建對象，所有的節(jié)點對象通過Create()靜態(tài)方法在堆上創(chuàng)建，通過Release()方法銷毀，由于Behavior是個抽象接口，故沒有提供Create()方法，本接口滿足如下契約

在Update方法被首次調(diào)用前，調(diào)用一次OnInitialize函數(shù)，負責初始化等操作

Update（）方法在行為樹每次更新時調(diào)用且僅調(diào)用一次。

當行為不再處于運行狀態(tài)時，調(diào)用一次OnTerminate（），并根據(jù)返回狀態(tài)不同執(zhí)行不同的邏輯

為了保證契約不被打破，我們將這三個方法包裝在Tick（）方法里。Tick（）的實現(xiàn)如下

//update方法被首次調(diào)用前執(zhí)行OnInitlize方法，每次行為樹更新時調(diào)用一次update方法
    //當剛剛更新的行為不再運行時調(diào)用OnTerminate方法
    if (Status != EStatus::Running)
    {
        OnInitialize();
    }

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

    return Status;

其中返回值Estatus是一個枚舉值，表示節(jié)點運行狀態(tài)。

enum class EStatus:uint8_t
{
    Invalid,   //初始狀態(tài)
    Success,   //成功
    Failure,   //失敗
    Running,   //運行
    Aborted,   //終止
};

動作是行為樹的葉子節(jié)點，表示角色做的具體操作（如攻擊，上彈，防御等），負責改變游戲世界的狀態(tài)。動作節(jié)點可直接繼承自Behavior節(jié)點，通過實現(xiàn)不同的Update()方法實現(xiàn)不同的邏輯，在OnInitialize（）方法中獲取數(shù)據(jù)和資源，在OnTerminate中釋放資源。

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

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

在這里我實現(xiàn)了一個動作基類，主要是為了一個公用的Release方法負責釋放節(jié)點內(nèi)存空間，所有動作節(jié)點均可繼承自這個方法

條件同樣是行為樹的葉子節(jié)點，用于查看游戲世界信息（如敵人是否在攻擊范圍內(nèi)，周圍是否有可攀爬物體等），通過返回狀態(tài)表示條件的成功。

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

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

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

這里我實現(xiàn)了條件基類，一個IsNegation來標識條件是否取反（比如是否看見敵人可以變?yōu)槭欠駴]有看見敵人）

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

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

實現(xiàn)了裝飾器基類，下面我們來實現(xiàn)下具體的裝飾器，也就是上面提到的重復(fù)執(zhí)行多次子節(jié)點的裝飾器

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函數(shù)負責創(chuàng)建節(jié)點，Release負責釋放
其中Update()方法的實現(xiàn)如下

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

邏輯很簡單，如果執(zhí)行失敗就立即返回，執(zhí)行中就繼續(xù)執(zhí)行，執(zhí)行成功就把計數(shù)器+1重復(fù)執(zhí)行

我們將行為樹中具有多個子節(jié)點的行為稱為復(fù)合節(jié)點，通過復(fù)合節(jié)點我們可以將簡單節(jié)點組合為更有趣更復(fù)雜的行為邏輯。
下面實現(xiàn)了一個符合節(jié)點的基類，將一些公用的方法放在了里面（如添加清除子節(jié)點等）

//復(fù)合節(jié)點基類
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)是復(fù)合節(jié)點的一種，它依次執(zhí)行每個子行為，直到所有子行為執(zhí)行成功或者有一個失敗為止。

//順序器：依次執(zhí)行所有節(jié)點直到其中一個失敗或者全部成功位置
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（）方法的實現(xiàn)如下

EStatus Sequence::Update()
{
    while (true)
    {
        EStatus s = (*CurrChild)->Tick();
        //如果執(zhí)行成功了就繼續(xù)執(zhí)行，否則返回
        if (s != EStatus::Success)
            return s;
        if (++CurrChild == Childern.end())
            return EStatus::Success;
    }
    return EStatus::Invalid;  //循環(huán)意外終止
}

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

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

EStatus Selector::Update()
{
    while (true)
    {
        EStatus s = (*CurrChild)->Tick();
        if (s != EStatus::Failure)
            return s;    
        //如果執(zhí)行失敗了就繼續(xù)執(zhí)行，否則返回
        if (++CurrChild == Childern.end())
            return EStatus::Failure;
    }
    return EStatus::Invalid;  //循環(huán)意外終止
}

顧名思義，并行器（Parallel）是一種讓多個行為并行執(zhí)行的節(jié)點。但仔細觀察便會發(fā)現(xiàn)實際上只是他們的更新函數(shù)在同一幀被多次調(diào)用而已。

//并行器：多個行為并行執(zhí)行
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是一個枚舉類型，表示成功和失敗的條件（是成功或失敗一個還是全部成功或失?。?/p>

//Parallel節(jié)點成功與失敗的要求，是全部成功/失敗，還是一個成功/失敗
enum class EPolicy :uint8_t
{
    RequireOne,
    RequireAll,
};

update函數(shù)實現(xiàn)如下

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

在代碼中，并行器每次更新都執(zhí)行每一個尚未終結(jié)的子行為，并檢查成功和失敗條件，如果滿足則立即返回。
另外，當并行器滿足條件提前退出時，所有正在執(zhí)行的子行為也應(yīng)該立即被終止，我們在OnTerminate（）函數(shù)中調(diào)用每個子節(jié)點的終止方法

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

監(jiān)視器是并行器的應(yīng)用之一，通過在行為運行過程中不斷檢查是否滿足某條件，如果不滿足則立刻退出。將條件放在并行器的尾部即可。

主動選擇器是選擇器的一種，與普通的選擇器不同的是，主動選擇器會不斷的主動檢查已經(jīng)做出的決策，并不斷的嘗試高優(yōu)先級行為的可行性，當高優(yōu)先級行為可行時胡立即打斷低優(yōu)先級行為的執(zhí)行（如正在巡邏的過程中發(fā)現(xiàn)敵人，即時中斷巡邏，立即攻擊敵人）。
其Update（）方法和OnInitialize方法實現(xiàn)如下

//初始化時將CurrChild初始化為子節(jié)點的末尾
virtual void OnInitialize() override { CurrChild = Childern.end(); }

    EStatus ActiveSelector::Update()
    {
        //每次執(zhí)行前先保存的當前節(jié)點
        Behaviors::iterator Previous = CurrChild;
        //調(diào)用父類OnInlitiallize函數(shù)讓選擇器每次重新選取節(jié)點
        Selector::OnInitialize();
        EStatus result = Selector::Update();
        //如果優(yōu)先級更高的節(jié)點成功執(zhí)行或者原節(jié)點執(zhí)行失敗則終止當前節(jié)點的執(zhí)行
        if (Previous != Childern.end()&CurrChild != Previous)
        {
            (*Previous)->Abort();    
        }

        return result;
    }

這里我創(chuàng)建了一名角色，該角色一開始處于巡邏狀態(tài)，一旦發(fā)現(xiàn)敵人，先檢查自己生命值是否過低，如果是就逃跑，否則就攻擊敵人，攻擊過程中如果生命值過低也會中斷攻擊，立即逃跑，如果敵人死亡則立即停止攻擊，這里我們使用了構(gòu)建器來創(chuàng)建了一棵行為樹，關(guān)于構(gòu)建器的實現(xiàn)后面會講到，這里每個函數(shù)創(chuàng)建了對應(yīng)函數(shù)名字的節(jié)點，

//構(gòu)建行為樹：角色一開始處于巡邏狀態(tài)，一旦發(fā)現(xiàn)敵人，先檢查自己生命值是否過低，如果是就逃跑，否則就攻擊敵人，攻擊過程中如果生命值過低也會中斷攻擊，立即逃跑，如果敵人死亡則立即停止攻擊
    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;

然后我通過一個循環(huán)模擬行為樹的執(zhí)行。同時在各條件節(jié)點內(nèi)部通過隨機數(shù)表示條件是否執(zhí)行成功（具體見文末github源碼）

    //模擬執(zhí)行行為樹
    for (int i = 0; i < 10; ++i)
    {
        Bt->Tick();
        std::cout << std::endl;
    }

執(zhí)行結(jié)果如下，由于隨機數(shù)的存在每次執(zhí)行結(jié)果都不一樣

上面創(chuàng)建行為樹的時候用到了構(gòu)建器，下面我就介紹一下自己的構(gòu)建器實現(xiàn)

//行為樹構(gòu)建器，用來構(gòu)建一棵行為樹,通過前序遍歷方式配合Back()和End()方法進行構(gòu)建
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;
    //用于存儲節(jié)點的堆棧
    std::stack NodeStack;
};

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

void BehaviorTreeBuilder::AddBehavior(Behavior* NewBehavior)
{
    assert(NewBehavior);
    //如果沒有根節(jié)點設(shè)置新節(jié)點為根節(jié)點
    if (!TreeRoot)
    {
        TreeRoot=NewBehavior;
    }
    //否則設(shè)置新節(jié)點為堆棧頂部節(jié)點的子節(jié)點
    else
    {
        NodeStack.top()->AddChild(NewBehavior);
    }

    //將新節(jié)點壓入堆棧
    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;
}

在上面的實現(xiàn)中，我在每個方法里創(chuàng)建對應(yīng)節(jié)點，檢測當前是否有根節(jié)點，如果沒有則將其設(shè)為根節(jié)點，如果有則將其設(shè)為堆棧頂部節(jié)點的子節(jié)點，隨后將其壓入堆棧，每次調(diào)用back則退棧，每個創(chuàng)建節(jié)點的方法都返回this以方便調(diào)用下一個方法，最后通過End（）表示行為樹創(chuàng)建完成并返回構(gòu)建好的行為樹。

那么上面就是行為樹的介紹和實現(xiàn)了，下一篇我們將對行為樹進行優(yōu)化，慢慢進入第二代行為樹。
github地址