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

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

作者主頁：

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

一、前言

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

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

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

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

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

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

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

二、運行邏輯

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

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

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

同樣不難：

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

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

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

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

三、代碼實現(xiàn)

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

1. 世界狀態(tài)

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

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

問題在于：

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

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

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

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

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

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

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

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

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

 , IComparable

 , IEquatable

 {     publicconstint MAXATOMS = 64;//存儲的狀態(tài)數(shù)上限，由于用long類型存儲，最多就是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;//存儲各個狀態(tài)名字與其在values中的對應(yīng)位，方便查找狀態(tài)     privateint curNamsLen;//存儲的已用狀態(tài)的長度     privatelong values;     privatelong dontCare;     privatelong shared;     ///      /// 初始化為空白世界狀態(tài)     ///      public GoapWorldState()     {         //賦值0，可將二進制位全置0；賦值-1，可將二進制位全置1         namesTable = new Dictionary

 ();         values = 0L; //全置0，意為世界狀態(tài)默認為false         dontCare = -1L; //全置1，意為世界狀態(tài)的位全沒有被使用         shared = -1L; //將shard的位全置1         curNamsLen = 0;     }     ///      /// 基于某世界狀態(tài)的進一步創(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ù)制已使用的位長度         shared = worldState.shared;//保留狀態(tài)共享性的信息     }     ///      /// 根據(jù)狀態(tài)名，修改單個狀態(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)對應(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)名獲取單個狀態(tài)在Values中的位，如果沒包含會嘗試添加     ///      /// 狀態(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;     }     //——————————三個接口需要實現(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()     {     } }

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

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

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

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

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

using System.Collections.Generic; publicinterfaceIAStarNode

  whereT : IAStarNode

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

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

2. 動作

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

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

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

///  /// Goap動作，也是Goap圖中的邊 ///  publicclassGoapAction {     publicint Cost{ get; privateset; } //動作代價，作為AI規(guī)劃的依據(jù)     public GoapWorldState Precondition => precondition;     public GoapWorldState Effect => effect;     privatereadonly GoapWorldState precondition; //動作得以執(zhí)行的前提條件     privatereadonly GoapWorldState effect; //動作成功執(zhí)行后帶來的影響，體現(xiàn)在對世界狀態(tài)的改變     ///      /// 根據(jù)給定世界狀態(tài)樣式創(chuàng)建「前提條件」和「行為影響」，     /// 這為了讓它們的位與世界狀態(tài)保持一致，方便進行位運算     ///      /// 作為基準(zhǔn)的世界狀態(tài)     /// 動作代價     public GoapAction(GoapWorldState baseState, int cost = 1)     {         Cost = cost;         precondition = new GoapWorldState(baseState);         effect = new GoapWorldState(baseState);     }     ///      /// 判斷是否滿足動作執(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);     }     //----------------------------------------------------------------     ///      /// 動作實際執(zhí)行成功的影響     ///      /// 實際世界狀態(tài)     public void Effect_OnRun(GoapWorldState worldState)     {         worldState.Values = ((worldState.Values & effect.DontCare) | (effect.Values & ~effect.DontCare));     }     ///      /// 設(shè)置動作前提條件，利用元組，方便一次性設(shè)置多個     ///      public GoapAction SetPrecontidion(params (string, bool)[] atomName)     {         foreach(var atom in atomName)          {             precondition.SetAtomValue(atom.Item1, atom.Item2);         }         returnthis;     }     ///      /// 設(shè)置動作影響     ///      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)了這個動作類的奇怪之處——它沒有像OnRunning或OnUpdate之類的動作執(zhí)行函數(shù)，這樣一來要如何執(zhí)行動作？是的，這個類主要是用來充當(dāng)圖的邊，來連接各個狀態(tài)，它會作為 字典中的值，并于一個動作名字符串綁定。我們會通過動作名，再查找另一個同樣以動作名為鍵、但值為事件的字典，找到對應(yīng)的事件，這個事件才是真正運行的動作函數(shù)。

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

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

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

public classMyGraph

 {     publicreadonly HashSet NodeSet; //節(jié)點列表     publicreadonly Dictionary > NeighborList; //鄰居列表     publicreadonly Dictionary<(TNode, TNode), List > EdgeList; //邊列表     public MyGraph()     {         NodeSet = new HashSet ();         NeighborList = new Dictionary >();         EdgeList = new Dictionary<(TNode, TNode), List >();     }     ///      /// 尋找指定節(jié)點     ///      ///  找到的節(jié)點，沒找到時返回null     public TNode FindNode(TNode node)     {         NodeSet.TryGetValue(node, out TNode res);         return res;     }     ///      /// 尋找指點起、終點之間直接連接的所有邊     ///      /// 起點     /// 終點     ///  找到的邊，沒找到時返回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é)點，用HashSet，包含重復(fù)檢測     ///      public bool AddNode(TNode node)     {         return NodeSet.Add(node);     }     ///      /// （前提是邊兩端結(jié)點已添加進圖）添加指定邊，含空節(jié)點判斷、重復(fù)添加判斷     ///      /// 邊起點     /// 邊終點     /// 指定邊     ///  添加成功與否     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é)點     ///      ///  移除成功與否     public bool RemoveNode(TNode node)     {         return NodeSet.Remove(node);     }     ///      /// 移除指定起、終點的指定邊     ///      /// 邊起點     /// 邊終點     /// 指定邊     ///  移除成功與否     public bool RemoveEdge(TNode source, TNode target, TEdge edge)     {         var allEdges = FindEdge(source, target);         return allEdges != null && allEdges.Remove(edge);     }     ///      /// 移除指定起、終點的所有邊     ///      /// 邊起點     /// 邊終點     ///  移除成功與否     public bool RemoveEdgeList(TNode source, TNode target)     {         return EdgeList.Remove((source, target));     }     ///      /// 獲取指定節(jié)點可抵達的所有鄰居節(jié)點     ///      public List   GetNeighbor(TNode node)     {         NeighborList.TryGetValue(node, out List res);         return res;     }     ///      /// 獲取指定節(jié)點所延伸出的所有邊     ///      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é)點

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

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

累計代價，也相當(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)度的計算。

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

//堆屬于常用數(shù)據(jù)結(jié)構(gòu)中的一種，我默認大家都會了，原理就不加以注釋說明了 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é)點在數(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;     } }

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

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

 , IComparable

 , IEquatable

 {     ……     ///      /// 計算該世界狀態(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)計有多少位是不同的，以表示差異度         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ù)找到的動作，對抵達下個結(jié)點的代價進行計算         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)前的世界狀態(tài)」，即currentNode.Equals(target)         如「動作的條件」：餓-true，而「當(dāng)前的世界狀態(tài)」：餓-true，累-true，困-true；顯然此時世界狀態(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. 動作集

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

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

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

 ();     }     public GoapAction this[string idx]     {         get => actionSet[idx];     }     ///      /// 添加動作至動作集合中     ///      /// 動作名     /// 對應(yī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;     }     ///      /// 返回兩個狀態(tài)轉(zhuǎn)化的動作名     ///      /// 起點狀態(tài)     /// 狀態(tài)后的狀態(tài)     ///  所需執(zhí)行動作名     public string GetTransAction(GoapWorldState from, GoapWorldState to)     {         return actionGraph.FindEdge(from, to)[0];     } }

5. A星尋路

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

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

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

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

using System; using System.Collections.Generic; using JufGame.Collections.Generic; ///  /// A星搜索器，T_Node額外實現(xiàn)IComparable用于優(yōu)先隊列的比較，實現(xiàn)IEquatable用于HashSet和Dictionary等同一性的判斷 ///  ///  搜索的圖類 ///  搜索的節(jié)點類 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é)點的上限，避免陷入無止境搜索的情況         openList = new MyHeap (maxNodeSize);     }     ///      /// 搜索（尋路）     ///      /// 起點     /// 終點     /// 返回生成的路徑     public void FindPath(T_Node start, T_Node target, Stack pathRes )     {         T_Node currentNode;         pathRes.Clear();//清空路徑以備存儲新的路徑         closeList.Clear();         openList.Clear();         openList.PushHeap(start);         while (!openList.IsEmpty)         {             currentNode = openList.Top;//取出邊緣集中最小代價的節(jié)點             openList.PopHeap();             closeList.Add(currentNode);//擬定移動到該節(jié)點，將其放入探索集             if (currentNode.Equals(target) || openList.IsFull)//如果找到了或圖都搜完了也沒找到時             {                 GenerateFinalPath(start, currentNode, pathRes);//生成路徑并保存到pathRes中                 return;             }             UpdateList(currentNode, target);//更新邊緣集和探索集         }     }     private void GenerateFinalPath(T_Node startNode, T_Node endNode, Stack pathStack )     {         pathStack.Push(endNode);//因為回溯，所以用棧儲存生成的路徑         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é)點的后繼節(jié)點         if(successors == null)         {             return;         }         for (int i = 0; i < successors.Count; ++i)         {             sucNode = successors[i];             if (closeList.Contains(sucNode))//后繼節(jié)點已被探索過就忽略                 continue;             tpCost = curNode.GCost + sucNode.SelfCost;             isNotInOpenList = !openList.Contains(sucNode);             if (isNotInOpenList || tpCost < sucNode.GCost)             {                 sucNode.GCost = tpCost;                 sucNode.HCost = sucNode.GetDistance(endNode);//計算啟發(fā)函數(shù)估計值                 sucNode.Parent = curNode;//記錄父節(jié)點，方便回溯                 if (isNotInOpenList)                 {                     openList.PushHeap(sucNode);                 }             }         }     } }

6. 代理器

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

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

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

 actionPlan;//存儲規(guī)劃出的動作序列     private Stack path;     private EStatus curState;//存儲當(dāng)前動作的執(zhí)行結(jié)果     privatebool canContinue;//是否能夠繼續(xù)執(zhí)行，記錄動作序列全部是否執(zhí)行完了     private GoapAction curAction;//記錄當(dāng)前執(zhí)行的動作     private Func curActionFunc; //記錄當(dāng)前運行的動作函數(shù)     ///      /// 初始化代理器     ///      /// 世界狀態(tài)，用來復(fù)制成自身狀態(tài)     /// 動作集     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);     }     ///      /// 為動作名設(shè)置對應(yīng)的動作函數(shù)     ///      public void SetActionFunc(string actionName, Func func )     {         actionFuncs.Add(actionName, func);     }     ///      /// 規(guī)劃GOAP并運行     ///      ///      ///      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)為「失敗」，就表示動作執(zhí)行失敗         {             //那就重新規(guī)劃，找出新的動作序列             actionPlan.Clear();             goapAStar.FindPath(goal, curSelfState, path);             //通過狀態(tài)序列得到動作序列             path.TryPop(outvar cur);             while(path.Count != 0)             {                 actionPlan.Push(actionSet.GetTransAction(cur, path.Peek()));                 cur = path.Pop();             }         }         if(curState == EStatus.Success)//執(zhí)行結(jié)果為「成功」，表示動作順利執(zhí)行完         {             curAction.Effect_OnRun(curWorldState); //動作就會對全局世界狀態(tài)造成影響             /*這同樣要更新自身狀態(tài)，以防這次改變的是「私有」?fàn)顟B(tài)，全局世界狀態(tài)可是只維護「共享」部分。             所以需要自身狀態(tài)也記錄下這次影響，即便是共享狀態(tài)也沒關(guān)系，反正下次會與世界的共享狀態(tài)融合*/             curAction.Effect_OnRun(curSelfState);         }         //如果執(zhí)行結(jié)果不是「運行中」，就表示上個動作要么成功了，要么失敗了。都該取出動作序列中新的動作來執(zhí)行         if (curState != EStatus.Running)         {             canContinue = actionPlan.TryPop(outstring curActionName);             if (canContinue)//如果成功取出動作，就根據(jù)動作名，選出對應(yīng)函數(shù)和動作             {                 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);     } }

注意，代碼里的這個部分，因為A星搜索得到的是結(jié)點——也就是狀態(tài)，但我們所需要的是鏈接狀態(tài)的動作，所以要再「加工」一下：

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

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

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

四、尾聲

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

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

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

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語言版本的GOAP

https://github.com/stolk/GPGOAP

[4] gitee項目

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

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

近期精彩回顧

【萬象更新】

【萬象更新】

【萬象更新】

【萬象更新】