行为树(Behavior Tree)实践(1)– 基本概念


自从开博以来,每天都会关心一下博客的访问情况,看到一些朋友的订阅或者访问,不胜欣喜,也促使我去写一些更好的博文,来和大家分享和交流,从访问统计来看,有相当一部分是来自于搜索引擎的流量,关键字以“行为树”,或者“Behavior Tree”居首位,我想大家对此可能有些兴趣,加上,这几年反反复复一直在AI中研究和运用行为树,所以这次就来谈谈关于行为树(Behavior Tree)的一些东西,以前也写过一些文章(123)来讨论行为树,不过已经是一两年前的事情了,较之以前,这次会更为系统,也会添加一些我新的思考和感悟。所谓行为树实践,其实在我脑海里就是Practice in Behavior Tree,没法子,受英文教材影响太多了:)

我想通过一个例子来介绍一下行为树的基本概念,会比较容易理解,看下图:

bv-tree-1

这是我们为一个士兵定义的一颗行为树(可以先不管这些绿圈和红圈是干吗的),首先,可以看到这是一个树形结构的图,有根节点,有分支,而且子节点个数可以任意,然后有三个分支,分别是巡逻(Patrol),攻击(Attack),逃跑(Retreat),这个三个分支可以看成是我们为这个士兵定义的三个大的行为(Behavior),当然,如果有更多的行为,我们可以继续在根节点中添加新的分支。当我们要决策当前这个士兵要做什么样的行为的时候,我们就会自顶向下的,通过一些条件来搜索这颗树,最终确定需要做的行为(叶节点),并且执行它,这就是行为树的基本原理。

值得注意的是,我们标识的三大行为其实并不是真正的决策的结果,它只是一个类型,来帮助我们了解这个分支的一些行为是属于这类的,真正的行为树的行为都是在叶节点上,一般称之为行为节点(Action Node),如下图红圈表示的

bv-tree-action-node

这些叶节点才是我们真正通过行为树决策出来的结果,如果用我以前提到的那个层次化的AI结构来描述的话,这些行为结果,相当于就是一个个定义好的“请求”(Request),比如移动(Move),无所事事(Idle),射击(Shoot)等等。所以行为树是一种决策树,来帮助我们搜寻到我们想要的某个行为。

行为节点是游戏相关的,因不同的游戏,我们需要定义不同的行为节点,但对于某个游戏来说,在行为树上行为节点是可以复用的,比如移动,在巡逻的分支上,需要用到,在逃跑分支上,也会用到,这种情况下,我们就可以复用这个节点。行为节点一般分为两种运行状态:

  1. 运行中(Executing):该行为还在处理中
  2. 完成(Completed):该行为处理完成,成功或者失败

除了行为节点,其余一般称之为控制节点(Control Node),用树的“学名”的话,就是那些父节点,如下图绿圈表示

bv-tree-control-node

控制节点其实是行为树的精髓所在,我们要搜索一个行为,如何搜索?其实就是通过这些控制节点来定义的,从控制节点上,我们就可以看出整个行为树的逻辑走向,所以,行为树的特点之一就是其逻辑的可见性。

我们可以为行为树定义各种各样的控制节点(这也是行为树有意思的地方之一),一般来说,常用的控制节点有以下三种

  1. 选择(Selector):选择其子节点的某一个执行
  2. 序列(Sequence):将其所有子节点依次执行,也就是说当前一个返回“完成”状态后,再运行先一个子节点
  3. 并行(Parallel):将其所有子节点都运行一遍

用图来表示的话,就是这样,依次为选择,序列和并行

bv-tree-sel

bv-tree-seq

bv-tree-pal

可以看到,控制节点其实就是“控制”其子节点(子节点可以是叶节点,也可以是控制节点,所谓“执行控制节点”,就是执行其定义的控制逻辑)如何被执行,所以,我们可以扩展出很多其他的控制节点,比如循环(Loop)等,与行为节点不同的是,控制节点是与游戏无关的,因为他只负责行为树逻辑的控制,而不牵涉到任何的游戏代码。如果是作为一个行为树的库的话,其中就一定会包含定义好的控制节点库。

如果我们继续考察选择节点,会产生一个问题,如何从子节点中选择呢?选择的依据是什么呢?这里就要引入另一个概念,一般称之为前提(Precondition),每一个节点,不管是行为节点还是控制节点,都会包含一个前提的部分,如下图

bv-tree-precondition

前提就提供了“选择”的依据,它包含了进入,或者说选择这个节点的条件,当我们用到选择节点的时候,它就是去依次测试每一个子节点的前提,如果满足,则选择此节点。由于我们最终返回的是某个行为节点(叶节点),所以,当前行为的“总”前提就可以看成是:

当前行为节点的前提 And 父节点的前提 And 父节点的父节点的前提 And….And 根节点的前提(一般是不设,直接返回True)

行为树就是通过行为节点,控制节点,以及每个节点上的前提,把整个AI的决策逻辑描述了出来,对于每次的Tick,可以用如下的流程来描述:

action = root.FindNextAction(input);
if action is not empty then
action.Execute(request,  input)  //request是输出的请求
else
print “no action is available”

从概念上来说,行为树还是比较简单的,但对AI程序员来说,却是充满了吸引力,它的一些特性,比如可视化的决策逻辑,可复用的控制节点,逻辑和实现的低耦合等,较之传统的状态机,都是可以大大帮助我们迅速而便捷的组织我们的行为决策。希望这次简单的介绍,对大家有所帮助,能力有限,不一定能表述的很清楚,有问题,或者有指教的,都请和我多多交流,最后,我对这个士兵的巡逻分支画了一个示意图,供大家参考:

S — 选择节点   Se — 序列节点

bv-tree-patrol-example

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————



(已被阅读50,766次)

37 评论

  1. 楼主 再次请教一个问题 如一个战士 当前是待机状态 当我点击键盘A键的时候 他会攻击。在FMS中 只需要关注当前的状态是否关注这个输入,是否会被这个输入影响改变成其他状态(待机–>>攻击)。在行为树 按照每次都从root节点开始遍历节点条件 来得到是否可以执行子节点。那每个子节点的条件里面 考虑的条件是否会变很多。如: 战士当前是否在空中 战士是否死亡等等。可能我对行为树没有理解清楚。

    1. 你可以这样想,在状态机里需要判断的条件->跳转,基本都可以变成一个“与”关系的条件组合,而这个条件组合可以看成是行为树中进入到这个行为的条件,当然,这个只是从状态机到行为树概念上的转变,行为树主要是为了解决状态机爆炸(状态太多,跳转复杂),还有复合的复杂行为的解决方案(比如用序列节点),还有就是节点的复用性(比如Attack这个节点可以用在不同的行为分支中),建议你可以先用一个行为树的工具(比如unity里的Behavior Designer)用用看,体会一下

  2. 楼主我想问一下 FMS中不同状态下需要用到的特定的数据 都直接保存在 state中 那么行为树 中 不同的分支节点所要用到的 特定数据 就只能全部存在其他地方吗?

  3. 感觉ai上用行为树比状态机是好多了,接下来打算用。
    问个不大相关的问题,不知道对于主角操作控制,能否建议下怎么实现好呢?现在用状态机实现,不知道还有没有其他更好的方法

  4. 您好,一口气看了您好多篇AI的文章,写的非常好,深入浅出。
    我正在开发一个小游戏,人物AI最初使用的FSM来快速实现,现在不断加入新的角色状态,FSM的弊端越来明显。现在想使用行为树来重构AI系统,有个问题想请教一下。

    如果人物在行走过程中,被攻击了,需要播放攻击动画,假如说是0.5s,随后需要继续行走。 状态机只需要保存前一个状态就好,用行为树可以怎么实现呢?人物A*获取的路点存放在哪里比较好?MoveAction中么?

    1. 对于这个行为,行为树可以这样做

      做一个节点A是“被攻击”,前提是“是否被攻击”,然后再做一个节点B是“移动”,前提可以永远为真,然后把这两个节点作为带优先级选择节点的子节点,保证A在B的前面,也就是说A在B的左边

      这样的行为树就可以满足你的这个逻辑

      路点怎么存问题不大,存在人身上,或者存在某个全局信息里,都可以,只要行为树能访问到就行

      如果你的重构一个FSM系统,我建议完全抛弃原有的基于FSM的思路,用行为树的思路来考虑,然后重构,而不是说,还是用FSM的思路,再改成行为树,因为这两种的思路是不同的,FSM重点在状态切换,行为树重点在于前提,行为和行为控制的组合。

      感谢对于博客的关注,欢迎随时留言讨论

  5. 我想问下,行为节点会重复不?假设我有个开枪的行为节点,然后有 跑,走,蹲,跳,这四个选择节点,然后我可以在上诉四个状态下开枪,大改是怎么协调?把 开枪提到和上诉四个状态的选择节点同级别,共同归于一个loop下面么?

  6. 您好,想问下 如果某个动作 比如施法吟唱 吟唱过程中需要进行对目标判定 比如目标距离太远之类的 这类是术语动作内包含的 还是行为树中的 再比如一个需要持续施法的法术 过程中也要对目标判定之类的 这个用行为树怎么表示 再就是当外部改变时 比如某人打断了我的施法 这个 过程中 行为树 还是从头遍历嘛? 发现改变才做调整?

    1. 实现方法不唯一,要看具体需求,吟唱的合法性判定,可以做在precondition里,因为行为树每帧都会检查precondition,不合法的自然就跳出了,目标判定可以做在节点里,也可以外部算好传给行为树,外部改变属于我提到的被动请求或者外部事件,可以考虑用黑板接收后,传给行为树处理

  7. 楼主您好,我是新入行的游戏程序员,在公司做AI方面,自己业务时间做了一个简单的AI编辑器,可配置节点。
    但是现在有一个问题没想清楚,就是事件节点在行为树中怎么实现?例如定时器事件或者周围触发的事件之类的。
    我想只用行为树去控制AI,这样只有一个控制源了,但是没想清楚在行为树中怎么实现事件?

    1. 事件我都是用外部黑板来实现的,由外部黑板接受事件,更新黑板状态,而不是行为树直接接受事件,行为树只是根据黑板状态来执行

    2. 那么这样是不是只有等到下一次遍历行为树的时候,才能执行事件触发的那个行为?而不是某个事件一触发,马上执行某个行为?

    1. 如果按照种类来建行为树,内存几乎可以忽略不计,如果你说的是每个实例的话,可以用共享节点型的行为树,看这里http://www.aisharing.com/archives/563和这里http://www.aisharing.com/archives/572

  8. 又看了一遍,略微懂了,但是请问Tick是什么意思,还有实例代码中的input指什么?
    实例代码是每帧都执行,还是事件驱动执行?

  9. 请问 行为树 和 层次状态机 有什么区别啊。
    我了解过层次状态机,看这个文章觉得跟行为树没什么区别呀?

    1. 这个要说起来就多了,简单的说吧,行为树是树状结构,绝对没有“回路”,而状态机是图状的结构,就是有时会形成一个“回路”,而且,行为树的决策方式是自顶向下的,状态机是在每一个状态内部做决策的

    2. 对于每一帧的Update()函数来说:
      状态机,只需currentState.Update(),在其中遍历当前状态的所有Transition(转换条件)即可。
      而行为树,却需要从根部节点按照遍历规则,从头开始遍历。(比如说从最左边的节点开始)
      这样以来,是不是每一次Update,BT都要“统揽全树”,而FSM只需要“关心自己”,BT所做的事情就要比FSM多?效率会降低吗?

      另外,今天看了一片英文文章,文章说,BT和FSM的区别在于,相对于FSM,BT把“转换条件”从“状态”中剥离出来,也就是说,FSM中的“状态”,在BT中演化成了“转换条件”+“行为”?

    3. 由于只是对转换条件的判断,所以效率并不低,而且从本质上来说,你在状态机中也是需要判断所有可能的转换条件的,顺便说一句,这篇文章对于区别说的比我好,呵呵

发表评论

电子邮件地址不会被公开。

Copyright © 2011-2017 AI分享站    登录