面向数据的行为树（2）：震惊！面向对象行为树并不面向数据

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

系列文章目录

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

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

背景

简单的行为树可以使用面向对象方式来实现，如果性能满足需求，非常适合人手不多开发时间紧张的小型团队。

简单实现如下：

class BehaviorTreeNode {
public:
  // ...
  virtual BehaviorState update() = 0;
  virtual void resetState() = 0;
};

template class ActionBehaviorTreeNode : public BehaviorTreeNode {
public:
  explicit ActionBehaviorTreeNode(ActionData *data);

  // Calls a certain member function of actor.
  virtual BehaviorState update();

  // Does nothing.
  virtual void resetState();

private:
  ActionData *data;
};

class SequenceBehaviorTreeNode : public BehaviorTreeNode {
public:
  // ...
  // Iterate through children, start from next to run until done or a child
  // returns that it is running.
  virtual BehaviorState update();

  // Calls resetState for the next to run node as it might have returned a
  // running state during the last update.
  // Prepares to start from the first child on next update.
  virtual void resetState();

private:
  std::vector children; // In sequence order.
  std::size_t nextChildToUpdateIndex;
};

class PriorityBehaviorTreeNode : public BehaviorTreeNode {
public:
  // ...
  // Iterate through children, start from next to run until the first one
  // returns success or that it is running.

  // If this child's index is lower than that of the previous one returning
  // running, rest the later child.
  virtual BehaviorState update();

  // Calls resetState for the next to run child as it might have returned a
  // running state during the last update.
  // Prepares to start from the first child on next update.
  virtual void resetState();

private:
  std::vector children; // In highest to lowest priority order.
  std::size_t nextChildToUpdateIndex;
};

// ... and so on with other node types...

Tony Albrecht 在 演讲 “Pitfalls of Object Oriented Programming”¹²中指出了面向对象编程的一些缺点，如忽视了内存访问模型以及目标平台内存系统需求。他还演示了如何将面向对象的场景树重写为以数据为中心的结构，从而获得了显著的性能提升。

行为树简化了游戏AI的建模复杂度，减轻了调试难度。即使要考虑性能以及如何充分使用硬件，也只是一个次要任务。但硬件平台各异，不良的内存访问模型会降低性能。比如：

• 树的遍历要跟踪节点的指针，引发随机内存访问，不利于缓存，当内存延迟出现时更是如此。
• 树节点的递归更新导致其调用栈深度不可控。
• 每次调用节点类update函数会在虚函数表（vtable）中查找实际的成员函数，产生间接的运行开销。有很多潜在的数据和指令缓存干扰问题！
• 在具有非统一内存地址空间的异构架构或平台上，例如 Cell SPU 的主内存和本地存储（local storage），或者 GPU 的 主机内存（host memory） 和 设备内存（device memory），试图移动这样一个基于图的行为树指针，会导致完全序列化 —— 即复制所有节点，并修复所有指针。—— 没有什么便捷方法可以一次性复制整个行为树。
• 在遍历时会调用叶节点的动作，这些动作会处理专门的动作数据，这会破坏缓存。如果在不同工作线程上遍历不同的行为树，则不会协调内存访问，也不会利用共享内存或缓存协调。
• 更糟的情况是：行为树系统的使用者可以用任意的内存访问模型和指针来实现他们自己的节点类。如果并行运行行为树却又忘了同步共享数据，从而引发条件竞争，但行为树系统对此没有任何办法来阻止这种情况的发生。更不必说由此带来的性能损耗了，因为高效的序列化取决于对共享数据作正确的同步访问。

基于模板的快速派发调用（Template-based fast dispatch calls）或许可以化解虚函数表带来的开销，一个任务队列系统也可以使调用栈深度变得可控（实现详见 AiGameDev.com 的行为树实现）。尽管如此，底层数据访问问题仍促使我们寻找不同的行为树运行时表示方式，这就是这个系列文章的目的。

译注：Template-based fast dispatch calls 是指使用模板来生成与不同行为树节点类型相关联的函数调用。例如

template <typename NodeType>
void ProcessNode(NodeType& node) {
    // 处理特定类型的节点
}

硬件墙

由于时钟频率的提高，指令级并行（ILP）³的利用，将内存或缓存放入芯片中以最大程度地减少访问较慢主内存，处理器变得越来越快。而更高的时钟速度会导致更多的热量，更复杂的功能导致更多的晶体管，产生更多的热量反而降低了性能，一头撞上了这些硬件墙⁴：

• 功耗墙：能消散多少热量的物理限制，由于时钟频率增加导致功耗增加，但散热限制了功耗的增长。
• 复杂度墙：为分支预测和推测执行而增加的晶体管会降低性能，架构的复杂度和晶体管数量需要在功耗和性能方面得到论证。
• 光速：影响信息在芯片上传输多远的物理限制。
• 内存墙：虽然内存带宽和读取速度随着时间的推移而增加，但并没有跟上处理器发展的步伐，正如 David A. Patterson 在 2004 年的发现⁵。现在的 CPU 等待数据从主存到达的周期比以往更久。

硬件制造商通过在处理器中加入更多核心，在核心中加入更多的晶体管的办法来对抗前两堵墙。这些核心通常比它们的单核 CPU 更简单。更多的核心意味着更大的计算潜力，而核心速度却没有增加太多。许多时钟频率不变甚至更低的核心直接转化为更低的功耗要求，从而减少热量产生。

另外一个策略是引入异构处理器：将不同架构的核心组合封装在一个芯片或物理处理器中。比如 图形处理单元（GPU），向量处理单元（SSE），或者 Cell Broadband 处理器 PPU 和 SPU 在一个芯片上。对于同一类任务，专门用于特定任务的核心比通用处理单元效率更高（功率和性能方面）。

在使用并行处理前，CPU 会通过将内存层次结构嵌入其中来克服内存墙。越靠近核心，速度越快，内存越小。一些例如x86处理器架构，在无需开发者干预的情况下自动使用缓存，而 Cell 的 SPU 的本地存储，以及一些 GPU 处理器的不同内存池，则属于不同的内存地址空间，需要开发者显式控制。

抛开不同内存层次结构的复杂性、功耗需求和核心数量的可扩展性不谈，有一点永远是正确的：”缓存未命中“和”等待从主存储器过来的数据“严重限制了单核和多核处理器的性能。正如 Tony Albrecht 所说的：“承认房间里的延迟大象”⁶，优化数据和数据访问模式是充分利用平台性能的关键。

不要相信 Mike Acton⁷ 所指出的三大谎言⁸——了解你的游戏将在哪个平台上运行（参考文森特·斯卡伊布⁹提供的游戏平台概览¹⁰）。

面向数据的设计

在 2011 年 GDC 上，Daniel Collin¹¹ 在他的演讲 “Culling the Battlefield – Data Oriented Design in Practice”¹² 介绍了 DICE 如何替换渲染和模拟中用来做剔除的树结构，转而直接使用数组蛮力处理，获得了可观的性能提升，代码更简洁，将来性能优化也更加容易。

他们遵循了面向数据的思想和设计。Noel Llopis¹³ 写了两篇精彩的文章《Data-Oriented Design (Or Why You Might Be Shooting Yourself In The Foot With OOP)》¹⁴和《Data-Oriented Design Now And In The Future》¹⁵，他在文章中生动地解释了这种思维方式和编程方法。

那么，何谓“面向数据的设计”（data-oriented design）？

• 考虑要解决的问题，要遵守的约束条件，不同的解决方案的优点和缺点：首先，期望的输出数据是什么样的？其次，输出的数据如何计算？最后考虑输入数据。
• 只将代码视为转换数据表示形式的一种手段。
• 专注于解决方案的数据表示，以最大限度地降低内存访问成本，最大限度地提高目标平台缓存或本地存储的局部性。由于其连续的内存布局，简单的数组可以击败复杂的数据表示。
• 考虑大批量的数据，而不是单独的数据。对数据排序，避免对数据进行逐条的条件类型检查（if-then-else语句 或 虚函数表查询）。
• 明确数据的访问模式（读、写、读写）并排序，再分阶段组织计算。同一个阶段中只读但不写入的共享数据则可以并行处理，而不会有竞争条件的危险。没有任何依赖的数据写入也可以安全地并行处理。与其对每个数据项进行影响性能的同步操作，不如用几个阶段来分隔同步的时机。

有意思的是，面向数据的设计不仅会带来更快的计算速度，还会带来更简单、更模块化的代码。更容易编写、调试、维护和优化的代码——这一切都要归功于数据优先的思想。

尾声

延迟大象已经到来，不要逃避，要面对它！线性内存访问允许进行访问预测和预取，击败随机内存访问 - 随机指针跟踪。根据数据的使用进行组织，并保持其内存占用小，可以实现数据局部性，最小化缓存碎片化，节省内存带宽。

桥梁建造者需要遵守物理规则 - 软件开发人员，尤其是游戏引擎开发人员需要了解他们的目标平台。

在介绍了行为树，邂逅数据导向设计之后，现在一切都为史诗般的第三篇文章做好准备。在这一篇文章中，我们将最终看到试验中的行为树设计。

所以，哈哈，之前承诺的”灵魂拷问“来了，你认为：

• 你想从一个行为树中得到什么？它应该生成什么样输出？
• 表示行为树的数据是什么样子的？它是如何使用/遍历的，是否有明显的访问规则？
• 在遍历期间更改了哪些数据，哪些数据没有修改？
• 行为树更新需要什么输入？

如果你在目前开发中的游戏里使用行为树：

• 你的游戏中有多少不同的行为树？
• 它们包含多少个节点？
• 它们在性能分析过程中是否”亮相“过？
• 你在哪里以及如何运行行为树更新，在多个主核心上并行运行，甚至在SPU上？

参考资料