GOAP与游戏AI简述 —— 技术篇

避雷针：防止浪费时间请先行尝试查看目录与总结

偷偷把标题里的氛围AI改成了游戏AI

（因为一不小心又把题开大了）

上一篇其实多少有些离题太远，这一篇我们好回归一些干货。

（对不起写完回来看又离题万里了）

在这一节中，我们会介绍 GOAP 的技术组成，使得我们能更直观地发现其架构的优越性，并进一步产生使用其制造些许大玩具的想法。

（结果最后看下来，全是想法没有一点介绍）

‍

一点参考链接：

ReGoap（目标导向的 AI 系统）中文文档 | 登峰造极者，殊途亦同归。 (lfzxb.top)

luxkun/ReGoap: Generic C# GOAP (Goal Oriented Action Planning) library with Unity3d examples (github.com)

Introduction | GOAP (crashkonijn.com)

V3.0 Changes | GOAP (crashkonijn.com)

HTN 框架介绍、开发心得-CSDN 博客

游戏引擎 Gameplay 玩法系统：高级 AI (Part 1) | GAMES104-现代游戏引擎：从入门到实践

从 AI 到智能系统 —— 从 LLMs 到 Agents – 再见，避风港！

‍

背景简述 - AI 方法 Overview

‍

在具体开始讨论 GOAP 的有趣之处前，我们可以尝试先看一眼最为常见和常用的 AI 方法，亦即状态机和行为树（相信闲着会来看这篇文章的人对此都有相当的熟悉了）

‍

状态机和行为树是当今游戏中使用最为广泛的 AI 技术栈了，其中以后者尤甚。在我近年经历的三个项目中，无一例外使用行为树作为 AI 的核心方法。

而至于为什么我们提到状态机呢，因为在实际使用中，使用行为树模拟状态机也是屡见不鲜的做法了。

比方说，我们可以为行为树编辑如下这一情景

上述案例可以简单向我们直观呈现，行为树和状态机实质上只是不同的可视化工具，并因此适用于不同的场景（比如状态机的盘丝洞和状态爆炸，相比之下行为树具有更高的灵活性用于处理复杂问题）。但其逻辑底层在很大程度上能够等价。

‍

这向我们抛出了一个问题，其共性因何而存在？该共性能否延申向更多的 AI 方法。

‍

一个观点：离散数学之于 AI

在先前的某个思路中，我希望尝试从命题逻辑的发展这一视角归纳 AI 方法的表达能力，可惜失败了

仅从命题逻辑的角度，我很难说明更高阶 AI 方法对命题逻辑的超越该如何定义，终究是才疏学浅了

HTN 和 GOAP 此类方法的超越性源自一二阶逻辑对零阶逻辑的超越？还是源自模糊逻辑对二值逻辑的超越？还是源自图论集合论等对传统数理逻辑的超越？

只能说，很遗憾我没能进一步把握离散数学这门学科的脉络（）

但毫无疑问，这一视角在一定程度上可以为我们引入些许思路

下面直接贴出一段与 GPT4o 的 Q&A，仅供在进入正题前抛砖引玉

作者：问题

最近我在尝试对游戏中的 AI 方法进行一个综述，提及 FSM、BT、HTN、GOAP 等 AI 方法，你能尝试从离散数学这门学科的脉络出发，尝试寻找 AI 方法发展的主线么？

GPT-4o：思路

从离散数学的角度来看，游戏中的 AI 方法（例如有限状态机 FSM、行为树 BT、分层任务网络 HTN 和目标导向行为规划 GOAP）都可以被理解为不同的图结构、逻辑系统或组合优化问题的具体应用。离散数学为这些 AI 方法提供了理论基础，帮助理解和设计其行为。以下是从离散数学脉络出发，尝试寻找这些 AI 方法发展主线的分析：

1. 有限状态机（Finite State Machine, FSM）

离散数学基础：有限状态自动机是离散数学中自动机理论的经典模型，它由一个有限的状态集合、转换规则和输入输出的离散集合组成。FSM 可以看作是一个有向图，节点代表状态，边代表状态之间的转换。

AI 方法中的应用：在游戏 AI 中，FSM 用于简单的 AI 行为切换，例如敌人的巡逻、追逐、攻击等状态。每个状态表示 AI 的某种行为，而状态之间的转换由特定条件触发。

数学拓展：

图论：FSM 可以用图论的术语解释，AI 状态切换就是图中节点间的遍历。

逻辑与语言：FSM 往往与正则语言相关联，条件判断可以看作是逻辑运算。

2. 行为树（Behavior Tree, BT）

离散数学基础：行为树是一种树形结构，常用于表示 AI 的决策过程。行为树是离散数学中树结构的应用，树的每个节点是一个条件或行为，叶子节点代表具体的 AI 动作。

AI 方法中的应用：行为树比 FSM 更灵活，能更好地分离不同的行为模块。开发者可以通过组合或嵌套行为来构建复杂的 AI 行为，如条件判断、并行处理等。

数学拓展：

树与递归结构：行为树是树的递归结构，每个子树可以看作一个独立的决策单元。

逻辑推理：行为树可以通过布尔逻辑来解释，节点的条件判断相当于逻辑表达式的求值。

3. 分层任务网络（Hierarchical Task Network, HTN）

离散数学基础：HTN 是一种分解规划问题的方法，背后的数学基础是树结构与图搜索。HTN 将任务分解成子任务，直到这些子任务可以直接执行。

AI 方法中的应用：HTN 通常用于更复杂的 AI 规划系统中，它通过层次化分解任务，将复杂问题拆解为更小的可管理部分。比如，在战略游戏中，AI 需要制定高层次战略并逐步细化为具体战术。

数学拓展：

图搜索与规划：HTN 的任务分解可以视作在任务图上的搜索问题，通过分解来找到最优的执行路径。

组合优化：分解任务的过程可以通过组合优化问题来建模，寻找最优的子任务组合以达到全局目标。

4. 目标导向行为规划（Goal-Oriented Action Planning, GOAP）

离散数学基础：GOAP 是基于规划问题的 AI 方法，通常涉及状态空间搜索和图搜索算法（如 A*）。GOAP 将 AI 的行为看作一系列动作的组合，这些动作通过特定的条件和效果来影响世界状态。

AI 方法中的应用：GOAP 的特点是 AI 根据目标动态规划行为路径，而不是预定义的行为序列。它通过搜索一个状态空间来找到从当前状态到目标状态的最优路径。

数学拓展：

状态空间搜索：GOAP 的核心是状态空间中的路径搜索问题，这与经典的图论问题密切相关。

逻辑与约束求解：GOAP 可以结合约束求解来处理复杂的行为规划问题，即在满足特定约束的情况下找到最优解。

5. 主线脉络：图结构、逻辑与搜索

从离散数学的角度来看，这些 AI 方法可以归纳为以下几个核心概念的应用：

图与树结构：无论是 FSM 的有向图、行为树的树结构，还是 HTN 的任务分解树，图结构是这些 AI 方法的核心。通过节点和边的关系，AI 可以在状态空间中进行转换和规划。

逻辑推理与布尔代数：条件判断、状态转换和任务分解都可以用逻辑表达式来描述，AI 在不同状态之间的决策过程本质上是布尔逻辑的求解过程。

搜索与优化：GOAP 等方法引入了搜索问题，通过在状态空间中寻找最优路径来完成目标。这与经典的图搜索算法（如 A*算法）和组合优化问题密切相关。

6. 进一步的数学模型与发展方向

博弈论：随着 AI 复杂度的增加，尤其是在多人对抗游戏中，博弈论可以为 AI 决策提供新的模型。AI 可以根据对手的策略调整其行为，寻找纳什均衡点。

概率与统计模型：随着 AI 方法的发展，离散数学中的概率论也开始发挥作用。例如，马尔可夫决策过程（MDP）是一个经典的离散状态模型，AI 可以基于概率预测未来状态并做出决策。

形式化验证：形式化验证理论（如模型检测）可以用于验证 AI 系统的正确性，例如确保 AI 在任意情况下都能满足特定安全性或稳定性要求。

总结

从离散数学的角度来看，游戏 AI 方法的发展可以看作是图结构、逻辑推理和搜索优化问题的不同应用。FSM 起源于自动机理论，行为树和 HTN 基于树结构，GOAP 则涉及状态空间搜索和路径规划。随着 AI 方法的复杂化，博弈论、概率模型等更高级的离散数学工具也逐渐应用于 AI 设计中。这些方法共同推动了游戏 AI 从简单的状态切换到复杂的目标导向规划的发展。

‍

可以看出，游戏 AI 在某些情境下也与另一个我们常见的 AI 存在交点，如作为人工智能三大学派中 符号主义 主要成果之一的专家系统，其实质便是一个推理自动机，依赖结构化知识和输入进行推理。其毫无疑问便是游戏中常见 AI 技术的一种典型变体。

相似的还有，在游戏 AI 的诸环节引入连接主义思想进行黑箱决策 / 在拟人 AI 中使用强化学习方法。

当然，我们今天不会聊得那么远，先回到正题罢

‍

AI 方法发展纵览

通过上述例子，我们可以粗浅看出 AI 方法发展的几个主要脉络

状态空间的演化
决策方法的演化

我们可以逐一展开详细描述

状态空间的演化

游戏 AI 的状态空间经历了从预定义的简单状态到动态推演、适应实际环境的复杂状态空间的演化。这条脉络可以分为以下几个阶段：

预定义的状态空间
- 阶段特征：在该阶段中，AI 所处的状态空间是由开发者进行预定义的，AI 在有限的状态之间进行转换，难以结合环境产生复杂的状态和逻辑。此类方法的典例便是 FSM。
- 局限性：静态而有限的状态空间通常基于 Agent 自身状态搭建，或围绕具体的环境搭建。虽然上限仍具有相当强大的表达能力，但通常难以拓展和产生更智能的决策
预定义状态的细分
- 阶段特征：在该阶段中，为了应付游戏环境的日渐复杂化，预定义空间中的状态被进一步地拆解，让 AI 可以在更复杂的状态空间中进行灵活的决策。BT 便是这一阶段的代表之一。其将“状态”进一步拆解为行为，并关注每个行为的运行状态，通过逻辑组合构建最终的复杂状态表现。这一模块化思想很好地影响了后续的 AI 方法。
- 优势：行为树将树状层次结构与状态进行了很好的结合，使得其可以同时表达叶子的行为状态和层次化的 Agent 状态。这同时使得行为树在除 AI 方法外，也能作为更通用的可视化脚本工具使用
- 局限性：基于预定义结构的状态空间，终究还是难以应付更加动态的情景。想要实现相关能力，反而会依赖 AI 系统中组合行为树的更多硬编码逻辑。预定义的局限性让行为树更多是作为一种 AI 方法，而不是一个完善的 AI 系统。
- 另提一句：HTN 中也保留了预定义的 Domain，这在很大程度上增加了 HTN 决策的可读性，这在某种层面上也带来了很大的优势。
动态推演与环境适应
- 阶段特征：进一步的演化体现在 AI 根据环境动态进行状态的推演与更新。HTN 和 GOAP 便代表了这一阶段中的进步。在这一阶段中，AI 倾向于不再仅关注自身所处、自己所执行的状态。并开始关注自身如何改变世界，如何在自身与环境状态之间平衡决策。
- 优势：这种演化使得 AI 不仅能应对预定义的状态，还能够根据实际环境实时推演状态变化，提升了决策的智能化和动态适应能力。

决策方法的演化

游戏 AI 的决策方法经历了从简单的逻辑判断到基于复杂规划的推理决策的转变。该脉络的演化同样经历了几个关键阶段：

线性逻辑判断
- 阶段特征：早期 AI 决策依赖于线性的逻辑判断，即通过一系列预设的命题及其推理来决定 AI 的行为。例如在 FSM 中，AI 的状态迁移都依赖于简单的逻辑判断。
- 局限性：此类方法很大程度上缺乏灵活性和深层的推理能力，难以应对复杂和动态的游戏情景。
符合现代编程思想的逻辑判断
- 阶段特征：该阶段实质还是上一阶段的延申，但引入了很多现代编程思想。诸如，模块化结构和并行运行。通过拆解状态，行为树的决策运行变得更加灵活。
- 优势：该方法虽然并未在本质上脱离普通逻辑判断的范畴，但引入了更强的灵活性，使其能在普遍范围内
规划与决策
- 阶段特征：在早先的 AI 方法中，始终是不存在规划和复杂决策的。后期有 HTN 引入了任务分解和规划的基本思想，在预定义的决策空间中执行高效搜索。其不再仅依赖于逻辑判断，逐渐开始引入对完成目标、优先级、执行顺序的复杂推理。
- 进一步演化：GOAP 当前代表了 AI 决策演化的阶段性形态。其不再依赖于预先设定的逻辑载体进行判断，而是通过主动搜索状态空间，结合环境变化与目标的动态规划，生成最优的行为路径。这种方法使 AI 具备了自适应能力，能够在复杂环境中进行自主决策。

总结：AI 方法的系统化

总体看来，随着游戏复杂度和玩家期望的提升，AI 从预定义的有限状态管理和简单的线性决策，逐步演化为能够动态推演环境变化、基于复杂规划进行智能决策的系统。

所谓系统化，实质上便是 AI 演化的阶段性目标，也是后续继承更丰富 AI 能力的基础锚点。

对于系统化重要性的相关阐述，可以看一看一年前我写的对 LLMAgent 化阐述的文章

从 AI 到智能系统 —— 从 LLMs 到 Agents – 再见，避风港！

于是，在简略的讨论之后，我们终于该切入正题了（怎么又是 4000 字过去了

‍

GOAP 的基本介绍

‍

参考上述观点，GOAP、HTN 此类新 AI 方法的实质是，构建一套系统，让 AI 可以创造性地解决实际游戏情景中的问题。因此，第一步，我们可以讨论该系统中的诸元素。

对于任意一个系统而言，我们都能以输入、输出、处理对其进行三分。而在此基础上，AI 方法作为一个以改造游戏世界为目的的控制系统，我们能进一步视其为负反馈控制系统，从而引入我们所需的诸要素。

现代 AI 作为负反馈系统

上面这张图，如果是自动化或者其它工科出身的老哥应该都相当熟悉了，其是负反馈系统的基本框图

‍

为了避免部分同学不够了解，我们可以简单介绍一下这个循环中的诸流程：

输入信号($x$)：系统原始输入 $x$，主要驱动力
前向通道($G$)：系统正向过程中的主要运算，用于基于输入 $x$ 产生输出 $y$
输出信号($y$)：系统的输出 $y$
反馈通道($H$)：用于处理系统输出，生产反馈信号的矫正模块
反馈信号($z$)：反馈信号，用于和原始输入比对以控制输出符合系统目标
比较器($±$)：用于结合比对输入信号 x 与反馈信号 z，形成前向输入的模块

举些简单的例子，我们在跑步时通过控制速度稳定心率、在垫球时修正击球角度、在吃华莱士之后服用蒙脱石散，都是典型的负反馈。在这些决策中，我们倾向于通过系统更新输出修正扰动，从而维系系统的稳态（即此处我们的系统性目标）。

‍

通过类比，我们能很快发现，这一系统构成思路，和现代 AI 方法中的诸元素完全可以一一对应，我们即刻展开相关观点。

输入信号($x$)：即对应 GOAP 中的 Goal(目标)，Goal 定义了系统期望达到的状态
输出信号($y$)：即对应 GOAP 中的 Action(动作)，Action 定义了系统如何对外界产生影响
前向通道($G$)：前向通道期望基于 Goal 生成 Action，即对应 GOAP 中的 Planner(规划器)，系统通过 Planner 进行决策，尝试通过决定并执行 Action 使得 Goal 得以满足

上述逻辑为最经典的前向逻辑，而后续的逆向逻辑，则能将 Agent 与 World 更好地绑定在一起

反馈通道($H$)：将 GOAPAgent 对外界的影响理解为一个时序过程，那 World 本身就是系统的反馈通道，Action 影响 World，World 产生变化，继而生成对 Agent 的反馈
反馈信号($z$)：基于 World 反馈，GOAPAgent 通过 Sensor(传感器)将其采样，使得反馈重新纳入系统
比较器($±$)：通过更新 Sensor 采样的 WorldState，对比 Goal 期望获得的 WorldState。比较器将产生对前向通道的直接输入，即控制系统在时序上进一步产生或更新决策

在上述这一闭环控制中，我们成功提到了 GOAP 的所有核心要素。如果你还熟悉 HTN 的话，你会发现其背后逻辑惊人的一致性。保存着上述印象，能让你更好地阅读下文对 GOAP 诸模块的详解。

‍

GOAP 的诸模块

在上面这一则系统流图中，我们可以相对清晰地看到 GOAP 这一 AI 系统中的诸元素，而接下来我们将对其逐一介绍，以提供一个更清晰准确的认知。

（这一节中，我们暂时不会讨论 GOAP 的完整决策过程）

我们以 World 这一 AI 之外的模块作为入口，来尝试拆解 GOAP 的完整决策链条

‍

传感器 Sensor

传感器对于 AI 而言是个屡见不鲜的模块。原则上，任何 AI 框架中都会拥有这一模块，即目标为改造客观世界的 AI 首先要充分了解客观世界。Sensor 便是这一前提。

‍

而 GOAP 的传感器显然没有什么特别，唯一值得注意之处的是，GOAP 的传感器并不直接根据 Sensor 的采样结果进行决策，而是将 Sensor 的结果缓存汇入自身记录的世界状态，并将其作为唯一决策依据。

‍

世界状态 WorldState

‍

世界状态也并非是一个新鲜的概念，在 HTN 中也同样被充分应用，而他们的共同来源是 STRIPS 方法。

STRIPS 方法

文本源自 Claude3.5 Sonnet

最早提出 WorldState 概念的 AI 方法应该是 STRIPS(Stanford Research Institute Problem Solver) 规划系统。

STRIPS 是由 Richard Fikes 和 Nils Nilsson 于 1971 年在斯坦福研究院(SRI)开发的。它是 AI 规划领域的一个重要里程碑，引入了几个关键概念:

WorldState(世界状态):描述了环境的当前状态。

动作(Actions):可以改变世界状态的操作。

目标状态(Goal State):希望达到的最终状态。

STRIPS 使用这些概念来形式化规划问题,并提出了一种通过搜索从初始状态到目标状态路径的方法来解决问题。

这个方法对后来的 AI 规划研究产生了深远的影响。许多现代规划算法和系统仍然基于 STRIPS 的基本思想,尽管它们在效率和表达能力上有了很大提升。

不难看出，GOAP 中的许多其它概念也同样源自 STRIPS 这一决策方法。

WorldState 是 GOAP 进行决策最核心的组件。GOAP 通过 WorldState 对世界当前的状态进行记录和描述，并依此评估世界是否符合自身的期望，进而决定需要对世界施加怎样的影响。

‍

不同于直接反映现实状态的 Sensor，WorldState 更倾向作为现实的一种主观建模和抽象，包括其包含对 Agent 自身状态的维护。换句话说，这一环节中，允许设计师基于设计注入一系列偏置。

举个例子，在一款潜行游戏中，我们要如何让 AI 智能地响应玩家暴露的信息？例如，我们想进行这样一个 Gameplay 设计，当玩家造成异响、偷偷抹杀敌人被发现时，将为 AI 积累一定的不安感。而动态的不安感积累将决定 AI 将如何用最为高效的方式消除不安。

此时，不安感的积累是一个纯主观，可编码的状态，但同时也是 Agent 决策所依赖的 WorldState。可以这么认为，如何有效编码 WorldState，是基于 GOAP 的 AI 设计中至关重要的元素之一。

‍

目标 Goal

‍

Goal 的引入是 GOAP 与绝大多数早期游戏 AI 方法的主要不同，也包括 HTN

从某种程度上来说，其和效用 AI 倒是有着些许相似之处

‍

我们将这些 AI 划归不同派别的核心依据在于决策过程。

Goal 的引入使得 GOAP 构建了一个完全目标导向的逆向决策过程，这与很多早期方法中的前向执行并形成决策的模式并不相同。由此浮现出了一种智能性。

AI 的不同决策模式

正向决策

正向决策的 AI 方法基于当前状态和预定规则，直接推导出下一步行动。

类似 FSM、BT 等其它早期方法，其根本思路便是在正向过程中流转逻辑，快速更新状态。

这类方法通常基于响应式，或者主动轮询，能较好地实现快速响应，但往往并不能形成智能体系，只部分相对简单的和及时性的任务中有奇效。

关键词： 判断和决策、瞬时性

‍

逆向决策

参考前一节提到的 STRIPS ，其通过引入目标，构建以达成目标为目的的决策，从而实现现实灵活环境中复杂问题的解决。

一定程度上，逆向决策有时会带来更低的运算效率，其依赖于对空间更完整的搜索和优先级的判断，因此往往需要更多计算量，难以处理极度灵活的表现。相比之下，逆向决策会更适合解决复杂的规划问题。

（勘误：在解空间极大且目标明确时，逆向方法有着绝对的优势）

关键词： 评估和优化、长期性

‍

混合方法

一些特殊的混合方法可以为 AI 设计提供些许展望。

在深度学习/强化学习方法中，AI 的决策并非单纯的正向或逆向过程。其通过训练过程，将逆向决策中的评估和优化整合进了前向路径中，使得在运行时仅通过正向过程便能整合逆向决策的优势。

‍

相关思路的弱化版也在 HTN 中有着一定的体现，HTN 以顶层任务为出发点，基于正向任务分解计算可行的执行路径。与此同时，最小化 Cost 的优化目标作为惩罚，在决策时产生逆向的约束，由此形成完整决策过程。

（但由于 HTN 过于依赖手搓路径，所以我的整体评价还是略低于 GOAP。

‍

总结

不同模式的决策在 AI 系统中往往是需要积极互补的，实际使用时往往会根据时效性、解空间特性、对路径约束的要求实际进行选择。

但在此节中，我们会更倾向于讨论目标驱动方法的相对优越性。

‍

在 GOAP 中，Goal 也可以被称为 GoalState，其实际表示的是一个 GOAPAgent 期望达到的 WorldState 集合。

比方说，在一组城镇氛围 AI 中，可能有 Agent 的生活目标是减肥和搞钱，而这个 Weight--、Gold++ 的 Goal 将会作为 Agent 生活决策的依据，令其专心工作避免当饭桶 🤦‍♂️。同时理所当然地决定蹭公司的每一顿早餐，然后省下午餐的饭钱 🤤

‍

由此引入一个问题，上述这一对我们而言理所当然的计划，是怎么通过算法让 AI 基于目标自动形成？

‍

除此之外，一个 Agent 可能具有多个 Goal，其中存在基于 WorldState 对 Goal 激活状态进行管理的 Precondition，也存在 Goal 之间的 Priority 关系。

但整体 Goal 作为系统的输入端，对其的选择策略可以以更多方式构建，遂不会在此详尽讨论。

‍

规划器 Planner

‍

Planner 是 GOAP 系统中负责生成行动计划的核心组件，但我们想要介绍 Planner 就不能只介绍 Planner，还得介绍 Action、Precondition、Effect、Cost 这系列要素。因为 Planner 的规划便是基于它们进行的。

因此，在这一环节，我会先介绍 Planner 的基本目标，而把 GOAP 的完整决策过程留在下一个大节中，结合所有的背景知识进行详细介绍。

‍

简单来说，Planner 的存在目的在于选出一组最合适的 Actions，来抹平 WorldState 到当前 Goal 的差距

Planner 的解空间可以简单表示为下面这个表达式

$$\mathcal{P}(W, G) = \{ A \mid \text{Execute}(A, W) = G - W \}$$

而对于上述这一解集，进一步引入 Cost 最小化这一要素

$$p(W, G) = \argmin_{A \in \mathcal{P}(W, G)} \text{Cost}(A)$$

从而，我们能得到 AI 当前所应执行的 Action 序列。

在上述逻辑中，我们完全隐去了 Precondition、Effect 这些 Action 内部的要素，并只对 Cost 粗浅提及，这都是需要在后文中进一步完善的。

‍

动作 Action

‍

相信上一节对 Planner 草率的介绍只会让人更加一头雾水。没事，这一节便会揭晓绝大多数关键的概念。

Action 是 GOAP 最核心的要素，其通过定义，将客观与主观、当下与预期串联起来。

‍

Action 的核心逻辑包含两个部分：

其一是执行模块，其与行为树中的节点并无二致，用于操控 GoapAgent 执行所需的实际逻辑

另一部分则是评估模块，用于评估行动的前提条件 Preconditions、预期效果 Effects 和执行成本 Cost

‍

Action 的三要素

Precondition

Precondition 是 WorldState 的子集，运行时，Precondition 将检验当前的 WorldState，验证自身是否全部满足，如果未满足，则当前 Action 无法执行，无法纳入解中。

Effect

Effect 也是 WorldState 的子集，描述运行 Action 后，GoapAgent 能对 WorldState 产生的预期影响。我们通常希望 Effect 能让 WorldState 更加趋近于 Goal，亦或者我们希望 Effect 能作为另一 Action 的 Precondition，使得 Goal 能更好地被达成。

Cost

Cost 将在最后作为评估一组用于抵达目标的 Actions 是否高效的评价手段。

‍

在动作实际执行之前，Planner 将基于预期去假设 Action 被执行，以验证 Action 是否能执行、是否能满足改造世界的需要，又是否是当前最经济的决策。

而正是“假设执行”这一环节，成为了 GOAP 规划最核心的逻辑。

‍

有趣的是，当我们引入上述三个要素时，可以明显地发现其概念可以完美的与图这一数据结构 Mapping

Precondition 决定了节点的入度
Effect 决定了节点的出度
Cost 决定了节点的权重

通过此三者作为连接点，Planner 搜索 Actions 序列的问题，成功转化为了一个图优化问题，也使得整套问题的求解有迹可循。

‍

在引出最后这一概念后，我们终于能尝试完整梳理 GOAP 的决策过程。

‍

GOAP 的决策过程

GOAP 的决策过程其实并不复杂，本质即是将面向目标的决策转化成一个既有的算法问题，并基于此套用既有方法求解。因此，若我们想要充分理解 GOAP 的决策原理，只需尝试探究其算法原型。

‍

GOAP 的决策过程，被等同于一个图搜索问题，即搜索一个加权有向图中的最短路径。

在这个图中：

节点(Node)表示世界状态(WorldState)
边(Edge)代表动作(Action)
边的权重(Weight)代表动作的成本(Cost)

通过此番建模，我们能将问题转化为：

搜索从当前 WorldState 到目标 WorldState 所表示节点，所花费综合 Cost 最小的路径，即边的集合及其顺序，对应 Action 队列。

‍

我们将分几个部分讨论该问题的构建与求解

图的构建与算法选择
算法执行流程
优化策略

图的构建与算法选择

‍

图搜索作为 GOAP 方法中最核心的问题，使得相关算法的选择直接关系了 AI 的决策效率与质量。

其可能涉及几组决策：图构建方法的决策、具体优化算法的选择。

图搜索问题的演化

在早期图论中，我们讨论的往往是静态的、确定的图结构。一系列最经典的算法，如广度优先搜索(BFS)、深度优先搜索(DFS)等均是基于这一规范。他们通过各自的方式来实现有效的求解。

后续，随着带权图、最短路需求等的引入，经典的 Dijkstra 算法也被引入。其用于在既定的图空间内，找到最符合目标的需求的解。与此相近的还有 Bellman-Ford 算法、‌Floyd-Warshall 算法等。

‍

但随着图结构脱离传统图论领域，被进一步引入计算机、控制等复杂体系中时。图搜索算法为了应对工程问题的复杂和效率需求，衍生了一系列更多的分支。

一个典例是适用于未知深度搜索问题的迭代加深深度优先搜索(IDDFS)，其在 DFS 的基础上增加了迭代加深这一逻辑，优先期望在浅层得到。该方法被用于搜索过深的状态空间，同时保证效率。

‍

但即便如此，上述方法处理的依旧是固定状态空间的问题。

进一步的，我们会考虑到，当状态空间大到不可控，或具有更强的动态特性时，我们要如何保证效率和有效地进一步求解。

由此，更多启发式的搜索方法被端上前台。他们通过引入偏置和估计，动态构建搜索的状态空间，牺牲一定的准确性换取绝对的效率。如我们即将讨论到的 A*

没必要卖关子，GOAP 最终选择的决策算法就是 A*，算是最经典的启发式方法之一。

‍

对于 GOAP 中复杂的 WorldState 和多样的 Action 选择，往往将带来一份难以构建的状态图。

以 WorldState 中的数值状态为例，对于连续型的数值，诸如位置等，其状态空间天然难以降维到离散的状态图中。为了解决相关问题，在 GOAP 的实际使用中，此类连续数值往往被反映成一个布尔关系。如是否靠近敌人/血线是否安全等。

但与此相应的，这种抽象依赖于设计师的设计，其机制天然难以在完全连续的状态空间上精准决策。

A*算法，其优势之一便在于不再依赖明确的状态空间，而是基于搜索过程动态地创建所需的状态空间。

‍

A*算法的核心思路

A* 算法是一种启发式搜索算法，常用于路径规划和图搜索问题。它的核心思想是在搜索过程中，结合已知信息和预估信息来指导搜索方向，从而在效率和最优性之间取得平衡。

A* 的核心思想包含如下几个关键点：

启发式搜索：算法利用启发信息指导搜索方向，不期望探索完整状态空间

动态状态空间：在搜索过程中逐步构建和扩展状态空间，无需预先定义所有可能状态

代价评估：综合考虑已知代价和预期代价，决定对节点搜索的倾向

A* 使用函数 f(n) = g(n) + h(n) 对节点进行评估，其中 g(n) 为起点到当前节点所花费的实际代价，而 h(n) 则为我们一再提到的启发式函数，手工打造，用于估计当前节点到目标节点的代价

贪心策略：优先探索评估当前代价最小的节点，期望最快速趋近目标

在实际算法流程中，A* 算法追求搜索效率和解质量之间的平衡。它不保证找到绝对最优解，但通常能在合理时间内找到较好的解。这种折中使得 A 特别适合需要快速决策的实时系统，如游戏 AI。

‍

这有一篇很好的文章，用可视化 demo 完整阐述了 A*算法执行的过程

A-Star（A*）寻路算法原理与实现 - 知乎 (zhihu.com)

‍

基于这些核心思路与优势，A*算法很好地与 GOAP 方法构建的图抽象相结合，并成为了 GOAP 在实践中选用的决策算法。

在下一节中，我们将展示这一算法是如何在 GOAP 的状态图上运行的。

‍

算法执行流程

‍

有一说，如果你最初只是为了了解 GOAP 这一算法的逻辑和搭建方法而打开了这篇文章，那它一定坑害了你。恭喜你已经浪费了大把的时间，就像我浪费了大把的时间写这篇没用的东西一样。

如果你想对 GOAP 产生一个相对直观的理解，其实你最该做的事是，打开下面这条链接，然后从第 45 分钟看到第 67 分钟：17.游戏引擎 Gameplay 玩法系统：高级 AI (Part 1) | GAMES104-现代游戏引擎：从入门到实践_哔哩哔哩_bilibili

王希老师不会让你失望，就像他不会让两年前对做游戏仍然懵懂的我失望那样。

‍

不过，一半是为了践行费曼学习法，一半是为了不让文章空出大半版面，总归还是得写下去的。

（要不还是算了，写完后面的部分回来突然觉得索然无味了）

‍

我们尝试回顾我们所拥有的素材：WorldState、Goal、Action，我们要如何基于此实现 GOAP 中一段完整决策的运行，从而使我们的 Planner 创建出 GOAPAgent 所需的 Action 队列？

（TBD...）

‍

讨论：AI 方法的整合与嵌套

‍

在上述篇章中，除开我们最初想讨论的 GOAP 外，我们实际对当今常用的 AI 方法进行了完整的 Overview

其实，在 Overview 的过程中，我们可以发现一个问题。

‍

AI 方法在很多视角下均不是严格的迭代关系。当今，我们讨论 AI 时往往讨论的是经典决策 AI 到复杂规划 AI 的演变，从线性决策到系统化决策的演变。但我们该认为这一趋势是一种全面的迭代吗？那么如果强化学习、大语言模型驱动的更复杂的决策 AI 被引入系统，是否说明 GOAP 将和有限状态机一样将被视为古典而朴素的 AI 方法？

先给出我的结论，这显然是否定。

‍

在实际的开发使用中，AI 技术并非简单的选型，而是取百家之长，以最精准有效的姿态满足开发需求。

为此，我们可能需要 状态机的稳定、强化学习的灵活动态、语言模型的拟人决策和感知、GOAP 的直观和原子化、行为树的设计师友好和可视化编程。

而为了讨论如何尽最大可能性整合框架之间的优势，我们将讨论对于一个足够强大的 AI 而言，其可能包含的诸层级，而不同的 AI 方法，是如何基于层级有效进行整合的。

‍

排列组合

研究 AI 方法排列组合的这一基本思路源自先前听过的一场读书会

（这里可以安利一手集智）

在那次读书会上，主讲人尝试讨论如何拆解一个大模型的构建元素，如下图所示

这张图中，从模型架构、预训练目标构建、适应调整、微调、评估这五个角度来讨论一个大模型架构的完整搭建与训练流程。

我们自然而然想到，这样的层次规则，是否能类推到相似的工程上？

AI 方法的能力层级

当然，考虑到我们讨论的还是一个相对抽象的问题，我们仅先用简单的方式进行剖分，即将 AIAgent 的综合能力划归到五个层级 / 两个方面进行评判

长期决策层 / 目标层
中期决策层 / 规划层
短期决策层 / 行为层
短期反馈层 / 感知层
长期反馈层 / 记忆层

即对 AI 的能力从主动决策和被动反馈两个方面，随时效性所需的不同能力进行剖分

全局工作空间理论

非常有趣的是，如果你接触过全局工作空间理论（在我去年的一篇文章中有简单提及【附链接】），你会发现我们给出的剖分能跟其组织的五个要素初步的 Mapping

长时记忆（过去）—— 记忆层

评估系统（价值）—— 规划层

注意系统（关注）—— 目标层

知觉系统（现在）—— 感知层

运动系统（未来）—— 行为层

如果事物存在异曲同工的相似，那说明其背后必然隐藏着更多奥秘不是么？

基于这个简单的分层，我们能继续介绍其实际作用，以及不同 AI 方法其优势区间

‍

短期决策 —— 行为层

行为树，这个名字里天生带有行为的 AI 方法，既是我们阐述行为层功能的核心讨论点

行为层是 AI 系统最直接的输出层，负责执行具体的短期行为和动作。其涉及到所有不带决策与规划的短期内行为表现。但视实际情况包含简单的反射性质行为。

‍

如机器人或人脑控制中，握持指定物体这一指令，被有效封装为可被决策系统感知的最小单位。

值得注意的是，Agent 往往对行为的执行过程缺乏意识，更偏重于检查执行结果。

我们可以挑出生活和游戏中几个简单例子

当你打字时，大脑考虑的是敲出指定文字，而不会思考要如何有效地敲击键盘输入拼音（叠甲并非歧视五笔或外文）。这一环节往往被机体反射有效接管。

当游戏中 AI 执行射击行为时，往往不会将行为进一步拆分为瞄准 + 射击这一固定环节往往被直接封装为行为，避免了冗余的决策。

‍

在这一层面上，在实际情境中，对行为层的封装往往有几种主流的方式

硬编码封装，通过程序写死底层代码与逻辑，实现对边界条件较好的控制，和灵活的直接调用
- HTN、GOAP、FSM 和传统使用语境下的 BT，或者说归根结底只要是游戏最后都会变成硬编码
- 核心区别还是在于执行原子化的程度
行为树封装，通过行为树的分支执行节点对完整行为过程进行封装。
- 该封装通常对应传统完整行为树 AI 中的一条子树，用于处理分支条件下的应变
- 当然，究其节点仍是硬编码罢
系统封装，也是硬编码封装的另一表现形式，即将单个行为视为一个自动控制系统。
- 其呈现形式可以是给定目标 Y 值的过程控制，也可能是给定输入生成连续输出的系统响应
- 在该类型封装下，其可以与两年余前的反射式神经网络接轨，用于实现灵活的控制

‍

这一层的关键在于快速响应和执行，同时要与上层规划保持一致。其方法使用核心在于实现灵活而有效的对外输出。同时，行为层也是最为即插即用的模块之一，任何行为实现方式都可以与既有 AI 方法相结合

‍

短期反馈 —— 感知层

感知层负责处理即时的环境信息,为决策提供输入。

在经典的 AI 方法中，往往有着更为直接粗暴的感知方法。

对于很多动作游戏而言，便有老生常谈的操作，如读指令。即在相关情境中，AI 直接将客观世界的输入作为可感知的要素，并依此进行判断与决策，构建反馈。

‍

但在实际使用情境中，相关方案未必是最合适的。一方面，读指令式 AI 很容易为玩家带来一系列的负反馈，让玩家感受到不对等的博弈。另一方面，对于部分复杂 AI 而言，其所能掌握的必然不能是完全信息。

以 OpenAI 早期参与的星际 AI 挑战赛为例，对于星际争霸系列原生的游戏 AI 而言，为了确保其妥善的表现，设计师通常让其能够掌握地图的全局信息，并基于此进行诸多决策，从而在简单规则之下获得一定的智能，赢得与玩家进行初步博弈的空间。

相比之下，用于和高端玩家对称竞技的基于强化学习的 AI，则必然要求更多限制。即对称性表示，AI 必须拥有跟玩家等同的信息，并基于这一信息展开与玩家相同的决策过程，进而战胜玩家。

当下诸多陪玩性质的 AI，亦或竞技场合的 AI，为了避免让玩家感受到不公正，往往都会为其搭建更加严苛限制的感知层，使其以接口和输出为形式获取的感知信息，与玩家通过感官所能辨别的并无二致。

（当然，程序读取信息的带宽跟肉眼可怜的信息摄入角度相比、CPU 的运算时钟跟人脑可怜的神经递质相比，处理信息的效率又是另一层面的考量了）

简单来说，对于游戏 AI 中感知层这一环节的设计，虽然没有太多异构，但也存在着大批不同的倾向

全局信息输入，诸如我们熟悉的 FSM、BT 等方法，在未经复杂的系统化之前，都仅考虑以程序读取的直接信息作为判断。即程序读取全局的条件关键字，作为状态转换、节点执行的返回值
主客观分离，HTN、GOAP 等方法为游戏创意性地引入了 WorldState 这一层级，进一步将 Agent 所能感知的主观信息与客观信息进行了分离。为 AI 引入了“改造世界”这一诉求。同时这一分离也使得更多合适的评估指标有着合适的位置进行储存。
*感知数值设计，原则上这是一个辅助模块，穿插在上面两种主流方法之间。
- 最为典型的就有潜行感知系统、仇恨系统等等
- 设计师会基于相关模块，牢牢把控游戏的真实环境到 Agent 主观之间的映射，以塑造 Agent 和玩家之间独特的互动。更多相关系统的设计，都是设计师介入 AI 表现的空间所在

透过感知层的设计，设计师能够在不影响AI本身决策方法的前提下，进一步规划自己设计的体验。同时构造一个更加拟人而非程式化的AI。

‍

中期决策 —— 规划层

规划层即是当前绝大多数算法驱动AI所能达到的决策表现顶峰，其所实现的是通过规划，在当前情境下实现满足目标的行为路径。

暨相比之使用智能才能定义的目标（对于当前的主流AI方法而言，目标即为人类智能所定义的，为AIAgent进行表现的核心目的所在），规划层负责在目标和行为之间搭建桥梁

‍

基于决策结构的硬编码，行为树、状态机等方法，依赖于人类基于其结构硬编码的状态/行为流转，实现不同情境下行为序列的生成。但其本身并非具有规划智能
HTN决策方法，基于人类预构建的解空间进行搜索和规划，选取当前实际情境下效率最优（预定义）的方案并执行
GOAP决策方法，Agent基于改造世界达成目标的驱动力主动搜索行为实现路径，具有更灵活的表现
蒙特卡洛树搜索，以更高的效率在高度不确定环境中进行决策和规划。
强化学习算法，基于与环境模拟预训练，学习多种境况下的决策方式，并储存到预训练模型中供实际使用时调用。RL方法的核心竞争力在于其预训练时预演算步骤足够长，能更好地面对未来精打细算。
大语言模型，基于人类语言中储存的智能实现基础的自主规划，但生成并无约束，往往需要额外的程序集进行修正与验证，实际并不效率（更适合被架到目标层）

规划层的关键在于平衡计划的质量和计算效率。

对于求解复杂问题和组合问题。比方说模拟一个都市市民的日常生活，并让其在树下和老大爷下棋。在基础模拟中，简单的HTN或GOAP方法便能构建其拟人的日常表现。但在下棋过程中，强化学习 or MCTS 算法的介入，才能让其有更充分的复杂智能表现。

因此，在实际情境中，除了对前向任务的分解本身，对于单个任务也可能存在着进一步的分层与复合。

‍

长期决策 —— 目标层

目标层负责制定长期策略和高层目标。

但这一问题对于绝大多数游戏AI而言往往是无需考虑的，原因其实也很简单。

游戏AI就是基于设计师预定的目标而构建的

亦即游戏AI中编写的所有部分，天然就是为了服务于一个既定的目标，因而AI往往并不需要主动对自身的目标进行决策。也正是因此，在倒推框架时，我们微妙的找到了这个空余的部分。

当然，这对于AI本身而言也确实可有可无，将其纳入讨论范围，无非希望这则文章能尽可能全面罢。

‍

对于AI的目标切换，同样有这样一个最合适的例子。亦即AI从Idle、Patrol等状态切换到Battle中。

对于一个清晰分层的AI而言，这一组“状态”的切换，其实质便是目标的切换。无论其功能实现如何，在玩家对AI本身能动性的叙事性解释上，其必然象征其目标的切换。

‍

而一旦AI朝着复杂与智能发展，对相关逻辑的建模也必然要更加显式与清晰。

‍

状态切换硬编码，对绝大多数传统AI方法而言，AI的目标均是既定的，其与规划与行为相绑定。而对于这种相对清晰的状态切换，其时常表现为另一种制式的有限状态机。在目标状态机切换时，自主切换不同决策过程与行为组。
- 相关思路在ReGoap的示例仓库中便有体现，其使用简易FSM为GOAPAgent构建目标切换的逻辑
- 与此相似的还有日常NPCAI中的课程表规则
基于优先级评估的切换，和硬编码切换相似的模式，预定义了目标集合，并在运行时根据环境输入进行优先级评估，暨不存在状态转移机制的另一形式。
- e.g.1 依据硬编码优先级决定当前行为
- e.g.2 为GOAP中的Goal引入效用AI的评估函数
全局目标分配系统，相似处理方式用在城市氛围AI中较多，此类AI会在创建时依据全局系统需要分配氛围塑造目标，并视全局调度需要进行切换。
- 相关AI方法往往更定制化，可以参考看门狗2的MassAI分享
*强化学习方法，由于RL方法显著倾向于行为主义，其对行为的出发点往往不做显式呈现，而是一路贯通到行为接口。遂其独自面对复杂问题时可以起到较好成效，但难以与其它方法进行有效集成
目标生成系统，基于现代大语言模型的能力，基本为Agent带来了自主生成目标的可能，最为典型的便是 Generative Agents 一文
- 可以阅读个人博客中对相关文献的讨论：从 AI 到智能系统 —— 从 LLMs 到 Agents
- 在必要的时候，通过类人AI的参与，可以为Agent达成更多有趣而鲜活的表现

‍

目标层需要考虑长期影响和整体优化，通常服务于玩家最终对AI系统可信度的整体观感。

同样的，目标层中的诸多方法也可以相互集成。例如由全局目标分配系统分配日常表现目标，但允许Agent硬编码切换至与玩家敌对的战斗状态。类似还有将目标生成系统和目标分配系统的输出按实际表现需要（如玩家观测程度）进行汇集，共同指导下层的行为规划。

‍

在多数相对浅度，且不服务于开放世界智能体验的游戏中，对于目标层进行过度设计确实是得不偿失的。但也正因为对其的关注整体偏少，真正需要时我们才能在其间做出更多文章。

‍

长期反馈 —— 记忆层

记忆层的设计，往往是一个更加彪悍的工作，相比于设计AI表现，其更多考虑的是在全局上构造玩家体验

也正是因为如此，这也是最为定制化的AI系统组件，我们很难在其中列出一些更通用的分析，只能尝试举几个典型例子罢。

‍

DDA(Dynamic Difficulty Adjustment)系统，先从一个歪门邪道的例子来，通常我们并不会将其认知为一个AI模块组件，但它可以是。其通过玩家互动构建难度指标，使得游戏挑战性维系在一个合理范畴内，这种围绕时间做渐进反馈修正的方案，其实是个非常合适的思路。
- 可以参考的文章游戏设计——动态难度调整（DDA与MDDA） - 知乎
参数化记忆系统，比较典型的有好感度系统，即基于玩家好感度积累，差分Agent的AI表现。相关设计从诸如早期AVG，到各式RPG都在使用，即通过算法积累互动数值，并最终体现在AI的表现上，从而提供一种更深层的互动感。
- 和参数化记忆系统相匹配的还有类似消息传递系统之类的设计，但这类优秀的设计倒是没有相对典型的分享，遂我们没有一个切入点对此大书特书。相关比较有趣的应用，有诸如老滚5中NPC买凶杀人的桥段。
基于语言模型的复杂记忆处理，近期也有一些尚未投入应用的新方法，即基于大语言模型的记忆处理。其通过主动的记忆上下文检索，来执行更符合当下情景的处理方案。这一环节原则上是与目标层高度整合的。