行为树(Behavior Tree)实践(2)– 进一步的讨论

2011年8月1日 | 分类: AI分享 | 标签: , , , , , , , ,
(24 票,评分 5.00)
Loading...

上次提到了一些行为树的基本概念,包括行为节点,控制节点(选择,序列,并行),这次来更多,更深入的讨论行为树的一些东西,如果对行为树不是很了解,请参看这里

一. 关于选择节点的讨论

我们说过选择节点的定义是通过判断子节点的前提条件来选择一个节点执行,这就牵涉到判断顺序的问题,是自左向右,还是随机选择,或者其他的一些规则等等,这样就延伸出各种各样的选择节点。

 

 

  • 带优先级的选择节点(Priority Selector):这种选择节点每次都是自左向右依次选择,当发现找到一个可执行的子节点后就停止搜索后续子节点。这样的选择方式,就存在一个优先级的问题,也就是说最左边的节点优先级最高,因为它是被最先判断的。对于这种选择节点来说,它的子节点的前提设定,必须是“从窄到宽”的方式,否则后续节点都会发生“饿死”的情况,也就是说永远不会被执行到,为了更清楚的说明,看下面第一张图,这三个子节点在一个带优先级的选择节点下,它们的前提会被依次判断,可以看到这个三个子节点的前提从左向右,一个比一个更严格,如果我们现在a为9,按照下图的定义会执行第一个子节点,如果a为7,则会执行第二个子节点,如果a=11,则会执行第三个子节点。下面的第二张图演示了一种节点“饿死”(Starvation)的情况,我们看到第一个子节点的前提,比第二个子节点更宽泛,只要a<10,那自左向右判断的话,永远会进第一个节点,所以,如果要用到带优先级的选择节点,则必须检查每一个子节点的前提,以防止节点饿死的情况.

 

bv-tree-priority-selector-1

bv-tree-priority-selector-2

  • 不带优先级的选择节点(Non-priority Selector):这种选择节点的选择顺序是从上一个执行过的子节点开始选择,如果前提满足,则继续执行此节点,如果条件不满足,则从此节点开始,依次判断每一个子节点的前提,当找到一个满足条件的子节点后,则执行该节点。这种方式,是基于一种称之为“持续性”的假设,因为在游戏中,一个行为一般不会在一帧里结束,而是会持续一段时间,所以有时为了优化的目的,我们可以优先判断上一个执行的节点,当其条件不满足时,再寻找下一个可执行的节点。这种寻找方式不存在哪个节点优先判断的问题,所以对于前提的设置的要求,就是要保证“互斥”(Exclusion)。如果我们用上面第一张图来说明,如果我们把控制节点换成不带优先级的选择节点,可以看到,当a=3时,第二个子节点会被执行,下一次当a变成9时,由于不是从头依次判断前提的,所以,我们还是会选择第二个节点,而不是我们可能期望的第一个节点。正确的做法见下图,注意每一个子节点的前提是“互斥的”。所以对于不带优先级的选择节点,它子节点的排列顺序就不是那么重要了,可以任意排列。

bv-tree-nonpriority-selector-1

  • 带权值的选择节点(Weighted Selector):对于这种选择节点,我们会预先为每一个分支标注一个“权值”(Weight Value),然后当我们选择的时候,采用随机选择的方式来选,随机时会参考权值,并且保证已经被测试过的节点的不会再被测试,直到有一个节点的前提被满足,或者测试完所有的节点。带权值的选择节点对于子节点前提由于随机的存在,所以子节点的前提可以任意,而不会发生“饿死”的情况,一般来说,我们通常会把所以子节点的前提设为相同,以更好的表现出权值带来的概率上的效果。当所有子节点的权值一样时,这种选择节点就成为了随机选择节点(Random Selector)带权值的选择节点对于需要丰富AI行为的地方,非常适用,比如养成类游戏中,小狗表示开心的时候,可能会有各种各样的表现,我们就可以用这种选择节点,添加各种子节点行为来实现。

bv-tree-weighted-selector-1

这些就是常用的选择节点类型,我们可以根据需要,定义更多的选择节点的选择行为,其实我们可以看到,不同的选择行为对于子节点前提的要求会有略微的不同,这是在我们搭建行为树的时候需要注意的地方。

二. 关于并行节点结束条件的讨论

我们每个节点都会有一个运行状态,来表示当前行为是否结束。对于控制节点来说,它的运行状态就是其子节点的运行状态,选择节点和序列节点比较好处理,因为对于这两种控制节点来说,每时刻,只会有一个子节点在运行,只要返回在运行的这个子节点的状态即可。但对于并行节点来说,它同时刻会有多个子节点运行,那我们如何来处理并行节点的运行状态问题呢?一般有两种:

  • 与:只有所有的子节点都运行结束,才返回结束。
  • 或:只要有一个子节点运行结束,就返回结束。

为什么要需要有节点的运行状态呢?

  • 序列控制节点中,需要用运行状态来控制序列的执行
  • 外部世界需要了解行为的运行状态,来决定是否要更新决策(如果行为树在决策层)/请求(如果行为树在行为层),关于AI分层,请参考这里

对于第二点,可以举个例子,比如我们有一个行为是“走到A点”,假设这个行为是不可被打断的,那当我们在走向A点的过程中,行为树的运行状态就是“正在执行”,当到达A点时,行为树就返回“已完成”,这样,对外部来说,当我们看到行为树是“正在执行”的时候,我们就不需要做任何新的行为(为了优化,或者为了行为抖动等等),当看到“已完成”的时候,我们就可以做新的决策或者行为了。这样一个运行状态还有助于我们检测行为树的状态,帮助调试。

三.关于具体实现的讨论

行为树的实现可以有多种多样,我这边提出一些建议,一般来说,行为树每个节点需要有进入(Enter),离开(Exit),运行(Execute)等部分,需要有行为节点(ActionNode),控制节点(ControlNode),前提(Precondition)等基类,然后,还需要定义行为树的输入(InputParam)和输出(OutputParam),一般来说,我们希望行为树是一个黑盒,也就是说,它仅依赖于预定义的输入。输入可以是黑板(Blackboard),工作池(Working Memory)等等数据结构,输出可以是请求(Request),或者其他自定义的数据结构,如下图:

bv-tree-arch

代码的话,就不写了,因为blog没有代码插件,写代码效果不是很好,以后我会在TsiU里面发布一个行为树的库的版本。

四.关于绘制和调试的讨论

看到行为树的定义后,作为程序员的直觉,我们很自然的就会想到,这好像应该能做一个工具来辅助行为树的创建和调试,我们可以把预定义好的前提和节点,在一个可视化的编辑器里搭建成行为树,然后再导出成数据给游戏用。对于调试来说,我们可以让工具和游戏通信,然后实时的检测行为树的运行状况,比如当前在哪个分支中等等。由于行为树的逻辑是可见的,并且是静态的,所以我们看其选择的路径,我们就可以知道AI为什么会作出这样的决策了。当我刚接触到行为树的时候,就在想做这样一个编辑器,但迫于项目压力,一直没有时间做(工作量还是挺大的),有兴趣,有时间的朋友,可以考虑做一个。顺便说一句,我现在对于行为树的搭建都是在代码中完成的,虽然没有数据驱动那么“先进”,但通过宏定义,排版等方式,还是能非常清晰的表示树的整体结构。

关于行为树,我想这个系列就到这里了。在使用行为树的过程中,可能还会碰到这样和那样的问题,包括我自己在实践中的一些经验,我想就先不包括在这个系列里了,以后再单独拿出来聊,这个系列作为行为树的入门,希望对大家有所帮助,欢迎指教和讨论。

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



发表评论 | Trackback | 已被阅读10,674次
  1. ShionRyuu
    2014年9月26日16:00

    几个问题:
    1、BevNodeNonePrioritySelector代码和上面说的“如果条件不满足,则从此节点开始”不一样,而是直接从第一个节点开始测试。
    2、BevNodeParallel的mab_ChildNodeStatus没有什么作用,每个动作最后都是全部重置mab_ChildNodeStatus。
    3、判断条件满足后为什么不是立即执行?这样有什么考虑?
    4、要不要考虑把svn迁到Github上面,这样比较容易访问。

  2. Helay
    2014年8月19日10:53

    博主你好,从您的一系列文章中学到了很多知识,
    我正在学习使用行为树来实现游戏中的AI,
    有一点疑问请教博主,行为树每一次tick都是从root开始抉择吗?当一个控制节点执行完毕以后,下一次抉择是应当从root开始吗?

    • 2014年8月22日10:14

      是的,每一次都是从root开始,因为有precondition的原因,遍历速度很快

      • ash
        2014年12月27日16:10

        您所说的precondition,是不是其它文章里所说的条件节点(condition)?

  3. krish
    2014年3月28日10:08

    我疑惑一些问题,既然选择节点为带优先级的选择节点,也就是本来就是从左到右的,左边的优先级会高,执行的时候也是按照这个顺序执行, 而不是 不带优先级(互斥)的选择节点,或者带权重(几率)的选择节点, 那怎么会有存在节点转移的事件呢,也就是说只要我正在执行的节点,肯定已经从优先级高的(左边)执行过来的, 也就是说,不会存在优先级高的排在右边的情况。求解惑。。。

    • 2014年3月28日10:13

      因为虽然它优先级高,但他的前提条件可能不满足,也就是说他不会被执行。节点执行的一定要满足前提条件。比如有A,B两个节点,A的优先级比B高,A的前提条件是s>0 and s <1,B的前提是s>-5 and s < 5,假设现在s=3,根据带优先级的选择节点的定义,他会从A开始检查,发现不满足,然后检查B,发现满足了,那就执行B了,下一次当s=0.5,这个时候A满足了,所以就执行A了,这样的话,就发生从执行B到执行A的节点转移了

  4. 2013年7月22日18:56

    I constantly spent my half an hour to read this blog’s articles or reviews everyday along with a cup of coffee.

  5. Heya i am for the primary time here. I came across this board and I find It truly helpful & it helped me out a lot. I hope to present something back and help others such as you helped me.

  6. 小N_大进行曲
    2011年11月26日00:26

    带优先级的选择节点 和 不带优先级的选择节点 这两种。
    只要他们的子节点的条件都做到互斥,是否带优先级,是不是也就不重要了?
    因为子节点条件互斥了,同一时刻只可能有一种条件满足,顺序也就无所谓了吧?

    • 2011年11月26日12:18

      完全正确~

      • ash
        2014年12月27日16:34

        应该是有所区别的,

        除非判断条件在该选择节点完全执行完前将不发生改变 或者 执行的内容在一次循环内便可执行完毕,他所说的结论才能完全成立。

        我想不带优先级的选择节点重点在于它具有记忆性,即 在Non-priority Selector节点的子执行节点,若处于running状态下,则进入该选择节点后将直接跳入该执行节点,而不是从该选择节点的第一个节点重新走一遍。

        • 2015年1月2日12:54

          对的,但一般不建议在判断条件的时候改变所收集的游戏世界的信息,推荐的流程是:收集信息,判断条件,跑行为,改变世界

  7. Finney
    2011年8月3日09:10

    新空间评论测试,欢迎大家访问

无觅相关文章插件,快速提升流量