AI處理是網(wǎng)游服務器邏輯層重要的一塊，也是耗CPU最多的一塊，剛剛在網(wǎng)上看到了這篇文章，挺有意思，轉(zhuǎn)來大家一起分享。
原文地址：http://blog.csdn.net/akara/article/details/6084786
談到游戲AI，很明顯智能體擁有的知識條目越多，便顯得更智能，但維護
龐大數(shù)量的知識條目是個噩夢：使用有限狀態(tài)機(FSM)，分層有限狀態(tài)機(HFSM)，
決策樹(Decision Tree)來實現(xiàn)游戲AI總有那么些不順意。
試試Next-Gen AI的 行為樹(Behavior Tree) 吧。
雖說Next-Gen AI，但距其原型提出已有約10年時間，而Halo系列(HFSM like)，
Spore，Crysis 2，Red Dead Redemption等早已用行為樹作為它們的AI結(jié)構(gòu)。
如從未接觸，那wikipedia(http://en.wikipedia.org/wiki/Behavior_Trees)
絕對是入門好資料。
---------------------------------------------------------------------
先貼本文最具價值圖(配色可花了不少時間)
為顯美觀：BT被橫放，Node層次被刻意減少，Dec被刻意安插，Cond被刻意捏造。
PS：其實真正的高效的Node Group剔除應多加一層Sequence Node。
---------------------------------------------------------------------
行為樹(Behavior Tree) 具有如下的特性：
它只有4大類型的Node：
* Composite Node
* Decorator Node
* Condition Node
* Action Node
任何Node被執(zhí)行后，必須向其Parent Node報告執(zhí)行結(jié)果：成功 / 失敗。
這簡單的成功 / 失敗匯報原則被很巧妙地用于控制整棵樹的決策方向。
---------------------------------------------------------------------
先看Composite Node，其實它按復合性質(zhì)還可以細分為3種：
* Selector Node
當執(zhí)行本類型Node時，它將從begin到end迭代執(zhí)行自己的Child Node：
如遇到一個Child Node執(zhí)行后返回True，那停止迭代，
本Node向自己的Parent Node也返回True；否則所有Child Node都返回False，
那本Node向自己的Parent Node返回False。
* Sequence Node
當執(zhí)行本類型Node時，它將從begin到end迭代執(zhí)行自己的Child Node：
如遇到一個Child Node執(zhí)行后返回False，那停止迭代，
本Node向自己的Parent Node也返回False；否則所有Child Node都返回True，
那本Node向自己的Parent Node返回True。
* Parallel Node
平行執(zhí)行它的所有Child Node。
而向Parent Node返回的值和Parallel Node所采取的具體策略相關(guān)：
Parallel Selector Node: 一False則返回False，全True才返回True。
Parallel Sequence Node: 一True則返回True，全False才返回False。
Parallel Fall On All Node: 所有False才返回False，否則返回True。
Parallel Succeed On All Node: 所有True才返回True，否則返回False。
Parallel Hybird Node: 指定數(shù)量的Child Node返回True或False后才決定結(jié)果。
Parallel Node提供了平行的概念。
不需要像Selector/Sequence那樣預判哪個Child Node應擺前，哪個應擺后，
常見情況是：
(1)用于平行掛接多棵Action子樹。
(2)在Parallel Node下掛一棵子樹，并掛上多個Condition Node，
以提供實時性和性能。
Parallel Node增加方便性的同時，也增加實現(xiàn)和維護復雜度。
PS：上面的Selector/Sequence準確來說是Liner Selector/Liner Sequence。
AI術(shù)語中稱為strictly-order：按既定先后順序迭代。
Selector和Sequence可以進一步提供非線性迭代的加權(quán)隨機變種。
Weight Random Selector Node提供每次執(zhí)行不同F(xiàn)irst True Child Node的功能。
Weight Random Probability Node提供每次挑選唯一一個Node的功能。
Weight Random Sequence Node則提供每次不同的迭代順序。
AI術(shù)語中稱為partial-order，能使AI避免總出現(xiàn)可預期的結(jié)果。
---------------------------------------------------------------------
再看Decorator Node，它的功能正如它的字面意思：它將它的Child Node執(zhí)行
后返回的結(jié)果值做額外處理后，再返回給它的Parent Node。很有些AOP的味道。
比如Decorator Not/Decorator FailUtil/Decorator Counter/Decorator Time...
更geek的有Decorator Log/Decorator Ani/Decorator Nothing...
---------------------------------------------------------------------
然后是很直白的Condition Node，它僅當滿足Condition時返回True。
---------------------------------------------------------------------
最后看Action Node，它完成具體的一次(或一個step)的行為，視需求返回值。
而當行為需要分step/Node間進行時，可引入Blackboard進行簡單數(shù)據(jù)交互。
---------------------------------------------------------------------
整棵行為樹中，只有Condition Node和Action Node才能成為Leaf Node，而也
只有Leaf Node才是需要特別定制的Node；Composite Node和Decorator Node均
用于控制行為樹中的決策走向。(所以有些資料中也統(tǒng)稱Condition Node和Action
Node為Behavior Node，而Composite Node和Decorator Node為Decider Node。)
更強大的是可以加入Stimulus和Impulse，通過Precondition來判斷masks開關(guān)。
通過上述的各種Nodes幾乎可以實現(xiàn)所有的決策控制：if, while, and, or,
not, counter, time, random, weight random, util...
---------------------------------------------------------------------
總的來說，行為樹具有如下幾種優(yōu)點，確實是實現(xiàn)AI框架的利器，甚至是一種
通用的可維護的復雜流程管理利器：
> 靜態(tài)性
越復雜的功能越需要簡單的基礎(chǔ)，否則最后連自己都玩不過來。
靜態(tài)是使用行為樹需要非常著重的一個要點：即使系統(tǒng)需要某些"動態(tài)"性。
其實諸如Stimulus這類動態(tài)安插的Node看似強大，
但卻破壞了本來易于理解的靜態(tài)性，弊大于利。
Halo3相對于Halo2對BT AI的一個改進就是去除Stimulus的動態(tài)性。
取而代之的做法是使用Behavior Masks，Encounter Attitude，Inhibitions。
原則就是保持全部Node靜態(tài)，只是根據(jù)事件和環(huán)境來檢查是否啟用Node。
靜態(tài)性直接帶來的好處就是整棵樹的規(guī)劃無需再運行時動態(tài)調(diào)整，為很多優(yōu)化
和預編輯都帶來方便。
> 直觀性
行為樹可以方便地把復雜的AI知識條目組織得非常直觀。
默認的Composite Node的從begin往end的Child Node迭代方式就像是處理一個
預設(shè)優(yōu)先策略隊列，也非常符合人類的正常思考模式：先最優(yōu)再次優(yōu)。
行為樹編輯器對優(yōu)秀的程序員來說也是唾手可得。
> 復用性
各種Node，包括Leaf Node，可復用性都極高。
實現(xiàn)NPC AI的個性區(qū)別甚至可以通過在一棵共用的行為樹上不同的位置來
安插Impulse來達到目的。
當然，當NPC需要一個完全不同的大腦，比如70級大BOSS，
與其絞盡腦汁在一棵公用BT安插Impulse，不如重頭設(shè)計一棵專屬BT。
> 擴展性
雖然上述Node之間的組合和搭配使用幾乎覆蓋所有AI需求。
但也可以容易地為項目量身定做新的Composite Node或Decorator Node。
還可以積累一個項目相關(guān)的Node Lib，長遠來說非常有價值。