种一颗小小的行为树 - 开发笔记

本文是最近开发的一个简单的 C++ 行为树库 bt.cc 的开发笔记。

行为树是游戏和机器人中 AI 领域最常用的编程模式之一。

这里所说的 AI 不是指机器学习那一套，而是「硬AI」，或者说是一种「伪 AI」，因为其中并没有真正的智能，只是行为的丰富性让实体看上去有了智能而已。

说白了就是 如何模块化的组织好预设的行为模块，本质上是一种编程框架。

设计要点 ¶

1. 实体的状态和数据，同行为分离。

   如果存在大量的同一种实体、有着同一套行为，我们期望把所有实体放在一起存储（比如放在一块连续内存上），那么如何把行为和实体的状态数据分离是一个问题。

2. 代码按树状结构组织成树。

   行为树本身是一个树状结构，那么在代码中即可组织成一颗树的模样，清晰直观。

3. 支持带优先级的、随机的、带状态的行为。

行为树 ¶

各个事先设计好的行为模块组织成树，从树根递归向子孙节点传播 Tick() 调用，根据节点的类型不同，形成不同的行为模式。

在执行 Tick 函数之后，节点要回答其状态：

bt::Status::RUNNING  // 执行中
bt::Status::FAILURE  // 已失败
bt::Status::SUCCESS  // 已成功

最基础的几种节点，如下分类：

• 叶子节点：没有任何子节点

  具体有两种：Action 和 Condition。

  其中 Action 负责执行一个具体的动作，Condition 则检查一个具体的条件而不含 RUNNING 状态。

  比如说，下图中，只有当条件 C 检查成功后，才会执行动作 A。

  

  Condition 的一个示意实现

  virtual bool ConditionNode::Check(const Context& ctx); // 需要填充
  Status ConditionNode::Update(const Context& ctx) override {
    return Check(ctx) ? Status::SUCCESS : Status::FAILURE;
  }
  

  有的行为树库直接把条件节点实现为一种装饰节点，用起来更方便。在 bt.cc 中我做了一个类似的叫做 ConditionalRun 的装饰节点。

  ConditionRun 的一个示意实现

  Status ConditionalRunNode::Update(const Context& ctx) {
    // condition 是一个 Condition 节点, child 是另一个子节点
    if (condition->Tick(ctx) == Status::SUCCESS) return child->Tick(ctx);
    return Status::FAILURE;
  }
  

• 单孩子节点：即只含有一个子节点，代表就是装饰器节点 Decorator。

  比如说，下图中，Repeat(2) 是一个循环节点，直到其修饰的子节点成功执行两次，它才向上汇报成功。 也就是，在第二帧的时候，动作 A 第二次成功时，根节点才成功。

  Repeat 节点的一个示意实现

  Status RepeatNode::Update(const Context& ctx) {
    auto status = child->Tick(ctx);
    if (status == Status::RUNNING) return Status::RUNNING;
    if (status == Status::FAILURE) return Status::FAILURE;
    if (++counter == n) return Status::SUCCESS;
    return Status::RUNNING;
  }
  

  

• 组合节点：可以包含多个子节点。

  又可以继续细分为三种：

  • Sequence： 全部子节点返回成功时，才成功，否则一个失败即全部失败。

    Sequence 节点的一个示意实现

    Status SequenceNode::Update(const Context& ctx) override {
      for (auto& c : children) {
        auto status = c->Tick(ctx);
        if (status == Status::RUNNING) return Status::RUNNING;
        if (status == Status::FAILURE) return Status::FAILURE;
      }
      return Status::SUCCESS;
    }
    

    下图中，左边的在 3 帧全部成功后，sequence 节点才会汇报成功。而右边的，一旦遇到一个失败的子节点会立即汇报失败、不再继续尝试后续的子节点。

    

  • Selector： 全部子节点返回失败时，才失败，否则一个成功即全部成功。

    Selector 节点的一个示意实现

    Status SelectorNode::Update(const Context& ctx) override {
      for (auto& c : children) {
        auto status = c->Tick(ctx);
        if (status == Status::RUNNING) return Status::RUNNING;
        if (status == Status::SUCCESS) return Status::SUCCESS;
      }
      return Status::FAILURE;
    }
    

    下图中，左边的在第 2 帧就遇到一个成功的子节点，直接汇报成功。右边的会在 3 帧所有孩子失败后，汇报失败。

    

  • Parallel： 并行检查所有子节点，全部成功时才算成功，否则算作失败。

    和前面的两个不同之处在于，Parallel 节点无论如何会执行一遍每一个子节点，最后再汇总结果。

    Parallel 节点的一个示意实现

    Status ParallelNode::Update(const Context& ctx) override {
      int cntFailure = 0, cntSuccess = 0;
    
      for (auto& c : children) {
        auto status = c->Tick(ctx);
        if (status == Status::FAILURE) cntFailure++;
        if (status == Status::SUCCESS) cntSuccess++;
      }
      if (cntSuccess == children.size()) return Status::SUCCESS;
      if (cntFailure > 0) return Status::FAILURE;
      return Status::RUNNING;
    }
    

    比如说下图中，左右两边都会让每个子节点被执行到，但是根据成功子节点的个数来汇总决定 Parallel 的最终结果。

    

当然，上面给出的代码，属于第一版的实现，最终因为 bt.cc 加入了 Stateful 组合节点、和 优先级等因素，实现变的稍许复杂了一些， 不过道理仍然是这个道理。

可视化 ¶

如果要画一张图来表示一颗行为树，可以有两种方式：

左边是一个中规中矩的树状结构，右边则整齐很多，所以我推荐右边的方式，在这种方式下：

• 自上而下是兄弟节点的优先级关系，上面的更优先
• 自左而右是父子关系。

深度优先的情况下就是先从左向右、然后再向下走。

bt.cc 支持一个简单的功能，就是输出到 console 可视化行为树的每一帧， 也是按照这种方式来排列一颗行为树的，其中绿色的是正在激活中的节点：

组织一颗行为树 ¶

在代码中，同样遵循着这种排列方式：

bt::Tree root;

root
 .Sequence()
 ._().If<A>()
 ._()._().Action<B>()
 ._().Selector()
 ._()._().Action<C>()
 ._()._().Parallel()
 ._()._()._().Action<D>()
 ._()._()._().Action<E>()
 .End()
;

其中，一个特殊的方法 _() 负责递增缩进，这样整个代码看上去就是这颗行为树最终的样子。

细节只是，不要忘记调用 End()。

内部实现上，在构建一颗树时，有一个栈来保存「中间节点」的缩进路径：

std::stack<InternalNode*> stack;

• 当遇到一个「中间节点」时（比如一个组合节点）、则会把它 push 到栈顶。
• 当遇到一个新的节点添加时，会看栈顶的「中间节点」（比如下方的 Sequence )，作为其孩子节点。
• 当缩进收缩时，也就是小于栈的深度时，会抹平栈顶多余的部分，此时 Sequence 节点封住、从栈中弹出。

子树 ¶

行为树最美妙的特点之一是，行为能力的模块化。

而且，我们可以把一套行为组成一颗树，然后挂载到另一颗树上，作为子树存在。这像极了函数中的子过程调用。

// Walk 函数构造一颗子树
auto Walk = [&](int poi) {
  bt::Tree subtree("Walk");
  subtree
    .Sequence()
    ._().Action<Movement>(poi)
    ._().Action<Standby>()
    .End()
  ;
  return subtree;
};

root.
  .RandomSelector()
  ._().Subtree(Walk(point1)) // 这里是 move
  ._().Subtree(Walk(point2)) // 这里是 move
  .End();

其实行为树的描述本身就很像一种编程语言，你看，我还实现了 Switch/Case：

root
  .Switch()
  ._().Case<ConditionX>()
  ._()._().Action<TaskX>()
  ._().Case<ConditionY>()
  ._()._().Action<TaskY>()
  .End()
;

钩子函数 ¶

主要支持下面的几种钩子函数：

class MyAction : public bt::ActionNode {
 public:
  // 在一轮的开始时会被调用，就是说本节点的状态从其他变成 RUNNING 的时候：
  virtual void OnEnter(const Context& ctx) {}
  // 在一轮的结束时会被调用，就是说本节点的状态变成 FAILURE/SUCCESS 的时候：
  virtual void OnTerminate(const Context& ctx, Status status) {}
  // 在这个节点刚被构建完成时调用
  virtual void OnBuild() {}
  // 每一帧执行的 Update
  virtual bt::Status Update(const Context& ctx) {}
};

其中 OnEnter 和 OnTerminate 的执行的时机可以看下图：

当然，这肯定依赖于「带状态」的数据，那么这些数据如何和行为树本身的组织分离呢？

数据和行为分离 ¶

具体的说，是要把「实体相关的数据」和行为树本身分离开来。

在模块实现上，可能需要把所有实体放在一个模块、把行为树的这些 class 和树结构的代码放在另外一个模块（或者系统）。

我搞了一个叫做 TreeBlob 的概念，用来存储一颗行为树在某个实体上的数据，分为两种实现。

struct Entity {
  // DynamicTreeBlob 存储行为树中所有和实体相关的状态数据
  bt::DynamicTreeBlob blob;

  // 或者用一个固定大小的 TreeBlob, 会直接内嵌到 Entity 结构体内
  // 最多 8 个节点 x 每个节点最多64个字节, 固定大小二维数组
  bt::FixedTreeBlob<8, 64> blob;
};

用哪一种都可以、FixedTreeBlob 更快点但是也麻烦点，它的好处是直接跟随实体的内存存储，缓存友好。

然后，通过「临时绑定」的方式，来让行为树操作实体数据，主循环中是这样的：

bt::Context ctx;

// Tick 主循环中
while(...) {
  // 遍历每个实体的 blob 数据块
  for (auto& e : entities) {
    // 绑定一个实体的数据块
    root.BindTreeBlob(e.blob);
    ++ctx.seq;
    root.Tick(ctx)
    // 解绑
    root.UnbindTreeBlob();
  }
}

bt.cc 中内置的有状态的节点（比如一些装饰器 RepeatNode, RetryNode 等、节点的通用状态数据） 都会保存在 blob 中，而不会直接跟随树结构。

总而言之，行为和实体数据在代码上、内存上都是分开的，通过临时绑定来在一起 work：

带状态的组合节点 ¶

bt.cc 对三种组合节点，支持了「带状态」的能力，它们的设计意义在于，在一轮的执行中，可以避免重复的询问已经成功（或者已经失败）的子节点，提高效率。

下图以 StatefulSequence 为例，第 1 帧的时候，动作 A 执行成功，动作 B 处于执行中，第 2 帧的时候会直接跳过 A，从 B 开始询问 Tick。 直到所有的子节点成功或者失败，一轮算作结束。下一次执行就恢复如初。

在内部实现中，会有一个容器来存储哪些子节点需要跳过，在一轮的开始时会去清理它。

带优先级的组合节点 ¶

默认的情况，所有子节点之间是平权的，都是 1，会按照在树中组织的顺序、自上向下来 tick。

不过可以重载方法 Priority，来实现兄弟节点之间的不同优先级：

class A : public bt::ActionNode {
 public:
  unsigned int Priority(const bt::Context& ctx) const override {
      // TODO, 返回一个正整数
  }
};

比如，对下图中的选择节点来说，会优先询问 B 的 Tick() 方法。

这个优先级是支持动态的，也就是说在两帧之间，优先级可以变化，一个组合节点会一直优先考虑最高优先级的子节点进行 Tick。

内部实现上，是采用了一个优先级队列。

细节上做了两点优化：

1. 帧内优先级缓存

   因为 Priority() 方法会在每一帧递归执行，所以它的性能至关重要，内部会对当前帧的节点优先级进行缓存。

   也就是说，在同一帧内，保证每一个节点的优先级最多只被询问一次。

   另外，虽然节点的优先级是和实体相关的数据，但是因为其生命周期仅限于一帧之内，所以大可放心的存在树节点上， 这样只作为树的运行时数据的意义存在。

2. 等权优化

   由于采用了优先级队列，理论上的时间复杂度就成为了 O(logN)。但是，这对于无需优先级的情况是一种性能退化。

   一种办法是，节点直接显式声明自己不考虑优先级。不过我目前还是采用了一个「运行时」一点的优化，即每一帧刷新 Priority 的时候， 会看一下一个组合节点的所有子节点是否平权。如果是平权的话，那么就不按优先级队列、而是用一个一般的预设内存的 O(N) 队列来平替。

   下图中，在当前帧内，如果三个子节点是平权的，那么会走 q1，它是一个简单的 FIFO 队列（内存预先申请的、没有运行时内存申请）， 否则，如果三个子节点不平权，那么会走 q2，它是优先级队列，总体时间复杂度是 logN 的。

   

随机选择节点 ¶

顺便支持了一个随机选择节点 RandomSelector，它的设计目的是，随机选择可以让 AI 变的不那么呆板，总不能每次做完全一样的事情。 我们的怪兽 NPC 可以这一次向左走巡逻、下一次向右走巡逻。

随机选择节点也会考虑节点的优先级，即加权随机，也即是说，权重越大的子节点，会有更大的概率被选中。

而又因为它是一种 Selector 节点，所以会不断随机选择，直到遇到一个成功的子节点，否则最终失败。

比如下面的图中，要执行哪一个子节点是不一定的，只能说 B 被选择的概率最高。

此外，带状态的随机选择也是支持的，叫做 StatefulRandomSelector，这种情况下，已经测试失败的子节点就不会被重复考察。

黑板 ¶

行为树中要访问外部数据，比如说叫做 world，一般是采用黑板。

我觉得没必要把黑板封装成一个哈希表之类的东西，用一个简单的 struct 就足够了，又快又简单。 核心点在于，这个黑板的字段、业务话题、类别怎么设计，重点在其内容设计、具体的容器形式并不需讲究、越封装反而性能越差。

Tick() 函数支持一个上下文结构的参数，可以把外部数据的指针，比如说 blackboard 结构体的指针，放在 data 这里：

struct Context {
  ull seq;  // 当前全局的 tick 帧号
  std::chrono::nanoseconds delta;  // 全局的从上一次 tick 到本次 tick 的时间差
  std::any data; // 用户数据，比如可以存放一个指向黑板的指针
}

事件 ¶

我其实觉得，状态机更适合对事件做出反应，行为树则更偏向轮询的工作方式。所以行为树的性能比较浪费，它总要每次把可能的路径都询问一次。 有一种基于事件的行为树实现，不过我没有花太多功夫来理解这个「事件驱动」在正式的定义上是不是也是基于「轮询」的。

传统的行为树实现中，一切都起始于一个帧函数 Tick()，或者叫 Update()，那么如何把事件（信号）加进来呢？

为此，我单独实现了一个叫做 blinker.h 的信号库，它支持按信号名称组织成树，然后就可以按前缀匹配来订阅一批信号了。

把它用在行为树中，下图是一个示意，OnSignal 是一个自定义的装饰节点，表示只有所关心的信号激活时，才会向下传播 Tick。

我们已经可以把信号组织成树，那么，把所需关心的信号，尽可能地向上提，就可以优化行为树的 Tick 轮询过程、减少空询。 这其实有点像一种「事件监控」。

在代码中，可以这样使用：

root
  .OnSignal("a.*")      // 一旦这里没匹配到信号，就不会向下 tick 了
  ._().Selector()
  ._()._().Action<a>()
  ._()._().OnSignal("a.b.*")
  ._()._()._().Sequence()
  ._()._()._()._().Action<B>()
  ._()._()._()._().OnSignal("a.b.c")
  ._()._()._()._()._().Action<C>()
  ._()._().Action<D>()
.End()
;

未竞的性能优化… ¶

现在有几个事实：

1. 行为树在代码上是按照 dfs 顺序组织的
2. 我们的 Tick 是按照 dfs 顺序传播的
3. 每一帧我们都需要从树根开始执行 Tick

那么，很自然有个问题，是否可以让所有节点在内存上按 dfs 连续排布，以讨好 cpu cache ？ 在 《 Game AI Pro 1》 的行为树章节中，有提到这种性能优化的方法。 我兴冲冲地尝试实现了两次，就是简单地采用固定大小的连续内存的办法、但是压测都显示没有达到优化效果，所以算作一种「未竞的性能优化….」。

此外，关于「脚本」、「编辑器」，我都不怎么考虑，因为目前这个库就是给我这种（程序员）来用的，而程序员不怎么需要这些东西的支持，直接写在 C++ 程序中又快又轻巧~

最后，代码链接：https://github.com/hit9/bt.cc，欢迎给小星星。

（完）

本文原始链接地址： https://writings.sh/post/behavior-tree