第一次听说行为树还是在2011年珠三角技术沙龙上Akara的分享, 这里也有个不错的视频系列. 可惜此后一直未有机会实践. 这两天趁着假期用C写了实现(github repo). 顺便填填博客的坑.

背景

在游戏AI中, 常见的实现有决策树、状态机等, 它们各自存在着不足. 以状态机FSM为例, 它非常难以通用和扩展, 状态转化的复杂度随着每个新增状态将变得越发缭乱. 考虑到可能存在多个并行的状态机, 它们之间的交互更是复杂交错, 难解难分. 于是大神们创造了行为树(BehaviourTree),

行为树

(这张高大上的图片来自这里)

显而易见, 行为树作为一棵树, 必然有中间节点和叶子节点, 它们分别负责选择节点和执行AI逻辑. 在游戏中, 一般是每帧或者核心状态变化时执行行为树的Update(或称Tick)接口, 该接口从树根开始通过中间节点进行判断, 以此搜索到叶子节点.

叶子节点

叶子节点通常执行具体的动作, 一般需要提供以下回调:

• enter: 进入叶子节点, 一般用于初始化状态, 分配内存等

• excute/tick: 执行具体的AI逻辑

• exit: 退出叶子节点, 一般用于清理状态, 回收内存等

其中, excute/tick的执行结果分为完成和执行中两种运行状态. 行为树每次执行时, 可以从树根开始重新搜索, 也可以记忆最后一个返回执行中的子节点, 从该节点开始执行, 两种方式各有利弊.

中间节点

中间节点通常作为选择节点, 负责确认子节点中的执行顺序, 可以泛泛的分为以下几种:

• 顺序(sequence): 自左往右顺序执行子节点

• 随机(random): 随机执行一个子节点

• 优先(priority): 自左往右顺序执行子节点直到其中一个返回成功

黑板

考虑到节点之间或者行为树之间的输入输出, 引入了 黑板(blackboard) 的概念, 分为几种:

• global: 所有行为树共享

• per-tree: 一棵行为树的黑板, 该树的所有节点共享

• per-node: 单个节点的黑板, 主要用于节点

实现

来自育碧的finney用800行C++代码做了实现. 于我而言, 其封装层次过深, 略显臃肿(当然逻辑还是很清晰的), 且OO为个人不太喜欢的继承, 因此花了一天多的时间, 以组合的形式来面向对象,用400行代码完成了一份C的实现. 考虑到其中不少工作是在维护虚函数表, 如果换成C++实现, 相信200行代码足以, XD.

这里简单描述下API:

30 void *node_create(struct node_callbacks *cbs, void *blackboard); 创建一个子节点, cbs为回调集合. blackboard为按需初始化的per-node黑板, 当然你也可以在node的enter回调中设置.

33 void *branch_create(int type, int num, void **nodes); 创建中间节点, type表示执行类型(sequence, priority, random), nodes表示其子节点列表

34 void *behaviourtree_create(void *branch); 创建一棵行为树, branch表示树根的选择节点.

36 void behaviourtree_tick(void *bt, void *object); 执行行为树, object表示行为树的上下文, 一般可以用于为行为树绑定一个对象object.

在子节点node_callbacks的tick回调中, 需要明确告诉行为树自己的执行结果, 方式为回调函数类型的最后一个参数node_operations, 分为完成success, 失败fail, 运行中running.

具体使用可以参考example1和example2.

TODO

从example中可以看到, 行为树的构造是比较形式化的. 大厂一般会有自己一套编辑器可视化的编辑行为树,  生成其结构的描述数据. 这里有一个网页版的GUI, 生成的行为树结构为json格式, 以后需要的花可以编写代码解析其格式来自动构造行为树(大坑, 逃~).

建议继续学习：

1. 树与存储    (阅读：2354)
2. Trie树（字典树） 最热门的前N个搜索关键词    (阅读：1800)
3. B-树    (阅读：1143)