游戲人工智能開(kāi)發(fā)決策之6種方法

1、游戲人工智能開(kāi)發(fā)之6種決策方法人工智能遵循著：感知->思考->行動(dòng)決策方法：有限狀態(tài)機(jī)（Finite-State Machines），分層狀態(tài)機(jī)（Hierarchical Finite-State Machines），行為樹（Behavior Trees），效用系統(tǒng)（Utility Systems），目標(biāo)導(dǎo)向型行動(dòng)計(jì)劃（Goal-Oriented Action  Planners），分層任務(wù)網(wǎng)絡(luò)（Hierarchical Task Networks）一、有限狀態(tài)機(jī)有限狀態(tài)機(jī)是目前游戲AI中最常見(jiàn)的行為模型。狀態(tài)機(jī)的代碼簡(jiǎn)單又快速，使用上強(qiáng)大、靈活、計(jì)算開(kāi)銷小。狀

2、態(tài)機(jī)的一個(gè)好處是可以可視化，如下圖所示：圖中有四個(gè)狀態(tài)：巡邏(patrol)，查看(investigate)，攻擊(attack)，逃走(flee)，我們把實(shí)心圓當(dāng)做初始狀態(tài)。簡(jiǎn)要過(guò)程：假設(shè)NPC士兵正在保衛(wèi)他的陣地，當(dāng)前狀態(tài)為巡邏，當(dāng)他聽(tīng)到什么動(dòng)靜時(shí)就會(huì)轉(zhuǎn)到查看狀態(tài)，跑到聲音源去查看，如果看到敵人就轉(zhuǎn)到攻擊狀態(tài)，如果沒(méi)看到過(guò)一段時(shí)間又會(huì)回到巡邏狀態(tài)。在攻擊狀態(tài)中如果血值低下就會(huì)進(jìn)入逃跑狀態(tài)。如果擊敗了敵人，又會(huì)回到巡邏狀態(tài)。狀態(tài)機(jī)狀態(tài)類的一個(gè)主要結(jié)構(gòu)如下，onEnter函數(shù)就相當(dāng)于unity中的Start()函數(shù)，在類開(kāi)始時(shí)調(diào)用，作為對(duì)舊狀態(tài)的過(guò)度和新?tīng)顟B(tài)產(chǎn)生的開(kāi)始，比如當(dāng)從巡邏轉(zhuǎn)向攻擊狀態(tài)

3、時(shí)，可以在攻擊狀態(tài)的開(kāi)始讓NPC大喊“發(fā)現(xiàn)敵人！進(jìn)攻！”等等。onUpdate()就相當(dāng)于unity中的Update(),你可以讓它每幀都執(zhí)行，或者幾秒鐘執(zhí)行一次，是循環(huán)執(zhí)行的，每次執(zhí)行時(shí)間間隔由你來(lái)決定。onExit()就是在退出一個(gè)狀態(tài)之前要執(zhí)行的，比如，殺死敵人之后由攻擊狀態(tài)轉(zhuǎn)向巡邏狀態(tài)之前，讓NPC做一個(gè)歡呼手勢(shì)并大叫勝利了。FSMTransition列表為將要轉(zhuǎn)到的所有可能的狀態(tài)。1. class FSMState2. 3.   virtual void onEnter();4.   virtual void onUpdate();5.

4、60; virtual void onExit();6.   list<FSMTransition> transitions;7. ;每個(gè)狀態(tài)還存儲(chǔ)著FSMTransition的類，代表能從當(dāng)前狀態(tài)可以轉(zhuǎn)到的狀態(tài)1. class FSMTransition2. 3.   virtual bool isValid();4.   virtual FSMState* getNextState();5.   virtual void onTransition();6. 當(dāng)轉(zhuǎn)換條件滿足時(shí)isValid(

5、)返回true，比如當(dāng)發(fā)現(xiàn)敵人NPC就從巡邏狀態(tài)轉(zhuǎn)到攻擊，getNextState()返回將要轉(zhuǎn)到的狀態(tài)，onTransition()是狀態(tài)之間轉(zhuǎn)換的過(guò)渡，和上面說(shuō)的onEnter()差不多。最后是有限狀態(tài)機(jī)類FiniteStateMachine1. class FiniteStateMachine2. 3.   void update();4.   list<FSMState> states;5.   FSMState* initialState;6.   FSMState* activeState;

6、7. 有限狀態(tài)機(jī)類包含一個(gè)包含所有狀態(tài)的列表states，initialState為初始狀態(tài)，activeState為當(dāng)前狀態(tài)。偽代碼如下：1. 在  activeState.transtitions中循環(huán)調(diào)用isValid()，檢測(cè)是否符合達(dá)到下一狀態(tài)的條件2. 如果符合轉(zhuǎn)換條件3. 調(diào)用activeState.on Exit()，退出當(dāng)前狀態(tài)4. 設(shè)置activeState 為 validTransition.getNextState()，把當(dāng)前狀態(tài)賦值為下一狀態(tài)5. 調(diào)用activeState.onEnter()，下一狀態(tài)的開(kāi)始6. 如果不符合轉(zhuǎn)換條件，調(diào)用activ

7、eState.onUpdate()，讓NPC執(zhí)行當(dāng)前狀態(tài)需要做的事在編寫有限狀態(tài)機(jī)的代碼只前最好畫一個(gè)上面的草圖，這樣既可以明確轉(zhuǎn)換關(guān)系，又可以不漏掉該有的狀態(tài)。二、分層有限狀態(tài)機(jī)有限狀態(tài)機(jī)雖然好，但是它有很大的缺點(diǎn)，當(dāng)狀態(tài)少的時(shí)候可以運(yùn)用自如，當(dāng)狀態(tài)多的時(shí)候10個(gè)以上就已經(jīng)結(jié)構(gòu)非常復(fù)雜，而且容易出錯(cuò)。如果我們讓NPC巡邏兩個(gè)地方，比如安全的室內(nèi)，和門口。如果我們想在一個(gè)狀態(tài)上附加一些狀況，例如當(dāng)NPC在巡邏時(shí)，讓他接一個(gè)電話然后再恢復(fù)巡邏，此時(shí)如果使用有限狀態(tài)機(jī)的話我們必須要新建一個(gè)打電話的狀態(tài)來(lái)做過(guò)渡，但是此時(shí)的巡邏有兩個(gè)，所以能接到電話的狀態(tài)也有兩個(gè)，然后加了兩個(gè)相同的狀態(tài)，很多這樣的重

8、復(fù)的小狀態(tài)使得狀態(tài)機(jī)越來(lái)越復(fù)雜。如下圖：這時(shí)，我們可以用分層有限狀態(tài)機(jī)來(lái)解決這個(gè)問(wèn)題，把多個(gè)狀態(tài)機(jī)歸為一層，如下圖，把巡邏安全處和門口歸為看守建筑，這樣我們只需要有一個(gè)打電話狀態(tài)就可以了。分層有限狀態(tài)機(jī)增加了一個(gè)滯后，在有限狀態(tài)機(jī)中并沒(méi)有，在一個(gè)普通的有限狀態(tài)機(jī)中，是從初始狀態(tài)開(kāi)始的，在分層有限狀態(tài)機(jī)中是一個(gè)嵌套的狀態(tài)。注意上圖有H的圈，代表歷史狀態(tài)（history state），當(dāng)我們第一次進(jìn)入嵌套狀態(tài)->看守建筑時(shí)，歷史狀態(tài)H表示為初始狀態(tài)，之后歷史狀態(tài)H表示為最近處在的一個(gè)狀態(tài)。在我們的例子中：初始狀態(tài)就是看守建筑，然后進(jìn)入看到手機(jī)按住這個(gè)嵌套，巡邏安全處是初始狀態(tài)。當(dāng)從巡邏安全處

9、轉(zhuǎn)換到巡邏門口這個(gè)狀態(tài)時(shí)，H歷史狀態(tài)就轉(zhuǎn)變?yōu)檠策夐T口狀態(tài)，此時(shí)來(lái)電話了，轉(zhuǎn)換到接電話狀態(tài)，接電話結(jié)束，我們回到嵌套狀態(tài)中的歷史狀態(tài)，此時(shí)為巡邏門口，可見(jiàn)H歷史狀態(tài)就是一個(gè)臨時(shí)的，便于嵌套外的狀態(tài)返回到之前的嵌套內(nèi)的小狀態(tài)，以不至于出錯(cuò)，或者換回了別的狀態(tài)，如果接完電話回到巡邏安全處，那就出大錯(cuò)了。分層有限狀態(tài)機(jī)，就這樣避免了重復(fù)狀態(tài)，可以實(shí)現(xiàn)更大的更復(fù)雜的狀態(tài)。實(shí)例：Halo2使用了這一技術(shù)，如下圖：可見(jiàn)：把使用手雷、掩蔽、防御歸為自衛(wèi)，交戰(zhàn)部分使用了多層嵌套，但是原理是一樣的，向尸體設(shè)計(jì)和搜查尸體歸為戰(zhàn)后處理。在撤退和閑置部分只有一個(gè)行為被嵌套，但是日后可以繼續(xù)添加行為，可擴(kuò)展性良好。至于如

10、何在嵌套的層里對(duì)行為進(jìn)行選擇，可以就按這個(gè)順序執(zhí)行，也可以加上權(quán)重優(yōu)先級(jí)，或者你想讓他執(zhí)行哪個(gè)通過(guò)代碼來(lái)控制。三、行為樹行為樹是樹型結(jié)構(gòu)的，每個(gè)節(jié)點(diǎn)都代表了一個(gè)行為，每個(gè)行為都可以有子行為。所有行為都有一個(gè)先決條件，就是產(chǎn)生的這些行為的條件。整個(gè)算法先從樹的根部開(kāi)始，然后開(kāi)始檢查每一個(gè)先決條件。樹的每一層只可以執(zhí)行一個(gè)行為，所以當(dāng)一個(gè)行為正在執(zhí)行，它的兄弟節(jié)點(diǎn)都不會(huì)被檢查，但是它們的子節(jié)點(diǎn)還是要檢查的。相反如果一個(gè)行為的先決條件當(dāng)前并不滿足，則跳過(guò)判斷它的子節(jié)點(diǎn)，繼續(xù)判斷它的兄弟節(jié)點(diǎn)。一個(gè)樹全部檢查完畢之后，決定執(zhí)行優(yōu)先級(jí)最大的，然后再依次執(zhí)行每個(gè)動(dòng)作。1. 使根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)2. 當(dāng)存在當(dāng)前

11、節(jié)點(diǎn)3. 判斷當(dāng)前節(jié)點(diǎn)的先決條件4. 如果先決條件返回true5. 把節(jié)點(diǎn)加到執(zhí)行清單6. 使子節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)7. 否則8. 使兄弟節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)9. 執(zhí)行執(zhí)行清單上的所有行為 不同于狀態(tài)機(jī)，行為樹是無(wú)狀態(tài)的，不需要記下之前執(zhí)行的行為，只是判斷行為該不該執(zhí)行。行為樹的節(jié)點(diǎn)之間是不相關(guān)的，刪除或增加節(jié)點(diǎn)，對(duì)其他節(jié)點(diǎn)都無(wú)影響。所以，可擴(kuò)展性也是行為樹的一個(gè)優(yōu)勢(shì)。另外還可以為決策樹添加靈活性與隨機(jī)性，父節(jié)點(diǎn)可以隨機(jī)決定是否檢查子節(jié)點(diǎn)。缺點(diǎn)：決策樹做的選擇并不一定是最優(yōu)的，結(jié)果也不一定是我們想要的。而且決策每次都要從根部往下判斷選擇行為節(jié)點(diǎn)，比狀態(tài)機(jī)要耗費(fèi)時(shí)間。每次決策都要經(jīng)過(guò)大量的條件判斷語(yǔ)句，會(huì)變

12、得非常慢。另外還有一個(gè)問(wèn)題，例如：一個(gè)農(nóng)民要收割作物，敵人出現(xiàn)了，農(nóng)民逃跑，逃出了距離敵人的一定范圍之后，又回去收割作物，走到敵人的范圍又逃出，這樣來(lái)回往復(fù)，是一個(gè)弊端，可以根據(jù)情況來(lái)寫代碼避免，否則會(huì)被玩家*的。四、效用系統(tǒng)人工智能的邏輯->電腦的邏輯，是基于簡(jiǎn)單的bool問(wèn)題，比如：“我能看到敵人嗎？”，“我有彈藥嗎”，是簡(jiǎn)單的是或者不是的問(wèn)題，所以做出的行為通常是極端化的，一個(gè)單一的行動(dòng)。比如：1. if (CanSeeEnemy()2. 3.   AttackEnemy();4. 5. if (OutOfAmmo()6. 7.   Relo

13、ad();8. 9. 即時(shí)有多條件的行為，bool判斷帶來(lái)的也是一個(gè)單一的行動(dòng)。10. if (OutOfAmmo() && CanSeeEnemy()11. 12.   Hide();13. 所以有些情況，只是做這些布爾判斷是不合適的，會(huì)遺漏很多情況，判斷也不妥當(dāng)。比如：我們可能需要同時(shí)考慮與敵人的距離、有多少?gòu)椝?、饑餓程度、HP值，等等。這些判斷條件能映射出許多動(dòng)作，比我們單一的判斷做不做這個(gè)動(dòng)作要好很多。utility-based system，基于效用的系統(tǒng)，會(huì)根據(jù)權(quán)重、比率、隊(duì)列和許多需要考慮的事項(xiàng)來(lái)做出最優(yōu)選擇，使AI比普通的行為樹更有頭腦。根據(jù)

14、上面的例子，使用效用系統(tǒng)我們的AI可以做出我們想要的動(dòng)作，并根據(jù)當(dāng)前情況做出不同強(qiáng)度的動(dòng)作，使AI真實(shí)、更具可能性，也不再是只有一個(gè)正確的選擇了。決策樹就是對(duì)AI說(shuō)，“只是你將要做的一個(gè)行為”，效用系統(tǒng)就是對(duì)AI說(shuō)：“這些是你可能要做的行為”Sims模擬人生的人工智能就是使用的效用系統(tǒng)（sims的人工智能讓我膜拜至今），在sims中，小人結(jié)合當(dāng)前環(huán)境和自身的狀態(tài)，來(lái)做出行動(dòng)的選擇。例如：小人“非常餓”結(jié)合環(huán)境“沒(méi)有食物”會(huì)比只有“有一點(diǎn)餓”更加吸引人的眼球。如果“有一點(diǎn)餓”小人會(huì)以接近“美食”為第一執(zhí)行行為。注意，這里的“美食（的美味程度）”、“食物很少（食物儲(chǔ)備程度）”、“一點(diǎn)餓（餓的程度）

15、”，都是一個(gè)有范圍的數(shù)值（常用的是0-1的浮點(diǎn)值）。當(dāng)需要選擇新的行為時(shí)，我們通過(guò)分?jǐn)?shù)（上面說(shuō)的各種程度）來(lái)選擇相對(duì)最優(yōu)的選擇，或者加上一個(gè)隨機(jī)值再選擇，使得接近優(yōu)選的幾個(gè)選擇都有一定幾率（幾率可根據(jù)所加隨機(jī)值決定）被選中。五、目標(biāo)導(dǎo)向型行動(dòng)計(jì)劃GOAP來(lái)源于STRIPS方法，這兩種都是讓AI創(chuàng)造他們自己的方法去解決問(wèn)題，我們提供給它一系列可能的動(dòng)作作為對(duì)這個(gè)世界的描述，和每個(gè)動(dòng)作使用的先決條件，和行動(dòng)帶來(lái)的影響。AI擁有一個(gè)初始狀態(tài)和他需要達(dá)到的目標(biāo)。有一組目標(biāo)，AI可以通過(guò)優(yōu)先級(jí)或當(dāng)前狀態(tài)選擇一個(gè)。計(jì)劃系統(tǒng)決定一個(gè)動(dòng)作序列來(lái)滿足當(dāng)前目標(biāo)，計(jì)劃出一個(gè)像路徑一樣的能最簡(jiǎn)單達(dá)到目標(biāo)狀態(tài)的動(dòng)作序列

16、。GOAP是一個(gè)反向鏈接搜索，從要實(shí)現(xiàn)的目標(biāo)開(kāi)始，找到什么動(dòng)作能實(shí)現(xiàn)目標(biāo)，在尋找剛才動(dòng)作的先決條件，一直往前推，知道達(dá)到你的當(dāng)前（初始）狀態(tài)。這種反向鏈接搜索替代了啟發(fā)式的前向鏈接搜索。偽代碼：1. 把目標(biāo)加到未解決事件列表2. 對(duì)于每個(gè)為解決事件（for）3. 移除這個(gè)為解決事件4. 找到達(dá)成事件的動(dòng)作5. 如果動(dòng)作的先決條件已經(jīng)滿足6. 增加動(dòng)作到計(jì)劃中7. 往回推需要達(dá)到先決條件的動(dòng)作到計(jì)劃中8. 否則9. 添加該先決條件到未解決時(shí)間中例如：我們建立一個(gè)NPC士兵，把它的目標(biāo)設(shè)為殺死其他敵人，我們?cè)O(shè)置它的目標(biāo)為Target.Dead。為了讓目標(biāo)去死，NPC必須要有一個(gè)武器用來(lái)射擊，這是一

17、個(gè)先決條件，但是現(xiàn)在NPC并沒(méi)有正在裝備的武器，NPC就需要執(zhí)行找到武器這個(gè)動(dòng)作，如果NPC有武器庫(kù)，他就會(huì)從武器庫(kù)中拿一個(gè)，如果病沒(méi)有武器庫(kù)，就需要尋路去找一個(gè)武器裝備了。得到武器裝備之后就要找到敵人，實(shí)現(xiàn)方式多種多樣，徒步尋找、或者NPC周圍有車也可以開(kāi)著車去尋找。我么發(fā)現(xiàn)，我們給NPC大量的動(dòng)作選擇，讓NPC自己決定該做什么，因而產(chǎn)生動(dòng)態(tài)不可預(yù)知又有趣的行為，而且表現(xiàn)得很自然，比開(kāi)發(fā)者創(chuàng)建行為好多了。六、分層任務(wù)網(wǎng)絡(luò)HTN也是尋找一個(gè)計(jì)劃來(lái)讓AI執(zhí)行，不同之處在于怎樣找出這個(gè)計(jì)劃。開(kāi)始擁有一個(gè)初始狀態(tài)和一個(gè)跟任務(wù)代表我們需要解決的問(wèn)題。原理是最高級(jí)的任務(wù)分解成更小的任務(wù)再繼續(xù)分解直到我們

18、解決問(wèn)題。每個(gè)高級(jí)任務(wù)都有很多方式被完成，當(dāng)前世界狀態(tài)決定高級(jí)任務(wù)要分解成哪組小任務(wù)。HTN與GOAP相反，HTN是前向鏈接搜索，是從當(dāng)前狀態(tài)一直推到目標(biāo)狀態(tài)，向前推直到問(wèn)題解決。世界狀態(tài)分散成幾種屬性，它的HP、精力，敵人的HP、相距距離，計(jì)劃根據(jù)這些來(lái)制定。我們有兩種任務(wù)：原始任務(wù)和復(fù)合任務(wù)。原始任務(wù)是可以只解決問(wèn)題的任務(wù)，也就是可以直接達(dá)到目標(biāo)的任務(wù)。在游戲中，它可以為開(kāi)火、裝填子彈、移動(dòng)到掩蔽物。這些人物可以影響世界狀態(tài)，開(kāi)火這個(gè)任務(wù)需要先有子彈，并執(zhí)行裝填子彈這個(gè)任務(wù)。復(fù)合任務(wù)是高級(jí)別的任務(wù)，可以看作方法。一個(gè)方法是一組任務(wù)可以完成復(fù)合任務(wù)，這一組任務(wù)是由先決條件決定的。復(fù)合任務(wù)讓HTN推斷出世界并且決定該做什么動(dòng)作。使用復(fù)合任務(wù)，我們就能構(gòu)建一個(gè)HTN域，這個(gè)域是一大層任務(wù)，