上海
【USparkle專欄】如果你深懷絕技，愛“搞點研究”，樂于分享也博采眾長，我們期待你的加入，讓智慧的火花碰撞交織，讓知識的傳遞生生不息！
這是侑虎科技第1889篇文章，感謝作者狐王駕虎供稿。歡迎轉發分享，未經作者授權請勿轉載。如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群：793972859）
作者主頁：
https://home.cnblogs.com/u/OwlCat
一、前言
像先前提到的有限狀態機、行為樹、HTN，它們實現的AI行為，雖說能針對不同環境作出不同反應，但應對方法是寫死了的。有限狀態機終究是在幾個狀態間進行切換、行為樹也是根據提前設計好的樹來搜索……你會發現，游戲AI角色表現出的智能程度，終究與開發者的設計結構有關，就有限狀態機而言，各個狀態如何切換很大程度上就影響了AI智能的表現。
那有沒有什么決策方法，能夠僅需設計好角色需要的動作，而它自己就能合理決定要選擇哪些動作完成目標呢？這樣的話，角色AI的行為智能程度會更上一層樓，畢竟它不再被寫死的決策結構束縛；我們在添加更多AI行為時，也可以簡單地直接將它放在角色需要的動作集里就好，減少了工作量，不必像行為樹那樣，還要考慮節點間的連接。
沒錯，GOAP（目標導向型行為規劃）就可以做到。但請注意，并不是說GOAP就比其它決策方法好，后面也會提到它的缺點。選擇何種決策方法還得根據實際項目和自身需求。
PS：本教程需要你具備以下前提知識：
1. 知道數據結構、堆/優先隊列、棧、圖。
2. 知道A星尋路的流程，如不了解可看此視頻[1]。
3. 基本的位運算與位存儲（能做到理解Unity中的Layer和LayerMask的程度就行）。
二、運行邏輯
我們來看個簡單的尋路問題：你能找到從A到B的最短路線嗎？注意，道路是單向的。
聰明如你，這并不難找到：
現在，加大難度，假設每條道路口都有一個門，紅色表示門關上了，藍色表示門開著，你還能找出可達成的最短A到B路線嗎？
同樣不難：
這樣就足夠了，GOAP的規劃就是這么一個過程。只是把每個節點都當成一個狀態，每條道路都當作一個動作、道路長度作為動作代價、路口的門作為動作執行條件，然后像你這樣尋找出一條可以執行的最短「路線」，并記錄下途徑的道路（注意，不是節點），這樣就得到了「動作序列」，再讓AI角色逐一執行。GOAP中的圖會長成下面這樣（只畫出了一條路的樣子，但相信你們能舉一反三的）：
GOAP就是在不斷執行「從現有狀態到目標狀態」，上圖中的「現有狀態」和「目標狀態」分別就是「餓」和「飽」。請注意，雖說用了不同形狀，但中間的那些橢圓節點，比如「在上網」，也是和「餓」、「飽」同類別的存在。也就是說「在上網」也可以作為現有狀態或目標狀態。
可想而知，只要狀態夠多，動作夠多，AI就能做出更復雜的動作。雖說這對其它決策方法也成立，但GOAP不需要我們手動設置各動作、狀態之間的關系，它能自行規劃出要做的一系列動作，更省事且更智能，甚至可以規劃出超出原本設想但又合理的動作序列。
希望我講明白了它的運作（如果還是感覺有點不懂，可以看看這個視頻[2]），下面一起來實現一個簡單的GOAP進一步了解吧！順帶提一下，在Unity資源商店有免費的GOAP插件，并且做了可視化處理以及多線程優化，各位真的想將GOAP運用于項目的話，更推薦去學習使用成熟的插件。
三、代碼實現
本文「世界狀態」的實現參考了GitHub上一C語言版本的GOAP[3]。
1. 世界狀態
所謂「世界狀態」其實就是存儲所有的狀態放在一塊兒的合集。而狀態其實還有一個隱藏身份——動作條件。是的，狀態也充當了動作的執行條件，比如之前圖中的條件「有流量」，它其實也是一個狀態。
世界狀態會因自然因素變化，比如「飽」會隨著時間流逝而變「餓」；也會因角色自身的一些動作導致變化，比如一個角色多運動，也會使「飽」變「餓」。
問題在于：
1. GOAP規劃需要時時獲取最新的狀態，才能保證規劃結果的合理性（否則餓暈了還想著運動）；
2. 「世界狀態」中有些狀態是「共享」的，比如之前說的時間，但還有一些狀態是私有的，比如「飽」，是我飽、你飽還是他飽？在一個合集里該如何區分？
如果你看過上一篇關于HTN的文章的話，你會發現這是如此的眼熟。不過沒看過也沒關系，我們將采取一種新的實現「世界狀態」的方法——原子表示。
PS：在傳統人工智能Agent中，對于環境的表示方式有三種：
1. 原子表示（Atomic）：就是單純描述某個狀態有無，通常每個狀態都只用布爾值（True/False）表示就可以，比如「有流量」。
2. 要素化表示（Factored）：進一步描述狀態的具體數值，這時，狀態可以有不同的類型，可以是字符串、整數、布爾值……在HTN中，我們就是用這種方式實現的。
3. 結構化表示（Structured）：再進一步，每個狀態不但描述具體數值，還存儲于其它數據的連接關系，就像數據結構中「圖」的節點那樣。
接下來將采用位存儲的方式進行原子表示，因為借助位運算可以方便且高效地實現比較，還省空間。缺點就是有些難懂，所以，我希望你了解如int、long的二進制存儲方式或者Unity中LayerMask，再來看以下內容。當然，這段代碼之后我也會做些舉例說明，這個類還繼承了三個接口，其用意也會在后面解釋：
using System; using System.Collections.Generic; /// /// 用位表示的世界狀態 /// publicclassGoapWorldState : IAStarNode
, IComparable
, IEquatable
{ publicconstint MAXATOMS = 64;//存儲的狀態數上限，由于用long類型存儲，最多就是64（long類型為64位整數） publiclong Values//世界狀態值 { get => values; set => values = value; } publiclong DontCare//標記未被使用的位 { get => dontCare; set => dontCare = value; } publiclong Shared => shared;//判斷共享狀態位 public GoapWorldState Parent { get; set; } publicfloat SelfCost { get; set; } publicfloat GCost { get; set; } publicfloat HCost { get; set; } publicfloat FCost => GCost + HCost; privatereadonly Dictionary
namesTable;//存儲各個狀態名字與其在values中的對應位，方便查找狀態 privateint curNamsLen;//存儲的已用狀態的長度 privatelong values; privatelong dontCare; privatelong shared; /// /// 初始化為空白世界狀態 /// public GoapWorldState() { //賦值0，可將二進制位全置0；賦值-1，可將二進制位全置1 namesTable = new Dictionary
(); values = 0L; //全置0，意為世界狀態默認為false dontCare = -1L; //全置1，意為世界狀態的位全沒有被使用 shared = -1L; //將shard的位全置1 curNamsLen = 0; } /// /// 基于某世界狀態的進一步創建，相當于復制狀態設置但清空值 /// public GoapWorldState(GoapWorldState worldState) { namesTable = new Dictionary
(worldState.namesTable);//復制狀態名稱與位的分配 values = 0L; dontCare = -1L; curNamsLen = worldState.curNamsLen;//同樣復制已使用的位長度 shared = worldState.shared;//保留狀態共享性的信息 } /// /// 根據狀態名，修改單個狀態的值 /// /// 狀態名 /// 狀態值 /// 設置狀態是否為共享 /// 修改成功與否 public bool SetAtomValue(string atomName, bool value = false, bool isShared = false) { var pos = GetIdxOfAtomName(atomName);//獲取狀態對應的位 if (pos == -1) returnfalse;//如果不存在該狀態，就返回false //將該位 置為指定value var mask = 1L << pos; values = value ? (values | mask) : (values & ~mask); dontCare &= ~mask;//標記該位已被使用 if (!isShared)//如果該狀態不共享，則修改共享位信息 { shared &= ~mask; } returntrue;//設置成功，返回true } public void Clear() { values = 0L; namesTable.Clear(); curNamsLen = 0; dontCare = -1L; } /// /// 通過狀態名獲取單個狀態在Values中的位，如果沒包含會嘗試添加 /// /// 狀態名 /// 狀態所在位 private int GetIdxOfAtomName(string atomName) { if(namesTable.TryGetValue(atomName, outint idx)) { return idx; } if(curNamsLen < MAXATOMS) { namesTable.Add(atomName, curNamsLen); return curNamsLen++; } return-1; } //——————————三個接口需要實現的函數—————————— public float GetDistance(GoapWorldState otherNode) { } public List GetSuccessors(object nodeMap) { } public int CompareTo(GoapWorldState other) { } public bool Equals(GoapWorldState other) { } public override int GetHashCode() { } }
我們以添加兩個狀態為例，相信看了這個，你會更容易理解相關函數的內容。雖說總共有64位世界狀態，但這里只看4位：
將世界狀態分為「私有」和「共享」，我們就可以讓角色更新「私有」部分，而全局系統更新「共享」部分。當需要角色規劃時，我們就用位運算將該角色的「私有」與世界的「共享」進行整合，得到對于這個角色而言的當前世界狀態。這樣對于不同角色，它們就能得到對各自的而言的世界狀態啦！
如果去除注釋，這個類的內容其實并不多，在使用時幾乎只要用到SetAtomValue函數，像這樣：
worldState = new GoapWorldState(); worldState.SetAtomValue("血量健康", true); worldState.SetAtomValue("大半夜", false, true);
接下來就是那三個接口了，首先是IAStarNode ，前文稍提過：「世界狀態」是圖中的結點，「動作」都是圖中的邊，這是我用以輔助「泛用A星搜索器」的結點接口，本文就不贅述了，只要知道：繼承了這個類，都可以作為A星搜索中的結點，從而參與搜索。完整代碼如下：
using System.Collections.Generic; publicinterfaceIAStarNode
whereT : IAStarNode
{ public T Parent { get; set; }//父節點，通過泛型使它的類型與具體類一致 publicfloat SelfCost { get; set; }//自身單步花費代價 publicfloat GCost { get; set; }//記錄g(n)，距初始狀態的代價 publicfloat HCost { get; set; }//記錄h(n)，距目標狀態的代價 publicfloat FCost { get; }//記錄f(n)，總評估代價 /// /// 獲取與指定節點的預測代價 /// public float GetDistance(T otherNode); /// /// 獲取后繼（鄰居）節點 /// /// 尋路所在的地圖，類型看具體情況轉換， /// 故用object類型 /// 后繼節點列表 public List GetSuccessors(object nodeMap); /* IComparable實現的CompareTo函數，主要用于優先隊列的比較； 一般比較可用以下函數 public int CompareTo(AStarNode other) { var res = (int)(FCost - other.FCost); if(res == 0) res = (int)(HCost - other.HCost); return res; }*/ /* IEquatable實現的Equals函數，可以自定義HashSet和Dictionary的Contains判斷依據（但同樣要重寫GetHashCode） 以及在尋路時用于比對某點是否為終點，可以根據類的特點自行繼承 */ }
這段代碼的注釋也說明了另外兩個接口的用意。
2. 動作
我們之前說過，動作包含一個「前提條件」，其實和HTN一樣，它還包含一個「行為影響」，相當于之前圖中道路指向的橢圓表示的狀態。它們也都是世界狀態，注意是世界狀態，而不是單個狀態！
為什么不設置成單個？首先，「前提條件」和「行為影響」本身就可能是多個狀態組合成的，用單個不合適；其次，將它們也設置成世界狀態（64位的long類型），方便進行統一處理與位運算。Unity中的Layer也是這樣的。
只有當前世界狀態與「前提條件」對應位的值相同時，才算滿足前提條件，這個動作才有被選擇的機會。而動作一旦執行成功，世界狀態就會發送變化，對應位上的值會被賦值為「行為影響」所設置的值。
/// /// Goap動作，也是Goap圖中的邊 /// publicclassGoapAction { publicint Cost{ get; privateset; } //動作代價，作為AI規劃的依據 public GoapWorldState Precondition => precondition; public GoapWorldState Effect => effect; privatereadonly GoapWorldState precondition; //動作得以執行的前提條件 privatereadonly GoapWorldState effect; //動作成功執行后帶來的影響，體現在對世界狀態的改變 /// /// 根據給定世界狀態樣式創建「前提條件」和「行為影響」， /// 這為了讓它們的位與世界狀態保持一致，方便進行位運算 /// /// 作為基準的世界狀態 /// 動作代價 public GoapAction(GoapWorldState baseState, int cost = 1) { Cost = cost; precondition = new GoapWorldState(baseState); effect = new GoapWorldState(baseState); } /// /// 判斷是否滿足動作執行的前提條件 /// /// 當前世界狀態 /// 是否滿足前提 public bool MetCondition(GoapWorldState worldState) { var care = ~precondition.DontCare; return (precondition.Values & care) == (worldState.Values & care); } //--------------------------------------------------------------- /// /// 判斷世界狀態是否可由執行影響導致 /// /// 當前世界狀態 /// 是否能導致 public bool MetEffect(GoapWorldState worldState) { var care = ~effect.DontCare; return (effect.Values & care) == (worldState.Values & care); } //---------------------------------------------------------------- /// /// 動作實際執行成功的影響 /// /// 實際世界狀態 public void Effect_OnRun(GoapWorldState worldState) { worldState.Values = ((worldState.Values & effect.DontCare) | (effect.Values & ~effect.DontCare)); } /// /// 設置動作前提條件，利用元組，方便一次性設置多個 /// public GoapAction SetPrecontidion(params (string, bool)[] atomName) { foreach(var atom in atomName) { precondition.SetAtomValue(atom.Item1, atom.Item2); } returnthis; } /// /// 設置動作影響 /// 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(); } }你可能發現了這個動作類的奇怪之處——它沒有像OnRunning或OnUpdate之類的動作執行函數，這樣一來要如何執行動作？是的，這個類主要是用來充當圖的邊，來連接各個狀態，它會作為 字典中的值，并于一個動作名字符串綁定。我們會通過動作名，再查找另一個同樣以動作名為鍵、但值為事件的字典，找到對應的事件，這個事件才是真正運行的動作函數。
這樣豈不多此一舉？其實這是為了提高GOAP圖的重用性。如果GOAP中的道路并不是真正的動作函數，而是用了動作名來標記。那么我們可以為多個角色設計同一種動作，但不同的表現。比如「攻擊」動作，在弓箭手中就是射擊函數，槍手中就是開火函數……這樣一來，即便不同角色都可以使用同一張GOAP圖，不用重復創建（除非有特殊需求）。
這樣是GOAP的一般做法，只用少數GOAP圖，而不同角色可以共同使用一張GOAP圖來進行互不干擾的規劃。這可以省很多代碼量，試想在有限狀態機中，不做特殊處理你都無法讓不同敵人共用「攻擊」狀態，就得不斷寫大同小異的代碼。GOAP的這種將結構與邏輯分離的做法，就可以很方便地復用結構或進行定制化設計，也是其優勢之一。
PS：GOAP圖也得用「圖」這一數據結果存儲，而這種數據結構在C# 中是沒有提供的，得自己實現，這里我給個簡單的，方便后續其他功能（如果你有自己的一套，也可以用自己的，只是后續文章中相應的函數要進行替換）：
public classMyGraph
{ publicreadonly HashSet NodeSet; //節點列表 publicreadonly Dictionary > NeighborList; //鄰居列表 publicreadonly Dictionary<(TNode, TNode), List > EdgeList; //邊列表 public MyGraph() { NodeSet = new HashSet (); NeighborList = new Dictionary >(); EdgeList = new Dictionary<(TNode, TNode), List >(); } /// /// 尋找指定節點 /// /// 找到的節點，沒找到時返回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; } /// /// 添加節點，用HashSet，包含重復檢測 /// public bool AddNode(TNode node) { return NodeSet.Add(node); } /// /// （前提是邊兩端結點已添加進圖）添加指定邊，含空節點判斷、重復添加判斷 /// /// 邊起點 /// 邊終點 /// 指定邊 /// 添加成功與否 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; } /// /// 移除指定節點 /// /// 移除成功與否 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)); } /// /// 獲取指定節點可抵達的所有鄰居節點 /// public List GetNeighbor(TNode node) { NeighborList.TryGetValue(node, out List res); return res; } /// /// 獲取指定節點所延伸出的所有邊 /// 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星節點
接下來要實現的就是那三個接口所需的函數了，這三個接口其實都是為了方便尋找「路徑」，GOAP會采用啟發式搜索，就像A星尋路所用的那樣。所謂「啟發式搜索」就是有按照一定「啟發值」進行的搜索，它的反面就是「盲目搜索」，如深度優先搜索、廣度優先搜索。啟發式搜索需要設計「啟發函數」來計算「啟發值」。
在A星尋路中，我們通過計算「當前位置離起點的距離 + 當前位置離終點的距離」做為啟發值來尋找最短路徑；類似的，在我們實現的這個GOAP中，我們會通過計算「起點狀態至當前狀態累計的動作代價+ 當前狀態與目標狀態的相關度」作為啟發值。
累計代價，也相當于與起始狀態的「距離」；與目標狀態的相關度，在世界狀態類中已經說明了，就是比較當前狀態與目標狀態的有效位的值有多少是相同的，通常相同的越多就越接近。當然，思路不唯一，可以搜索《數據挖掘》相關的文章，了解更多關于數據相關度的計算。
PS：在尋路時，常需要選取已探索過的節點中具有最小啟發值的節點。用遍歷倒也能做到，但總歸效率不高，故可以用「堆」，也就是「優先隊列」：
//堆屬于常用數據結構中的一種，我默認大家都會了，原理就不加以注釋說明了 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; //記錄結點在數組中的位置，方便查找 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; } }
三個接口所需的函數實現如下：
/// /// 用位表示的世界狀態 /// publicclassGoapWorldState : IAStarNode
, IComparable
, IEquatable
{ …… /// /// 計算該世界狀態與指定世界狀態的差異度 /// public float GetDistance(GoapWorldState otherNode) { var care = otherNode.dontCare ^ -1L; var diff = (values & care) ^ (otherNode.values & care); int dist = 0; //統計有多少位是不同的，以表示差異度 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); //根據找到的動作，對抵達下個結點的代價進行計算 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星搜索器中，總是「動作的條件」對比「當前的世界狀態」，即currentNode.Equals(target) 如「動作的條件」：餓-true，而「當前的世界狀態」：餓-true，累-true，困-true；顯然此時世界狀態應當滿足條件 這樣可以避免當前世界狀態過于“包容”卻被誤判不滿足*/ return (values & ~dontCare) == (other.values & ~dontCare); } public override int GetHashCode() { return HashCode.Combine(values & ~dontCare, dontCare); } }
4. 動作集
照理說，動作集不過是動作的合集，單獨將它也制成一個類，是為了方便「動作序列」規劃，主要體現在GetPossibleTrans函數，根據傳入的節點的世界狀態，在合集中遍歷出「前提條件」滿足的動作：
using System.Collections.Generic; publicclassGoapActionSet { public MyGraph string> actionGraph; // 動作與狀態構成的圖 privatereadonly Dictionary
actionSet; public GoapActionSet() { actionGraph = new MyGraph string>(); actionSet = new Dictionary
(); } public GoapAction this[string idx] { get => actionSet[idx]; } /// /// 添加動作至動作集合中 /// /// 動作名 /// 對應動作 /// 動作集，方便連續添加 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; } /// /// 返回兩個狀態轉化的動作名 /// /// 起點狀態 /// 狀態后的狀態 /// 所需執行動作名 public string GetTransAction(GoapWorldState from, GoapWorldState to) { return actionGraph.FindEdge(from, to)[0]; } }
5. A星尋路
一切條件都準備好了，現在實現下用來「尋路」的類。首先，我們會進行反向搜索，意思是說，我們不會「起始狀態-->目標狀態」，而是「目標狀態-->起始狀態」，如果成功找到，就將得到的動作序列逆向執行。
為什么這么麻煩？其實恰恰相反，這還是一種簡化。如果真的「起始狀態-->目標狀態」，未必最終會找到目標狀態（因為有可能能抵達的動作暫時條件不滿足）；但反向搜索，必定會包含目標狀態，也一定會找到一條路（因為總會抵達一個當前已經符合的世界狀態，否則就是設計的有問題了），只不過可能不是最短的。
我們也能接受這種結果，雖說非最優解，但這種不確定因素，也變相讓AI增加了點隨機性，更接近真實決策情況。
它的整體搜索過程和A星尋路是一樣的，直接用「泛用A星搜索器」即可：
using System; using System.Collections.Generic; using JufGame.Collections.Generic; /// /// A星搜索器，T_Node額外實現IComparable用于優先隊列的比較，實現IEquatable用于HashSet和Dictionary等同一性的判斷 /// /// 搜索的圖類 /// 搜索的節點類 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用于限制路徑節點的上限，避免陷入無止境搜索的情況 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;//取出邊緣集中最小代價的節點 openList.PopHeap(); closeList.Add(currentNode);//擬定移動到該節點，將其放入探索集 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);//找出當前節點的后繼節點 if(successors == null) { return; } for (int i = 0; i < successors.Count; ++i) { sucNode = successors[i]; if (closeList.Contains(sucNode))//后繼節點已被探索過就忽略 continue; tpCost = curNode.GCost + sucNode.SelfCost; isNotInOpenList = !openList.Contains(sucNode); if (isNotInOpenList || tpCost < sucNode.GCost) { sucNode.GCost = tpCost; sucNode.HCost = sucNode.GetDistance(endNode);//計算啟發函數估計值 sucNode.Parent = curNode;//記錄父節點，方便回溯 if (isNotInOpenList) { openList.PushHeap(sucNode); } } } } }
6. 代理器
我們最后創建一個「代理器」，它用來整合了上述內容，并統籌運行：
public enum EStatus { Failure, Success, Running, Aborted, Invalid } publicclassGoapAgent { privatereadonly GoapActionSet actionSet; //動作集 publicreadonly GoapWorldState curSelfState; //當前自身狀態，主要是存儲私有狀態 privatereadonly AStar_Searcher goapAStar; privatereadonly Dictionary
actionFuncs; //各動作名字對應的動作函數 private Stack
actionPlan;//存儲規劃出的動作序列 private Stack path; private EStatus curState;//存儲當前動作的執行結果 privatebool canContinue;//是否能夠繼續執行，記錄動作序列全部是否執行完了 private GoapAction curAction;//記錄當前執行的動作 private Func curActionFunc; //記錄當前運行的動作函數 /// /// 初始化代理器 /// /// 世界狀態，用來復制成自身狀態 /// 動作集 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 (); } /// /// 修改自身狀態值 /// public bool SetAtomValue(string stateName, bool value) { return curSelfState.SetAtomValue(stateName, value); } /// /// 為動作名設置對應的動作函數 /// public void SetActionFunc(string actionName, Func func ) { actionFuncs.Add(actionName, func); } /// /// 規劃GOAP并運行 /// /// /// public void RunPlan(GoapWorldState curWorldState, GoapWorldState goal) { UpdateSelfState(curWorldState);//將自身的私有狀態與世界的共享狀態融合，得到真正的「當前世界狀態」 if (curState == EStatus.Failure) //當前狀態為「失敗」，就表示動作執行失敗 { //那就重新規劃，找出新的動作序列 actionPlan.Clear(); goapAStar.FindPath(goal, curSelfState, path); //通過狀態序列得到動作序列 path.TryPop(outvar cur); while(path.Count != 0) { actionPlan.Push(actionSet.GetTransAction(cur, path.Peek())); cur = path.Pop(); } } if(curState == EStatus.Success)//執行結果為「成功」，表示動作順利執行完 { curAction.Effect_OnRun(curWorldState); //動作就會對全局世界狀態造成影響 /*這同樣要更新自身狀態，以防這次改變的是「私有」狀態，全局世界狀態可是只維護「共享」部分。 所以需要自身狀態也記錄下這次影響，即便是共享狀態也沒關系，反正下次會與世界的共享狀態融合*/ curAction.Effect_OnRun(curSelfState); } //如果執行結果不是「運行中」，就表示上個動作要么成功了，要么失敗了。都該取出動作序列中新的動作來執行 if (curState != EStatus.Running) { canContinue = actionPlan.TryPop(outstring curActionName); if (canContinue)//如果成功取出動作，就根據動作名，選出對應函數和動作 { curActionFunc = actionFuncs[curActionName]; curAction = actionSet[curActionName]; } } curState = canContinue && curAction.MetCondition(curSelfState) ? curActionFunc() : EStatus.Failure; } /// /// 中斷當前Goap執行 /// public void AbortedGoapCurState() { curState = EStatus.Aborted; } /// /// 更新自身狀態的共享部分與當前世界狀態同步 /// private void UpdateSelfState(GoapWorldState curWorldState) { curSelfState.Values = (curWorldState.Values & curWorldState.Shared) | (curSelfState.Values & ~curWorldState.Shared); } }
注意，代碼里的這個部分，因為A星搜索得到的是結點——也就是狀態，但我們所需要的是鏈接狀態的動作，所以要再「加工」一下：
goapAStar.FindPath(goal, curSelfState, path); //通過狀態序列得到動作序列 path.TryPop(out var cur); while(path.Count != 0) { actionPlan.Push(actionSet.GetTransAction(cur, path.Peek())); cur = path.Pop(); }這個類中，RunPlan函數與上一期的HTN中的基本一樣。但我想可能有些人還不大明白UpdateSelfState函數是如何融合自身狀態與世界狀態的，我就簡單舉個例：
可以看到得到的值，恰好保留了世界狀態的共享部分和自身狀態的私有部分。其實這也并非「恰好」，這樣的位運算理應得到這樣的結果才是。你也可以自己動手嘗試一些值或者用更多位的數來驗證。
四、尾聲
GOAP的缺點主要是在設計難度上，它的設計相較FSM、行為樹那些不那么直接，你需要把控好動作的條件和影響對應的狀態，比其它決策方法更費腦子些。因為GOAP沒有顯示的結構，如何定義好一個狀態，使它能在邏輯層面合理地成為一個動作的前提條件，又能成為另一個動作條件的影響結果（比如「有流量」，想想看，將其做為條件可以設計什么動作？作為影響結果又應該怎么設計呢？）是比較考驗開發人員的架構設計的。但毋庸置疑的是，在面對較復雜的AI時，它的代碼量一定是小于FSM、行為樹和HTN的。而且添加和減少動作也不需要進行過多代碼修改，只要將新行動加入到動作集或將欲剔除的動作從動作集中刪去就可以，這也是它沒有顯式結構的好處。
這里也簡單用上文所學內容做一個簡單的太空射擊飛船敵人的AI：gitee項目[4]
在EnemyConfig中為敵人指定了GOAP圖并共用，一個非常簡單的敵人邏輯（只是用GOAP實現了而已）：當敵人健康時會嘗試瞄準玩家后射擊，當玩家弱勢（無力）時，敵人追擊玩家；當敵人自身不安全時會退避并以較低命中率的方式射擊：
goal = new GoapWorldState(WarSpaceManager.worldState); goal.SetAtomValue("擊殺玩家", true); actionSet = new GoapActionSet(); actionSet .AddAction("低命中射擊", new GoapAction(WarSpaceManager.worldState, 1) .SetPrecontidion(("安全區內", true)) .SetEffect(("擊殺玩家", true))) .AddAction("追擊", new GoapAction(WarSpaceManager.worldState, 4) .SetPrecontidion(("彈藥充足", true), ("玩家無力", true)) .SetEffect(("擊殺玩家", true))) .AddAction("瞄準玩家", new GoapAction(WarSpaceManager.worldState, 3) .SetPrecontidion(("瞄準就緒", false)) .SetEffect(("瞄準就緒", true))) .AddAction("射擊", new GoapAction(WarSpaceManager.worldState, 2) .SetPrecontidion(("瞄準就緒", true)) .SetEffect(("擊殺玩家", true))) .AddAction("躲避", new GoapAction(WarSpaceManager.worldState, 1) .SetPrecontidion(("安全", false)) .SetEffect(("安全區內", true)));到這里就結束了。
參考：
[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， 如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群： 793972859 ）。
近期精彩回顧
【萬象更新】
【萬象更新】
【萬象更新】
【萬象更新】
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
