游戲AI行為決策——GOAP（目標(biāo)導(dǎo)向型行為規(guī)劃）

【USparkle專欄】如果你深懷絕技，愛“搞點(diǎn)研究”，樂于分享也博采眾長(zhǎng)，我們期待你的加入，讓智慧的火花碰撞交織，讓知識(shí)的傳遞生生不息！

這是侑虎科技第1889篇文章，感謝作者狐王駕虎供稿。歡迎轉(zhuǎn)發(fā)分享，未經(jīng)作者授權(quán)請(qǐng)勿轉(zhuǎn)載。如果您有任何獨(dú)到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群：793972859）

作者主頁(yè)：

https://home.cnblogs.com/u/OwlCat

一、前言

像先前提到的有限狀態(tài)機(jī)、行為樹、HTN，它們實(shí)現(xiàn)的AI行為，雖說能針對(duì)不同環(huán)境作出不同反應(yīng)，但應(yīng)對(duì)方法是寫死了的。有限狀態(tài)機(jī)終究是在幾個(gè)狀態(tài)間進(jìn)行切換、行為樹也是根據(jù)提前設(shè)計(jì)好的樹來搜索……你會(huì)發(fā)現(xiàn)，游戲AI角色表現(xiàn)出的智能程度，終究與開發(fā)者的設(shè)計(jì)結(jié)構(gòu)有關(guān)，就有限狀態(tài)機(jī)而言，各個(gè)狀態(tài)如何切換很大程度上就影響了AI智能的表現(xiàn)。

那有沒有什么決策方法，能夠僅需設(shè)計(jì)好角色需要的動(dòng)作，而它自己就能合理決定要選擇哪些動(dòng)作完成目標(biāo)呢？這樣的話，角色AI的行為智能程度會(huì)更上一層樓，畢竟它不再被寫死的決策結(jié)構(gòu)束縛；我們?cè)谔砑痈郃I行為時(shí)，也可以簡(jiǎn)單地直接將它放在角色需要的動(dòng)作集里就好，減少了工作量，不必像行為樹那樣，還要考慮節(jié)點(diǎn)間的連接。

沒錯(cuò)，GOAP（目標(biāo)導(dǎo)向型行為規(guī)劃）就可以做到。但請(qǐng)注意，并不是說GOAP就比其它決策方法好，后面也會(huì)提到它的缺點(diǎn)。選擇何種決策方法還得根據(jù)實(shí)際項(xiàng)目和自身需求。

PS：本教程需要你具備以下前提知識(shí)：

1. 知道數(shù)據(jù)結(jié)構(gòu)、堆/優(yōu)先隊(duì)列、棧、圖。

2. 知道A星尋路的流程，如不了解可看此視頻[1]。

3. 基本的位運(yùn)算與位存儲(chǔ)（能做到理解Unity中的Layer和LayerMask的程度就行）。

二、運(yùn)行邏輯

我們來看個(gè)簡(jiǎn)單的尋路問題：你能找到從A到B的最短路線嗎？注意，道路是單向的。

聰明如你，這并不難找到：

現(xiàn)在，加大難度，假設(shè)每條道路口都有一個(gè)門，紅色表示門關(guān)上了，藍(lán)色表示門開著，你還能找出可達(dá)成的最短A到B路線嗎？

同樣不難：

這樣就足夠了，GOAP的規(guī)劃就是這么一個(gè)過程。只是把每個(gè)節(jié)點(diǎn)都當(dāng)成一個(gè)狀態(tài)，每條道路都當(dāng)作一個(gè)動(dòng)作、道路長(zhǎng)度作為動(dòng)作代價(jià)、路口的門作為動(dòng)作執(zhí)行條件，然后像你這樣尋找出一條可以執(zhí)行的最短「路線」，并記錄下途徑的道路（注意，不是節(jié)點(diǎn)），這樣就得到了「動(dòng)作序列」，再讓AI角色逐一執(zhí)行。GOAP中的圖會(huì)長(zhǎng)成下面這樣（只畫出了一條路的樣子，但相信你們能舉一反三的）：

GOAP就是在不斷執(zhí)行「從現(xiàn)有狀態(tài)到目標(biāo)狀態(tài)」，上圖中的「現(xiàn)有狀態(tài)」和「目標(biāo)狀態(tài)」分別就是「餓」和「飽」。請(qǐng)注意，雖說用了不同形狀，但中間的那些橢圓節(jié)點(diǎn)，比如「在上網(wǎng)」，也是和「餓」、「飽」同類別的存在。也就是說「在上網(wǎng)」也可以作為現(xiàn)有狀態(tài)或目標(biāo)狀態(tài)。

可想而知，只要狀態(tài)夠多，動(dòng)作夠多，AI就能做出更復(fù)雜的動(dòng)作。雖說這對(duì)其它決策方法也成立，但GOAP不需要我們手動(dòng)設(shè)置各動(dòng)作、狀態(tài)之間的關(guān)系，它能自行規(guī)劃出要做的一系列動(dòng)作，更省事且更智能，甚至可以規(guī)劃出超出原本設(shè)想但又合理的動(dòng)作序列。

希望我講明白了它的運(yùn)作（如果還是感覺有點(diǎn)不懂，可以看看這個(gè)視頻[2]），下面一起來實(shí)現(xiàn)一個(gè)簡(jiǎn)單的GOAP進(jìn)一步了解吧！順帶提一下，在Unity資源商店有免費(fèi)的GOAP插件，并且做了可視化處理以及多線程優(yōu)化，各位真的想將GOAP運(yùn)用于項(xiàng)目的話，更推薦去學(xué)習(xí)使用成熟的插件。

三、代碼實(shí)現(xiàn)

本文「世界狀態(tài)」的實(shí)現(xiàn)參考了GitHub上一C語(yǔ)言版本的GOAP[3]。

1. 世界狀態(tài)

所謂「世界狀態(tài)」其實(shí)就是存儲(chǔ)所有的狀態(tài)放在一塊兒的合集。而狀態(tài)其實(shí)還有一個(gè)隱藏身份——動(dòng)作條件。是的，狀態(tài)也充當(dāng)了動(dòng)作的執(zhí)行條件，比如之前圖中的條件「有流量」，它其實(shí)也是一個(gè)狀態(tài)。

世界狀態(tài)會(huì)因自然因素變化，比如「飽」會(huì)隨著時(shí)間流逝而變「餓」；也會(huì)因角色自身的一些動(dòng)作導(dǎo)致變化，比如一個(gè)角色多運(yùn)動(dòng)，也會(huì)使「飽」變「餓」。

問題在于：

1. GOAP規(guī)劃需要時(shí)時(shí)獲取最新的狀態(tài)，才能保證規(guī)劃結(jié)果的合理性（否則餓暈了還想著運(yùn)動(dòng)）；

2. 「世界狀態(tài)」中有些狀態(tài)是「共享」的，比如之前說的時(shí)間，但還有一些狀態(tài)是私有的，比如「飽」，是我飽、你飽還是他飽？在一個(gè)合集里該如何區(qū)分？

如果你看過上一篇關(guān)于HTN的文章的話，你會(huì)發(fā)現(xiàn)這是如此的眼熟。不過沒看過也沒關(guān)系，我們將采取一種新的實(shí)現(xiàn)「世界狀態(tài)」的方法——原子表示。

PS：在傳統(tǒng)人工智能Agent中，對(duì)于環(huán)境的表示方式有三種：

1. 原子表示（Atomic）：就是單純描述某個(gè)狀態(tài)有無，通常每個(gè)狀態(tài)都只用布爾值（True/False）表示就可以，比如「有流量」。

2. 要素化表示（Factored）：進(jìn)一步描述狀態(tài)的具體數(shù)值，這時(shí)，狀態(tài)可以有不同的類型，可以是字符串、整數(shù)、布爾值……在HTN中，我們就是用這種方式實(shí)現(xiàn)的。

3. 結(jié)構(gòu)化表示（Structured）：再進(jìn)一步，每個(gè)狀態(tài)不但描述具體數(shù)值，還存儲(chǔ)于其它數(shù)據(jù)的連接關(guān)系，就像數(shù)據(jù)結(jié)構(gòu)中「圖」的節(jié)點(diǎn)那樣。

接下來將采用位存儲(chǔ)的方式進(jìn)行原子表示，因?yàn)榻柚贿\(yùn)算可以方便且高效地實(shí)現(xiàn)比較，還省空間。缺點(diǎn)就是有些難懂，所以，我希望你了解如int、long的二進(jìn)制存儲(chǔ)方式或者Unity中LayerMask，再來看以下內(nèi)容。當(dāng)然，這段代碼之后我也會(huì)做些舉例說明，這個(gè)類還繼承了三個(gè)接口，其用意也會(huì)在后面解釋：

using System; using System.Collections.Generic; ///  /// 用位表示的世界狀態(tài) ///  publicclassGoapWorldState : IAStarNode

 , IComparable

 , IEquatable

 {     publicconstint MAXATOMS = 64;//存儲(chǔ)的狀態(tài)數(shù)上限，由于用long類型存儲(chǔ)，最多就是64（long類型為64位整數(shù)）     publiclong Values//世界狀態(tài)值     {         get => values;         set => values = value;     }     publiclong DontCare//標(biāo)記未被使用的位     {         get => dontCare;         set => dontCare = value;     }     publiclong Shared => shared;//判斷共享狀態(tài)位     public GoapWorldState Parent { get; set; }     publicfloat SelfCost { get; set; }     publicfloat GCost { get; set; }     publicfloat HCost { get; set; }     publicfloat FCost => GCost + HCost;     privatereadonly Dictionary

 namesTable;//存儲(chǔ)各個(gè)狀態(tài)名字與其在values中的對(duì)應(yīng)位，方便查找狀態(tài)     privateint curNamsLen;//存儲(chǔ)的已用狀態(tài)的長(zhǎng)度     privatelong values;     privatelong dontCare;     privatelong shared;     ///      /// 初始化為空白世界狀態(tài)     ///      public GoapWorldState()     {         //賦值0，可將二進(jìn)制位全置0；賦值-1，可將二進(jìn)制位全置1         namesTable = new Dictionary

 ();         values = 0L; //全置0，意為世界狀態(tài)默認(rèn)為false         dontCare = -1L; //全置1，意為世界狀態(tài)的位全沒有被使用         shared = -1L; //將shard的位全置1         curNamsLen = 0;     }     ///      /// 基于某世界狀態(tài)的進(jìn)一步創(chuàng)建，相當(dāng)于復(fù)制狀態(tài)設(shè)置但清空值     ///      public GoapWorldState(GoapWorldState worldState)     {         namesTable = new Dictionary

 (worldState.namesTable);//復(fù)制狀態(tài)名稱與位的分配         values = 0L;         dontCare = -1L;         curNamsLen = worldState.curNamsLen;//同樣復(fù)制已使用的位長(zhǎng)度         shared = worldState.shared;//保留狀態(tài)共享性的信息     }     ///      /// 根據(jù)狀態(tài)名，修改單個(gè)狀態(tài)的值     ///      /// 狀態(tài)名     /// 狀態(tài)值     /// 設(shè)置狀態(tài)是否為共享     ///  修改成功與否     public bool SetAtomValue(string atomName, bool value = false, bool isShared = false)     {         var pos = GetIdxOfAtomName(atomName);//獲取狀態(tài)對(duì)應(yīng)的位         if (pos == -1) returnfalse;//如果不存在該狀態(tài)，就返回false         //將該位 置為指定value         var mask = 1L << pos;         values = value ? (values | mask) : (values & ~mask);         dontCare &= ~mask;//標(biāo)記該位已被使用         if (!isShared)//如果該狀態(tài)不共享，則修改共享位信息         {             shared &= ~mask;         }         returntrue;//設(shè)置成功，返回true     }     public void Clear()     {         values = 0L;         namesTable.Clear();         curNamsLen = 0;         dontCare = -1L;     }     ///      /// 通過狀態(tài)名獲取單個(gè)狀態(tài)在Values中的位，如果沒包含會(huì)嘗試添加     ///      /// 狀態(tài)名     ///  狀態(tài)所在位          private int GetIdxOfAtomName(string atomName)     {         if(namesTable.TryGetValue(atomName, outint idx))         {             return idx;         }         if(curNamsLen < MAXATOMS)         {             namesTable.Add(atomName, curNamsLen);             return curNamsLen++;         }         return-1;     }     //——————————三個(gè)接口需要實(shí)現(xiàn)的函數(shù)——————————     public float GetDistance(GoapWorldState otherNode)     {     }     public List   GetSuccessors(object nodeMap)     {     }     public int CompareTo(GoapWorldState other)     {     }     public bool Equals(GoapWorldState other)     {     }     public override int GetHashCode()     {     } }

我們以添加兩個(gè)狀態(tài)為例，相信看了這個(gè)，你會(huì)更容易理解相關(guān)函數(shù)的內(nèi)容。雖說總共有64位世界狀態(tài)，但這里只看4位：

將世界狀態(tài)分為「私有」和「共享」，我們就可以讓角色更新「私有」部分，而全局系統(tǒng)更新「共享」部分。當(dāng)需要角色規(guī)劃時(shí)，我們就用位運(yùn)算將該角色的「私有」與世界的「共享」進(jìn)行整合，得到對(duì)于這個(gè)角色而言的當(dāng)前世界狀態(tài)。這樣對(duì)于不同角色，它們就能得到對(duì)各自的而言的世界狀態(tài)啦！

如果去除注釋，這個(gè)類的內(nèi)容其實(shí)并不多，在使用時(shí)幾乎只要用到SetAtomValue函數(shù)，像這樣：

worldState = new GoapWorldState(); worldState.SetAtomValue("血量健康", true); worldState.SetAtomValue("大半夜", false, true);

接下來就是那三個(gè)接口了，首先是IAStarNode ，前文稍提過：「世界狀態(tài)」是圖中的結(jié)點(diǎn)，「動(dòng)作」都是圖中的邊，這是我用以輔助「泛用A星搜索器」的結(jié)點(diǎn)接口，本文就不贅述了，只要知道：繼承了這個(gè)類，都可以作為A星搜索中的結(jié)點(diǎn)，從而參與搜索。完整代碼如下：

using System.Collections.Generic; publicinterfaceIAStarNode

  whereT : IAStarNode

 {     public T Parent { get; set; }//父節(jié)點(diǎn)，通過泛型使它的類型與具體類一致     publicfloat SelfCost { get; set; }//自身單步花費(fèi)代價(jià)     publicfloat GCost { get; set; }//記錄g(n)，距初始狀態(tài)的代價(jià)     publicfloat HCost { get; set; }//記錄h(n)，距目標(biāo)狀態(tài)的代價(jià)     publicfloat FCost { get; }//記錄f(n)，總評(píng)估代價(jià)     ///      /// 獲取與指定節(jié)點(diǎn)的預(yù)測(cè)代價(jià)     ///      public float GetDistance(T otherNode);     ///      /// 獲取后繼（鄰居）節(jié)點(diǎn)     ///      /// 尋路所在的地圖，類型看具體情況轉(zhuǎn)換，     /// 故用object類型     ///  后繼節(jié)點(diǎn)列表     public List   GetSuccessors(object nodeMap);     /* IComparable實(shí)現(xiàn)的CompareTo函數(shù)，主要用于優(yōu)先隊(duì)列的比較；         一般比較可用以下函數(shù)     public int CompareTo(AStarNode other)     {         var res = (int)(FCost - other.FCost);         if(res == 0)             res = (int)(HCost - other.HCost);         return res;     }*/     /* IEquatable實(shí)現(xiàn)的Equals函數(shù)，可以自定義HashSet和Dictionary的Contains判斷依據(jù)（但同樣要重寫GetHashCode）        以及在尋路時(shí)用于比對(duì)某點(diǎn)是否為終點(diǎn)，可以根據(jù)類的特點(diǎn)自行繼承 */ }

這段代碼的注釋也說明了另外兩個(gè)接口的用意。

2. 動(dòng)作

我們之前說過，動(dòng)作包含一個(gè)「前提條件」，其實(shí)和HTN一樣，它還包含一個(gè)「行為影響」，相當(dāng)于之前圖中道路指向的橢圓表示的狀態(tài)。它們也都是世界狀態(tài)，注意是世界狀態(tài)，而不是單個(gè)狀態(tài)！

為什么不設(shè)置成單個(gè)？首先，「前提條件」和「行為影響」本身就可能是多個(gè)狀態(tài)組合成的，用單個(gè)不合適；其次，將它們也設(shè)置成世界狀態(tài)（64位的long類型），方便進(jìn)行統(tǒng)一處理與位運(yùn)算。Unity中的Layer也是這樣的。

只有當(dāng)前世界狀態(tài)與「前提條件」對(duì)應(yīng)位的值相同時(shí)，才算滿足前提條件，這個(gè)動(dòng)作才有被選擇的機(jī)會(huì)。而動(dòng)作一旦執(zhí)行成功，世界狀態(tài)就會(huì)發(fā)送變化，對(duì)應(yīng)位上的值會(huì)被賦值為「行為影響」所設(shè)置的值。

///  /// Goap動(dòng)作，也是Goap圖中的邊 ///  publicclassGoapAction {     publicint Cost{ get; privateset; } //動(dòng)作代價(jià)，作為AI規(guī)劃的依據(jù)     public GoapWorldState Precondition => precondition;     public GoapWorldState Effect => effect;     privatereadonly GoapWorldState precondition; //動(dòng)作得以執(zhí)行的前提條件     privatereadonly GoapWorldState effect; //動(dòng)作成功執(zhí)行后帶來的影響，體現(xiàn)在對(duì)世界狀態(tài)的改變     ///      /// 根據(jù)給定世界狀態(tài)樣式創(chuàng)建「前提條件」和「行為影響」，     /// 這為了讓它們的位與世界狀態(tài)保持一致，方便進(jìn)行位運(yùn)算     ///      /// 作為基準(zhǔn)的世界狀態(tài)     /// 動(dòng)作代價(jià)     public GoapAction(GoapWorldState baseState, int cost = 1)     {         Cost = cost;         precondition = new GoapWorldState(baseState);         effect = new GoapWorldState(baseState);     }     ///      /// 判斷是否滿足動(dòng)作執(zhí)行的前提條件     ///      /// 當(dāng)前世界狀態(tài)     ///  是否滿足前提     public bool MetCondition(GoapWorldState worldState)     {         var care = ~precondition.DontCare;         return (precondition.Values & care) == (worldState.Values & care);     }     //---------------------------------------------------------------     ///      /// 判斷世界狀態(tài)是否可由執(zhí)行影響導(dǎo)致     ///      /// 當(dāng)前世界狀態(tài)     ///  是否能導(dǎo)致     public bool MetEffect(GoapWorldState worldState)     {         var care = ~effect.DontCare;         return (effect.Values & care) == (worldState.Values & care);     }     //----------------------------------------------------------------     ///      /// 動(dòng)作實(shí)際執(zhí)行成功的影響     ///      /// 實(shí)際世界狀態(tài)     public void Effect_OnRun(GoapWorldState worldState)     {         worldState.Values = ((worldState.Values & effect.DontCare) | (effect.Values & ~effect.DontCare));     }     ///      /// 設(shè)置動(dòng)作前提條件，利用元組，方便一次性設(shè)置多個(gè)     ///      public GoapAction SetPrecontidion(params (string, bool)[] atomName)     {         foreach(var atom in atomName)          {             precondition.SetAtomValue(atom.Item1, atom.Item2);         }         returnthis;     }     ///      /// 設(shè)置動(dòng)作影響     ///      public GoapAction SetEffect(params (string, bool)[] atomName)     {         foreach (var atom in atomName)         {             effect.SetAtomValue(atom.Item1, atom.Item2);         }         returnthis;     }     public void Clear()     {         precondition.Clear();         effect.Clear();     } }

你可能發(fā)現(xiàn)了這個(gè)動(dòng)作類的奇怪之處——它沒有像OnRunning或OnUpdate之類的動(dòng)作執(zhí)行函數(shù)，這樣一來要如何執(zhí)行動(dòng)作？是的，這個(gè)類主要是用來充當(dāng)圖的邊，來連接各個(gè)狀態(tài)，它會(huì)作為 字典中的值，并于一個(gè)動(dòng)作名字符串綁定。我們會(huì)通過動(dòng)作名，再查找另一個(gè)同樣以動(dòng)作名為鍵、但值為事件的字典，找到對(duì)應(yīng)的事件，這個(gè)事件才是真正運(yùn)行的動(dòng)作函數(shù)。

這樣豈不多此一舉？其實(shí)這是為了提高GOAP圖的重用性。如果GOAP中的道路并不是真正的動(dòng)作函數(shù)，而是用了動(dòng)作名來標(biāo)記。那么我們可以為多個(gè)角色設(shè)計(jì)同一種動(dòng)作，但不同的表現(xiàn)。比如「攻擊」動(dòng)作，在弓箭手中就是射擊函數(shù)，槍手中就是開火函數(shù)……這樣一來，即便不同角色都可以使用同一張GOAP圖，不用重復(fù)創(chuàng)建（除非有特殊需求）。

這樣是GOAP的一般做法，只用少數(shù)GOAP圖，而不同角色可以共同使用一張GOAP圖來進(jìn)行互不干擾的規(guī)劃。這可以省很多代碼量，試想在有限狀態(tài)機(jī)中，不做特殊處理你都無法讓不同敵人共用「攻擊」?fàn)顟B(tài)，就得不斷寫大同小異的代碼。GOAP的這種將結(jié)構(gòu)與邏輯分離的做法，就可以很方便地復(fù)用結(jié)構(gòu)或進(jìn)行定制化設(shè)計(jì)，也是其優(yōu)勢(shì)之一。

PS：GOAP圖也得用「圖」這一數(shù)據(jù)結(jié)果存儲(chǔ)，而這種數(shù)據(jù)結(jié)構(gòu)在C# 中是沒有提供的，得自己實(shí)現(xiàn)，這里我給個(gè)簡(jiǎn)單的，方便后續(xù)其他功能（如果你有自己的一套，也可以用自己的，只是后續(xù)文章中相應(yīng)的函數(shù)要進(jìn)行替換）：

public classMyGraph

 {     publicreadonly HashSet NodeSet; //節(jié)點(diǎn)列表     publicreadonly Dictionary > NeighborList; //鄰居列表     publicreadonly Dictionary<(TNode, TNode), List > EdgeList; //邊列表     public MyGraph()     {         NodeSet = new HashSet ();         NeighborList = new Dictionary >();         EdgeList = new Dictionary<(TNode, TNode), List >();     }     ///      /// 尋找指定節(jié)點(diǎn)     ///      ///  找到的節(jié)點(diǎn)，沒找到時(shí)返回null     public TNode FindNode(TNode node)     {         NodeSet.TryGetValue(node, out TNode res);         return res;     }     ///      /// 尋找指點(diǎn)起、終點(diǎn)之間直接連接的所有邊     ///      /// 起點(diǎn)     /// 終點(diǎn)     ///  找到的邊，沒找到時(shí)返回null     public List   FindEdge(TNode source, TNode target)     {         var s = FindNode(source);         var t = FindNode(target);         if (s != null && t != null)         {             var nodePairs = (s, t);             if (EdgeList.ContainsKey(nodePairs))             {                 return EdgeList[nodePairs];             }         }         returnnull;     }     ///      /// 添加節(jié)點(diǎn)，用HashSet，包含重復(fù)檢測(cè)     ///      public bool AddNode(TNode node)     {         return NodeSet.Add(node);     }     ///      /// （前提是邊兩端結(jié)點(diǎn)已添加進(jìn)圖）添加指定邊，含空節(jié)點(diǎn)判斷、重復(fù)添加判斷     ///      /// 邊起點(diǎn)     /// 邊終點(diǎn)     /// 指定邊     ///  添加成功與否     public bool AddEdge(TNode source, TNode target, TEdge edge)     {         var s = FindNode(source);         var t = FindNode(target);         if (s == null || t == null)             returnfalse;         var nodePairs = (s, t);         if(!EdgeList.ContainsKey(nodePairs))         {             EdgeList.Add(nodePairs, new List ());         }         var allEdges = EdgeList[nodePairs];         if(!allEdges.Contains(edge))         {             allEdges.Add(edge);             if(!NeighborList.ContainsKey(source))             {                 NeighborList.Add(source, new List ());             }             NeighborList[source].Add(target);             returntrue;         }         returnfalse;     }     ///      /// 移除指定節(jié)點(diǎn)     ///      ///  移除成功與否     public bool RemoveNode(TNode node)     {         return NodeSet.Remove(node);     }     ///      /// 移除指定起、終點(diǎn)的指定邊     ///      /// 邊起點(diǎn)     /// 邊終點(diǎn)     /// 指定邊     ///  移除成功與否     public bool RemoveEdge(TNode source, TNode target, TEdge edge)     {         var allEdges = FindEdge(source, target);         return allEdges != null && allEdges.Remove(edge);     }     ///      /// 移除指定起、終點(diǎn)的所有邊     ///      /// 邊起點(diǎn)     /// 邊終點(diǎn)     ///  移除成功與否     public bool RemoveEdgeList(TNode source, TNode target)     {         return EdgeList.Remove((source, target));     }     ///      /// 獲取指定節(jié)點(diǎn)可抵達(dá)的所有鄰居節(jié)點(diǎn)     ///      public List   GetNeighbor(TNode node)     {         NeighborList.TryGetValue(node, out List res);         return res;     }     ///      /// 獲取指定節(jié)點(diǎn)所延伸出的所有邊     ///      public List   GetConnectedEdge(TNode node)     {         var resEdge = new List ();         var neighbor = GetNeighbor(node);         for(int i = 0; i < neighbor.Count; ++i)         {             var curEdgeList = EdgeList[(node, neighbor[i])];             for(int j = 0; j < curEdgeList.Count; ++j)             {                 resEdge.Add(curEdgeList[j]);             }         }         return resEdge;     } }

3. A星節(jié)點(diǎn)

接下來要實(shí)現(xiàn)的就是那三個(gè)接口所需的函數(shù)了，這三個(gè)接口其實(shí)都是為了方便尋找「路徑」，GOAP會(huì)采用啟發(fā)式搜索，就像A星尋路所用的那樣。所謂「啟發(fā)式搜索」就是有按照一定「啟發(fā)值」進(jìn)行的搜索，它的反面就是「盲目搜索」，如深度優(yōu)先搜索、廣度優(yōu)先搜索。啟發(fā)式搜索需要設(shè)計(jì)「啟發(fā)函數(shù)」來計(jì)算「啟發(fā)值」。

在A星尋路中，我們通過計(jì)算「當(dāng)前位置離起點(diǎn)的距離 + 當(dāng)前位置離終點(diǎn)的距離」做為啟發(fā)值來尋找最短路徑；類似的，在我們實(shí)現(xiàn)的這個(gè)GOAP中，我們會(huì)通過計(jì)算「起點(diǎn)狀態(tài)至當(dāng)前狀態(tài)累計(jì)的動(dòng)作代價(jià)+ 當(dāng)前狀態(tài)與目標(biāo)狀態(tài)的相關(guān)度」作為啟發(fā)值。

累計(jì)代價(jià)，也相當(dāng)于與起始狀態(tài)的「距離」；與目標(biāo)狀態(tài)的相關(guān)度，在世界狀態(tài)類中已經(jīng)說明了，就是比較當(dāng)前狀態(tài)與目標(biāo)狀態(tài)的有效位的值有多少是相同的，通常相同的越多就越接近。當(dāng)然，思路不唯一，可以搜索《數(shù)據(jù)挖掘》相關(guān)的文章，了解更多關(guān)于數(shù)據(jù)相關(guān)度的計(jì)算。

PS：在尋路時(shí)，常需要選取已探索過的節(jié)點(diǎn)中具有最小啟發(fā)值的節(jié)點(diǎn)。用遍歷倒也能做到，但總歸效率不高，故可以用「堆」，也就是「優(yōu)先隊(duì)列」：

//堆屬于常用數(shù)據(jù)結(jié)構(gòu)中的一種，我默認(rèn)大家都會(huì)了，原理就不加以注釋說明了 publicclassMyHeap

  whereT : IComparable

 {     publicint CurLength {get; privateset;}     publicreadonlyint capacity;     publicbool IsFull => CurLength == capacity;     publicbool IsEmpty => CurLength == 0;     public T Peak => heapArr[0];     privatereadonlybool isReverse;     privatereadonly T[] heapArr;     privatereadonly Dictionary int> idxTable; //記錄結(jié)點(diǎn)在數(shù)組中的位置，方便查找     public MyHeap(int size, bool isReverse = false)     {         CurLength = 0;         capacity = size;         heapArr = new T[size];         idxTable = new Dictionary int>();         this.isReverse = isReverse;     }     public void Push(T value)     {         if(!IsFull)         {             if (idxTable.ContainsKey(value))                 idxTable[value] = CurLength;             else                 idxTable.Add(value, CurLength);             heapArr[CurLength] = value;             Swim(CurLength++);         }     }     public void Pop()     {         if(!IsEmpty)         {             idxTable[heapArr[0]] = -1;             heapArr[0] = heapArr[--CurLength];             idxTable[heapArr[0]] = 0;             Sink(0);         }     }     public bool Contains(T value)     {         return idxTable.ContainsKey(value) && idxTable[value] > -1;     }     public T Find(T value)     {         return Contains(value) ? heapArr[idxTable[value]] : default;     }     public void Clear()     {         idxTable.Clear();         CurLength = 0;     }     private void Swim(int index)     {         int father;         while(index > 0)         {             father = (index - 1) / 2;             if(IsBetter(heapArr[index], heapArr[father]))             {                 SwapValueByIndex(father, index);                 index = father;             }             elsereturn;         }     }     private void Sink(int index)     {         int best, left = index * 2 + 1, right;         while(left < CurLength)         {             right = left + 1;             best = right < CurLength && IsBetter(heapArr[right], heapArr[left]) ? right : left;             if(IsBetter(heapArr[best], heapArr[index]))             {                 SwapValueByIndex(best, index);                 index = best;                 left = index * 2 + 1;             }             elsereturn;         }     }     private void SwapValueByIndex(int i, int j)     {         (heapArr[j], heapArr[i]) = (heapArr[i], heapArr[j]);         idxTable[heapArr[i]] = i;         idxTable[heapArr[j]] = j;     }     private bool IsBetter(T v1, T v2)     {         return isReverse ^ v1.CompareTo(v2) < 0;     } }

三個(gè)接口所需的函數(shù)實(shí)現(xiàn)如下：

///  /// 用位表示的世界狀態(tài) ///  publicclassGoapWorldState : IAStarNode

 , IComparable

 , IEquatable

 {     ……     ///      /// 計(jì)算該世界狀態(tài)與指定世界狀態(tài)的差異度     ///      public float GetDistance(GoapWorldState otherNode)     {         var care = otherNode.dontCare ^ -1L;         var diff = (values & care) ^ (otherNode.values & care);         int dist = 0; //統(tǒng)計(jì)有多少位是不同的，以表示差異度         for (int i = 0; i < MAXATOMS;++i)         {             /*diff的位不為1，則表示不同*/             if ((diff & (1L << i)) != 0)                 ++dist;  // 差異越多，距離越大         }         return dist;     }     public List   GetSuccessors(object nodeMap)     {         var goapActionSet = nodeMap as GoapActionSet;         var actionMap = goapActionSet.actionGraph;         var res = actionMap.GetNeighbor(this);         //根據(jù)找到的動(dòng)作，對(duì)抵達(dá)下個(gè)結(jié)點(diǎn)的代價(jià)進(jìn)行計(jì)算         for(int i = 0; i < res.Count; ++i)         {             res[i].SelfCost = goapActionSet.actionSet[actionMap.FindEdge(this, res[i])[0]].Cost;         }         return res;     }     public int CompareTo(GoapWorldState other)     {         var res = (int)(FCost - other.FCost);         if(res == 0)             res = (int)(HCost - other.HCost);         return res;     }     public bool Equals(GoapWorldState other)     {         /*后文提及的所使用的A星搜索器中，總是「動(dòng)作的條件」對(duì)比「當(dāng)前的世界狀態(tài)」，即currentNode.Equals(target)         如「動(dòng)作的條件」：餓-true，而「當(dāng)前的世界狀態(tài)」：餓-true，累-true，困-true；顯然此時(shí)世界狀態(tài)應(yīng)當(dāng)滿足條件         這樣可以避免當(dāng)前世界狀態(tài)過于“包容”卻被誤判不滿足*/         return (values & ~dontCare) == (other.values & ~dontCare);     }     public override int GetHashCode()     {         return HashCode.Combine(values & ~dontCare, dontCare);     } }

4. 動(dòng)作集

照理說，動(dòng)作集不過是動(dòng)作的合集，單獨(dú)將它也制成一個(gè)類，是為了方便「動(dòng)作序列」規(guī)劃，主要體現(xiàn)在GetPossibleTrans函數(shù)，根據(jù)傳入的節(jié)點(diǎn)的世界狀態(tài)，在合集中遍歷出「前提條件」?jié)M足的動(dòng)作：

using System.Collections.Generic; publicclassGoapActionSet {     public MyGraph string> actionGraph; // 動(dòng)作與狀態(tài)構(gòu)成的圖     privatereadonly Dictionary

 actionSet;     public GoapActionSet()     {         actionGraph = new MyGraph string>();         actionSet = new Dictionary

 ();     }     public GoapAction this[string idx]     {         get => actionSet[idx];     }     ///      /// 添加動(dòng)作至動(dòng)作集合中     ///      /// 動(dòng)作名     /// 對(duì)應(yīng)動(dòng)作     ///  動(dòng)作集，方便連續(xù)添加     public GoapActionSet AddAction(string actionName, GoapAction newAction)     {         actionSet.Add(actionName, newAction);         actionGraph.AddNode(newAction.Effect);         actionGraph.AddNode(newAction.Precondition);         actionGraph.AddEdge(newAction.Effect, newAction.Precondition, actionName);         returnthis;     }     ///      /// 返回兩個(gè)狀態(tài)轉(zhuǎn)化的動(dòng)作名     ///      /// 起點(diǎn)狀態(tài)     /// 狀態(tài)后的狀態(tài)     ///  所需執(zhí)行動(dòng)作名     public string GetTransAction(GoapWorldState from, GoapWorldState to)     {         return actionGraph.FindEdge(from, to)[0];     } }

5. A星尋路

一切條件都準(zhǔn)備好了，現(xiàn)在實(shí)現(xiàn)下用來「尋路」的類。首先，我們會(huì)進(jìn)行反向搜索，意思是說，我們不會(huì)「起始狀態(tài)-->目標(biāo)狀態(tài)」，而是「目標(biāo)狀態(tài)-->起始狀態(tài)」，如果成功找到，就將得到的動(dòng)作序列逆向執(zhí)行。

為什么這么麻煩？其實(shí)恰恰相反，這還是一種簡(jiǎn)化。如果真的「起始狀態(tài)-->目標(biāo)狀態(tài)」，未必最終會(huì)找到目標(biāo)狀態(tài)（因?yàn)橛锌赡苣艿诌_(dá)的動(dòng)作暫時(shí)條件不滿足）；但反向搜索，必定會(huì)包含目標(biāo)狀態(tài)，也一定會(huì)找到一條路（因?yàn)榭倳?huì)抵達(dá)一個(gè)當(dāng)前已經(jīng)符合的世界狀態(tài)，否則就是設(shè)計(jì)的有問題了），只不過可能不是最短的。

我們也能接受這種結(jié)果，雖說非最優(yōu)解，但這種不確定因素，也變相讓AI增加了點(diǎn)隨機(jī)性，更接近真實(shí)決策情況。

它的整體搜索過程和A星尋路是一樣的，直接用「泛用A星搜索器」即可：

using System; using System.Collections.Generic; using JufGame.Collections.Generic; ///  /// A星搜索器，T_Node額外實(shí)現(xiàn)IComparable用于優(yōu)先隊(duì)列的比較，實(shí)現(xiàn)IEquatable用于HashSet和Dictionary等同一性的判斷 ///  ///  搜索的圖類 ///  搜索的節(jié)點(diǎn)類 publicclassAStar_Searcher

  whereT_Node: IAStarNode

 , IComparable

 , IEquatable

 {     privatereadonly HashSet closeList; //探索集     privatereadonly MyHeap openList; //邊緣集     privatereadonly T_Map nodeMap;//搜索空間（地圖）     public AStar_Searcher(T_Map map, int maxNodeSize = 200)     {         nodeMap = map;         closeList = new HashSet ();         //maxNodeSize用于限制路徑節(jié)點(diǎn)的上限，避免陷入無止境搜索的情況         openList = new MyHeap (maxNodeSize);     }     ///      /// 搜索（尋路）     ///      /// 起點(diǎn)     /// 終點(diǎn)     /// 返回生成的路徑     public void FindPath(T_Node start, T_Node target, Stack pathRes )     {         T_Node currentNode;         pathRes.Clear();//清空路徑以備存儲(chǔ)新的路徑         closeList.Clear();         openList.Clear();         openList.PushHeap(start);         while (!openList.IsEmpty)         {             currentNode = openList.Top;//取出邊緣集中最小代價(jià)的節(jié)點(diǎn)             openList.PopHeap();             closeList.Add(currentNode);//擬定移動(dòng)到該節(jié)點(diǎn)，將其放入探索集             if (currentNode.Equals(target) || openList.IsFull)//如果找到了或圖都搜完了也沒找到時(shí)             {                 GenerateFinalPath(start, currentNode, pathRes);//生成路徑并保存到pathRes中                 return;             }             UpdateList(currentNode, target);//更新邊緣集和探索集         }     }     private void GenerateFinalPath(T_Node startNode, T_Node endNode, Stack pathStack )     {         pathStack.Push(endNode);//因?yàn)榛厮荩杂脳?chǔ)存生成的路徑         var tpNode = endNode.Parent;         while (!tpNode.Equals(startNode))         {             pathStack.Push(tpNode);             tpNode = tpNode.Parent;         }         pathStack.Push(startNode);     }     private void UpdateList(T_Node curNode, T_Node endNode)     {         T_Node sucNode;         float tpCost;         bool isNotInOpenList;         var successors = curNode.GetSuccessors(nodeMap);//找出當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)         if(successors == null)         {             return;         }         for (int i = 0; i < successors.Count; ++i)         {             sucNode = successors[i];             if (closeList.Contains(sucNode))//后繼節(jié)點(diǎn)已被探索過就忽略                 continue;             tpCost = curNode.GCost + sucNode.SelfCost;             isNotInOpenList = !openList.Contains(sucNode);             if (isNotInOpenList || tpCost < sucNode.GCost)             {                 sucNode.GCost = tpCost;                 sucNode.HCost = sucNode.GetDistance(endNode);//計(jì)算啟發(fā)函數(shù)估計(jì)值                 sucNode.Parent = curNode;//記錄父節(jié)點(diǎn)，方便回溯                 if (isNotInOpenList)                 {                     openList.PushHeap(sucNode);                 }             }         }     } }

6. 代理器

我們最后創(chuàng)建一個(gè)「代理器」，它用來整合了上述內(nèi)容，并統(tǒng)籌運(yùn)行：

public enum EStatus {     Failure, Success, Running, Aborted, Invalid } publicclassGoapAgent {     privatereadonly GoapActionSet actionSet; //動(dòng)作集     publicreadonly GoapWorldState curSelfState; //當(dāng)前自身狀態(tài)，主要是存儲(chǔ)私有狀態(tài)     privatereadonly AStar_Searcher goapAStar;     privatereadonly Dictionary

 actionFuncs;  //各動(dòng)作名字對(duì)應(yīng)的動(dòng)作函數(shù)     private Stack

 actionPlan;//存儲(chǔ)規(guī)劃出的動(dòng)作序列     private Stack path;     private EStatus curState;//存儲(chǔ)當(dāng)前動(dòng)作的執(zhí)行結(jié)果     privatebool canContinue;//是否能夠繼續(xù)執(zhí)行，記錄動(dòng)作序列全部是否執(zhí)行完了     private GoapAction curAction;//記錄當(dāng)前執(zhí)行的動(dòng)作     private Func curActionFunc; //記錄當(dāng)前運(yùn)行的動(dòng)作函數(shù)     ///      /// 初始化代理器     ///      /// 世界狀態(tài)，用來復(fù)制成自身狀態(tài)     /// 動(dòng)作集     public GoapAgent(GoapWorldState baseWorldState, GoapActionSet actionSet)     {         curSelfState = new GoapWorldState(baseWorldState)         {             DontCare = baseWorldState.DontCare         };         actionFuncs = new Dictionary

 ();         actionPlan = new Stack

 ();         this.actionSet = actionSet;         goapAStar = new AStar_Searcher ( this.actionSet);         path = new Stack ();     }     ///      /// 修改自身狀態(tài)值     ///      public bool SetAtomValue(string stateName, bool value)     {         return curSelfState.SetAtomValue(stateName, value);     }     ///      /// 為動(dòng)作名設(shè)置對(duì)應(yīng)的動(dòng)作函數(shù)     ///      public void SetActionFunc(string actionName, Func func )     {         actionFuncs.Add(actionName, func);     }     ///      /// 規(guī)劃GOAP并運(yùn)行     ///      ///      ///      public void RunPlan(GoapWorldState curWorldState, GoapWorldState goal)     {         UpdateSelfState(curWorldState);//將自身的私有狀態(tài)與世界的共享狀態(tài)融合，得到真正的「當(dāng)前世界狀態(tài)」         if (curState == EStatus.Failure) //當(dāng)前狀態(tài)為「失敗」，就表示動(dòng)作執(zhí)行失敗         {             //那就重新規(guī)劃，找出新的動(dòng)作序列             actionPlan.Clear();             goapAStar.FindPath(goal, curSelfState, path);             //通過狀態(tài)序列得到動(dòng)作序列             path.TryPop(outvar cur);             while(path.Count != 0)             {                 actionPlan.Push(actionSet.GetTransAction(cur, path.Peek()));                 cur = path.Pop();             }         }         if(curState == EStatus.Success)//執(zhí)行結(jié)果為「成功」，表示動(dòng)作順利執(zhí)行完         {             curAction.Effect_OnRun(curWorldState); //動(dòng)作就會(huì)對(duì)全局世界狀態(tài)造成影響             /*這同樣要更新自身狀態(tài)，以防這次改變的是「私有」?fàn)顟B(tài)，全局世界狀態(tài)可是只維護(hù)「共享」部分。             所以需要自身狀態(tài)也記錄下這次影響，即便是共享狀態(tài)也沒關(guān)系，反正下次會(huì)與世界的共享狀態(tài)融合*/             curAction.Effect_OnRun(curSelfState);         }         //如果執(zhí)行結(jié)果不是「運(yùn)行中」，就表示上個(gè)動(dòng)作要么成功了，要么失敗了。都該取出動(dòng)作序列中新的動(dòng)作來執(zhí)行         if (curState != EStatus.Running)         {             canContinue = actionPlan.TryPop(outstring curActionName);             if (canContinue)//如果成功取出動(dòng)作，就根據(jù)動(dòng)作名，選出對(duì)應(yīng)函數(shù)和動(dòng)作             {                 curActionFunc = actionFuncs[curActionName];                 curAction = actionSet[curActionName];             }         }         curState = canContinue && curAction.MetCondition(curSelfState) ? curActionFunc() : EStatus.Failure;     }     ///      /// 中斷當(dāng)前Goap執(zhí)行     ///      public void AbortedGoapCurState()     {         curState = EStatus.Aborted;     }     ///      /// 更新自身狀態(tài)的共享部分與當(dāng)前世界狀態(tài)同步     ///      private void UpdateSelfState(GoapWorldState curWorldState)     {         curSelfState.Values = (curWorldState.Values & curWorldState.Shared) | (curSelfState.Values & ~curWorldState.Shared);     } }

注意，代碼里的這個(gè)部分，因?yàn)锳星搜索得到的是結(jié)點(diǎn)——也就是狀態(tài)，但我們所需要的是鏈接狀態(tài)的動(dòng)作，所以要再「加工」一下：

goapAStar.FindPath(goal, curSelfState, path); //通過狀態(tài)序列得到動(dòng)作序列 path.TryPop(out var cur); while(path.Count != 0) {     actionPlan.Push(actionSet.GetTransAction(cur, path.Peek()));     cur = path.Pop(); }

這個(gè)類中，RunPlan函數(shù)與上一期的HTN中的基本一樣。但我想可能有些人還不大明白UpdateSelfState函數(shù)是如何融合自身狀態(tài)與世界狀態(tài)的，我就簡(jiǎn)單舉個(gè)例：

可以看到得到的值，恰好保留了世界狀態(tài)的共享部分和自身狀態(tài)的私有部分。其實(shí)這也并非「恰好」，這樣的位運(yùn)算理應(yīng)得到這樣的結(jié)果才是。你也可以自己動(dòng)手嘗試一些值或者用更多位的數(shù)來驗(yàn)證。

四、尾聲

GOAP的缺點(diǎn)主要是在設(shè)計(jì)難度上，它的設(shè)計(jì)相較FSM、行為樹那些不那么直接，你需要把控好動(dòng)作的條件和影響對(duì)應(yīng)的狀態(tài)，比其它決策方法更費(fèi)腦子些。因?yàn)镚OAP沒有顯示的結(jié)構(gòu)，如何定義好一個(gè)狀態(tài)，使它能在邏輯層面合理地成為一個(gè)動(dòng)作的前提條件，又能成為另一個(gè)動(dòng)作條件的影響結(jié)果（比如「有流量」，想想看，將其做為條件可以設(shè)計(jì)什么動(dòng)作？作為影響結(jié)果又應(yīng)該怎么設(shè)計(jì)呢？）是比較考驗(yàn)開發(fā)人員的架構(gòu)設(shè)計(jì)的。但毋庸置疑的是，在面對(duì)較復(fù)雜的AI時(shí)，它的代碼量一定是小于FSM、行為樹和HTN的。而且添加和減少動(dòng)作也不需要進(jìn)行過多代碼修改，只要將新行動(dòng)加入到動(dòng)作集或?qū)⒂蕹膭?dòng)作從動(dòng)作集中刪去就可以，這也是它沒有顯式結(jié)構(gòu)的好處。

這里也簡(jiǎn)單用上文所學(xué)內(nèi)容做一個(gè)簡(jiǎn)單的太空射擊飛船敵人的AI：gitee項(xiàng)目[4]

在EnemyConfig中為敵人指定了GOAP圖并共用，一個(gè)非常簡(jiǎn)單的敵人邏輯（只是用GOAP實(shí)現(xiàn)了而已）：當(dāng)敵人健康時(shí)會(huì)嘗試瞄準(zhǔn)玩家后射擊，當(dāng)玩家弱勢(shì)（無力）時(shí)，敵人追擊玩家；當(dāng)敵人自身不安全時(shí)會(huì)退避并以較低命中率的方式射擊：

goal = new GoapWorldState(WarSpaceManager.worldState); goal.SetAtomValue("擊殺玩家", true); actionSet = new GoapActionSet(); actionSet .AddAction("低命中射擊", new GoapAction(WarSpaceManager.worldState, 1)     .SetPrecontidion(("安全區(qū)內(nèi)", true))     .SetEffect(("擊殺玩家", true))) .AddAction("追擊", new GoapAction(WarSpaceManager.worldState, 4)     .SetPrecontidion(("彈藥充足", true), ("玩家無力", true))     .SetEffect(("擊殺玩家", true))) .AddAction("瞄準(zhǔn)玩家", new GoapAction(WarSpaceManager.worldState, 3)     .SetPrecontidion(("瞄準(zhǔn)就緒", false))     .SetEffect(("瞄準(zhǔn)就緒", true))) .AddAction("射擊", new GoapAction(WarSpaceManager.worldState, 2)     .SetPrecontidion(("瞄準(zhǔn)就緒", true))     .SetEffect(("擊殺玩家", true))) .AddAction("躲避", new GoapAction(WarSpaceManager.worldState, 1)     .SetPrecontidion(("安全", false))     .SetEffect(("安全區(qū)內(nèi)", true)));

到這里就結(jié)束了。

參考：

[1] A星尋路的流程視頻

https://www.bilibili.com/video/BV147411u7r5?p=1&vd_source=c9a1131d04faacd4a397411965ea21f4

[2] 視頻

https://www.bilibili.com/video/BV1iG4y1i78Q/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=c9a1131d04faacd4a397411965ea21f4

[3] C語(yǔ)言版本的GOAP

https://github.com/stolk/GPGOAP

[4] gitee項(xiàng)目

https://gitee.com/OwlCat/some-projects-in-tutorials/tree/master/GOAP

文末，再次感謝狐王駕虎 的分享， 作者主頁(yè)：https://home.cnblogs.com/u/OwlCat， 如果您有任何獨(dú)到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群： 793972859 ）。

近期精彩回顧

【萬象更新】

【萬象更新】

【萬象更新】

【萬象更新】