關於行為樹實現的疑惑?
關於行為樹的實現,我在網上看到幾個實現版本都對節點規划了running狀態,表示節點的動作未執行完畢,每次執行時從上次未執行完畢的節點開始執行而跳過之前已經執行完畢的節點。
問題在於,處於同一selector節點下的子節點,位置越靠前的節點優先順序是越高的,如果因為running恢復機制而跳過了已經執行完畢的節點,豈不是無法實現「打斷」現有邏輯的需求?例如:
root
\_ selector
\__ sequence(戰鬥)
| \_ condition(是否發現敵人)
| |_ action(攻擊敵人)
\_ sequence(遊走)
\_ moveToA(如果此節點處於running,戰鬥節點豈不無法被執行???)
|_ moveToB
我想問,節點running狀態的引入是為了解決什麼問題?為什麼不每次都top-down執行所有節點?
我參考的其中一份實現版本是騰訊的,他的selector實現如下:behaviac/selector.cpp at master · TencentOpen/behaviac · GitHub
1. 行為樹肯定要有 RUNNING狀態的,否則你長時間做一件事情很難描述呀,比如你先做「走過去」,再做「採礦」再做「返回」,一顆行為樹就表達完了。每件事情都是持續的,如果沒有RUNNING,那其實就更像一顆「決策樹」而非「行為樹」了。2. 假設你有三層狀態機,行為樹也只會用在最後一層,頭兩層都是一些「確定的動作」,不需要行為樹來弄,比如「跑過去」,「採礦」這些分解動作,本來變化也不多,如果這都要行為樹來弄的話,你的開發反而會很累。3. 行為樹是「樹形邏輯」,「樹形狀態變遷」,但是有些時候邏輯不是樹形的,比如就是個純粹的是有向圖的,這種情況下非要用行為樹的話,要打比較多Patch4. 針對你說的「停止」,問題,狀態機/行為樹,肯定要可以隨時打斷安排新任務的,具體的做法可能是,update的時候傳入一個事件(比如時鐘,或者結束),就像tcp的狀態機,時鐘和網路包都是它的輸入,如果不能處理輸入,那你做出來的東西只會自顧自的在屏幕上動來動去罷了。5. 針對實現停止,有三種做法,一種是節點前判斷,一種是行為樹跑完後,都要跑一個通用的狀態機;第二種是增加RESET整棵樹的操作;第三種是通用狀態機來處理任務改變的消息,一旦改變就複位樹,或者調用一顆新的樹,比如你把「巡邏」,「逃避」,「進攻」,寫成了三顆不同的行為樹,相當於一個「高級狀態」來用。
請訪問行為樹的基本概念及進階獲取更新。
行為樹,英文是Behavior Tree,簡稱BT,是由行為節點組成的樹狀結構:
對於FSM,每個節點表示一個狀態,而對於BT,每個節點表示一個行為。同樣是由節點連接而成,BT有什麼優勢呢?
在BT中,節點是有層次(Hierarchical)的,子節點由其父節點來控制。每個節點的執行都有一個結果(成功Success,失敗Failure或運行Running),該節點的執行結果都由其父節點來管理,從而決定接下來做什麼,父節點的類型決定了不同的控制類型。節點不需要維護向其他節點的轉換,節點的模塊性(Modularity)被大大增強了。實際上,在BT里,由於節點不再有轉換,它們不再是狀態(State),而是行為(Behavior)。
由此可見,BT的主要優勢之一就是其更好的封裝性和模塊性,讓遊戲邏輯更直觀,開發者不會被那些複雜的連線繞暈。
一個例子Permalink
上圖中,3號Sequence節點有3個子節點,分別是:
- 4號Condition節點
- 5號Action節點
- 6號Wait節點
而3號節點的父節點是2號的Loop節點。
先補充下各節點類型的執行邏輯(詳見節點說明):
- 序列(Sequence)節點:順序執行所有子節點返回成功,如果某個子節點失敗返回失敗。
- 循環(Loop)節點:循環執行子節點到指定次數後返回成功,如果循環次數為-1,則無限循環。
- 條件(Condition)節點:根據條件的比較結果,返回成功或失敗。
- 動作(Action)節點:根據動作結果返回成功,失敗,或運行。
- 等待(Wait)節點:當指定的時間過去後返回成功。
執行說明Permalink
- 如果4號條件節點的執行結果是成功,其父節點3號節點則繼續執行5號節點,如果5號動作節點返回成功,則執行6號等待節點,如果6號節點返回成功,則3號節點全部執行完畢且會返回成功,那麼2號節點繼續下個迭代。
- 如果4號條件節點的執行結果是失敗,其父節點3號節點則返回失敗不再繼續執行子節點,並且2號節點繼續下個迭代。
進階Permalink
聰明的讀者可能會問,上面的例子中只講了成功或失敗的情況,但如果動作要持續一段時間呢?如果5號節點,Fire需要持續一段時間呢?
- 節點的執行結果可以是「成功」,「失敗」,或「運行」。
- 對於持續運行一段時間的Fire動作,其執行結果持續返回「運行」,結束的時候返回「成功」。
- 對於持續運行一段時間的Wait動作,其執行結果持續返回「運行」,當等待時間到達的時候返回「成功」。
當節點持續返回「運行」的時候,BT樹的內部「知道」該節點是在持續「運行」的,從而在後續的執行過程中「直接」繼續執行該節點,而不需要從頭開始執行,直到該運行狀態的節點返回「成功」或「失敗」,從而繼續後續的節點。從外面看,就像「阻塞」在了那個「運行」的節點上,其父節點就像不再管理,要一直等運行的子節點結束的時候,其父節點才再次接管
(請注意,這一段說明只是從概念上這樣講,概念上可以這樣理解,實際上即使運行狀態的節點每次執行也是要返回的,只是其返回值是運行,其父節點對於返回值是運行狀態的節點,將使其繼續,所以看上去好像父節點不再管理。)。
另一個例子Permalink
如上圖,為了清晰說明運行狀態,來看另一個例子。在這個例子中,Condition,Action1,Action3是3個函數。
- 0號節點是個Loop節點,循環3次。
- 1號節點是個Sequence節點
- 2號節點模擬一個條件,直接返回成功。
- 3號節點Action1是一個動作,直接返回成功。
- 4號節點Action3同樣是一個動作,返回3次運行,然後返回成功。
其代碼如下:
bool CBTPlayer::Condition()
{
m_Frames = 0;
cout &<&< " Condition
";
return true;
}
behaviac::EBTStatus CBTPlayer::Action1()
{
cout &<&< " Action1
";
return behaviac::BT_SUCCESS;
}
behaviac::EBTStatus CBTPlayer::Action3()
{
cout &<&< " Action3
";
m_Frames++;
if (m_Frames == 3)
{
return behaviac::BT_SUCCESS;
}
return behaviac::BT_RUNNING;
}
而執行該BT樹的C++代碼如下:
int frames = 0;
behaviac::EBTStatus status = behaviac::BT_RUNNING;
while (status == behaviac::BT_RUNNING)
{
cout &<&< " frame " &<&< ++frames &<&< std::endl;
status = g_player-&>btexec();
}
上面的執行行為樹的代碼就如同遊戲更新部分。status = g_player-&>btexec()是在遊戲的更新函數(update或tick)里,需要每幀調用。
特別的,對於運行狀態,即使運行狀態概念上講是「阻塞」在節點,但是依然是每幀需要調用btexec,也就是說,其節點依然是每幀都在運行,只是下一幀是繼續上一幀,從而表現的是運行狀態,在其結束之前,其父節點不會把控制轉移給其他後續節點。這裡的「阻塞」並非真的被阻塞,並非後續的代碼(上面的other codes部分)不會被執行。status = g_player-&>btexec()後面如果有代碼,依然被執行。
執行結果會是個什麼樣的輸出呢?
第1幀:
2號節點Condition返回「成功」,繼續執行3號Action1節點,同樣返回「成功」,接續執行4號Action3,返回「運行」。
第2幀:
由於上一幀4號Action3返回「運行」,直接繼續執行4號Action3節點。
第3幀:
由於上一幀4號Action3返回「運行」,直接繼續執行4號Action3節點。
同樣需要注意的是,2號Condition節點不再被執行。
而且,本次Action3返回「成功」,1號Sequence節點返回成功。0號Loop節點結束第1次迭代。
第4幀:
Loop的第2次迭代開始,就像第1幀的執行。
再進階Permalink
又有聰明的讀者要問了,持續返回「運行」狀態的節點固然優化了執行,但其結果就像「阻塞」了BT的執行一樣,如果發生了其他「重要」的事情需要處理怎麼辦?
在behaviac里至少有多種辦法。
使用前置
每個節點都可以添加前置附件或後置附件。
上圖的action節點添加了一個前置,兩個後置。
可以添加前置附件,並且「執行時機」設為Update或Both,則在每次執行之前都會先執行前置里配置的條件。
使用Parallel節點Permalink
如上圖,可以使用Parallel節點來「一邊檢查條件,一邊執行動作」,該條件作為該動作的「Guard」條件。當該條件失敗的時候來結束該處於持續運行狀態的動作節點。
使用SelectorMonitor節點Permalink
- SelectorMonitor是一個動態的選擇節點,和Selector相同的是,它選擇第一個success的節點,但不同的是,它不是只選擇一次,而是每次執行的時候都對其子節點進行選擇。如上圖所示,假若它選擇了下面有True條件的那個節點(節點7)並且下面的1號Sequence節點在運行狀態,下一次它執行的時候,它依然會去檢查上面的那個8號條件的子樹,如果該條件為真,則終止下面的運行節點而執行9號節點。
- WithPrecondition有precondition子樹和action子樹。只有precondition子樹返回success的時候,action子樹才能夠被執行。
使用Event子樹Permalink
任何一個BT都可以作為事件子樹,作為event附加到任何的一個節點上(用滑鼠拖動BT到節點)。當運行該BT的時候,如果發生了某個事件,可以通過Agent::FireEvent來觸發該事件,則處於running狀態的節點,從下到上都有機會檢查是否需要響應該事件,如果有該事件配置,則相應的事件子樹就會被觸發。請參考behaviac的相關文檔獲取詳細信息。
總結Permalink
行為樹的基本概念:
- 執行每個節點都會有一個結果(成功,失敗或運行)
- 子節點的執行結果由其父節點控制和管理
- 返回運行結果的節點被視作處於運行狀態,處於運行狀態的節點將被持續執行一直到其返回結束(成功或失敗)。在其結束前,其父節點不會把控制轉移到後續節點。
其中理解運行狀態是理解行為樹的關鍵,也是使用好行為樹的關鍵。
其他Permalink
上文另一個例子中「demo_running」的例子在安裝包及源碼里都有提供。最好查看源碼,編譯運行,自行嘗試體會。
可以查看目錄說明
請指定demo_running作為參數或不指定任何參數運行demo_running:
源碼及示例下載地址:Tencent/behaviac
請訪問行為樹的基本概念及進階獲取更新。
騰訊的behaviortree裡面有解決方法。selectorloop結合withprecondition就可以解決了比如說樓主的例子可以改為:
root
\_ selectorloop
\__ withprecondition
| \_ condition(是否發現敵人)
| |_ action(攻擊敵人)
\_ withprecondition
\_condition(是否可以巡邏)
\_ moveToA(如果此節點處於running,戰鬥節點豈不無法被執行???)
這樣基本上就能實現moveToA過程中的打斷。
selectorloop與selector的區別就在於每次執行的時候,還會對其他節點進行選擇。
在這個例子中就是moveToA的過程中,AI還會檢查是否發生敵人,如果發現就會攻擊敵人
#我想問,節點running狀態的引入是為了解決什麼問題?為什麼不每次都top-down執行所有節點?#[引用]
——————————————————————————————————————————本人使用行為樹一段時間,也算是小菜級別的,看到樓主這個問題,也來湊一下熱鬧,把自己的遇到的坑和得到的一些理解和樓主分享一下。行為樹用於遊戲,功能實現可以說是第一位的,但是性能效率也不能輸於功能。如果每次執行行為樹都top-down那麼,如果我們遍歷的節點個數大約應該是1/2 * N。如果樹的節點比較多,且之前的節點判斷結果等待都需要時間,比如0.5秒[且這種節點又比較多,多麼糟糕的假設,可是現實中就會遇到],那麼這種top-down方式就會造成明顯的效率降低,如果我們給常用的節點一個running狀態,那麼下一次直接就執行它,不在遍歷先前節點狀態,那麼效率是十分可觀的。所以行為樹的亮點之一就是running狀態的使用。光是理解這個狀態還是不行的,如果一個節點一直是running,那麼這個樹就沒辦法執行其他的節點了,所以,合理的行為樹應該是在需要長時間執行的時候,那麼這個動作將是一直running狀態的,比如某個小兵一直打怪[此間執行打怪action,此action返回running],但是如果小兵血量偏低,或者接到其他的命令時,就不能讓打怪Action返回running了,應該返回success或者fail。那麼這個小兵的行為將會根據新狀態再在行為樹里選擇一個合適的動作進行執行,比如逃跑Action,那麼其間逃跑action可以一直返回running。———————————————————————————————————————————如果是新手上手,也和樓主一樣,推薦用一下騰訊的開源的行為樹插件TencentOpen/behaviac · GitHub。裡面有一些demo,無論是unity,cocos還是SDL2.0.都是適用的,因為它現在主要支持兩種語言平台C#和C++。額。。。好像有點兒廢話了,想表達的是,它的編輯器有一個調試的功能,這樣更方便的調試程序,理解處於running和success等各種狀態後樹的執行步驟和方式。上傳兩個截圖。不然光說無意。圖a 這個是官網常式的調試斷點下的截圖,可以清晰的看到運行走的路徑再來一張
圖b.這個是官網的坦克大戰調試狀態下的行為樹執行狀態的圖。如果單步調試,你可以了解行為樹每一步的具體執行步驟,各種狀態下行為樹如何執行。以上都是官方demo的運行截圖。感覺回答的有點兒亂,但是主要的要點感覺已經提及,希望有所幫助。歡迎拍磚。也寫過behavior tree,聊聊對behavior tree(BT)的理解,希望能有點幫助。
BT的定義並不嚴格,甚至不能被稱之為一個演算法,只是定義了一種邏輯的組織和執行方式。網上大量關於behavior tree的文章,每個版本具體到定義節點的時候,都多少有點出入,如果在aigamedev上挖掘過BT相關的東西,也應該發現這東西其實是open to intepretation的,從演算法角度非常不嚴謹。甚至BT最初的設計目標也比較模糊,有的是為了呈現一種所謂emergent behavior,有的就是為了高效組織寫死的腳本。
正因為這種定義的不準確性,很多hack和heurstics就應運而生,基本上是看到需要啥就會加點啥,而後果有時候未必能夠很明顯的感覺到。而你說的running節點的這種行為,就是一個常用「優化」。它的後果也確實如你所說,而為了克服這個後果,如 @伍一峰 所說的,又會加一些奇怪的東西進來。
BT遠不是遊戲AI的silver bullet,甚至在很多項目上根本就不合適。對於它的利弊可以參考 Artificial Intelligence for Games的相關章節,也推薦去aigamedev上挖掘一下相關的長篇討論。「打斷」子流程,實現的方式很多種。可以規劃一種名為parallel的組合結點,並發地執行所有子結點(單幀內並行),能實現「打斷」。或者行為結點可以支持返回Continue,也能實現。最近剛寫了篇關於行為樹的博客, 漫談遊戲中的人工智慧
我先來回答題主的疑惑,為什麼你的行為樹卡在了遊走那裡。
因為你的AI層和行為層沒有分開來,比如說你沒有發現敵人,進入到遊走,那麼下層應該有一個狀態機,你把狀態切成遊走就行,而不是把遊走的邏輯也寫進AI層。你在行為層遊走的同時,AI層仍然可以在固定的時間間隔後調用行為樹,如果還是決定要遊走,那麼不切換狀態,如果發現敵人,再切到攻擊狀態。很多行為樹介紹的文章都喜歡舉AI的例子,但是你要仔細看一下這些例子,比如說使用行為樹(Behavior Tree)實現遊戲AI,裡面的行為節點都是唯一的節點,不會出現一個順序節點下面兩個行為節點的事情,這些節點的實際含義其實是切到對應的狀態,而不是真實的在這裡就開始做這件事情。
題主順便可以看看這個回答:即時戰略遊戲(比如 WAR3)的 AI 是怎樣實現的?
然後行為樹為什麼要running狀態呢?因為加上了running,就可以和狀態機等價了。仍舊使用題主的例子,如果你已經改寫了代碼,把AI層和行為層分離了開來,那麼下一層級其實可以不用狀態機,用行為樹也行,實際上代碼都有了,就是seq下面的moveToA和moveToB。謝謝邀請
1. 為什麼不每次都top-down執行所有節點?
由於行為樹每個節點都可能存在許多條件測試,而某些測試可能計算量比較大,所以有一些行為樹框架就選擇不從root重新開始檢測。2. 豈不是無法實現「打斷」現有邏輯的需求?
Unity上的一個行為樹框架Behavior Designer為了實現「打斷」,引入了conditional abort的概念,也就是設置了abort的節點將會每次update都進行條件測試 [1]。Unreal 4也是這麼乾的 [2]。Reference:[1] Behavior Designer Documentation: Opsive.com :: Behavior Designer[2] How Unreal Engine 4 Behavior Trees Differ: https://docs.unrealengine.com/latest/INT/Engine/AI/BehaviorTrees/HowUE4BehaviorTreesDiffer/index.html什麼叫狀態機?寫代碼本身就是實現一個有限狀態機。我們天天都在做狀態機。行為樹,樹比圖簡單,理想化的模型而已,實際應用,往往因為一個邏輯上的關聯就打破了這種樹的模型。實際的模型,往往都是圖,彼此之間都有關聯,無法簡單切割。如果沒有明確的抽象以及普適的應用場景,這個概念就是無用的。工程重實用,有些學院派的概念聽起來很美,其實跟項目經理的ppt差不多。搞到最後,還是得寫代碼,不可能通過一個行為樹編輯器就可以實現ai。
如果是想實現巡邏的同時發現敵人並攻擊,這個結構顯然是實現不了。
前段時間弄了一個,寫了個總結:BehaviourTree AI 行為樹AI 實現的一些總結思考
推薦閱讀: