面向数据的行为树（1）：行为树入门

这篇文章是 Bjoern Knafla 撰写的系列文章《面向数据的行为树（Data-oriented Behavior Tree Series）》 第1篇。文章原载于AltDevBlogADay，AltDevBlogADay 是一个技术文集，主要由游戏业界老兵们于2011-2014年撰写。原站已经关闭，即使时隔多年，很多文章仍值得一看。

系列文章目录

《面向数据的行为树》系列文章介绍了作者在面向数据的行为树设计过程中的思考和探索，以下是系列文章的目录：

1. 面向数据的行为树（1）：行为树入门
2. 面向数据的行为树（2）：震惊！面向对象行为树并不面向数据
3. 面向数据的行为树（3）：数据导向流催生的行为树
4. 面向数据的行为树（4）：面向数据的行为树概述
5. 面向数据的行为树（5）：行为树结构剖析

行为树简介

什么是行为树？它的工作原理是什么？它在游戏AI中又起什么作用？

本文介绍了作者将面向数据、内存优化的行为树二者结合，以简化开发过程中的创建和修改的试验（读作：探索）经历。作者写这篇文章是为了记录其发现和决定，并征求读者的反馈意见，最终实现一个真正有用的BSD许可的BT工具包。

背景

越来越多的游戏AI程序员采用了行为树(BT)来实现虚拟生物的响应式决策和控制，正如 Alex Champandard 在 “retrospective for 2010 and outlook for 2011”¹ 提到的那样。

行为树及其原理

作者对行为树的观点和理解很大程度上受到 Alex Champandard 的 AiGameDev.com 教程和线上大师课的影响。Alex 的行为树定义非常详实精细。关于游戏中行为树的其他重要在线资源包括 Damian Isla 关于 Halo 2 中 AI 的文章²、Max Dyckhoff 的 “Decision Making and Knowledge Representation in Halo 3”³，以及 Ricard Pillosu 的 “Coordinating Agents with Behavior Trees”⁴ 幻灯片中介绍其在孤岛危机中的应用。Joost van Dongen 在博客中介绍了行为树在《剑与勇士》中的使用⁵⁶.

以作者的理解，行为树不仅仅是树，而是有向无环图（DAG）。一个节点可以有多个父节点，父节点可以重用子树，从而实现模块化。

行为树使用限制性更强但也更结构化的遍历定义方法，它取代了有限状态机 （FSM） 混乱难搞的状态转换。行为树是由节点组成的行为子树分层组织而成。访问一个节点，或者说访问以它为根的子树，它会按照它的预定行为或功能来运行。节点或子行为树的执行会产生一个汇总的返回状态，例如：

• 节点在调用之前已经准备就绪，状态为 ready
• 已成功完成，状态为 success
• 行为尚未完成，仍在运行中，状态为 running
• 运行失败，没有副作用，状态为 failed
• 运行时发生错误，存在副作用，需要明确处理，状态为 error

更新行为树时，始终以_深度优先_顺序从其根节点开始遍历。每个遍历的节点都会影响遍历过程。 选择器（Selector） 节点会选择其中一个子节点（如果有的话）进行下一步遍历。在第一个子节点及其子树被遍历后，选择节点会重新运行以响应子节点返回的状态，从而决定是否应该向上遍历到其自身的父节点，还是选择下一个子节点进行下一步遍历。

内部节点明确控制遍历语义，例如：

• 在每次遍历时，优先选择器（ priority selector）⁷ 要按优先顺序运行哪个子节点，直到第一个子节点成功或返回正在运行。这里有两种处理选择：
  1. 在下一次行为树更新时再次调用最后仍在运行的节点。
  2. 始终从最高优先级子节点重新开始遍历，如果上一个正在运行的子节点没被选中时，取消它的运行。
• 序列选择器（ sequence selector） 一个接一个地运行子节点以完成。如果一个或多个失败，则整个序列也失败。在没有重置或完成最后一个子节点的情况下，序列将存储最后运行的子节点，以便在下一次遍历时立即回到这个节点。
• 循环（Loop） 就像序列一样，但是它们在遍历到最后一个子节点时又会从头开始，而不是像序列节点那样返回到父节点。
• 随机选择器（Random Selector） 随机选择要访问的子节点。如果一个运行中的节点再次访问，直到它完成。
• 并发（Concurrent）⁸ 节点在每次遍历中访问其所有子节点。预先指定的数量的子节点需要失败才能使并发节点失败。与真正并行运行其子节点不同，可能存在一种特定的遍历顺序，可以在向并发节点添加条件（见下文）时利用，因为一个早期失败的条件会阻止其后续并发兄弟节点的运行。
• 装饰器（Decorator） 节点通常只有一个子节点，并用于强制执行某种返回状态或执行定时/计数，从而限制子节点在给定时间内运行的频率，或者在不暂停的情况下可以执行的次数。

叶节点可以分为：

• 动作（Action） ：最终引起角色或游戏世界状态的变化，例如规划路径并移动，探测最近的敌人，显示特定的动画，切换武器或播放指定的声音。动作通常会协调并调用不同的游戏系统。它们可能在一个模拟时钟周期（一帧）内运行，或者可能需要在多帧内才能完成其工作。
• 条件（Condition） ：检查某些角色或游戏世界状态是否为真。如果序列节点的一个子节点是条件，那么条件失败将阻止其在更新期间遍历后续节点。如果把条件节点放在并发节点下时，条件成为一种不变性检定，如果必要的状态变为非法，则阻止其兄弟节点运行。

在行为树更新过程中，通过传递给其角色（Actor）特定黑板（Blackboard）上收集的或预先计算的值，动作和条件来获取对角色和世界状态的访问。

”此处有龙“⁹——一个示例行为树及其遍历

直到开始亲自实现行为树的更新遍历，才能真正理解了所有细节。为了缩短这一过程，我们先看一个龙的行为树，这是一个简单的行为树示例：

• 0. 根节点  priority selector
  • 1. 守护宝藏 concurrent selector
    • 1.1. 宝藏附近的小偷能否被发现？ condition
    • 1.2. 赶跑（或吃掉）小偷 sub-behavior
  • 2. 抢得更多财宝 sequence selector
    • 2.1. 选择飞去的目标城堡！ action
    • 2.2. 飞向城堡！ action
    • 2.3. 攻击（并吃掉）守卫 sub-behavior
    • 2.4. 是否有力气携带宝藏回去？ condition
    • 2.5. 带上金子！ action
    • 2.6. 飞回巢穴！ action
    • 2.7. 将新抢来的宝藏放好！ action
  • 3. 发一张宝藏照片到 Facebook sub-behavior

每个子节点（以及子节点的子节点，以及… 你懂的）可能是另一个定义行为的子树。在这个例子中，我们只要考虑子节点1和2的情况。

实例中的根节点是一个 优先（Priority） 节点（id为0）。

节点1（守护宝藏） 是一个有2个子节点的 并行节点（concurrent）。 节点1.1（宝藏附近的小偷能否被发现？） 只有在宝藏附近的入侵者被发现时，才会返回 success ，否则返回 failed。要注意不仅要测试小偷是否靠近藏宝处，还要检查龙是否处于可以发现小偷的位置。如果龙目前正在去找黄金，它就会因为没看到小偷而不会攻击。请记住，优先选择器可能会首先检查其优先级最高的子行为，而不是继续执行上次“running”状态的子行为。

节点1.2（赶跑（或吃掉）小偷） 可以是一个子树，也可以是一个激活战斗系统的 action。

回到根节点的第二个子节点，节点2（抢得更多财宝） 是一个序列（sequence）节点。节点2.1 是一个选择要袭击的城堡并搜索到达路径的动作。通过 节点2.2，龙沿着计算出的路径飞行到城堡。以上就是在示例遍历过程中涵盖的节点，其他节点也可以根据名称非常容易理解。

遍历开始之前，所有节点的状态都是  ready，为执行做好准备。 

当行为树首次更新开始时，它会首先访问并运行状态为 ready 的根节点 0。

该优先节点从第一个子节点开始检查，直到某个子节点返回“success”或“running”状态。如果找不到成功或运行中的子节点，则该节点失败。

优先节点的第一个子节点。是一个Id 为 1 ，状态为 ready 的并行节点。

要遍历它，就要同时访问它的所有的子节点。

它的子节点——条件节点 1.1. 宝藏附近的小偷能否被发现？ 执行失败，因为没有看到入侵者。

因此整个并行节点 1.（守护宝藏） 执行失败。

优先节点 0. 根节点 尝试按其优先级顺序运行下一个子节点。 节点 2. 抢得更多财宝 已处于  ready 状态，因此被访问。

序列节点首先将遍历引导到其子节点 2.1. 选择飞去的目标城堡！

目标城堡已成功被选中。 A target castle has been chosen successfully.

执行序列节点的下一个子节点 - 节点 2.2. 飞向城堡！

由于城堡很远，因此在这一次更新步骤中无法到达，因此它返回  ”running“ 状态。

序列节点 2. 不能再往前，并且会返回 running 状态 至其父节点。

优先节点 根节点也以 running 状态退出，它找到了一个正在运行的子节点，因此不需要继续遍历优先级较低的子节点。此次更新遍历已完成。

在下一次遍历之前，所有未运行的节点都设置为 ready 状态。

在下一个模拟步骤中，行为树将再次更新，遍历将在根节点重新启动。

它会检查第一个子节点，但仍然失败，因为龙看不到它宝藏附近的小偷。

因此遍历到达优先节点的下一个子节点 2. 抢得更多财宝，它还没有重置其 running 状态，并且仍然保存着上一次执行的子节点，因为没有更高优先级的兄弟节点运行，所以它没有被重置。

序列节点 2. 抢得更多财宝 已经存储了它最后访问的子节点：动作  2.2.飞向城堡！，在本次更新步骤中它可能会成功，继续运行，或者失败。

行为树的遍历图解暂时告一段落。

行为树与有限状态机的对比

为什么要用行为树替代有限状态机（FSM）？

FSM 状态之间的转换带来了很大的自由度，但也陷入了一个难以理解和追踪的混乱状态，随着状态的增多，这种情况变得越来越严重。不过分层有限状态机（HFSM）在这方面有所帮助。

行为树的主要优点在于它们相对于有限状态机来说语义更加清晰，即使有点受限。更容易专注于设计者想要表达的内容，而对于复杂的有限状态机，常常让人感到有些迷茫和不知所措。在这种情况下，约束是有益的——它会为我们的思考指引方向。

选择器迫使我们以一种非常具体的方式思考和看待问题，使得 FSM 状态转换的局限性显现出来。

此外，作为原子构建块的 条件（condition） 和 动作（action） 可以插入选择器中，使其更具可重用性。一个动作甚至整个行为子树可以出现在树的多个位置。条件（condition） 和 动作（action） 节点也可以和特定的条件相结合，保证树的不同位置的行为正确执行。如果有与战斗招式相关的动作，那么将其与条件相结合，这些动作就可以在角色接近敌人并有足够的空间使用特定招式时执行。

Alex Champamdard 经常强调要把动作、行为和子树视为要实现的目标，这些目标构成了行为树¹⁰。行为树在运行时会检查它们是否可以完成，执行一系列步骤来接近目标，还要确保没有其他更高优先级的目标来“吸引”角色的关注。

由于行为树清晰明了的结构，让内存组织结构的优化成为可能，从而能够实现非常有效的遍历，目前这在有限状态机上是无法想象的。

下一步计划

这篇文章就到这里了。希望能给你一个很好的介绍，让你了解行为树是什么，以及它是如何运作的。下一篇文章将解释为什么需要一个流式内存布局的行为树，这种面向数据的行为树是什么样子的，并且开始实现一个基于测试驱动的行为树。

参考资料