行為樹（Behavior Tree）實踐（1）– 基本概念

自從開博以來，每天都會關心一下博客的訪問情況，看到一些朋友的訂閱或者訪問，不勝欣喜，也促使我去寫一些更好的博文，來和大家分享和交流，從訪問統(tǒng)計來看，有相當一部分是來自于搜索引擎的流量，關鍵字以“行為樹”，或者“Behavior Tree”居首位，我想大家對此可能有些興趣，加上，這幾年反反復復一直在AI中研究和運用行為樹，所以這次就來談談關于行為樹（Behavior Tree）的一些東西，以前也寫過一些文章（1，2，3）來討論行為樹，不過已經(jīng)是一兩年前的事情了，較之以前，這次會更為系統(tǒng)，也會添加一些我新的思考和感悟。所謂行為樹實踐，其實在我腦海里就是Practice in Behavior Tree，沒法子，受英文教材影響太多了:)

我想通過一個例子來介紹一下行為樹的基本概念，會比較容易理解，看下圖：

這是我們?yōu)橐粋€士兵定義的一顆行為樹（可以先不管這些綠圈和紅圈是干嗎的），首先，可以看到這是一個樹形結構的圖，有根節(jié)點，有分支，而且子節(jié)點個數(shù)可以任意，然后有三個分支，分別是巡邏（Patrol），攻擊（Attack），逃跑（Retreat），這個三個分支可以看成是我們?yōu)檫@個士兵定義的三個大的行為（Behavior），當然，如果有更多的行為，我們可以繼續(xù)在根節(jié)點中添加新的分支。當我們要決策當前這個士兵要做什么樣的行為的時候，我們就會自頂向下的，通過一些條件來搜索這顆樹，最終確定需要做的行為（葉節(jié)點），并且執(zhí)行它，這就是行為樹的基本原理。

值得注意的是，我們標識的三大行為其實并不是真正的決策的結果，它只是一個類型，來幫助我們了解這個分支的一些行為是屬于這類的，真正的行為樹的行為都是在葉節(jié)點上，一般稱之為行為節(jié)點（Action Node），如下圖紅圈表示的

這些葉節(jié)點才是我們真正通過行為樹決策出來的結果，如果用我以前提到的那個層次化的AI結構來描述的話，這些行為結果，相當于就是一個個定義好的“請求”（Request），比如移動（Move），無所事事（Idle），射擊（Shoot）等等。所以行為樹是一種決策樹，來幫助我們搜尋到我們想要的某個行為。

行為節(jié)點是游戲相關的，因不同的游戲，我們需要定義不同的行為節(jié)點，但對于某個游戲來說，在行為樹上行為節(jié)點是可以復用的，比如移動，在巡邏的分支上，需要用到，在逃跑分支上，也會用到，這種情況下，我們就可以復用這個節(jié)點。行為節(jié)點一般分為兩種運行狀態(tài)：

1. 運行中（Executing）：該行為還在處理中
2. 完成（Completed）：該行為處理完成，成功或者失敗

除了行為節(jié)點，其余一般稱之為控制節(jié)點（Control Node），用樹的“學名”的話，就是那些父節(jié)點，如下圖綠圈表示

控制節(jié)點其實是行為樹的精髓所在，我們要搜索一個行為，如何搜索？其實就是通過這些控制節(jié)點來定義的，從控制節(jié)點上，我們就可以看出整個行為樹的邏輯走向，所以，行為樹的特點之一就是其邏輯的可見性。

我們可以為行為樹定義各種各樣的控制節(jié)點（這也是行為樹有意思的地方之一），一般來說，常用的控制節(jié)點有以下三種

1. 選擇（Selector）：選擇其子節(jié)點的某一個執(zhí)行
2. 序列（Sequence）：將其所有子節(jié)點依次執(zhí)行，也就是說當前一個返回“完成”狀態(tài)后，再運行先一個子節(jié)點
3. 并行（Parallel）：將其所有子節(jié)點都運行一遍

用圖來表示的話，就是這樣，依次為選擇，序列和并行

可以看到，控制節(jié)點其實就是“控制”其子節(jié)點（子節(jié)點可以是葉節(jié)點，也可以是控制節(jié)點，所謂“執(zhí)行控制節(jié)點”，就是執(zhí)行其定義的控制邏輯）如何被執(zhí)行，所以，我們可以擴展出很多其他的控制節(jié)點，比如循環(huán)（Loop）等，與行為節(jié)點不同的是，控制節(jié)點是與游戲無關的，因為他只負責行為樹邏輯的控制，而不牽涉到任何的游戲代碼。如果是作為一個行為樹的庫的話，其中就一定會包含定義好的控制節(jié)點庫。

如果我們繼續(xù)考察選擇節(jié)點，會產(chǎn)生一個問題，如何從子節(jié)點中選擇呢？選擇的依據(jù)是什么呢？這里就要引入另一個概念，一般稱之為前提（Precondition），每一個節(jié)點，不管是行為節(jié)點還是控制節(jié)點，都會包含一個前提的部分，如下圖

前提就提供了“選擇”的依據(jù)，它包含了進入，或者說選擇這個節(jié)點的條件，當我們用到選擇節(jié)點的時候，它就是去依次測試每一個子節(jié)點的前提，如果滿足，則選擇此節(jié)點。由于我們最終返回的是某個行為節(jié)點（葉節(jié)點），所以，當前行為的“總”前提就可以看成是：

當前行為節(jié)點的前提 And 父節(jié)點的前提 And 父節(jié)點的父節(jié)點的前提 And….And 根節(jié)點的前提（一般是不設，直接返回True）

行為樹就是通過行為節(jié)點，控制節(jié)點，以及每個節(jié)點上的前提，把整個AI的決策邏輯描述了出來，對于每次的Tick，可以用如下的流程來描述：

action = root.FindNextAction(input);
if action is not empty then
action.Execute(request,  input)  //request是輸出的請求
else
print “no action is available”

從概念上來說，行為樹還是比較簡單的，但對AI程序員來說，卻是充滿了吸引力，它的一些特性，比如可視化的決策邏輯，可復用的控制節(jié)點，邏輯和實現(xiàn)的低耦合等，較之傳統(tǒng)的狀態(tài)機，都是可以大大幫助我們迅速而便捷的組織我們的行為決策。希望這次簡單的介紹，對大家有所幫助，能力有限，不一定能表述的很清楚，有問題，或者有指教的，都請和我多多交流，最后，我對這個士兵的巡邏分支畫了一個示意圖，供大家參考：

S — 選擇節(jié)點   Se — 序列節(jié)點

————————————————————————
作者：Finney
Blog：AI分享站(http://www./)
Email：finneytang@gmail.com
本文歡迎轉載和引用，請保留本說明并注明出處
————————————————————————