簡介
因為網上有太多的行為樹的教程和手冊，當我在決定哪一個适合Zomboid項目時，總是反複遇到相同的問題。我看的很多手冊都很嚴重地依賴于具體代碼的實作，或者簡單地基于通用的節點的工作流，都沒有實際的實作案例，就像下面這張圖：
因為那些教程對于我了解行為樹的核心規則沒有用處，我發現我盡管知道行為樹是如何操作的，但對于在遊戲中應當使用何種節點，或者真正完整的行為樹是怎樣的，都沒有一個實際的概念。
我已經花了海量的時間做試驗，是以我不擔心實際的編碼實作，而且關于這有大量的教程，基于各種遊戲引擎的都有。
可能在我描述的稍微具體點的修飾節點類型中有些實際上是包含于JBT的，而不是通常的行為樹的概念，但是我發現它們在PZ行為樹完全适用，是以，如果你的行為樹架構不支援的話，也很值得考慮實作一下。
我并不是想說我想在行為樹上成為專家，然而在開發Zomboid項目的NPC的過程中我發現并不能這樣，是以我花心思搞出幾樣東西，有了它們會讓我的第一次嘗試更加順暢，或者至少讓我知道用行為樹能做到什麼。我不會深入闡述具體實作，僅僅給出幾個抽象的例子，它們都是我在Zomboid項目中使用的。
基礎
顧名思義，不同于有限狀态機或者其它AI系統，行為樹就是一棵節點層次分明的樹，控制着AI物體的一系列決定。從樹延伸出的葉子節點，執行控制AI物體的指令。各種工具節點組成樹的分支，來控制AI指令的走向以形成一系列的指令，這樣來滿足遊戲需要。
它可以是一棵很高的樹，可以具有完成特定功能的子樹，開發者可以建立行為庫并把它們适當地連接配接起來以達到非常真實的AI行為。開發過程是高度可疊代的，你可以先排出一個基礎的行為樹，然後建立新的分支來處理各種達到目标的可選方案，這些分支按照它們的優先級排列，這樣AI在一個特定的行為失敗可以回溯到另一個政策，這是行為樹巨大優勢所在。
資料驅動 vs 代碼驅動
這個差別與這篇手冊關聯不大，但是應該提一下，行為樹可能有很多種方法來實作。一個主要的差別是行為樹是否在代碼之外被定義的：可能用XML檔案或者其它專門的格式，用外部編輯器來修改；也可能是直接在代碼中的嵌套的類執行個體。
JBT用一種比較奇特的方法，混合上述兩種方式。你可以用一個編輯器來可視化建立你的行為樹，但是實際上是一個導出的指令行工具生成了java代碼，在代碼中表示你的行為樹。
不論如果實作，葉子節點是你實際處理遊戲邏輯的地方，用來控制你的角色或者判斷角色所處的情景或周圍的事物，這些東西你都需要自已在代碼裡定義，代碼可以是你本地的語言或者Lua和Python這樣的腳本語言，而行為樹會利用它們達到複雜的行為。這些節點都是有實際作用的，有時它們就像标準庫一樣調用，行為樹自己處理内部資料，而不是簡單地給角色發送指令。行為樹這一點讓我很興奮。
樹的周遊
行為樹的一個核心方面就是，不同于你代碼中的方法，某個特定的節點或者分支可以要花好幾幀才能完成。行為樹的基本實作中，系統每一幀從樹的根部開始周遊，檢測每一個節點是否被激活，沿途重新檢查所有節點，直到到達目前激活的節點讓它重新整理。
這不是一個高效的方法，尤其當随着開發過程它變得越來越高，擴充得很大的時候。我想說很有必要在你實作的行為樹中儲存正在處理的節點，這樣下次就能直接重新整理而不是每一幀都周遊整棵樹。應該感謝JBT已經做到了這一點。
工作流
行為樹是由很多類型節點組成的，但是它們都有一些核心的功能，那就是它們都傳回三種狀态之一。（這依賴于行為樹的具體實作，可以有三種以上的狀态，但是我還沒有實踐過這些，它們和主題也沒太大關系）有如下三個狀态：
Success
Failure
Running
前面的兩個，就像它們的名字一樣，通知它們的父節點它們的操作是成功或者失敗的。第三個表明成功或者失敗還不确定，這個節點還會一直運作，下一次整棵樹重新整理時它仍然會重新整理，那時将再次有機會決定它是成功、失敗或者繼續運作。
這個功能是行為樹強大的關鍵所在，因為這允許一個節點持續幾幀進行操作。例如，一個“行走”節點，在它計算路徑時和移動角色到目标地點時會送出Running狀态。如果因為某種原因尋路失敗，或者有障礙阻擋角色到達目的地，這個節點會傳回failure給它的父節點。一旦角色到達了目的地，它會傳回success，表明Walk指令成功執行了。
這說明這個節點就它本身來說有一個固定不變的協定來表示成功和失敗，任何使用它的行為樹都可以從它擷取到這個結果。這些狀态傳導和定義整棵行為樹的工作流，生成一系列事件和多個不同的執行路徑，進而達到想要的AI行為。
行為樹節點的原型
Composite
Decorator
Leaf
Composite（合成節點）
合成節點可以有一個或多個子節點。它們處理子節點的順序可以是從第一個到最後一個，或者某些特定的合成節點的随機順序，在某一階段會根據它的子節點的處理結果向它的父節點傳回success或者failure，通常這取決于它的子節點的success或者failure（譯者：這裡提到了三層節點）。當它在處理子節點時，會向它的父節點持續發送running。
最常用的合成節點是Sequence節點，它按照順序運作每一個子節點，如果任何一個子節點傳回了failure，它傳回failure；如果所有子節點傳回成功狀态，它才傳回成功。
Decorator（修飾節點）
修飾節點同合成節點相似，可以擁有子節點，與之不同點在于，它有且隻有一個子節點。它的功能就是：将子節點的結果傳遞給父節點，停止子節點；或者重複執行子節點，這取決于具體的修飾節點類型。
一個常用的修飾節點的用法就是Inverter（反相器），它隻是把子節點的結果反相。當它的子節點傳回了失敗，它給它的父節點傳回成功，反之亦反。
Leaf（葉子節點）
它是最底層的節點類型，不能擁有子節點。
但葉子節點是最強大的節點類型，因為它在遊戲中被你定義和實作，來做具體遊戲或具體角色的檢測或者動作，讓你的行為樹真正做一些事情。
舉一個例子，和之前類似，是一個行走的行為。一個Walk節點會讓角色行走到指定的地點，然後根據行走的結果來傳回成功或者失敗。
因為你可以定義你自已的葉子節點（經常是少量代碼），放在合成節點和修飾節點以下，使你可以做出很強大的行為樹，可以有很複雜的層次和智能優先級的行為，這非常優秀。
用遊戲代碼去類比，可以将合成和修飾節點當作函數、分支結構和循環結構，還有其它程式設計語言的結構，用它們來定義你代碼的邏輯。而葉子節點就像遊戲中具體的代碼邏輯，會讓你的AI角色做一些實際上的事情或者檢測它們的狀态或場景。
葉子節點可以帶參數。例如Walk節點就可以接收一個角色将走向的坐标。
這些參數可以取自儲存在行為樹空間中的變量。例如一個目标點可以被一個“擷取安全地點”節點來決定，儲存在變量中，然後Walk節點可以利用這個值來定義目标地點。這是通過使用一個節點之間共享的空間來儲存和修改任意的長駐的變量來實作的，它讓行為樹變得無比強大。
另一個葉子節點的大類型是調用其它的行為樹的節點，将已存在的行為樹的資料空間傳遞給被調用的行為樹。
這一點很重要，因為這允許你将行為樹深度子產品化來建立可以無限重用的行為樹，可能會用到空間中一個特定的變量來操作。例如，一個“闖入建築”的行為可能需要一個“目标建築”的變量來進行操作，是以父樹可以在空間設定這個變量，然後通過一個子樹的葉子節點調用另一棵子樹。
Composite Nodes（合成節點）
接下來我們會讨論在行為樹中見到的最常用的合成節點。也有其它的，但我們隻包含這些基本的，已經可以讓你寫出很複雜的行為樹了。
Sequences（序列）
行為樹中應用的最簡單的合成節點，它的名稱已經說明了一切。一個序列節點會順序通路每個子節點，從第一個開始，如果它傳回成功，那麼通路下一個，依次類推。如果任何子節點失敗了，它立即向它的你節點傳回失敗；如果最後一個子節點也成功，序列節點會向它的父節點傳回成功。
你必須明白這個類型的節點在行為樹中有着廣泛的應用。最明顯的一個用法是，定義一系列必須全部完成的任務，任何一個節點的失敗都意味着後續節點的處理都是無用的。
例如：
這個序列很明顯，讓角色穿過一扇門，然後關上身後的門。事實上，這些節點可能有點抽象，在實際生産環境中會使用一些參數。Walk(地點),Open(是否開着),Walk(地點),Close(是否開着);
處理順序如下：
Sequence -> Walk to Door (success) -> Sequence (running) -> Open Door (success) -> Sequence (running) -> Walk through Door (success) -> Sequence (running) -> Close Door (success) -> Sequence (success) -> at which point the sequence returns success to its own parent.
如果角色沒有走到門前，可能路被擋住了，那麼嘗試去開門也沒有意義了，更不用說穿過門。序列節點在行走失敗的時候已經傳回失敗了，然後這個序列節點的父節點可以很好地處理這個失敗。
上述的序列節點讓角色完成一系列的動作，因為這似乎是行為樹的唯一用途，是以你可能不會想到除了讓角色完成一系列“事情”之外，還有很多不同的方法來使用序列節點。想一下下面的例子：
在上面的例子中，我們沒有用一系列的動作而用了檢測。子節點檢測角色是否餓了，是否有食物，是否在安全地點，隻有這些檢測都成功了之後，角色才會吃食物。這樣使用序列節點讓你可以在執行一個動作之前執行一個或多個檢測，就像代碼裡的if條件，電路裡的與門。因為需要所有子節點都成功，而且子節點可以是任意合成節點、修飾節點和葉子節點的組合，你可以在你的AI中建立非常強大的條件判斷。
思考下面的例子，用到了上文提到的反相器：
與上一例子功能相同，我們展示了如何使用反相器來将任何檢測取反，這樣你得到了一個非門。這意味着你可以暴力地剪掉一堆節點來測試角色或者遊戲的一些邏輯。
Selector（選擇器）
選擇器與序列節點正好相反。序列節點的作用是“與”，需要所有子節點都成功才傳回成功，而選擇器隻要有一個子節點傳回了成功，它就傳回成功，而且不再處理後續的節點。它先處理第一個節點，如果失敗了，就處理第二個，如果再失敗了，就第三個…直到有一個成功，那麼選擇器會立即傳回成功。如果所有子節點都失敗了，它才傳回失敗。這表示選擇器是一個“或”門，或者作為一個條件判斷用來判斷多個條件中是否有一個真的。
它最大的優點在于它可以代表多種不同的動作組合，按照最希望的到最不希望排列優先級，如果任何一支成功了它就傳回成功。它可以包含很多的結果，利用它可以快速建構出很複雜的行為樹。
讓我再看一下之前的進門序列案例，讓它變得更複雜一點，加入一個選擇器來解決。
如你所看到的，我們可以智能地解決上鎖的門，僅僅用了少數幾個節點。
是以當選擇器在處理時發生了什麼呢？
首先，它先處理“開門”節點，最希望的動作就是直接開門，毫無疑問。如果順利開門了，那選擇器成功，知道了這個動作已經成功完成。那麼就沒有必要處理後面的子節點了。
但是，如果因為有人鎖上了，開不了門，那“開門”節點會失敗，将失敗狀态傳回給選擇器。這時選擇器會執行第二個節點（或者第二希望執行的動作），來嘗試打開門鎖。
這裡我們建立了另一個序列（必須全部完成才會向選擇器傳回成功），先打開門鎖，然後嘗試打開門。
如果開鎖也失敗了（可能AI沒有鎖匙，或者沒有開鎖技巧，或是已經撬開了鎖，但發現門是固定的根本打不開？），那麼它會向選擇器傳回失敗，然後它會嘗試第三種做法，把門暴力地撞開。
如果角色不夠強壯，那他可能又要失敗了。這時沒有更多的動作組合，那這個選擇器就傳回失敗，相應地它的父節點也傳回失敗，放棄穿過門的嘗試了。
讓我們走得更遠些，可能在那個序列節點上面還有一個選擇器，因為這個序列節點的失敗決定使用另一套動作？
這裡我們擴充了這個行為樹，在最上層增加了一個選擇器。左邊（最希望的）我們從門進入，如果失敗了，就嘗試從窗戶進入。實際上的實作會和這個不太一樣，和我們在Zomboid項目中相比還是很簡單，但是足夠表達意思了，後面我們将會得到更通用和更實用的實作。
總之，我們得到了一個可靠的“進入建築”的行為，或者進入建築，或者通知父節點不能進入。可能根本連窗戶都沒有呢？這樣最頂層的選擇器就失敗了，可能這時一個父節點會讓AI去另一個建築？
對于我以前的嘗試來說，大大簡化行為樹開發的一個重要因素就是，失敗并不意味着就要停止我正在做的事情（例如，尋路失敗了，怎麼辦？），而是很自然地在行為樹中做出自然而合适的決定。
你可以将容錯機制和适應所有可能情況的可選行為組合放進去。一個Zomboid項目中例子就是EnsureItemInInventorybahviour。
這個行為接收一個物品類型，然後使用一個選擇器來從幾種不同動作中決定一個，來确定這個物品是否在NPC的物品欄裡，包括使用不同的參數對這個行為進行遞歸調用。
首先，它會檢測這個物品是否已經存在于這個角色的主物品欄中，這是最理想的情況，什麼都不必再做。如果是的話，選擇器成功，整個行為成功。EnsureItemInInventory就成功了，可以使用這個物品。
如果不在角色的物品欄中，那麼它會檢測角色的袋子或者背包中的内容。如果找到了，它會把物品傳送到主物品欄中。這會傳回一個成功，然後整個行為成功。
如果上面失敗了，那選擇器的第三個分支會做的的确定它是否在角色居住的建築中。如果是，角色會走到有這個物品的容器的位置，将它拿出來。依然行為是成功的。
如果上面還失敗了，就要考驗NPC的手藝了。它會周遊合成菜單，找到想要的物品，還會周遊找到合成需要的原料，再遞歸地調用EnsureItemInventorybehaviour找到每一個原料。那些動作都成功了，我們就知道NPC擁有合成那個物品的所有原料了。角色會使用這些原料制作出物品，我們已經知道擁有這個物品了，然後傳回成功。
如果上面還是失敗了，那EnsureItemInInventorybehaviour行為就失敗了，沒有再多回溯，NPC會将這個物品列入願望清單，在沒有這個物品的情況繼續生存，并在完成任務過程中尋找它。
事實是，隻要擁有原料，NPC就能立即制作出來，即使沒有原料也可以從建築中取到。
因為行為可以遞歸的特性，如果他自己沒有原料，他會嘗試用更底層的原料來制作原料，如有必要還會搜尋建築，将各個階段的物品制作出來，以制作最終想要的物品。
這樣我馬上就擁有了一個很複雜而且很好看的AI行為，實作方式也隻是幾層節點。EnsureItemInInventory行為可以在其它行為樹中任意使用，适用于所有我們需要确定NPC是否擁有某種物品的情況。
我覺得有些情況下，在開發過程中我們會做得更多，會有另一個回溯，假如他急切需要這個物品，就允許NPC出去尋找它，選擇一個掠奪的目标，很有可能會得到那個物品。
另一個相對優先級比較高的容錯機制是，考慮别的具有相同功用的物品。如果我們實作了對臨時工具的支援，當需要釘釘子時，比起穿越整個街區去一個被僵屍感染的五金店找錘子，還不如尋找不太有效的替代工具比如石頭。
因為開發過程中擴充行為樹很友善，可以先建立一個簡單的行為“做某事”，然後使用選擇器通過加入容錯機制和回溯機制來減少失敗的可能性。制造的回溯被加在很後面，而且也僅僅是找到裝備更多的NPC，他們具有幫助别人制造物品的行為。
除些之外，如果優先級配置設定很合理，這些回溯操作除了要高效的實作代碼，還要處理智能問題和自然決策。
Random Selectors / Sequences（随機選擇器/序列節點）
我不再細細探究這個了，因為它們的行為之前已經說過了。随機選擇器/序列節點的工作方式就像它們的名字，除了子節點的實際操作順序是随機的。這适用于角色對于每一種動作組合沒有偏向性，給予它更多的不可預測的因素。
Decorator Nodes（修飾節點）
Inverter（反相器）
我們之前已經說過了。将它們放在節點之上可以将其結果反相，成功變失敗，失敗變成功。它最常用在條件的測試上。
Succeeder（成功節點）
成功節點不管子節點傳回什麼，它都傳回成功。這适用于，有一個你希望或者可預料到會傳回失敗的節點，但是你不想讓它阻止它所在的序列的運作。如果是相反的情況，你會需要一個failer節點。
Repeater（重複節點）
重複節點每當它的子節點傳回一個結果時，會重複處理這個節點。這适用于行為樹中非常基礎的部分，需要它持續運作。重複節點可以是重複執行指定次數就傳回。
Repeat Until Fail（重複直到失敗）
像重複節點一樣，這個節點也會持續重複處理子節點。但是直到子節點傳回了失敗，它就會向父節點傳回成功。
Data Context（資料空間）
它的具體實作取決于行為樹的具體實作、使用的程式設計語言和其它因素，是以我們隻在抽象和概念層面讨論它。
當AI物體的行為樹被調用時，也會建立一個資料空間，作為一個存儲機制來存儲資料，這些資料在節點中解釋和修改（使用C#中的字典、Java中的HashMap、可能用C++的string/void* STL map建立序列,已經很久不用C++了，應該有更好的方式）。
節點可以讀寫這些變量，用以後續節點的處理，這樣行為樹就成為一個有機的整體。一旦你開始着重使用這塊内容，行為樹的複雜度和适用範圍就非常可觀了，你指尖的力量将是巨大的。一會兒當我們再次回到我們的“門和窗”行為時将會用到這個。
Defining Leaf Nodes（定義葉子節點）
同樣的，它的具體内容取決于具體實作。為了賦予葉子節點功能，讓具體的遊戲邏輯能夠添加到行為樹中，大多系統都有兩個需要實作的方法。
Init – 當節點第一次被父節點通路時調用。例如，當序列節點要處理它的子節點時會調用這個方法，它完成了這次處理傳回了之後，下一次再執行時，就不會調用init方法了。這個方法用于初始化節點，開始節點的動作。拿我們的例子來說，它會接收參數，可能初始化尋路工作。
方法裡傳回成功或失敗，它的執行将會終止，結果傳回給父節點。如果他傳回Running，它會在下一幀被重複執行，直到它傳回成功或失敗。在我們的例子當中，在尋路傳回成功或失敗之前，它會一直傳回Running。
節點可以擁有一些字段，可能是明确指定傳入的參數，也可以是資料空間的變量的引用。
我不會讨論具體實作，因為它不僅依賴于語言還依賴于行為樹的實作，但是參數和資料存儲的概念是通用的。
例如，我們可能會這樣定義Walk節點：
Walk (character, destination)
- success: Reached destination
- failure: Failed to reach destination
- running: En route
這種情況下，Walk有兩個參數，角色和目标地點。我們會很自然地想到運作這個AI行為的角色是确定的，因而我們沒必要明确将他作為參數傳遞，但是最好不要這樣想，盡管對于Walk是一個很靠譜的假設。有太多次的經驗，尤其是在條件節點，我在測試不同的角色狀态時或者互動時總是需要修改代碼，是以最好是多廢點力氣将角色當參數傳入，即使你堅信隻有那個AI會需要它。
目标地點這個參數，就像我之前說的，可以手動填入X,Y,Z坐标。但是很有可能它會儲存在資料空間，被另一個節點引用，可能包含了另一個遊戲物體、建築的位置，或者可能根據NPC的所在位置計算出來的安全地點。
Stacks（棧）
第一次思考行為樹時，很自然地把節點的使用範圍與角色動作、條件判斷或者角色環境聯系起來，這将會限制你發揮出行為樹的強大力量。
當我用節點實作棧操作時，我發現了這一點。是以我在遊戲中加入了以下的實作：
PushToStack(item, stackVar)
PopFromStack(stack, itemVar)
IsEmpty(stack)
就是這樣，就這麼三個節點。它們需要的也是init/process方法，用了很少的代碼實作了建立和修改标準庫的棧的操作，而且，衍生出了更多可能性。
例如，PushToStack會存儲傳入變量名，壓入棧中，如果棧不存在則建立一個。
相似地，pop方法将元素彈出棧，将值存儲在itemVar變量中，如果棧是空的，則會失敗，是以有IsEmpty節點來檢查棧是不是空的，如果是空就傳回成功。
有了上面的節點，我們可以這樣來周遊整個棧：
使用一個“直到失敗”的重複節點，我們可以重複從棧中彈出元素，并執行一些操作，直到棧為空，PopFromStack會傳回失敗，然後退出“直到失敗”重複節點。
接下來是幾個其它我常用的很重要的工具
SetVariable(varName, object)
IsNull(object)
這允許我們通過行為樹設定任意的變量。合成節點和修飾節點未提供足夠的支援來讓我們擷取到行為樹的資訊，這時它們就非常有用了。随後我們會創造這麼個情景，盡管我覺得還是有方法來解決的，它不是必需的。
現在假設我們添加一個節點叫GetDoorStackFromBuilding，會傳入一個建築物體，它會從中取出門物體的一個清單，用這些物體建立并且填充一個棧，然後設定目标。我怎麼用上面提到的工具來完成呢？
哎呀，搞得略複雜，一眼看過去很難知道到底在幹嘛，但和任何語言一樣，到最後還是很容易了解的，而且你犧牲可讀性換取了複雜度。
但是它到底做了什麼？一開始你可能有點頭疼，但是隻要你熟悉了節點的工作方法，以及失敗和成功的狀态是怎麼傳遞的，就很容易了解了。如有必要我可能擴充這一部分到行為樹的Walk，假如我的描述不夠充分的話。
簡而言之，這是一個會擷取建築所有門并進入，并且如果角色進入任意一個門就會傳回成功的行為，如果未能進入，則傳回失敗。
首先它擷取一個包含了進入建築的所有門的棧，然後調用一個“直到失敗”的重複節點，它會重複執行直到子節點傳回失敗。
那個子節點是一個序列節點，先從棧中彈出一個門，存儲在door變量中。
如果棧是空的，那說明根本沒有門，這個節點就會失敗，直到跳出重複節點，重複節點傳回一個成功（“直到失敗”節點總是傳回成功），繼續處理這個序列，我們加入了一個反相的IsNull檢測usedDoor。如果usedDoor是空（因為從來沒有設定過這個值），這會導緻整個行為失敗。
如果棧确實彈出了一個門物體，就會調用另一個序列（加了反相），它會嘗試走向門，打開然後穿過。
假如NPC用盡各種方法也沒穿過門去（門鎖了，NPC也不夠強壯将其打開），選擇器就失敗，傳回失敗給它的父節點，是一個反相器，将失敗反相為成功，意味着它無法跳出重複節點，然後回來再次調用它的子序列，将下一個門彈出，然後NPC會嘗試這個門。
如果NPC成功進入了一個門，那麼它将會将usedDoor設定為door的值，這時序列節點傳回一個成功，這個成功被反相為失敗，之後跳出重複節點的循環。
這種情況下，我們在IsNull節點的節點傳回失敗，因為usedDoor不是空。它被反相為成功，導緻整個行為成功。更高一層的父節點知道NPC成功找到一個門，進入了建築。
如果行為是失敗的，那麼會用一個GetWindwoStackFromBuilding節點來重複執行，來重複之前的操作從窗戶進入，需要少量的節點執行棧操作。或許你可以先後調用GetDoorStackFromBuilding和GetWindowStackFromBuilding，将窗戶壓入門的棧頂，然後在同一個循環裡處理所有，對門和窗執行相同的Open，Unlock，Close操作，還有變量的檢測。
最後，你可以注意到我到close door節點之上加了一個成功節點，這是因為如果NPC是破壞掉門進去的，它關門的動作會失敗。
如果沒有那個成功節點，會導緻這個序列傳回失敗，沒有給useDoor變量指派，并嘗試下一個門。一個可選方案是讓CloseDoor節點總是傳回成功，即使門被破壞了。但是，我們想要檢測關門是否成功（例如，在“保護安全屋”行為中，會将關不上門視為失敗，因為門已經不在門框上，也就是不安全了！），是以成功節點可以讓那個失敗被忽略，如果需要那種行為。
原文釋出時間為：2018-07-05
本文作者：Chris Simpson
本文來自雲栖社群合作夥伴“
Golang語言社群”，了解相關資訊可以關注“
”