從有限狀态機（FSM）到行為樹（Behavior Tree）（1）

原文：http://www.aisharing.com/archives/439

選這次主題，要感謝一位網友的來信，他詢問了一些如何将有限狀态機轉成行為樹的問題，當時，我回信給了一些建議，但後來我仔細想了一下，覺得可能說得還不夠全面，是以我就想通過這篇文章，來整理出一些比較典型的轉化“模闆”，給有這方面疑惑的朋友一些幫助，如果有朋友有一些自己的見解的，可以在後面留言，我們一起讨論。

有限狀态機維護了一張圖，圖的節點是一個個的狀态，節點和節點的連線是狀态間根據一定的規則做的狀态轉換，每一個狀态内的邏輯都可以簡要描述為：

如果滿足條件1，則跳轉到狀态1

如果滿足條件2，則跳轉到狀态2

…

否則，不做跳轉，維持目前狀态

稍作整理的話，我們可以對狀态機的幾種跳轉的情況一一描述出來，然後看看如果将這些情況用行為樹來表示的話，可以怎麼做。這就是我前面說的“轉化模闆”，當然我不能保證我下面列出的是狀态機的所有可能情況，如果大家在實踐中發現還有其他的情況，歡迎留言，我随時更新。

在這之前，我們可以先回憶一些關于行為樹的一些概念（可以參考1，2）

• 控制節點：選擇節點，序列節點，并行節點，等等
• 行為節點：兩種運作狀态，“運作中”和“完成”
• 前提條件

模式1：當處在任何狀态中，一旦某條件滿足，即跳轉到某個特定的狀态。

比如，在狀态機中的一些錯誤處理，經常會用到上面的這種模式，當狀态在運作過程中，發生了某些異常，那一般，我們會把狀态機跳轉到某個異常狀态。這種情況，我們可以用到帶優先級的選擇節點（Priority Selector）方式，如下圖，可以看到，我們把狀态c作為行為樹裡的行為節點，跳轉條件（Condition1）作為這個節點的前提（Precondition）。

再用上面舉到的錯誤處理的例子，在狀态機中，我們一般會這樣寫：

1: STATE A::Update()      

2: {      

3:     ...      

4:     if(error)      

5:     {      

6:         return TO_ERROR_STATE();      

7:     }      

8:     ...      

9:     return UNCHANGED_STATE();      

10: }      

轉換到行為樹中，我們會通過外部的黑闆來做通信（可以參考這裡），在行為節點a中，我們會這樣寫

1: EXECUTE_STATE A::Execute(BlackBoard& out)      

2: {      

3:     ...      

4:     if(error)      

5:     {      

6:         out.error = error;      

7:         return EXECUTE_STATE_FINISH;      

8:     }      

9:     ...      

10:     return EXECUTE_STATE_RUNNING;      

11: }      

然後對于節點c的前提裡，我們來讀取黑闆裡的error值

1: bool Condition1::IsTrue(const BlackBoard& in) const      

2: {      

3:     return in.error == true;      

4: }      

模式2：對于同一個跳轉條件，處在不同的狀态會有不同的跳轉

比如，我們有兩個狀态，a和b，他們都對同一個跳轉條件作出響應，但和模式1不同的是，a對跳轉到狀态c，而b會跳轉到狀态d，換句話說，這是一種帶有上下文的狀态跳轉方式。對于這種情況，可以用到序列節點的相關特性，如下圖

序列節點中，目前一個節點運作完成後，會執行下一個節點，利用此特性，在上圖中可以看到，我們在a中，當滿足條件Condition1的時候，則傳回“完成”，那行為樹就會自動跳轉到c節點中，參考代碼如下：

1: EXECUTE_STATE A::Execute(BlackBoard& out)      

2: {      

3:     ...      

4:     if(condition1 == true)      

5:     {      

6:         return EXECUTE_STATE_FINISH;      

7:     }      

8:     ...      

9:     return EXECUTE_STATE_RUNNING;      

10: }      

對于這種模式的另一種轉化，可以不用序列節點，還是用到選擇和前提的組合，但我們在前提中加上一個目前狀态的附加條件，如下圖

在第二層的前提中，我們可以這樣寫

1: bool InACState::IsTrue(const BlackBoard& in)      

2: {      

3:     return in.current_running_node = A::GetID() ||      

4:            in.current_running_node = C::GetID();      

5: }      

6: bool InBDState::IsTrue(const BlackBoard& in)      

7: {      

8:     return in.current_running_node = B::GetID() ||      

9:            in.current_running_node = D::GetID();      

10: }      

這樣對于c的前提就是Condition1和InACState的“與”（回想一下前提的相關内容）。由于我們保留了上下文的資訊，是以通過對于前提的組合，我們就轉化了這種模式的狀态機。

（待續…）

————————————————————————

作者：Finney

Blog：AI分享站(http://www.aisharing.com/)

Email：[email protected]

本文歡迎轉載和引用，請保留本說明并注明出處

————————————————————————