游戲AI行為決策——Behavior Tree（行為樹）

【USparkle專欄】如果你深懷絕技，愛“搞點研究”，樂于分享也博采眾長，我們期待你的加入，讓智慧的火花碰撞交織，讓知識的傳遞生生不息！

這是侑虎科技第1825篇文章，感謝作者狐王駕虎供稿。歡迎轉發分享，未經作者授權請勿轉載。如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群：793972859）

作者主頁：

https://home.cnblogs.com/u/OwlCat

一、前言

行為樹，是目前游戲中應用較為廣泛的一種行為決策模型。這離不開它成熟的可視化編輯工具，例如Unity商城中的「Behaviour Designer」，甚至是虛幻引擎也自帶此類編輯工具。而且它的設計邏輯并不復雜，其所利用的樹狀結構，很符合人的思考方式。

接下來，我們會先對它的運作邏輯進行介紹，然后再試圖用代碼實現它。樹狀結構在不借助可視化工具的情況下是不容易呈現清楚的，這里我借鑒了Steve Rabin的《Game AI Pro》[1]中行為樹的實現方式，利用代碼縮進稍稍實現了一些可視化（本教程使用C#代碼實現）。下面我們就開始吧！

二、運動邏輯

1. 根節點驅動

如果你已經了解「有限狀態機（FSM）」的話，你應該知道，有限狀態機在運作時常常會停留在一個狀態中，不斷執行該狀態的邏輯，直至接受到狀態轉移的指令才變化到其它狀態。而行為樹則是會不斷從根節點向下搜索，即「根節點驅動」，來找到合適的「動作」執行，執行完畢后會再回到根節點重復這個過程。以下面這個「怪物攻擊玩家」行為樹為例：

假設「攻擊」動作的邏輯是「向玩家揮一拳」，現在怪物發現玩家且玩家在攻擊范圍內。那么，按照行為樹的邏輯，它會經過「戰斗 ? 試圖攻擊 ? 攻擊」一路下來，最終向玩家揮出一拳。

至此，「攻擊」就算是完成了，若是在狀態機中，攻擊也算是一種狀態的話，怪物必然會停留于此，等待下一幀時再揮出一拳。但在行為樹中呢？它確實也會在下一幀時再揮出一拳，只是會再經過「戰斗 ? 試圖攻擊 ? 攻擊」這個過程，也就是前面所說的，從根節點再次出發。

你可能也發現了，這明顯是多此一舉的行為，它確實可以算是行為樹的小缺點。但其實行為樹的深度通常并不會太深，多幾次布爾判斷或小遍歷倒也不打緊；而且有一種事件驅動的行為樹實現方法，能以“空間換時間”的手段改善這種情況，感興趣的同學可以去了解一下。

2. 特殊的節點

行為樹的一大特點，就是將條件與行為本身進行了分離。

什么意思呢？我們仍以上面那張圖為例，只是稍稍修改下表現方式（也更接近行為樹真正的樣子）：

好像多了幾個圈？那現在，請你將這些圈也視為和「攻擊」一樣類型的節點。這樣一來，我們將「判斷邏輯」、「順序遍歷（圖中的紅色箭頭）」、「動作」都用節點來表示了。這有什么好處呢？好處就在于我們可以將它們進行各種各樣的組合！比如，如果有一個怪物比較膽小，遇到玩家后會逃跑，我們就可以用圖中的「發現玩家」+「移動到該位置（逃跑的位置）」來實現；也可以配合新的節點來組合，比如「已知玩家最后出現的位置」+ 新節點：「朝指定位置開火」，就可以實現遠程追擊。

總之，正是因為行為樹有一系列特殊的節點，使得開發者可以降低各個行為之間的關聯（也就是解耦），再配合上樹狀結構的特點，開發者可以靈活地進行組裝，實現節點的重復利用，避免寫重復的代碼，提高了開發效率。（用過有限狀態機寫游戲AI的同學一定能體會到這點的好處。）

三、代碼實現

現在，我們就一起來實現行為樹，先看看我們有哪些要實現的（它們的具體含義后面會解釋）：

1. 組合節點（Composite），指有多個子節點的特殊節點，具體包括：

a. 順序器（Sequence）

b. 選擇器（Selector）

c. 并行器（Parallel）

d. 過濾器（Filter）

e. 主動選擇器（ActiveSelector）

f. 監視器（Monitor）

2. 修飾節點（Decorator），指僅有一個子節點的特殊節點，具體包括：

a. 取反器（Inverter）

b. 重復執行器（Repeat）

3. 動作節點，指可以自定義的節點，比如「攻擊」、「巡視」之類的。

1. 基礎準備

正式實現它們之前，我們應當準備它們的基類，畢竟它們都是節點，有一些共性的東西可以提取出來，這樣可以減少一些重復的代碼。

/// /// 運行結果狀態的枚舉 /// publicenumEStatus {     //失敗，成功，運行中，中斷，無效     Failure, Success, Running, Aborted, Invalid } /// /// 行為樹節點基類 /// publicabstractclassBehavior {     publicboolIsTerminated=> IsSuccess || IsFailure;//是否運行結束     publicboolIsSuccess=> status == EStatus.Success;//是否成功     publicboolIsFailure=> status == EStatus.Failure;//是否失敗     publicboolIsRunning=> status == EStatus.Running;//是否正在運行     protected EStatus status;//運行狀態     publicBehavior()     {         status = EStatus.Invalid;     }     //當進入該節點時才會執行一次的函數，類似FSM的OnEnter     protected virtual voidOnInitialize() {}     //該節點的運行邏輯，會時時返回執行結果的狀態，類似FSM的OnUpdate     protectedabstract EStatus OnUpdate();     //當運行結束時才會執行一次的函數，類似FSM的OnExit     protected virtual voidOnTerminate() {}     //節點運行，從中應該更能了解上述三個函數的功能     //它會返回本次調用的結果，為父節點接下來的運行提供依據     public EStatus Tick()     {         if(!IsRunning)             OnInitialize();         status = OnUpdate();         if(!IsRunning)             OnTerminate();         return status;     }     //添加子節點     public virtual voidAddChild(Behavior child) {}     //重置該節點的運作     publicvoidReset()     {         status = EStatus.Invalid;     }     //強行打斷該節點的運作     publicvoidAbort()     {         OnTerminate();         status = EStatus.Aborted;     } }

2. 組合節點

首先實現「組合節點」這個基類。

using System.Collections.Generic; publicabstractclassComposite : Behavior {     protected LinkedList children; //用雙向鏈表構建子節點列表     publicComposite()     {         children = newLinkedList ();     }     //移除指定子節點     public virtual voidRemoveChild(Behavior child)     {         children.Remove(child);     }     publicvoidClearChildren()//清空子節點列表     {         children.Clear();     }     public override voidAddChild(Behavior child)//添加子節點     {         //默認是尾插入，如：0插入「1，2，3」中，就會變成「1，2，3，0」         children.AddLast(child);     } }

接下來就是具體類的實現了，我會對這些節點的功能作出解釋（有參考虛幻引擎的行為樹節點介紹），再進行代碼實現。

a. 順序器

邏輯上來講（非代碼結構），它長這樣：

順序器會按從左到右的順序執行其子節點。當其中一個子節點執行失敗時，將停止執行，也就是說，任一子節點失敗，順序器就會失敗。只有所有子節點運行都成功，順序器才算成功。

public classSequence : Composite {     protected LinkedListNode currentChild; //當前運行的子節點     protected override voidOnInitialize()     {         currentChild = children.First;//從第一個子節點開始     }     protected override EStatus OnUpdate()     {         while(true)         {             vars= currentChild.Value.Tick();//記錄子節點運行返回的結果狀態             /*             如果子節點運行，還沒有成功，就直接返回該結果。             是「運行中」那就表明本節點也是運行中，有記錄當前節點，下次還會繼續執行；             是「失敗」就表明本節點也運行失敗了，下次會再經歷OnInitialize，從頭開始。             */             if( s != EStatus.Success)                 return s;             //如果運行成功，就換到下一個子節點             currentChild = currentChild.Next;             //如果全都成功運行完了，就返回「成功」             if(currentChild == null)                 return EStatus.Success;         }     } }

b. 選擇器

從邏輯上講，它的結構應該長這樣：

每次只會選擇一個可以運行的子節點來運行。

但從代碼上來說，選擇器的結構和順序器完全一致，只是運行邏輯變化了：按從左到右的順序執行其子節點。當其中一個子節點執行成功時，就停止執行，也就是說，任一子節點成功運行，就算運行成功。只有所有子節點運行都失敗，選擇器才算運行失敗。

所以，只要簡單地繼承「順序器」并修改它的OnUpdate邏輯，就能得到選擇器啦！

public classSelector : Sequence {     protected override EStatus OnUpdate()     {         while(true)         {             vars= currentChild.Value.Tick();             if( s != EStatus.Failure)                 return s;             currentChild = currentChild.Next;             if(currentChild == null)                 return EStatus.Failure;         }     } }

c. 并行器

并行器，它會同時執行所有子節點。

可這樣就有問題了：

1. 怎么「同時」運行，要用多線程嗎？

2. 同時執行必然會返回多個結果，該如何確定最終返回運行結果呢？

對于問題1，是不用多線程的，我們只要在一幀中把所有子節點都執行一次，就算是「同時」執行了；

對于問題2，我們可以根據需求自行設置并行器成功或失敗的標準，一般可分為「全都」和「只要有一個」。

看看代碼就知道了：

public classParallel : Composite {     protected Policy mSuccessPolicy;//成功的標準     protected Policy mFailurePolicy;//失敗的標準     ///     /// Parallel節點成功與失敗的要求，是全部成功/失敗，還是一個成功/失敗     ///     publicenumPolicy     {         RequireOne, RequireAll,     }     //構造函數初始化時，會要求給定成功和失敗的標準     publicParallel(Policy mSuccessPolicy, Policy mFailurePolicy)     {         this.mSuccessPolicy = mSuccessPolicy;         this.mFailurePolicy = mFailurePolicy;     }     protected override EStatus OnUpdate()     {         intsuccessCount=0, failureCount = 0;//記錄執行成功和執行失敗的節點數         varb= children.First;//從第一個子節點開始         varsize= children.Count;         for (inti=0; i < size; ++i)         {             varbh= b.Value;             if(!bh.IsTerminated)//如果該子節點還沒運行結束，就運行它                 bh.Tick();             b = b.Next;             if(bh.IsSuccess)//該子節點運行結束后，如果運行成功了             {                 ++successCount;//成功執行的節點數+1                 //如果是「只要有一個」標準的話，那就可以返回結果了                 if(mSuccessPolicy == Policy.RequireOne)                     return EStatus.Success;             }             if(bh.IsFailure)//該子節點運行失敗的情況同理             {                 ++failureCount;                 if(mFailurePolicy == Policy.RequireOne)                     return EStatus.Failure;             }         }         //如果是「全都」標準的話，就需要比對當前成功/失敗個數與總子節點數         if(mFailurePolicy == Policy.RequireAll && failureCount == size)             return EStatus.Failure;         if(mSuccessPolicy == Policy.RequireAll && successCount == size)             return EStatus.Success;         return EStatus.Running;     }     //結束函數，只要簡單地把所有子節點設為「中斷」就可以了     protected override voidOnTerminate()     {         foreach(var b in children)         {             if(b.IsRunning)                 b.Abort();         }     } }

至此，基礎的組合節點就講完了，但還有一些常用的組合節點，它們是在這些基礎的組合節點上稍稍變形而來的。

d. 過濾器

過濾器，由順序器改造而來，就是在進入子節點之前，加了些條件判斷，如果不滿足任意一個，就不能執行后續的子節點，此即為「過濾」。

你會發現，它們甚至可以直接看作是在同一個列表里，只是「條件」都在前半段，真正要運行的子節點都在后半段。代碼也確實是這么設計的：

public classFilter : Sequence {     publicvoidAddCondition(Behavior condition)//添加條件，就用頭插入     {         children.AddFirst(condition);     }     publicvoidAddAction(Behavior action)//添加動作，就用尾插入     {         children.AddLast(action);     } }

e. 主動選擇器

假設，某人正在砍樹，但突然電鋸故障了，迫不得已，他只能換斧頭來砍樹；但突然被扔在一旁的電鋸又好起來了，那他還會繼續費力的用斧子來砍樹嗎？

我想，只要他還沒因為中暑把CPU干燒就不會這么做。但他如果是一個NPC的話，按照之前「選擇器」的邏輯，確實會出現這種荒謬的行為。所以我們需要一個特殊的選擇器，能始終執行最具優先級的子節點，甚至可以因此打斷正在運行的低優先級的子節點。

我們只需對「選擇器」的OnUpdate進行改造，在每次調用時，也從頭到尾進行選擇（默認高優先級的行為在前面）即可：

public classActiveSelector: Selector {     protected override EStatus OnUpdate()     {         varprev= currentChild;         base.OnInitialize();//注意這里，currentChild 會被賦值為children.First         varres= base.OnUpdate();//按Selector的OnUpdate執行，順序遍歷選擇         /*         只要不是遍歷結束或可執行節點不變，都應該中斷上一次執行的節點，無論優先是高是低。         因為如果當前優先級比之前的高，理應中斷之前的；         而如果比之前的低，那就證明之前高優先級的行為無法繼續了，         否則怎么會輪到現在的低優先級的行為呢？所以也應中斷它。         */         if(prev != null && currentChild != prev)             prev.Value.Abort();         return res;     } }

f. 監視器

監視器是對「并行器」的改造，改造的目的也是為了能持續檢查并行行為的條件。

從邏輯上看，它有兩個子樹，一邊負責條件，一邊負責具體行為。這種分離方式是合理的，防止了同步和爭用問題，因為只有一個子樹將運行對世界進行更改的操作。

從代碼上來說，其實它的改造方法和「過濾器」完全一致，因為我們完全可以把這兩個子樹看作一個，只是前半部分全是條件，后半部分全是具體動作而已：

public classMonitor: Parallel {     publicMonitor(Policy mSuccessPolicy, Policy mFailurePolicy)      : base(mSuccessPolicy, mFailurePolicy)     {     }     publicvoidAddCondition(Behavior condition)     {         children.AddFirst(condition);     }     publicvoidAddAction(Behavior action)     {         children.AddLast(action);     } }

終于，所有常用的組合節點我們都實現了，下面就該講講修飾節點了。

3. 修飾節點

修飾節點只有一個子節點，因為這樣就足夠了，想要多個條件只需要配合組合節點就可以實現。所以它的基類也十分簡單：

public abstract class Decorator : Behavior {     protected Behavior child;     public override void AddChild(Behavior child)     {         this.child = child;     } }

修飾節點理論上可以擴展成各種「條件」，完全取決于開發者的需求。所以這里，我們就不在這方面展開，就說說幾個比較實用的修飾器吧。

a. 取反器

簡單地對子節點執行結果的「成功」或「失敗」進行顛倒而已，但這小小的功能卻能幫我們省去很多冗余的代碼，比如有「存在敵人」的條件節點時，再想要「不存在敵人」的條件節點，就不必去寫代碼了，只需要在「存在敵人」前加上這樣一個「取反器」就可以了。

它的實現也很簡單：

public class Inverter : Decorator {     protected override EStatus OnUpdate()     {         child.Tick();         if(child.IsFailure)             return EStatus.Success;         if(child.IsSuccess)             return EStatus.Failure;         return EStatus.Running;     } }

b. 重復執行器

重復執行某（些）行為也是常見的動作需求，這些動作往往都是已實現的單一動作，例如，有了「點射」動作，我們就可以僅給它加上一個重復執行器，就可以實現「掃射」了。

重復執行器的邏輯也很直接：

public classRepeat : Decorator {     privateint conunter;//當前重復次數     privateint limit;//重復限度     publicRepeat(int limit)     {         this.limit = limit;     }     protected override voidOnInitialize()     {         conunter = 0;//進入時，將次數清零     }     protected override EStatus OnUpdate()     {         while (true)         {             child.Tick();             if(child.IsRunning)                 return EStatus.Running;             if(child.IsFailure)                 return EStatus.Failure;             //子節點執行成功，就增加一次計算，達到設定限度才返回成功             if(++conunter >= limit)                 return EStatus.Success;         }     } }

4. 動作節點

動作節點也是自由發揮的節點，具體功能隨需求，但有一點要嚴格遵守——不能有子節點。

要實現動作節點，只要繼承并重寫節點基類就可以了，例如一個打印一些字的節點：

public class DebugNode : Behavior {     private string word;     public DebugNode(string word)     {         this.word = word;     }     protected override EStatus OnUpdate()     {         Debug.Log(word);         return EStatus.Success;     } }

5. 構建與運行

節點部分我們都講完了，現在就開始實現樹的構建與運行了。

我們先實現樹：

public classBehaviorTree {     publicboolHaveRoot=> root != null;     private Behavior root;//根節點     publicBehaviorTree(Behavior root)     {         this.root = root;     }     publicvoidTick()     {         root.Tick();     }     publicvoidSetRoot(Behavior root)     {         this.root = root;     } }

很簡短吧，實際上樹只需要記錄根節點就可以了，其余節點都會由各個節點用自己的子節點/子節點列表存儲。這么說來，其實一個普通的節點，也可以視為一棵樹嗎？是的，只是將二者進行區分還是很有必要的，省得邏輯混亂。它的運行，也只是簡單地遞歸調用子節點的Tick。當然，這只是對于簡單實現的行為樹來說是這樣而已，至于更加成熟的實現方式（如之前提到的事件驅動的行為樹）就不是這樣了。

言歸正傳，那這只是一棵樹而已，怎么向它增加節點呢？這里我們再單獨造一個管理樹邏輯的類：

public partial classBehaviorTreeBuilder {     private readonly Stack nodeStack; //構建樹結構用的棧     private readonly BehaviorTree bhTree;//構建的樹     publicBehaviorTreeBuilder()     {         bhTree = newBehaviorTree(null);//構造一個沒有根的樹         nodeStack = newStack (); //初始化構建棧     }     privatevoidAddBehavior(Behavior behavior)     {         if (bhTree.HaveRoot)//有根節點時，加入構建棧         {             nodeStack.Peek().AddChild(behavior);         }         else//當樹沒根時，新增得節點視為根節點         {             bhTree.SetRoot(behavior);         }         //只有組合節點和修飾節點需要進構建堆         if (behavior is Composite || behavior is Decorator)         {             nodeStack.Push(behavior);         }     }     publicvoidTreeTick()     {         bhTree.Tick();     }     public BehaviorTreeBuilder Back()     {         nodeStack.Pop();         returnthis;     }     public BehaviorTree End()     {         nodeStack.Clear();         return bhTree;     } }

這樣就實現了樹構建，還把調用也再包裝了一層。用BehaviorTreeBuilder，就可以既構建又運行了。接下來，我們來詳細說說里面的邏輯：

最開始用AddBehavior函數添加一個節點，它無疑會成為根：

再添加一個0，它會變成這樣：

再添加同理：

而當我們想要為0添加第二個子節點時，只需要先調用Back，Back會使棧頂元素彈出：

之后，再調用添加函數，由于該函數是向棧頂元素添加子節點，所以就變成了：

通過AddBehavior和Back，我們就可以設置樹的結構。如果又想給1添加子節點該怎么辦？可以直接在調用Back之前的代碼里，加上給1節點添加子節點的代碼。

配合縮進，我們可以勉強實現可視化，至少有層次感：

public classTest0 : MonoBehaviour {     BehaviorTreeBuilder builder;     privatevoidAwake()     {         builder = newBehaviorTreeBuilder();     }     privatevoidStart()     {         builder.Repeat(3)                     .Sequence()                         .DebugNode("Ok,")//由于動作節點不進棧，所以不用Back                         .DebugNode("It's ")                         .DebugNode("My time")                     .Back()                 .End();         builder.TreeTick();     } }

這里的Repeat，實際上就是對添加節點的包裝，以下是該類的完整代碼:

public partial classBehaviorTreeBuilder {     private readonly Stack nodeStack;     private readonly BehaviorTree bhTree;     publicBehaviorTreeBuilder()     {         bhTree = newBehaviorTree(null);         nodeStack = newStack ();     }     privatevoidAddBehavior(Behavior behavior)     {         if (bhTree.HaveRoot)         {             nodeStack.Peek().AddChild(behavior);         }         else         {             bhTree.SetRoot(behavior);         }         if (behavior is Composite || behavior is Decorator)         {             nodeStack.Push(behavior);         }     }     publicvoidTreeTick()     {         bhTree.Tick();     }     public BehaviorTreeBuilder Back()     {         nodeStack.Pop();         returnthis;     }     public BehaviorTree End()     {         nodeStack.Clear();         return bhTree;     }     //---------包裝各節點---------     public BehaviorTreeBuilder Sequence()     {         vartp=newSequence();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Seletctor()     {         vartp=newSelector();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Filter()     {         vartp=newFilter();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Parallel(Parallel.Policy success, Parallel.Policy failure)     {         vartp=newParallel(success, failure);         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Monitor(Parallel.Policy success, Parallel.Policy failure)     {         vartp=newMonitor(success, failure);         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder ActiveSelector()     {         vartp=newActiveSelector();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Repeat(int limit)     {         vartp=newRepeat(limit);         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Inverter()     {         vartp=newInverter();         AddBehavior(tp);         returnthis;     } }

你可能也注意到了，這個類是partial類，它還有另一部分內容，我將其與DebugNode寫在同一處：

public classDebugNode : Behavior {     private string word;     publicDebugNode(string word)     {         this.word = word;     }     protected override EStatus OnUpdate()     {         Debug.Log(word);         return EStatus.Success;     } } public partial classBehaviorTreeBuilder {     public BehaviorTreeBuilder DebugNode(string word)     {         varnode=newDebugNode(word);         AddBehavior(node);         returnthis;     } }

個人還沒想到好辦法，這種包裝確實好看，但要另寫這樣的函數屬實有點繁瑣。倒也可以修改AddBehavior類讓它也返回BehaviorTreeBuilder，但這樣在構建樹時，代碼會變得有些長，總之看個人選擇。如果你的Test0能輸出三次"Ok,It's My time"，那就說明你的構建沒錯。

內容到這也差不多了，個人其實還并沒有正式用過這個行為樹來做游戲，當然還有其它的行為決策方法我比較青睞，比如「分層任務網絡（HTN）」，個人就用的比較多。在我個人的一些游戲中就有使用到，有時間的話，也可以和大家交流下它的運行和實現。

參考：

[1]《Game AI Pro》

https://www.gameaipro.com/

文末，再次感謝狐王駕虎 的分享， 作者主頁：https://home.cnblogs.com/u/OwlCat， 如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群： 793972859 ）。

近期精彩回顧

【學堂上新】

【學堂上新】

【萬象更新】

【萬象更新】