作者developers (戒 定 慧)
看板GameDesign
標題[程式] 行為樹 behavior tree
時間Sun Aug 19 10:25:30 2012
小弟目前已在遊戲產業工作二年
敝公司主要是用unity引擎來開發遊戲
小弟的工作主要是寫程式
為了把遊戲的架構流程設計視覺化並且重複使用
我們使用一個model叫behavior tree
它其實有點類似state machine
並且有階層的概念
因此它又叫hierarchical state machine
它最原先的目的是被用來設計AI character的行為
因此叫行為樹
Halo這個遊戲正是使用行為樹來設計AI
這裡有一個大陸人寫的簡介
http://blog.csdn.net/akara/article/details/6084786
目前市面上似乎有二到三個behavior tree library 的plugin
可以在unity store裡面找到
我們自己當初是跟另一間小公司買他們的bt library
但他們的library並沒有支援parallel node
(這個部分應該是整個bt library最難實現的部分)
不知道板上有人也在用這個概念設計AI遊戲嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 50.140.5.33
1F：推 cowbaying:要平行只能加個積分制的東西 08/19 13:19
2F：→ cowbaying:要平行只能加個積分制的東西node 設定事件積分 08/19 13:20
3F：→ cowbaying:一次執行所有node 08/19 13:20
沒錯，那是基本的概念
我的實現方式是使每個child node都用一條獨立的thread來執行
一次執行所有node 然後記錄所有child node的回傳狀態
再根據所有狀態的總合來判斷是否可以往上層回傳結果(SUCCESS/FAILURE)
或是再要求新的執行來執行那些回傳EXECUTING的node
如果整個tree中只有一層的parallel node
那實現起來並不困難
真正困難的是當整個tree中有"多層的parallel node"
並且每個child node都有三種回傳結果
SUCCESS/FAILURE: 結果確定，不須再執行
EXECUTING: 要求再執行一次
這會使得parallel node 裡的critical section設計變的相當複雜
因為在最底層的某一個node的執行thread可能穿越中間多層的parallel node
到上層某一個parallel node的critical section
如何設計不同的條件來對應每條thread隨機進入critical section的順序
是最困難的部分
※ 編輯: developers 來自: 50.140.5.33 (08/19 23:43)
4F：推 littleshan:你需要的是「邏輯上的平行」而不是「時間上的平行」 08/20 14:19
5F：→ littleshan:可以考慮把 thread 改成 coroutine 08/20 14:19
6F：→ littleshan:這樣就避開許多 race condition 造成的 bug 08/20 14:20
用coroutine的確是比較快的方法
而且在unity裡，所有的Update function are getting called sequentially
即使我的行為樹dll(用c++寫成的dll當成plugin)是時間上的平行
最後指令傳到unity裡
全部都變sequential的東西
因為unity並不支援concurrency，也不是thread save
所以不管是用邏輯上的平行，或是時間上的平行……都沒差
但我的想法是
寫一個真正是時間上平行的行為樹
以後可以支援那些有threading的引擎
但是也相對比較困難就是了
※ 編輯: developers 來自: 76.108.235.49 (08/23 11:23)
7F：→ cowbaying:時間上真正要平行 首先機器要能夠這麼做才行吧 08/23 19:40
目前市面上多核的處理器都有支援平行處理
時間上的平行早已經是主流
當cpu的極速到達瓶頸無法再上升時
就是往橫向發展
※ 編輯: developers 來自: 76.108.235.49 (08/30 10:34)
8F：→ cowbaying:那如果同時有100個事件要判斷 你要幾核的電腦? 08/30 12:01
9F：→ cowbaying:目前都還是以多執行緒為主 08/30 12:03
要開100條thread不是問題
thread數目的上限是受限於address space的大小
如果能夠增加每條process裡的address space
就能增加thread的數目
根據小弟之前實驗的結果
在Windows7 intel i7 990 cpu 可用記憶體空間5G的電腦上
最多可以開到1411條thread
但小弟不知道如何修改address space 的大小
所以最多就是1411條
還請高人指點一下如何改address space
謝謝
※ 編輯: developers 來自: 98.77.182.140 (08/31 21:00)