本文介绍游戏AI与行为树的一些知识。本文希望做到：更加系统、与工具无关、附带练习。
游戏AI与行为树
本文中可能存在疏漏错误，或是夹杂了作者的主观观点，欢迎指正讨论。
游戏AI介绍
本节我们介绍一些AI的基础概念，如果你已经是一位老手了，那么本节中很多概念你应该都有有所耳闻，但是也不要急匆匆就跳过本节，因为精准的定义这些熟悉的概念往往并不是件容易的事情。
为什么需要AI
用一些具体的场合来回答这个问题：
- 在某次制作一个魂斗罗类的横版卷轴游戏时，为了使敌人不呆在原地，给敌人编写了简单的移动和攻击逻辑。
- 在制作大型团队副本时候，为了给玩家挑战，给BOSS编写了复杂的技能释放逻辑。
- 在多人合作游戏中，使用机器人混入真人玩家，给机器人一个合适的行为逻辑。
往往，我们会需要给一个游戏物体一定的行为逻辑，有时我们直接使用使用一系列固定的脚本，就行，而有时会需要一些条件判断，有时情况更加复杂，为了将这一块“行为逻辑”单独配置管理，在游戏开发中引入了游戏AI这个概念。
《Game AI Pro》中对游戏AI的目的描述更加上层，也能让我们更加聚焦游戏AI的目的：
游戏AI做，也只做一件事：那就是为玩家提供好的体验。
学术上的AI
“好的体验”并不是一个很好定义的概念，广义上的AI也是。
学术上的AI，多是在研究一些诸如固定情形下成功概率最大的行为的课题，比如投篮机器人、象棋对战AI、围棋对战AI，学术上会使用“问题空间”等概念来定义现实和问题的抽象，同时给出一个具象问题的抽象对应评估方式，并研究在各种情况下，何等行为能使评估方式给出的评分最高（概率最大）。
与学术上的AI不同，影视界也有AI的概念，这里的AI并不单单指科幻作品中的高智能、人格化的处理中枢形象，而是更加广泛的指虚拟但是从心底里让人感到真实的影视角色。比如猫和老鼠中的汤姆猫，兔八哥等，它们有自己的性格、行事偏好，影视作者们绞劲脑汁，让观众们觉得荧幕上的活动的色块就是一个活生生的角色，而影院中情绪被牢牢带动的观众们，也证明了创作者们的成功。
本文一致讨论的AI是游戏AI，从特征上讲，游戏AI并不是研究固定情况下期望最大的行为，游戏AI的目的更接近影视界的AI——两者同样专注于提供一些真实的行为、以假乱真的体验。中间可能会用到学术AI的算法和思想，但是会比学术AI更加有血有肉。
游戏AI受限于游戏类型、想要营造的体验，具体行为差异很大，用到的技术手段、算法也大有不同，在讨论的时候，我们可以关注以下游戏AI的特征：
AI的部分特征
- 作者控制：AI的修改权，衡量是否方便修改AI各种情况下的行为的能力。
- 反应性：AI是否能针对特定情形采取不一样的行为。
- 随机性：面对相同情形，AI采取的行为是否固定。
以作者控制为例，古典的游戏AI的逻辑是确定的，而近些年兴起的采用深度学习算法训练出的AI则是会根据训练集和评估方式产生变化的，你该如何对一个机器学习的模型表达出：“酷”、“傻大个”之类的概念呢，这种按照设计修改AI的能力就是作者控制。
我们可以按照作者控制给一些AI技术排一个序：
至于反应性和随机性，可以丰富AI体验，两者并不互斥，甚至可以结合起来。
这三者可能会根据游戏类型有着不同的倾向，也并不是“多就一定好”。
思考-1：
如何给机器学习的模型表达出：“酷”、“傻大个”之类的概念？
行为树历史概述
行为树是一种在游戏开发中广泛使用的AI技术，最早使用的主流游戏是《光环2》。行为树是分层状态机、调度、计划、与动作执行等AI技术的集合。
行为树最主要的优势是容易理解并且可以使用图形化编辑器（这很重要）。
你可能会敏锐的注意到，上面的AI技术排序中，并没有行为树，那是因为行为树的特性，很大程度上取决于行为树所使用的节点。后面我们会具体就行为树的特性展开叙述。
与有限状态机的对比
AI领域另一个常见的技术是有限状态机，经常会问的一个是问题是：两种技术各自适用的场景是什么？一般来说，行为树适用于AI，而有限状态机适用于其他的图形化逻辑，当然，两者可以互换，但是这不是这两个工具本来的设计意图。
对于一部分人来说，AI领域的有限状态机的时代已经结束了，这里不会继续深入叙述，但是行为树对比状态机确实有一定的优点。
- 灵活：比如支持并行、方便行为互斥。
- 可增长：在规模复杂以后，有限状态机的连线会很混乱。
- 容易修改：修改时只修改父层连线
行为树基础概念
本节我们会具体行为树的具体概念，我们会从底层开始，逐步解释行为树的构成、执行逻辑。
数据模型
故名思意，行为树采用树形数据结构储存数据，更准确的说，是有序树，因为显然，行为树对节点的顺序关系敏感（很多情况下有序的行为才有意义）。
节点类型
从节点是否可以连接子节点出发，我们可以把节点分为
- 叶子节点：不允许有子节点
- 父亲节点：允许有子节点
按照用途，叶子节点可以更加细分的分为：
- 条件节点：判断某一个条件，比如检测范围、检测属性、检测状态。
- 动作节点：执行某一个具体的行为，比如移动、设置属性、播放动作。
给一些具体的例子：
| 节点名 | 检测距离 |
|---|---|
| 节点类型 | 条件节点 |
| 节点说明 | 当距离在一定返回内，返回成功，否则返回失败 |
| 节点名 | 释放技能 |
|---|---|
| 节点类型 | 动作节点 |
| 节点说明 | 释放指定技能，成功释放，返回成功，否则返回失败 |
条件节点听起来就是会得到一个检测的结果，实际上，动作节点也有类似条件节点的“结果”，这里结果的意义可以是代表节点是否成功执行。
而且这些结果也就会用在下面这两种父亲节点上：
- 组合节点：储存一系列子节点，按照一定逻辑执行。比如与节点、或节点。
- 装饰节点：只能有一个子节点，修饰子节点的行为。比如非节点。
给一些具体的例子：
| 节点名 | 与节点（顺序节点） |
|---|---|
| 节点类型 | 组合节点 |
| 节点说明 | 会先逐个执行子节点，当有一个返回不为成功，则停止后续执行，返回失败。 |
| 全部为成功，返回成功。 | |
| 多用于一些前面条件不满足，后续行为失去意义的场合。 |
| 节点名 | 或节点（选择节点） |
|---|---|
| 节点类型 | 组合节点 |
| 节点说明 | 会先逐个执行子节点，当有一个返回为成功，则停止后续执行，返回成功。 |
| 全部为失败，返回失败。 | |
| 多用于一些并行行为的挑选的情况。 |
| 节点名 | 非节点 |
|---|---|
| 节点类型 | 装饰节点 |
| 节点说明 | 对子节点执行结果进行取反。 |
学过逻辑学我们会知道，与或非等基础逻辑行为，比如与是当参与运算的都为真才返回真。非是对结果取反。根据实际情况灵活组合，这三者已经有很强的逻辑表达能力了，还有命题逻辑等价逻辑（德摩根定律）。
下面我们给出一个例子：当检测距离节点检测到攻击距离合适的时候，就释放攻击。
那么稍微想想，假如现在要修改成：
- 检测不在某距离，释放某技能
- 在释放某技能后，再释放特定技能
- 随机概率释放某技能，如果概率不满足则释放特定技能
你会发现得益于基础的逻辑能力，将行为与特定条件组合起来这件事，变得异常简单。同时，对现有逻辑的修改、复用，也很轻松。
更多节点
本小节我们会给出更多节点和例子。由于游戏类型和目标体验的差异，不同游戏项目使用的节点可能差异很大，对于条件节点和动作节点这两类偏向业务逻辑的节点，这里不做过多赘述。本节更多地仍然是讨论一些表达能力上的组合节点，这些节点能很轻松地帮你解决特定类型的问题。
- 当结果不重要时：返回成功、返回失败
| 节点名 | 返回成功 |
|---|---|
| 节点类型 | 装饰节点 |
| 节点说明 | 无视子节点执行结果，返回成功 |
| 节点名 | 返回失败 |
|---|---|
| 节点类型 | 装饰节点 |
| 节点说明 | 无视子节点执行结果，返回失败 |
你会发现使用逻辑组合似乎也能达到返回成功或者返回失败的功能，有些时候引入新的节点就是为了使这种场景下的配置更加高效。
思考-2：
为什么说逻辑组合达到返回值不敏感和直接使用装饰节点的等价是似乎？
- 循环：重复节点、重复直到失败
| 节点名 | 重复节点 |
|---|---|
| 节点类型 | 装饰节点 |
| 节点说明 | 重复执行子节点，可以设置指定次数 |
| 通常放于顶端使整棵树重复执行 |
| 节点名 | 重复直到失败 |
|---|---|
| 节点类型 | 装饰节点 |
| 节点说明 | 重复执行子节点，直到子节点返回失败 |
这两个节点可能是实现相关的，会因为实现差异而有不同的表现，这里不给出单独的例子。
关于重复，后面还有更加深入的讨论。
- 更强大的选择：随机节点、可用性评估节点
| 节点名 | 随机节点 |
|---|---|
| 节点类型 | 组合节点 |
| 节点说明 | 随机选择子节点执行 |
| 可以延伸配置子节点的概率 |
| 节点名 | 可用性评估选择节点 |
|---|---|
| 节点类型 | 组合节点 |
| 节点说明 | 根据子节点的“可用性”选择最优子节点执行 |
这两个节点也可能会因为实现而产生差异，这里也不给出例子。
随机选择子节点执行，也是可以通过给行为前加概率来一定程度上实现的，这也是上文提到的，使用基础节点和使用专门的节点来达到相同的目的的问题。
可用性评估选择节点就是想问上文的作者控制的话题，行为可以自己知道自己是否更适合当前的场景，当然，你需要为行为指定一个合适的行为评估方式。
行为树高级概念
本节我们讨论一些更为复杂的行为树概念，比如对执行过程的建模、RUNNING与打断。
执行模型
以上节点的组合，成功完成了行为的组织，深入的另一个问题是这些节点具体如何执行，为了更加彻底的理解行为树，我们还需要了解行为树的执行行为。本小节节我们讨论更为深入的一些节点逻辑。
前面在介绍节点的时候，我们已经提到过返回值的概念，对于条件节点，返回值是条件的检测结果，对于动作节点，返回值可以是是否执行成功，或者是默认值。对于这两个叶子节点，我们可以将其逻辑提炼为：
//……
// 执行逻辑
void OnUpdate() {
// 执行动作
// 记录执行结果
};
//……
对于装饰节点和组合节点这两个父亲节点，事情变得没有这么简单，你可以已经留意到了，与节点和或节点，都是有短路行为的节点，子节点甚至可能会不执行，其关键逻辑可以抽象为：
//……
// 检测是否可以执行
bool CanExecute() {
// 有 子节点 且 合适执行
};
// 子节点执行完回调
void OnChildExecuted {
// 记录子节点执行情况
};
//……
实际上，就像状态机中角色每一帧一定会处于某个状态，行为树AI每一帧都会执行这些行为。是的，每一帧。你可能会敏感地在意到性能问题，后文会具体讨论，现在先让我们进行一个简单情况的假设，每个节点的性能很高——在一帧内，可以完成大量节点的执行，总结上面的两种类型：我们给出一个遍历事后的简单伪代码：
执行某个节点：
当前节点是父亲节点？
循环：是否有子节点合适执行
执行子节点
当前节点的实际执行
简单理解而言，是一个深度优先遍历，执行会先下后上，先左后右。
运行节点
本小节我们开始讨论是更加实际的情况（不再是上文的简单情况），事情会一下子变得复杂起来。
实际逻辑中，并不是所有动作都可以在一帧内完成，考虑一个持续2秒钟的攻击行为，在这2秒钟的时间内，你的AI行为树可能以每秒30次或60次的马不停蹄的执行着，为了防止意料之外的执行带来的后果（也包括性能后果）、安全的度过这段时间，节点的执行结果除了成功和失败之外，引入了运行状态（或者理解为“执行结果”）。
对于运行状态的节点，下次行为树执行时候会直接继续执行该节点，直到它完成运行状态，返回非运行执行结果（比如成功和失败），此时将继续执行该行为树的剩余部分。
运行节点真的是必要的吗？倒也不一定，运行节点主要解决了执行一个耗时行为的这几个问题：
-
性能，避免了行为树的层次遍历
-
副作用，执行行为树的遍历行为时动作节点执行带来的意外副作用
假如这几个问题有很合适地解决，或者根本不重要，那么运行节点的意义就大打折扣了。
在实际实现上，为了保证继续执行特定节点的目的，同时兼顾性能避免遍历，不同的解决方案可能会有不同的行为。
比如：采用储存运行状态的节点的方式，执行出结果后，会采用继续执行或者逆向遍历的方式。在执行运行状态的节点时候，对于复合节点，会存储当前执行的子节点个数。方便运行状态结束后继续执行未执行的部分。
你可能会想起了我们上面提到过的循环节点：
思考-3：
上文提到过循环节点，想想它和自定义运行节点和差异
打断返回值
上面我们说，运行节点结束后会继续执行，但是实际中会有这样的情况：对于一些完成运行节点执行后，后续节点已经判断不需要执行了。
为了更高效的解决这种问题，节点的运行结果在成功、失败（、未初始化）外，引入了打断状态，打断也是一个实现有差异的行为，最常见的打断状态是这样的：
- 顶层打断：顶层打断，向上传递，整棵行为树后续节点都会放弃执行。
有时，我们会引入自定义的运行节点，为了给自定义的运行节点返回成功、失败等正常结束信息，有时也会引入下面两个返回值。
对于自定义的运行节点，有很多种不同的做法，也有直接通过发送事件的手法完成告知结束这件事的，这里不展开描述。
- 成功打断：成功打断（分层），打断本层后续节点，向上传递，直到向上被父亲节点处理为成功（通常情况）。
- 失败打断：失败打断（分层），同成功打断，但是会被处理为失败（通常情况）。
注意，打断绝大部分情况都是配合运行节点使用的，在其前方没有运行节点时，会出现其后方节点未执行的情况（核心区别：缺失运行节点），其原因是：打断节点，当帧一定会打断后续所有节点的执行，但是下一帧，复合节点没有继续执行而是重新开始执行。（留意上文：运行状态才会让复合节点储存执行的个数。）
节点中运行与打断
不同节点对于RUNNING和打断的结果的处理可能是有差异的，本质上还是引入的状态过多，如何维护管理的问题。
推荐对于这些规则要有大致的了解，在实际使用时，不胡乱组合配置，不会遇到一些组合情况，如果有需要，建议实地充分测试组合运行结果和执行情况。
并行节点
并行并不是很高层的概念，之所以把并行放到这里来讨论，主要不同实现对含运行状态情况下情况下的并行节点的行为可能是有差异的。
并行的差异可能会体现在这几个方面：
- 短路行为：
- 逻辑与或短路是出现在节点执行之前还是之后
- 运行状态：
- 等待所有运行状态结束才算结束，还是任意一个结束结算结束
- 每次执行是所有运行状态的节点都会执行，还是只会执行一个运行状态的节点
某种实现的逻辑是如下所示的：
对于简单情况下的并行的与、或节点：对于与、或节点，短路行为是通过“是否有子节点可以执行”的判断完成的，对于简单情况下的并行与、或节点，会完成所有子节点的执行，而在当前节点的实际执行中，进行包含短路的判断，即：结果维持一致，但是“被短路的节点”会被执行。
对于含运行状态情况下的并行的与、或节点的讨论：在第一个运行状态完成计算后，逆向遍历执行的时，将有机会对其他节点进行执行，如果后续都是简单情况，则仍然会在当前节点的实际执行中，进行含短路的逻辑判断，如果后续仍有运行状态的节点，要小心运行状态的判断可能会被短路，对于整个并行与、或节点将可能返回确定的值。
动作游戏逻辑示例
本节我们以动作游戏给出一个行为的例子，大体思路会比较类似《只狼》的AI与MMORPG的结合。
只狼的AI可以通过拆包反编译得到LUA描述的逻辑，这里略过过程给出结果。
架构拆分
- 初始化部分
- 初始化FLAG值
- 设定目标
- 阶段A
- 固定演出
- 距离1：若干随机招式
- 距离2：若干随机招式
- 积蓄A：若干固定招式
- ……
- 阶段B
- ……
行为拆分
具体的行为会涉及到操控游戏角色的接口如何给出，这里我们讨论一些具体的行为
- 移动类
- 远离版边
- 靠近目标（走、跑、闪避）
- 攻击类
- 释放单个技能
- 依次释放技能
- 闪避远离
- 特殊逻辑
- 被攻击时脱出
- 固定演出
- ……
AI的设计
此处将补充若干AI设计方式和一些基础理论。
OODA循环
又称柏伊德循环（Boyd cycle），这个循环也可以对应AI的一个行为循环。
- 由美国空军上校约翰.柏伊德提出的决策方法。这个方法是一个循环，由观察（Observe），调整（Orient），决定（Decide），与行动（Act）组成，反复进行。这个方法最早应用于战斗机飞行员的训练。
- “调整”步骤在整个OODA循环中最为关键，因为如果敌人对外界威胁判断有误，或者对于周围的环境理解错误，那么必将导致方向调整错误，最终做出错误决策。
- 了解（Orient）：清楚自身的目的，預測對方的策略。
- AI设计里面的Orient在像是判断：通过一系列规则将观察的数据变为结论，用于配置AI差异化的参数，引入性格。
练习思考参考解答
- 考虑引导机器学习的对于最优评估的评估方式（函数），把高层行为拆分为数据。
- 如何证明等价？使用枚举化可以得在返回成功、失败时，得到的结果是相同的。但是对于运行和打断，可能不同的实现会有不同的结果。
- 考虑：
- 循环N次
- 无运行状态的简单情况（例如命令行输出一条日志），循环 5 次可以在单次Tick中完成，而自定义运行节点需要阻塞5次Tick打印。
- 有运行状态的真实情况（例如等待5秒钟），循环 5次等待5秒会等待25秒，自定义运行节点就是等待5秒。
- 循环N次直到打断
- 无运行状态的简单情况，两者大体等价，需要分析关于打断情况的处理。
- 有运行状态的真实情况，若运行节点支持嵌套，则两者大体定价。需要分析关于打断情况的处理。