行为树及其实现
第一次听说行为树还是在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格式, 以后需要的花可以编写代码解析其格式来自动构造行为树(大坑, 逃~).
建议继续学习:
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:ripwu 来源: godorz...
- 标签: 树 行为树
- 发布时间:2015-10-04 23:07:00
- [65] Oracle MTS模式下 进程地址与会话信
- [64] Go Reflect 性能
- [64] 如何拿下简短的域名
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [58] 【社会化设计】自我(self)部分――欢迎区
- [58] 图书馆的世界纪录
- [56] android 开发入门
- [53] 视觉调整-设计师 vs. 逻辑
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [45] 界面设计速成