AI决策-状态机+行为树+HTN+GOAP
1 前言
先放一下b站上games104关于简单ai的介绍视频
16.游戏引擎Gameplay玩法系统：基础AI (Part 2) | GAMES104-现代游戏引擎：从入门到实践
17.游戏引擎Gameplay玩法系统：高级AI (Part 1) | GAMES104-现代游戏引擎：从入门到实践
本篇是基于该games104视频内容的笔记性质的总结，根本目的是为本人理顺其中略微混乱的内容，具体内容以该视频为准（手动叠甲）
再放一篇大佬的帖子🙏受益匪浅
2 主观概述
简单ai中最古老最基础也是最容易理解的就是状态机，状态机的写法要求开发者给ai体设置多个"状态"，具体表现为——规定ai体在某个"状态"下执行的动作，为状态之间的转换设置条件
其中需要明确的是，
- 在任何时刻下的ai体都需要处于某"状态"中（可以不止一个，详见"并发状态机"）
- 任何状态都需要有被转换和转换为其他状态的条件（否则就相当于走进死胡同了）
- 状态的转换条件需要是可量化的（不然机器读不懂）
我对状态机的理解是特殊的循环，还有进阶一点的分层和并发状态机此处不赘述
但当外界情况复杂起来，ai体有大量状态时（或许可以用分层状态机简化，但这里假设分层之后仍复杂），常规的状态机写起来就会让人头大，毕竟新的状态很可能要飞很多根线连到原先的状态，这个时候我们就得用到行为树了（提一嘴，视频里提到行为树起源于03-04年间的halo）
我主观认为基础行为树是可以脱离状态机来理解的（因为我玩UE的时候是先接触了行为树再接触状态机的💦）
我对行为树的理解是特殊的遍历+if-else，至于有多特殊就等下展开
到后面的HTN（Hierarchical Tasks Network 层次任务网络）和GOAP（Goal-Oriented Action Planning 目标导向行为规划）就必须要提到，前面的状态机和行为树像是条件反射般地执行开发者设定的任务，而这两个ai就更像是开发者给ai设定一系列可选的行为，ai通过感知这个世界自己设定目的，然后根据开发者所给来选择要做的事
我们可以简记为：前两者是条件反射，后两者是目标导向
2.1 全篇速览举例
（这个例子看不懂的话就是不会接下来要讲的东西）
此处举一个比较直观的例子：我们需要做一个项羽和一个刘邦
2.1.1 用状态机的写法
项羽有"巡逻"，“冲锋”，“开大”，这三个的转换关系分别是，默认处于巡逻状态，在看到敌人后向其冲锋，当与敌人距离小于某个值时开大，随后直接进入巡逻状态，以此反复
刘邦就有"待命"，“摇人”，“撤退”，这三个的转换关系分别是，默认处于待命状态，看到敌人后进入摇人状态，随后直接进入撤退状态，在看不到敌人后进入待命状态，以此反复
2.1.2 用行为树的写法
每隔一段时间执行一次行为树
项羽：若看不到敌人就巡逻，若看到敌人就冲锋，冲锋后若敌人在身旁就开大
刘邦：若看不到敌人就待命，若看到敌人就摇人，然后撤退
其中是否看到敌人就是状态节点，其余逻辑就是动作节点，根节点是Sequence
2.1.3 用HTN的写法
（以下仅以项羽举例）
在HTN Domain中定义以下Node：
| precondition | action | effect |
|---|---|---|
| 看到敌人 && 不在敌人身边 | 冲锋 | 在敌人身边 |
| 看到敌人 && 在敌人身边 | 开大 | 无（造成伤害） |
| 看不到敌人 | 巡逻 | 无（移动） |
2.1.4 用GOAP的写法
（以下仅以项羽举例）
在Goal Set中定义以下Node：
| precondition | goal | state | priority |
|---|---|---|---|
| 看到敌人 && 在敌人身边 | 攻击敌人 | 无（造成伤害） | 1 |
| 看到敌人 && 不在敌人身边 | 靠近敌人 | 在敌人身边 | 2 |
| 看不到敌人 | 巡逻 | 无（移动） | 3 |
在Action Set中定义以下Node：
| precondition | action | effect | cost（这一栏需要根据情况定） |
|---|---|---|---|
| 攻击敌人 | 开大 | 无（造成伤害） | ？ |
| 靠近敌人 | 冲锋 | 在敌人身边 | ？ |
| 巡逻 | 巡逻（具体逻辑） | 无（移动） | ？ |
3 状态机
（基础状态机请见我之前的帖子，那是基于YouTube教程的总结，此处不展开）
4 行为树
（要了解行为树，我会推荐看看UE蓝图行为树是怎么样的）
原教程用这样一句话来引入行为树：“人的思考是分支性思考”
行为树就是如此，用自然语言来描述一个行为树时，我们会这样说：当有作业要写时，我会看看我的手上/桌子上/抽屉里有没有纸笔，有的话就拿过来开写，没有的话就去教室/图书馆/失物招领处找纸笔，假如还没找到就去文具店买纸笔（有纸笔后再次执行行为树，就会跳到有纸笔的分支执行写作业的逻辑）——这就是一个极简的行为树
4.1 构成
行为树由Node构成，节点分为Execution Node和Control Node
Execution Node分为Condition Node和Action Node
Control Node分为Sequence，Selector，Parallel，Decorator共3+1种（Decorator比较另类）
4.2 Execution Node（可执行节点，行为树中的叶节点）
4.2.1 Condition Node
（视频翻译为条件节点）
条件节点是一次对当前情况的判断，如：判断自己是否处于Powerful的状态？判断是否有Ghost正在追击？
返回值为true/false
我的理解中条件节点是一个门，当行为树执行到这个门时进行判断，向上返回true/false决定控制节点是否继续执行下去
比如Sequence可以先执行几个动作节点，在这些动作节点同行的后方加上条件节点，在执行条件节点后若返回true就继续执行后面的动作节点，若返回false就中断本次行为树的执行
4.2.2 Action Node
（视频翻译为动作节点）
动作节点是对具体动作逻辑的实现，比如执行移动，攻击的函数
返回值为success/failure/running
返回值的作用是告诉上方节点该动作的状态
4.3 Control Node（控制节点）
我的理解是这类节点就像是行为树上树枝分叉的地方
4.3.1 Sequence
标志着"顺序执行"
当行为树执行到该节点时，会依次执行其下所有子树，直到条件节点返回false或动作节点返回failure，当动作节点返回running时，会等待该动作节点执行，直到返回其余两值其一
例： Sequence -> 状态节点：门是锁着的？ -> 动作节点：解锁门 -> 动作节点：开门 -> 动作节点：进门
任何一个Sequence向上反馈的是和动作节点相同的状态类型，即success，failure，running，这个反馈取决于它执行的动作节点的返回值
比如：
- Sequence执行的动作节点返回running，那么Sequence就返回running，让这片区域的行为树停止一轮
- 假如Sequence执行的动作节点返回failure，就可以向上反馈说这套动作失败了，需要重新执行行为树
（看到这里不妨想一想状态机要怎么实现反馈失败动作并重新执行的，是不是就得飞根线回到初始的状态，是不是麻烦，行为树就简单了）
4.3.2 Selector
标志着"优先执行"
当行为树执行到该节点时，会依次执行其下所有子树，直到第一个动作节点返回success（就是依次执行动作，只要有一个成功了就不往下执行了）
（当然，开发者也可以定义特殊的Selector，比如要求至少得到2个success才返回，这个就自由发挥了）
理解了Sequence就很好类推到Selector了，它的返回也和Sequence一样的，不赘述
4.3.3 Parallel
标志着"并行执行"，就好比是移动射击，是两个行为叠加在一起的
视频里只有一张ppt上有parallel伪代码实现但并没有展开讲，此处给出的是其他地方的理论
Parallel的关键词是"并发 tick、记录状态、阈值判断"
- 并发tick
这里和并发状态机类似，并发状态机简单来讲就是在一个根节点的tick中执行多个状态机的update，这里parallel也是同理，它将同时执行所有子节点的逻辑
比如：parallel -> 移动 -> 射击 -> 跳跃
这样就会出现巴西跳扫(bushi
- 记录状态与阈值判断
执行所有子节点不是一股脑执行就完事的，还需要收集它们所有的返回值（success，failure，running），同时parallel也会存储一个或多个阈值（通常来说只有success和failure的阈值），当子节点的返回值达到某个阈值时，就向上反馈自身状况（success，failure，running）并终止执行
比如：（还是前面那个跳扫的例子）当手上的枪没子弹时，射击就会返回failure，这时假如该parallel的failure的阈值为1，那么就会立刻终止running的移动（跳跃应该是success），同时请求重新执行行为树，这时候大概就会换到另一个换弹的子树上去
通过调节阈值，可以实现各种复杂的并行行为策略，例如"等待至少两个条件满足"，“所有任务都必须完成，但其中一个失败则立即放弃"等
4.3.4 Decorator
作为修饰而存在的节点
当开发者想要执行一个这样的行为：移动 -> 暂停1s -> 反向移动 -> 1s ，我们当然可以把暂停1s写成一个Action Node，也当然可以把暂停1s写进移动的Action Node里面，但没必要，于是就有了Decorator，可以简便地在每个Action Node前添加小段逻辑（而不必要多new一个Action Node类）
4.4 节点总结
前五节点如下表（原视频这里有两行是反的，在此更正了）
| Node Type | Symbol | Succeeds | Fails | Running |
|---|---|---|---|---|
| Sequence | → | If all children succeed | If one child fails | If one child returns Running |
| Selector | ? | If one child succeeds | If all children fail | If one child returns Running |
| Parallel | ⇄ | If ≥ M children succeed | If > N - M children fail | else |
| Condition | text | If true | If false | Never |
| Action | text | Upon completion | If impossible to complete | During completion |
4.5 黑板Blackboard
是存储行为树输入输出数据的地方
我们当然可以散装存储ai体感知到的各种数据，但黑板的存在就是为了更方便地调用它，实现数据库分离那啥的思想嘛
当环境发生变化时，黑板中的数据会通过ai体的感知随之改变，ai体行为树中的状态节点都是读取黑板中的数据进行判断，动作节点也会在特定时间修改黑板上的数据，这一点也是在后面的HTN和GOAP的Sensor和World State的基础
4.6 行为树扩展
4.6.1 行为树Tick
行为树在每个周期都需要从根节点开始tick（所以当行为树和状态机都很大的时候，看着更复杂没条理的是状态机，用着性能开销大的是行为树），所以，当外界环境发生突变时，行为树也能很好地应对，如正在巡逻时发现了敌人，那么下一周期的行为树将停止running的巡逻，转而到负责攻击的子树的parallel或sequence啥的里面去（移动+攻击）
这里有一个扩展的部分，即event优化行为树tick，此处不展开，因为视频里也不主要讲这个
4.6.2 行为树优化-precondition
本质上是作为简化逻辑存在的
有一些子树，如：sequence -> 状态节点：门是锁着的？-> 动作节点：回头
它的存在就显得行为树有些臃肿，那么我们就可以把它简化成一个带有precondition的Action Node，只需要在回头这个动作节点的最前面加上一个判断门是否上锁就行了，写进类里面就是precondition
5 HTN和GOAP
HTN和GOAP在框架上其实是很类似的，所以在此放到一起来讲，我在此先写HTN的架构，再说GOAP从HTN上面换了些什么
5.1 HTN核心思想
“从目标出发”，即先立靶子，然后打靶
如上图，ai体会通过Sensor量化出World State（通常为bool），再依据World State从HTN Domain中获取任务，在Planner中将获取到的任务排成队列，然后在Plan Runner中依次执行
5.1.1 HTN速览举例
比如我是一个小兵，我的大招很厉害，那么我的HTN Domain中就会有一个Node是这样的：
precondition：敌人很多(true)
action：开大
effect：敌人不多(false)
那么怎么触发这个Node呢？
- 首先我会通过Sensor感知外部环境，这一步通常是用碰撞或区域检测完成的，即有多少个敌人在我的视野范围内，这些是Sensor的向World State传递的内容
- 随后我会根据这个返回值判断敌人多不多，比如有一个阈值，大于这个值就多，小于这个值就少，随后就在World State中写入关于敌人多不多的bool值
- 在Planner中依次判断World State是否符合HTN Domain里任务的precondition，假如符合就把它放入队列中
- 最后在Plan Runner中执行任务并根据effect修改World State
5.2 HTN的Primitive Task
基本构成为：precondition+action+effect
其中，
- precondiotion用于判断该任务可否执行，通常为对从World State中返回值的判断（bool）
- action为任务的执行逻辑，比如执行移动函数，执行攻击函数什么的
- effect为任务对World State的反馈，通常为改变World State中的值
比如视频中举例的解毒Primitive Task，precondition为中毒(true)且有解毒药水(true)，action为使用解毒药水，effect为失去中毒(false)和无解毒药水(false)（假设最多存储一个解毒药水，用了就没有了）
5.3 HTN的Compound Task
听前面的课程的时候其实我云里雾里的，因为光靠这样的任务只能构成一个糟糕的ai逻辑，我们的小兵会在和敌人战斗的时候突然收刀喝药或者喝药喝到一半突然翻滚然后不喝药了转而去打架什么的，这时候就得用上Compound Task了
5.3.1 priority
首先引入priority（优先级）的概念，这个概念很好理解，就像行为树里的Selector一样
我能这样干就不那样干，体现在ai逻辑里就是，我能喝解毒药，抗火药，红药，蓝药就不去喝万能药（假设万能药可以回满状态）
5.3.2 method
再引入method（方法）的概念，即我可以有一个连串的动作去完成一个既定的目标
比如我现在中毒了，手上只有万能药喝制作解毒药的材料，我就可以去做解毒药然后喝解毒药，这时就可以说，“喝万能药"和"做解毒药并喝"是两个method，再根据上面优先级的概念，“做解毒药并喝"的优先级显然大于"喝万能药”，那么前者就会被Planner放入队列中，被Plan Runner执行了
但在这里，前者的method将由两个Primitive Task组成，即
| Primitive Task1 | Primitive Task 2 | |
|---|---|---|
| precondition | 中毒(true) && 无解毒药(false) && 有做解毒药的材料(true) | 中毒(true) && 有解毒药(true) |
| action | 做解毒药 | 喝解毒药 |
| effect | 失去材料(false) && 有解毒药(true) | 失去中毒(false) && 无解毒药(false) |
视频里更简单的理解是Selector + Sequence的组合，没错，就是这个感觉
5.4 HTN的tick和World State
到此就得讲一下HTN的tick形式了，首先会议一下状态机的tick形式是状态变化时tick，行为树的tick形式是每一帧tick，而HTN的tick形式则是World State改变时tick
对于World State，视频中的解释是，HTN和GOAP的ai像是把世界以自己的方式抄下来，比如看到10个敌人就抄为"看到很多敌人”(true)，有1个草药和1个空瓶（假设是制作解毒药的材料）就抄为"有制作解毒药的材料”(true)
5.5 HTN的Planning
现在就得开始做规划了，我们需要在这里把ai体接下来要做的事情排成一个队列（可以理解为排列要执行的Task）
首先遍历HTN Domain中的method，看World State是否满足它的precondition，找到满足的，就把它放入将要执行的任务队列里
这里的遍历要怎么遍历呢？就是把method里的Task一层层展开，直到最底层的Premitive Task，随后比对其中的precondition，假如有不符合的就放弃这个method转而去下一个method
这里有一个至关重要的细节，那就是当ai体遍历到了可执行的Primitive Task后，需要把它的effect同步更新到World State里，假如后续决定不执行这个Primitive Task，再把effect更新回去
举上面解毒药的例子，Compound Task由两个Primitive Task组成，假如在遍历Primitive Task 1时不更新World State，那么就不可能满足Primitive Task 2的precondition
如此这般之后，planning就结束了，我们会获得一个仅以Primitive Task按优先级顺序形成的队列（Compound Task会被拆成Primitive Task）
5.6 HTN的Replanning
众所周知，做任何事情都需要时间，那么当ai体执行plan队列时外部环境发生变化，ai要怎么办？状态机会根据状态转换跳到其他状态，行为树每一帧都tick不需要考虑这个，HTN要怎么办？
其实就是重新规划
首先Sensor会告诉World State外部环境发生变化，此时会直接中断正在执行的Plan Runner再转回Planner中重新做计划
再比如说，我的某个动作失败了，ai要怎么办？比如我的某个Primitive Task是打开某门，我在规划时有钥匙，但这把钥匙在路上被偷走了，那么此时World State就会发生变化，就会强制中断Plan Runner的开锁计划，转到其他的method里去
5.7 GOAP相对于HTN的结构变化
最明显的莫过于将HTN Domain换成了Goal Set + Action Set
Goal Set称目标集，包含所有ai体可达成的目标（仅用数学方法表述），Action Set称动作集，含所有ai体可执行的动作
我们可以直观地理解为，HTN更像是做了一天的规划，而当这一天突然发生某些变数时，这个规划就得完全弃置，然后ai体就要重新开始规划，而GOAP更像是列了今天要干的事和今天能干的事，至于干什么就根据情况再定（有些抽象，看下面展开吧）
5.7.1 Goal Set
Goal Set由一些列Goal节点组成，Goal节点是一个由precondition，goal，state组成的节点，其本身有priority属性
以下是视频中举的一个Goal Set的例子
| precondition | goal | state | priority |
|---|---|---|---|
| 中毒 | 解毒 | 失去中毒 | 1 |
| 发现敌方是精英怪 | 逃跑 | 无 | 2 |
| 发现敌方是小怪 | 攻击 | 无 | 3 |
5.7.2 Action Set
Action Set由一些列Action节点组成，Action节点是一个由precondition，action，effect，cost组成的节点，其中cost为开发者的经验输入，用于告诉ai体这个行为的消耗大小，从而规划更好的Action队列
5.8 GOAP的Planning
这里直接放我的笔记，因为视频里这一部分讲了两遍有点混乱，理解了这个就理解了GOAP基本逻辑了，视频里讲清晰的地方从此处开始：
17.游戏引擎Gameplay玩法系统：高级AI (Part 1) | GAMES104-现代游戏引擎：从入门到实践 【精准空降到 57:31】
- Step 1
根据priority检查Goal Set
找到precondition符合World State且优先级最高的一个goal
- Step 2
比较goal的state与World State中的state
将为满足的state扔到栈stack of unsatisfied states
- Step 3
检查stack of unsatisfied states中第一个未满足的state
从Action Set中查找是否有Action的effect可以使该state改为goal需要的state（此处的effect通常称为set state）
将这个Action放入将执行的计划栈中（plan stack）
- Step 4
若将要放入plan stack中的Action的precondition未被满足，则将该precondition作为state放入stack of unsatisfied states中
继续执行Step 3，直到stack of unsatisfied states清空
输出plan stack作为计划执行队列交给Plan Runner
（以上有不严谨的地方，如在plan stack中的Action的先后顺序未被提及）
5.9 GOAP图
到上面那段其实AI就已经讲完了，这里的GOAP图一般是用辅助理清楚GOAP逻辑的
首先我们约定图例：
节点：World State
边：Action
距离：Action的cost
那么一张GOAP图就像下面这样：
比如当前的World State是A，目标是到达C，那么从A到C这中间的过程就是ai体要执行的Action，ai体需要寻找一个cost最小的一些Action执行
（看着是不是很眼熟？路径规划，淦！这不是A*吗，动态规划转A*这一块）
以上