GOAP（Goal Oriented Action Planning）是一种实现 AI 行为的算法框架。GOAP 以目标为导向，状态为节点，动作为边，进行 A-star 搜索从而得到一系列动作序列，根据动作序列做出行为的 AI 框架。
概念
在理解 GOAP 框架前，需要了解框架的一系列核心概念。
目标和状态
在 GOAP 中，状态是由离散的一系列键值对组成的，其中键是名称，值则是状态的值，例如{'hurtEnemy': true} 或者 {'hp': 233}。
而目标（Goal）则是另一个键值对，键是目标的名称，值是一系列状态，例如 {'killAllEnemy': {'hurtEnemy': true, 'live': true}}。
动作 Action
动作是 AI 一系列行为的基本要素，AI 通过规划出动作序列执行来改变游戏世界。
动作通常有前提条件（PreCondition）和效果（Effect），同样是键值对。
要执行一个动作，需要先满足前提条件，然后才能执行，并可选地把效果内容加入到 Memory 中。
记忆 Memory
记忆是 AI 记录世界状态的地方，同样也是键值对组成，作用类似于 AI 自己用的记事本，并且动作的前提条件都是看记忆的数据来判断。
感知器 Sensor
感知器是 AI 获取世界状态的组件。
在获取世界状态的时候，感知器可以对数据进行一定的预处理，再写入记忆中。
或者另一个常见的职能是负责管理数据订阅。例如订阅 AI 血量，当游戏世界中 AI 的血量变化时，触发感知器对 AI 的记忆进行更新。
运行
在有了上述概念后，运行的讲解就简单很多了。
GOAP 通过 A-star 规划一条从当前状态到目标状态的路径，移动的方式便是动作。
注意这里不是通常印象用在 2D 或 3D 网格上的 A-star，实际上是用在图搜索 A-star，和 2D/3D 的不同在于启发式函数上。在进行遍历搜索的时候，算法根据动作动态生成邻居节点（也就是状态），然后用某种启发式函数估算代价。关于这种启发式函数的一些讨论，可以见附录。
如果由多个目标，则根据目标的权值轮流对多个目标进行规划。例如目标A权值10，目标B权值5，如果搜索不出完成目标A的路径，那么就会进行目标B的规划。
优化和变体
ReGOAP 和反向搜索
然而在实际使用例如 ReGOAP 框架中，使用的不是正向 A-star 而是逆向 A-star——也就是从目标节点反向搜索到初始节点。
由于动作「反向使用」（也就是倒着走路径）并不会改变启发式函数估算的代价，所以倒着搜索出来的路径和正向搜索出来的路径代价是一致的（注意，顺序可能不一样）
那为什么要使用反向搜索呢？反向搜索带来的好处是减少可能性，从而提升搜索性能。
由于搜索路径的时候是在遍历同时扩展邻居节点，正向搜索的时候每个可以执行的动作都会产生一个邻居节点（也就是一个分支），随着搜索深度的增加，分支数量很容易爆炸。而反过来搜索只要考虑能对能到达当前状态的动作进行遍历，不会遍历不能到达当前状态的动作，从而减少产生的分支，避免爆炸。
例如下面这个例子：
目标是「开门」。
当前角色有 20 个可用 Action（移动、攻击、拾取、使用、等待……），其中 10 个当前都满足条件。那么从当前状态出发，遍历一圈估算代价，产生了 10 个下一深度会遍历的节点。
而从目标状态「钥匙已获得」反向搜索，发现可能只有两个 Action 能产生它：「从桌上拿钥匙」和「从敌人尸体上捡起」。反向从该节点扩张，最多产生 2 个前置状态，下一深度只需要遍历多两个节点。
大部分时候，反向的分支因子往往很小，搜索空间因此远小于正向。
多线程优化
由于 GOAP 本身主要是在进行 A-star 寻路，这部分是纯粹的逻辑运算，即不与游戏世界互动的，所以可以不放在游戏运行的主线程中，而是放在其他线程以优化性能。
此外，A-star 算法本身也可以支持多线程，所以可以使用多线程加速 A-star 的搜索。
注意，最终执行 Action 的时候要与游戏世界交互，所以 Action 这部分不能放在主线程以外运行。
动态 Action
动态 Action 是 ReGOAP 框架提供的额外功能，能够让 Action 在运行的时候属性动态进行变化，例如「根据 NPC 好感度不同而变化的交谈」动作。
不过我觉得，这个其实是灵活结合了 Memory 和 静态 Action 的包装，使用 Memory 和 静态 Action 也能达到同样的效果（但是容易搞复杂）。
注意，动态 Action 重点是变化属性来改变行为，而不是变化代码来改变行为。
动态 Action 的使用能够减少 Memory 里面临时标志位的出现，例如 Action 自己通过 Memory 或者外部数据（距离、仇恨值、资源数量等）来判断自己可不可用。
另一个好处是便于复用。不同的 AI 属性不同，但是 Action 是相同的，通过不同的属性可以算出不同的 Action 代价。
Goal 规划打断
也是 ReGOAP 支持的额外功能。简单说，每次执行完一个 Action 后，AI 都会检查 Action 执行结果，如果失败了，则重新评估目标（也就是选择目标）并重新规划路径。
打断可以有效应对外部带来的各种神奇原因，例如常见有以下原因：
- 动作执行失败：例如「走到一半路被堵了」，从而导致「移动」失败。
- 世界状态变化：例如「血量进了玩家的斩杀线」，导致当前 Goal 不如其他 Goal 紧急。
- 玩家指令：玩家输入了新的指令，引发世界状态变化。
而如果没有打断机制，AI 会机械执行完一个计划才考虑其他事，从而可能产生以下问题：
- 无视紧急威胁（着火还在吃饭）
- 无法响应玩家指令
- 动作失败后永远卡住（傻了）
附录
评价
GOAP 提供了一种很好的框架来设计复杂的 AI 行为。有人一定会拿它来和 FSM（有限状态机）或者 BT 行为树来比，但是实际上和 FSM/BT 的生态位并不冲突——GOAP 登场的时候正是「使用 FSM/BT 就会产生一大堆看着头疼的连线」的时候。
GOAP 在 「Fear」 和 「中土世界战争之影」中都被使用了，关于中土世界的设计介绍可以参考 GMTK 的视频——【游戏设计工具箱】 “复仇女神”系统：打造一个中土世界。
此外，在 GDC2017 上有更详细的技术演讲：【GDC】游戏中的AI技术：GOAP_哔哩哔哩_bilibili
上文提到的启发式算法
简单问了以下 AI。
A星怎么规划那些抽象的键值对的？这什么类型都有，怎么启发式估计？想出来这个的真是人才
其实关键原则很简单：启发式只需要返回一个从当前状态到目标的最小可能代价下界，不需要精确值。所以就算状态里面有整数、浮点数、布尔值、枚举，咱们也可以设计一个统一的估算规则。
最常用的方法就是松弛法，也就是把原问题中的一些约束去掉，得到一个更容易估算的下界。
先看布尔型的目标条件。比如目标是一组必须为真的条件，像 hasKey 得是 true，doorOpen 也得是 true。当前状态里如果有不满足的，那至少需要一个能产生那个效果的动作来完成。如果所有产生该效果的动作里，最小代价是 minCost，那这一项的贡献至少就是 minCost。更简单的做法是直接假设每个不满足的条件需要一个原子动作，代价设为 1 或者一个常数最小动作代价。
举个例子，当前 hasKey 是 false，目标要求 true。你检查所有动作：GetKey 代价 2，Pickpocket 代价 5，BuyKey 代价 3，最小代价是 2，所以启发式至少加 2。
再说数值型条件，整数或者浮点数都可以。比如目标要求 health 大于等于 80，当前只有 30，那就需要增加至少 50 点生命值。哪些动作能加生命？UsePotion 恢复 30，Rest 恢复 10，EatFood 恢复 20。每次最多恢复 30，那么至少需要 ceil(50/30)=2 次动作。如果 UsePotion 的代价是 1.5，那这项贡献至少就是 2 乘 1.5 等于 3。更简单的估算就是认为每个恢复类动作至少提供 1 点生命，代价是最小动作代价，那至少需要 50 乘最小代价。这仍然是下界，因为实际动作可能一次恢复更多，下界允许低估。
距离型的数值也一样，比如 distanceToTarget 当前是 100，目标要求小于等于 10，那就需要减少 90 距离。最快的移动动作是 Run，每次减 20 距离，代价 1，那么至少需要 ceil(90/20)=5 次，代价至少 5。
接下来是枚举或者符号型。比如目标要求 weaponType 是 Rifle，当前是 Pistol，那你就需要执行一个换武器动作。找到最小代价的能产生 weaponType=Rifle 的动作，比如 EquipRifle 代价 2，直接加 2 就行了。
最后一步就是把所有不满足项组合起来。一般启发式会把每个目标项的不满足代价相加，因为各条件可能通过不同动作独立达成，这是一个合法的下界。当然，如果某些动作能同时达成多个条件，取最大值可以得到更紧的下界，但简单相加已经足够，而且能保证可采纳性。