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

系列文章目录

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

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

前言

今天我们来看看行为树运行时实现的主要数据结构，以及在行为树更新期间它们是如何相互作用的。

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

系列文章目录

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

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

前言

上一篇关于面向数据行为树的文章对许多人来说太长，很难找到足够的时间完整阅读。我自己也会有困难抽出足够时间和精力完全消化它。因此，剥离面向数据设计的诸多实践内容后，这篇文章就是上篇文章的高层次概述。

动机

目前和未来硬件中，相比计算机在寄存器中的数据计算，内存访问和数据移动具有更高的成本（能量和时钟周期）。到主内存的内存带宽是有限的。测量以处理器周期为单位，内存访问速度和计算性能之间的差距是一个令人恐惧的鸿沟（夸张的说法）。缓存未命中和/或从主内存而不是 CPU 缓存获取数据的必要性是计算的瓶颈，并且可能窃取运行在其他核心上的计算任务的内存带宽。

依赖于节点指向其他节点的传统层次结构的行为树（BT）实现，在遍历树时很容易导致许多随机内存访问。每次随机内存访问都是一个潜在的缓存未命中（Cache Miss），这意味着等待数据并浪费时钟周期。

另外，如果叶节点调用的动作处理大量的数据，那么会发生更多的缓存未命中——请求的数据到达 CPU 时可能会逐出行为树数据，一旦树遍历继续，则需要从主内存中恢复。

虽然许多行为树的使用在性能分析器中不会看到其遍历的影响，但我们想了解并学习如何构建更高效的硬件和更面向数据的行为树，从而使许多实体（Entity）运行大量的行为树，甚至在 PS3 的 SPU 上。

在开发过程中，快速迭代和支持游戏 AI 的监控和调试是提高游戏性（玩家体验）的一个重要因素。我希望游戏运行时的行为树支持实时调整，而不是因为行为树变化，需要重新编译，重新启动游戏。

要点概括

为了满足在游戏中快速遍历行为树，以及快速修改和开发期间观察游戏的需求，我们使用两种不同的行为树表示形式，分别用于运行时和开发时。

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

系列文章目录

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

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

前言

如何使行为树及其分支、情境依赖性遍历以及它们的非规则数据访问模式与游戏平台的内存层次结构协调？如何将数据导向设计付诸实践？在运行时进行快速迭代和行为调整又该如何实现？

这些问题激发了作者对面向数据的行为树的探索。在第一篇文章中，我们了解了行为树的概念，在第二篇文章中，我们理解了平台的内存系统对发挥性能的关键作用，面向数据思想，以及如何适应这一编程思想，现在是时候将这些知识付诸实践了。

目标和需求

功能需求

行为树是一种工具，也是一种模型。它可以描述 Actor 的行为，并将整个决策过程分解为多个行为的组合。行为节点也具有明确的语义，它可以影响行为树的遍历方式，从而影响 Actor 的决策过程和执行结果。它的功能应该具备：

• 易于创建、理解 Actor 的决策过程；
• 简化行为的重用，具备重用的行为库；
• 能够实现游戏内 AI 行为的快速迭代、调试、优化；
• 提供直观的调试信息，最终实现AI内部运作信息的可视化。

性能需求

一款游戏可能只有几个，或者有数百到数千个，由行为树控制的实体（也称为 Actor）。在这两种情况下，游戏人工智能（AI）通常每帧只有很少的时间预算，行为树不应该夺走”导航“和”视线感知“所需的计算时间。宝贵的计算周期也不应该浪费在等待数据进入 CPU 核心寄存器上。对于我们这个实验，在运行时实现高效的决策制定和角色控制，以下因素至关重要：

• 最小化缓存碎片，减少随机内存访问，警惕内存访问延迟¹；
• 可以将 Actor 的行为树数据作为一个整体或逐块地移动到计算核心的本地内存中²；
• 节约内存带宽，保持较低的内存需求，利用内存分层结构内的数据共享；
• 了解最坏情况下的内存使用情况，预先分配内存并简化在游戏主机上的运行；
• 不要失去对调用堆栈深度的控制；
• 利用并发的优势。

总结起来就是，在游戏建模或开发阶段要求灵活性和快速迭代，而游戏运行阶段则要求执行效率和高性能。这些需求在很大程度上是相互对立的，因此此次尝试的前提条件是：对行为树的开发时和运行时表示使用单独的表示，然后再将二者巧妙地连接起来，两全其美，代价就是更大的代码量和复杂性。

这篇文章是 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...

这篇文章是 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工具包。

《蛤蟆先生去看心理医生》这本书借用《柳林风声》中的角色，讲述了蛤蟆先生的抑郁症状。在心理咨询师苍鹭的帮助下，蛤蟆先生发现自己的心理状态与童年经历息息相关。最终，他认识到自我，学会控制情绪，摆脱抑郁，并开始新的生活。