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

行為樹簡介

行為樹是一種樹狀的數(shù)據(jù)結(jié)構(gòu)，樹上的每一個(gè)節(jié)點(diǎn)都是一個(gè)行為。每次調(diào)用會(huì)從根節(jié)點(diǎn)開始遍歷，通過檢查行為的執(zhí)行狀態(tài)來執(zhí)行不同的節(jié)點(diǎn)。他的優(yōu)點(diǎn)是耦合度低擴(kuò)展性強(qiáng)，每個(gè)行為可以與其他行為完全獨(dú)立。目前的行為樹已經(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;
};

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

行為（behavior）

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

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

    EStatus GetStatus() { return Status; }
    virtual void AddChild(Behavior* Child){};
    
protected:
    //創(chuàng)建對(duì)象請(qǐng)調(diào)用Create()釋放對(duì)象請(qǐng)調(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é)點(diǎn)的核心，且我規(guī)定所有節(jié)點(diǎn)的構(gòu)造和析構(gòu)方法都必須是protected，以防止在棧上創(chuàng)建對(duì)象，所有的節(jié)點(diǎn)對(duì)象通過Create()靜態(tài)方法在堆上創(chuàng)建，通過Release()方法銷毀，由于Behavior是個(gè)抽象接口，故沒有提供Create()方法，本接口滿足如下契約

• 在Update方法被首次調(diào)用前，調(diào)用一次OnInitialize函數(shù)，負(fù)責(zé)初始化等操作
• Update（）方法在行為樹每次更新時(shí)調(diào)用且僅調(diào)用一次。
• 當(dāng)行為不再處于運(yùn)行狀態(tài)時(shí)，調(diào)用一次OnTerminate（），并根據(jù)返回狀態(tài)不同執(zhí)行不同的邏輯

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

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

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

    return Status;

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

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

動(dòng)作（Action）

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

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

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

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

條件

條件同樣是行為樹的葉子節(jié)點(diǎn)，用于查看游戲世界信息（如敵人是否在攻擊范圍內(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;
};

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

裝飾器（Decorator）

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

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

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

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ù)負(fù)責(zé)創(chuàng)建節(jié)點(diǎn)，Release負(fù)責(zé)釋放
其中Update()方法的實(shí)現(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í)行成功就把計(jì)數(shù)器+1重復(fù)執(zhí)行

復(fù)合行為

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

//復(fù)合節(jié)點(diǎn)基類
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;
};

順序器（Sequence）

順序器(Sequence)是復(fù)合節(jié)點(diǎn)的一種，它依次執(zhí)行每個(gè)子行為，直到所有子行為執(zhí)行成功或者有一個(gè)失敗為止。

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

選擇器（Selector）是另一種常用的復(fù)合行為，它會(huì)依次執(zhí)行每個(gè)子行為直到其中一個(gè)成功執(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）

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

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

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

update函數(shù)實(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í)行每一個(gè)尚未終結(jié)的子行為，并檢查成功和失敗條件，如果滿足則立即返回。
另外，當(dāng)并行器滿足條件提前退出時(shí)，所有正在執(zhí)行的子行為也應(yīng)該立即被終止，我們?cè)贠nTerminate（）函數(shù)中調(diào)用每個(gè)子節(jié)點(diǎn)的終止方法

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

監(jiān)視器（Monitor）

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

主動(dòng)選擇器

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

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

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

        return result;
    }

示例

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

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

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

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

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

構(gòu)建器的實(shí)現(xiàn)

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

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

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

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

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

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

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