游戏AI行为决策——GOAP（目标导向型行为规划）
- 作者：admin
- /
- 时间：5小时前
- /
- 浏览：21 次
- /
- 分类：厚积薄发
【USparkle专栏】如果你深怀绝技，爱“搞点研究”，乐于分享也博采众长，我们期待你的加入，让智慧的火花碰撞交织，让知识的传递生生不息！
一、前言
像先前提到的有限状态机、行为树、HTN，它们实现的AI行为，虽说能针对不同环境作出不同反应，但应对方法是写死了的。有限状态机终究是在几个状态间进行切换、行为树也是根据提前设计好的树来搜索……你会发现，游戏AI角色表现出的智能程度，终究与开发者的设计结构有关，就有限状态机而言，各个状态如何切换很大程度上就影响了AI智能的表现。
那有没有什么决策方法，能够仅需设计好角色需要的动作，而它自己就能合理决定要选择哪些动作完成目标呢？这样的话，角色AI的行为智能程度会更上一层楼，毕竟它不再被写死的决策结构束缚；我们在添加更多AI行为时，也可以简单地直接将它放在角色需要的动作集里就好，减少了工作量，不必像行为树那样，还要考虑节点间的连接。
没错，GOAP（目标导向型行为规划）就可以做到。但请注意，并不是说GOAP就比其它决策方法好，后面也会提到它的缺点。选择何种决策方法还得根据实际项目和自身需求。
PS：本教程需要你具备以下前提知识：
- 知道数据结构、堆/优先队列、栈、图。
- 知道A星寻路的流程，如不了解可看此视频[1]。
- 基本的位运算与位存储（能做到理解Unity中的Layer和LayerMask的程度就行）。
二、运行逻辑
我们来看个简单的寻路问题：你能找到从A到B的最短路线吗？注意，道路是单向的。
聪明如你，这并不难找到：
现在，加大难度，假设每条道路口都有一个门，红色表示门关上了，蓝色表示门开着，你还能找出可达成的最短A到B路线吗？
同样不难：
这样就足够了，GOAP的规划就是这么一个过程。只是把每个节点都当成一个状态，每条道路都当作一个动作、道路长度作为动作代价、路口的门作为动作执行条件，然后像你这样寻找出一条可以执行的最短「路线」，并记录下途径的道路（注意，不是节点），这样就得到了「动作序列」，再让AI角色逐一执行。GOAP中的图会长成下面这样（只画出了一条路的样子，但相信你们能举一反三的）：
GOAP就是在不断执行「从现有状态到目标状态」，上图中的「现有状态」和「目标状态」分别就是「饿」和「饱」。请注意，虽说用了不同形状，但中间的那些椭圆节点，比如「在上网」，也是和「饿」、「饱」同类别的存在。也就是说「在上网」也可以作为现有状态或目标状态。
可想而知，只要状态够多，动作够多，AI就能做出更复杂的动作。虽说这对其它决策方法也成立，但GOAP不需要我们手动设置各动作、状态之间的关系，它能自行规划出要做的一系列动作，更省事且更智能，甚至可以规划出超出原本设想但又合理的动作序列。
希望我讲明白了它的运作（如果还是感觉有点不懂，可以看看这个视频[2]），下面一起来实现一个简单的GOAP进一步了解吧！顺带提一下，在Unity资源商店有免费的GOAP插件，并且做了可视化处理以及多线程优化，各位真的想将GOAP运用于项目的话，更推荐去学习使用成熟的插件。
三、代码实现
本文「世界状态」的实现参考了GitHub上一C语言版本的GOAP[3]。
1. 世界状态
所谓「世界状态」其实就是存储所有的状态放在一块儿的合集。而状态其实还有一个隐藏身份——动作条件。是的，状态也充当了动作的执行条件，比如之前图中的条件「有流量」，它其实也是一个状态。
世界状态会因自然因素变化，比如「饱」会随着时间流逝而变「饿」；也会因角色自身的一些动作导致变化，比如一个角色多运动，也会使「饱」变「饿」。
问题在于：
- GOAP规划需要时时获取最新的状态，才能保证规划结果的合理性（否则饿晕了还想着运动）；
- 「世界状态」中有些状态是「共享」的，比如之前说的时间，但还有一些状态是私有的，比如「饱」，是我饱、你饱还是他饱？在一个合集里该如何区分？
如果你看过上一篇关于HTN的文章的话，你会发现这是如此的眼熟。不过没看过也没关系，我们将采取一种新的实现「世界状态」的方法——原子表示。
PS：在传统人工智能Agent中，对于环境的表示方式有三种：
- 原子表示（Atomic）：就是单纯描述某个状态有无，通常每个状态都只用布尔值（True/False）表示就可以，比如「有流量」。
- 要素化表示（Factored）：进一步描述状态的具体数值，这时，状态可以有不同的类型，可以是字符串、整数、布尔值……在HTN中，我们就是用这种方式实现的。
- 结构化表示（Structured）：再进一步，每个状态不但描述具体数值，还存储于其它数据的连接关系，就像数据结构中「图」的节点那样。
接下来将采用位存储的方式进行原子表示，因为借助位运算可以方便且高效地实现比较，还省空间。缺点就是有些难懂，所以，我希望你了解如int、long的二进制存储方式或者Unity中LayerMask，再来看以下内容。当然，这段代码之后我也会做些举例说明，这个类还继承了三个接口，其用意也会在后面解释：
using System;
using System.Collections.Generic;
/// <summary>
/// 用位表示的世界状态
/// </summary>
publicclassGoapWorldState : IAStarNode<GoapWorldState>, IComparable<GoapWorldState>, IEquatable<GoapWorldState>
{
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<string, int> namesTable;//存储各个状态名字与其在values中的对应位，方便查找状态
privateint curNamsLen;//存储的已用状态的长度
privatelong values;
privatelong dontCare;
privatelong shared;
/// <summary>
/// 初始化为空白世界状态
/// </summary>
public GoapWorldState()
{
//赋值0，可将二进制位全置0；赋值-1，可将二进制位全置1
namesTable = new Dictionary<string, int>();
values = 0L; //全置0，意为世界状态默认为false
dontCare = -1L; //全置1，意为世界状态的位全没有被使用
shared = -1L; //将shard的位全置1
curNamsLen = 0;
}
/// <summary>
/// 基于某世界状态的进一步创建，相当于复制状态设置但清空值
/// </summary>
public GoapWorldState(GoapWorldState worldState)
{
namesTable = new Dictionary<string, int>(worldState.namesTable);//复制状态名称与位的分配
values = 0L;
dontCare = -1L;
curNamsLen = worldState.curNamsLen;//同样复制已使用的位长度
shared = worldState.shared;//保留状态共享性的信息
}
/// <summary>
/// 根据状态名，修改单个状态的值
/// </summary>
/// <param name="atomName">状态名</param>
/// <param name="value">状态值</param>
/// <param name="isShared">设置状态是否为共享</param>
/// <returns>修改成功与否</returns>
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;
}
/// <summary>
/// 通过状态名获取单个状态在Values中的位，如果没包含会尝试添加
/// </summary>
/// <param name="atomName">状态名</param>
/// <returns>状态所在位</returns>
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<GoapWorldState> 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
using System.Collections.Generic;
publicinterfaceIAStarNode<T> whereT : IAStarNode<T>
{
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)，总评估代价
/// <summary>
/// 获取与指定节点的预测代价
/// </summary>
public float GetDistance(T otherNode);
/// <summary>
/// 获取后继（邻居）节点
/// </summary>
/// <param name="nodeMap">寻路所在的地图，类型看具体情况转换，
/// 故用object类型</param>
/// <returns>后继节点列表</returns>
public List<T> 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也是这样的。
只有当前世界状态与「前提条件」对应位的值相同时，才算满足前提条件，这个动作才有被选择的机会。而动作一旦执行成功，世界状态就会发送变化，对应位上的值会被赋值为「行为影响」所设置的值。
/// <summary>
/// Goap动作，也是Goap图中的边
/// </summary>
publicclassGoapAction
{
publicint Cost{ get; privateset; } //动作代价，作为AI规划的依据
public GoapWorldState Precondition => precondition;
public GoapWorldState Effect => effect;
privatereadonly GoapWorldState precondition; //动作得以执行的前提条件
privatereadonly GoapWorldState effect; //动作成功执行后带来的影响，体现在对世界状态的改变
/// <summary>
/// 根据给定世界状态样式创建「前提条件」和「行为影响」，
/// 这为了让它们的位与世界状态保持一致，方便进行位运算
/// </summary>
/// <param name="baseState">作为基准的世界状态</param>
/// <param name="cost">动作代价</param>
public GoapAction(GoapWorldState baseState, int cost = 1)
{
Cost = cost;
precondition = new GoapWorldState(baseState);
effect = new GoapWorldState(baseState);
}
/// <summary>
/// 判断是否满足动作执行的前提条件
/// </summary>
/// <param name="worldState">当前世界状态</param>
/// <returns>是否满足前提</returns>
public bool MetCondition(GoapWorldState worldState)
{
var care = ~precondition.DontCare;
return (precondition.Values & care) == (worldState.Values & care);
}
//---------------------------------------------------------------
/// <summary>
/// 判断世界状态是否可由执行影响导致
/// </summary>
/// <param name="worldState">当前世界状态</param>
/// <returns>是否能导致</returns>
public bool MetEffect(GoapWorldState worldState)
{
var care = ~effect.DontCare;
return (effect.Values & care) == (worldState.Values & care);
}
//----------------------------------------------------------------
/// <summary>
/// 动作实际执行成功的影响
/// </summary>
/// <param name="worldState">实际世界状态</param>
public void Effect_OnRun(GoapWorldState worldState)
{
worldState.Values = ((worldState.Values & effect.DontCare) | (effect.Values & ~effect.DontCare));
}
/// <summary>
/// 设置动作前提条件，利用元组，方便一次性设置多个
/// </summary>
public GoapAction SetPrecontidion(params (string, bool)[] atomName)
{
foreach(var atom in atomName)
{
precondition.SetAtomValue(atom.Item1, atom.Item2);
}
returnthis;
}
/// <summary>
/// 设置动作影响
/// </summary>
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之类的动作执行函数，这样一来要如何执行动作？是的，这个类主要是用来充当图的边，来连接各个状态，它会作为<string, GoapAction>字典中的值，并于一个动作名字符串绑定。我们会通过动作名，再查找另一个同样以动作名为键、但值为事件的字典，找到对应的事件，这个事件才是真正运行的动作函数。
这样岂不多此一举？其实这是为了提高GOAP图的重用性。如果GOAP中的道路并不是真正的动作函数，而是用了动作名来标记。那么我们可以为多个角色设计同一种动作，但不同的表现。比如「攻击」动作，在弓箭手中就是射击函数，枪手中就是开火函数……这样一来，即便不同角色都可以使用同一张GOAP图，不用重复创建（除非有特殊需求）。
这样是GOAP的一般做法，只用少数GOAP图，而不同角色可以共同使用一张GOAP图来进行互不干扰的规划。这可以省很多代码量，试想在有限状态机中，不做特殊处理你都无法让不同敌人共用「攻击」状态，就得不断写大同小异的代码。GOAP的这种将结构与逻辑分离的做法，就可以很方便地复用结构或进行定制化设计，也是其优势之一。
PS：GOAP图也得用「图」这一数据结果存储，而这种数据结构在C# 中是没有提供的，得自己实现，这里我给个简单的，方便后续其他功能（如果你有自己的一套，也可以用自己的，只是后续文章中相应的函数要进行替换）：
public classMyGraph<TNode, TEdge>
{
publicreadonly HashSet<TNode> NodeSet;//节点列表
publicreadonly Dictionary<TNode, List<TNode>> NeighborList;//邻居列表
publicreadonly Dictionary<(TNode, TNode), List<TEdge>> EdgeList;//边列表
public MyGraph()
{
NodeSet = new HashSet<TNode>();
NeighborList = new Dictionary<TNode, List<TNode>>();
EdgeList = new Dictionary<(TNode, TNode), List<TEdge>>();
}
/// <summary>
/// 寻找指定节点
/// </summary>
/// <returns>找到的节点，没找到时返回null</returns>
public TNode FindNode(TNode node)
{
NodeSet.TryGetValue(node, out TNode res);
return res;
}
/// <summary>
/// 寻找指点起、终点之间直接连接的所有边
/// </summary>
/// <param name="source">起点</param>
/// <param name="target">终点</param>
/// <returns>找到的边，没找到时返回null</returns>
public List<TEdge> 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;
}
/// <summary>
/// 添加节点，用HashSet，包含重复检测
/// </summary>
public bool AddNode(TNode node)
{
return NodeSet.Add(node);
}
/// <summary>
/// （前提是边两端结点已添加进图）添加指定边，含空节点判断、重复添加判断
/// </summary>
/// <param name="source">边起点</param>
/// <param name="target">边终点</param>
/// <param name="edge">指定边</param>
/// <returns>添加成功与否</returns>
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<TEdge>());
}
var allEdges = EdgeList[nodePairs];
if(!allEdges.Contains(edge))
{
allEdges.Add(edge);
if(!NeighborList.ContainsKey(source))
{
NeighborList.Add(source, new List<TNode>());
}
NeighborList[source].Add(target);
returntrue;
}
returnfalse;
}
/// <summary>
/// 移除指定节点
/// </summary>
/// <returns>移除成功与否</returns>
public bool RemoveNode(TNode node)
{
return NodeSet.Remove(node);
}
/// <summary>
/// 移除指定起、终点的指定边
/// </summary>
/// <param name="source">边起点</param>
/// <param name="target">边终点</param>
/// <param name="edge">指定边</param>
/// <returns>移除成功与否</returns>
public bool RemoveEdge(TNode source, TNode target, TEdge edge)
{
var allEdges = FindEdge(source, target);
return allEdges != null && allEdges.Remove(edge);
}
/// <summary>
/// 移除指定起、终点的所有边
/// </summary>
/// <param name="source">边起点</param>
/// <param name="target">边终点</param>
/// <returns>移除成功与否</returns>
public bool RemoveEdgeList(TNode source, TNode target)
{
return EdgeList.Remove((source, target));
}
/// <summary>
/// 获取指定节点可抵达的所有邻居节点
/// </summary>
public List<TNode> GetNeighbor(TNode node)
{
NeighborList.TryGetValue(node, out List<TNode> res);
return res;
}
/// <summary>
/// 获取指定节点所延伸出的所有边
/// </summary>
public List<TEdge> GetConnectedEdge(TNode node)
{
var resEdge = new List<TEdge>();
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<T> whereT : IComparable<T>
{
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<T, int> idxTable; //记录结点在数组中的位置，方便查找
public MyHeap(int size, bool isReverse = false)
{
CurLength = 0;
capacity = size;
heapArr = new T[size];
idxTable = new Dictionary<T, 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;
}
}
三个接口所需的函数实现如下：
/// <summary>
/// 用位表示的世界状态
/// </summary>
publicclassGoapWorldState : IAStarNode<GoapWorldState>, IComparable<GoapWorldState>, IEquatable<GoapWorldState>
{
……
/// <summary>
/// 计算该世界状态与指定世界状态的差异度
/// </summary>
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<GoapWorldState> 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<GoapWorldState, string> actionGraph; // 动作与状态构成的图
privatereadonly Dictionary<string, GoapAction> actionSet;
public GoapActionSet()
{
actionGraph = new MyGraph<GoapWorldState, string>();
actionSet = new Dictionary<string, GoapAction>();
}
public GoapAction this[string idx]
{
get => actionSet[idx];
}
/// <summary>
/// 添加动作至动作集合中
/// </summary>
/// <param name="actionName">动作名</param>
/// <param name="newAction">对应动作</param>
/// <returns>动作集，方便连续添加</returns>
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;
}
/// <summary>
/// 返回两个状态转化的动作名
/// </summary>
/// <param name="from">起点状态</param>
/// <param name="to">状态后的状态</param>
/// <returns>所需执行动作名</returns>
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;
/// <summary>
/// A星搜索器，T_Node额外实现IComparable用于优先队列的比较，实现IEquatable用于HashSet和Dictionary等同一性的判断
/// </summary>
/// <typeparam name="T_Map">搜索的图类</typeparam>
/// <typeparam name="T_Node">搜索的节点类</typeparam>
publicclassAStar_Searcher<T_Map, T_Node> whereT_Node: IAStarNode<T_Node>, IComparable<T_Node>, IEquatable<T_Node>
{
privatereadonly HashSet<T_Node> closeList;//探索集
privatereadonly MyHeap<T_Node> openList;//边缘集
privatereadonly T_Map nodeMap;//搜索空间（地图）
public AStar_Searcher(T_Map map, int maxNodeSize = 200)
{
nodeMap = map;
closeList = new HashSet<T_Node>();
//maxNodeSize用于限制路径节点的上限，避免陷入无止境搜索的情况
openList = new MyHeap<T_Node>(maxNodeSize);
}
/// <summary>
/// 搜索（寻路）
/// </summary>
/// <param name="start">起点</param>
/// <param name="target">终点</param>
/// <param name="pathRes">返回生成的路径</param>
public void FindPath(T_Node start, T_Node target, Stack<T_Node> 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<T_Node> 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<GoapActionSet, GoapWorldState> goapAStar;
privatereadonly Dictionary<string, Func<EStatus>> actionFuncs; //各动作名字对应的动作函数
private Stack<string> actionPlan;//存储规划出的动作序列
private Stack<GoapWorldState> path;
private EStatus curState;//存储当前动作的执行结果
privatebool canContinue;//是否能够继续执行，记录动作序列全部是否执行完了
private GoapAction curAction;//记录当前执行的动作
private Func<EStatus> curActionFunc;//记录当前运行的动作函数
/// <summary>
/// 初始化代理器
/// </summary>
/// <param name="baseWorldState">世界状态，用来复制成自身状态</param>
/// <param name="actionSet">动作集</param>
public GoapAgent(GoapWorldState baseWorldState, GoapActionSet actionSet)
{
curSelfState = new GoapWorldState(baseWorldState)
{
DontCare = baseWorldState.DontCare
};
actionFuncs = new Dictionary<string, Func<EStatus>>();
actionPlan = new Stack<string>();
this.actionSet = actionSet;
goapAStar = new AStar_Searcher<GoapActionSet, GoapWorldState>(this.actionSet);
path = new Stack<GoapWorldState>();
}
/// <summary>
/// 修改自身状态值
/// </summary>
public bool SetAtomValue(string stateName, bool value)
{
return curSelfState.SetAtomValue(stateName, value);
}
/// <summary>
/// 为动作名设置对应的动作函数
/// </summary>
public void SetActionFunc(string actionName, Func<EStatus> func)
{
actionFuncs.Add(actionName, func);
}
/// <summary>
/// 规划GOAP并运行
/// </summary>
/// <param name="curWorldState"></param>
/// <param name="goal"></param>
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;
}
/// <summary>
/// 中断当前Goap执行
/// </summary>
public void AbortedGoapCurState()
{
curState = EStatus.Aborted;
}
/// <summary>
/// 更新自身状态的共享部分与当前世界状态同步
/// </summary>
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星寻路的流程视频
[2] 视频
[3] C语言版本的GOAP
[4] gitee项目
这是侑虎科技第1889篇文章，感谢作者狐王驾虎供稿。欢迎转发分享，未经作者授权请勿转载。如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群：793972859）
作者主页：https://home.cnblogs.com/u/OwlCat
再次感谢狐王驾虎的分享，如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群：793972859）