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

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

前言

偶然发现收藏夹里躺了多年的文章链接¹，写作时间是2011年前后，作者是 Ronimo Games 的联合创始人 Joost van Dongen，简述了当时他们如何构建《剑与勇士》的 AI。《剑与勇士》（Swords & Soldiers）是 Ronimo Games 在2009年开发的一款2D横向卷轴RTS游戏。

简单翻译整理了一下，看看有没有参考价值。

译文

众所周知，为策略游戏创建良好的 AI 是一项艰巨的任务。AI 设计当然从来都不是一件容易的事，但对于策略游戏来说，选项和情况的复杂性非常高。我认为《剑与勇士》是第一款在游戏中实现真正出色 AI 的游戏，所以我想看看我们是如何做到这一点的会很有趣。

人工智能领域要么解决非常简单的问题，比如国际象棋（与实时战略游戏相比，国际象棋非常简单，更不用说与现实世界相比了！），要么只会提供大量精巧高效的辅助算法，比如寻路。在复杂情况下做出真正的决策本质上是一个尚未解决的问题，而且不会在短期内得到解决。