用800行代码做个行为树(Behavior Tree)的库(1)


最近一直在忙新项目的准备,甚少涉及AI的东西,所以博客也疏于更新。春节前,收到一个网友的邮件,说看了行为树的一些东西,但还是不知道如何去入手实现,我就乘着春节假期,动手写了一个简单的行为树的库,和大家一起边分析代码,边说说行为树的具体实现方法。这个库很简单,一共也就800行的代码左右,不过麻雀虽小,五脏俱全,行为树中的主要部分基本都有涵盖,包括前提(Precondition),选择节点(Selector),并行节点(Parallel),序列节点(Sequence)等等。在分析代码前,如果有朋友对行为树的相关概念还不是很了解,建议先阅读本站上对于行为树介绍的相关文章。

这次的代码以及示例程序,还是基于我自己维护的一个框架TsiU,在系列文章的最后会给出下载链接。

行为树,由名字就可以看到,它是一个树结构,通过各个节点相互连接,所以我先定义了节点的基类:

 1: class BevNode{}

要把树链接起来,需要在这个类中保留父节点指针,和子节点指针,我用了一个固定的数组来保存子节点指针,它的大小是16,也就是说,一个节点最多可以有16个子节点

 1: class BevNode
 2: {
 3: protected:
 4:     BevNode*    mao_ChildNodeList[k_BLimited_MaxChildNodeCnt];
 5:     ...
 6:     BevNode*    mo_ParentNode;
 7: }

有了这些变量的定义,我们就可以串联起一颗树了。到目前为止,这个节点类还仅仅是一个树的节点,作为行为树的节点还差了些东西,在以前的介绍中,我们知道行为树的每一个节点都可以绑定一个称为前提(Precondition)的部分,用来作为是否进入这个节点的条件,在我的实现中,我把这个前提拆分成了两个部分,一个称为“内在前提”,一个称为“外在前提”。“内在前提”是和节点类静态绑定的(也就是说,这个节点的固有前提),而“外在前提”是可以和节点做动态绑定的。这样做的原因是,由于在行为树上,节点是可以被复用的,在不同的子树上他的进入条件往往是不同的。比如,“移动”,这是一个常见的行为节点,逃跑的时候,可能需要“移动”,追击的时候也需要“移动”,但进入这个节点需要不同的“外在前提”,所以这里就需要让节点支持动态绑定的前提。“内在前提”,我用继承的方式来实现,而“外在前提”,我用了另一个类来实现

 1: class BevNode
 2: {
 3: public:
 4:     bool Evaluate(const BevNodeInputParam& input)
 5:     {
 6:         return (mo_NodePrecondition == NULL || mo_NodePrecondition->ExternalCondition(input)) && _DoEvaluate(input);
 7:     }
 8: protected:
 9:     virtual bool _DoEvaluate(const BevNodeInputParam& input)
 10:     {
 11:         return true;
 12:     }
 13: protected:
 14:     BevNodePrecondition* mo_NodePrecondition;
 15: }

可以看到这里用到了一个叫做BevNodePrecondition的类,用来表示“外在前提”,他是一个纯虚函数,只有一个方法,先看一下它的定义,后面会有详细的讨论。

 1: class BevNodePrecondition
 2: {
 3: public:
 4:     virtual bool ExternalCondition(const BevNodeInputParam& input) const = 0;
 5: };

_DoEvaluate虚方法就是需要被子类继承并实现的“内在前提”,这两种前提在Evaluate方法中被结合了起来,用来检测进入条件,当返回True时,就表示当前节点可以被运行。返回False时,就表示当前节点进入条件不满足,不能被运行。

在节点基类的中,还有两个重要的方法是:

 1: class BevNode
 2: {
 3: public:
 4:     void Transition(const BevNodeInputParam& input)
 5:     {
 6:         _DoTransition(input);
 7:     }
 8:     BevRunningStatus Tick(const BevNodeInputParam& input, BevNodeOutputParam& output)
 9:     {
 10:         return _DoTick(input, output);
 11:     }
 12: }

转移(Transition)的概念是第一次出现,转移(Transition)指从上一个可运行的节点切换到另一个节点的行为。这个方法会被在节点切换的时候调用,比如,在一个带优先级的选择节点下有节点A,和节点B,节点A的优先级高于节点B,当前运行的节点是B,然后发现节点A可以运行了,但带优先级的选择节点就会选择去运行节点A,这时就会调用节点B的Transition方法,所以在这个方法中,一般可以用来做一些清理的工作。Tick方法就是通常的更新方法,就不多说了。

再来看一下这三个重要方法的参数,一共有两种类型的参数,BevNodeInputParam和BevNodeOutputParam,前者是传入参数,可以认为是行为树的输入,用const作为限定符,表示只读,后者是传出参数,可以认为是行为树的输出,可以修改。其实,从代码中可以看到,这两种类型的本质都是一样的,都是一个名为AnyData的类

 1: typedef AnyData BevNodeInputParam;
 2: typedef AnyData BevNodeOutputParam;

由于输入和输出参数是游戏相关的,所以这里用AnyData这个类来表示,这个类可以存放任意的数据结构,所以,这个类中真正的内容是需要玩家自己定义的。

最后来看看行为树是如何被定义和更新的(可以在示例程序中找到相关代码)

 1: //define input & output data
 2: struct BevInputData{...}
 3: struct BevOutputData{...}
 4: BevInputData    m_BevTreeInputData;
 5: BevOutputData   m_BevTreeOutputdata;
 6: ....
 7: //create tree
 8: m_BevTreeRoot = CreateTree();
 9: ...
 10: //update
 11: BevNodeInputParam input(&m_BevTreeInputData);
 12: BevNodeOutputParam output(&m_BevTreeOutputdata);
 13: if(m_BevTreeRoot->Evaluate(input))
 14: {
 15:     m_BevTreeRoot->Tick(input, output);
 16: }
  1. 定义自己的输入和输出参数(BevInputData,BevOutputData)
  2. 创建行为树,保存根节点指针(m_BevTreeRoot)
  3. 测试是否有可以运行的节点,如有则更新

(待续…)

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



(已被阅读15,612次)

18 评论

  1. 博主好! 关于你的行为树库,我有以下几个疑惑的地方想请教下你:

    首先汇报代码中的一处小bug,在循环节点的tick方法中,”if(mi_CurrentCount == mi_LoopCount)”这里的”==”应该改成”<"。

    下面是我的几个疑问

    1:节点中的"lastActiveNode"成员变量有什么特殊意义吗?我的理解是:它只是为了调试时(比如输出节点名)可以过滤掉一些无关紧要的行为(比如"呼吸")。如果只是这个作用的话,那么去掉这个成员变量,在那些"无关紧要"的行为节点中重写"setActiveNode"方法(什么都不做)是否更好?这样的话整个树中就只有一个全局的"当前活动节点"是否更清晰?

    2:关于"k_BRS_ERROR_Transition"返回值,我的理解是:它是当前节点主动请求转移的方式(假设被动转移的情况是选择节点调用子节点的"Transition"方法),当序列节点捕获到这个请求后就会将当前索引重置到0。问题:我的理解正确吗?还有,合理的情况下当一个行为节点抛出这个请求后,它的父节点应不应该继续往上抛?我看了你的实现是:选择抛、并行不抛、序列抛、循环不抛,我不太理解为什么要这么做?我认为这样可能会导致混乱,比如一个序列节点A的父节点是一个选择节点B,子节点是一个叶节点C,节点B的父节点是一个序列节点D,一旦节点C返回"k_BRS_ERROR_Transition",那么节点A和节点D都会将当前子节点索引重置。
    同样的,假设将这棵树中的节点B换成并行节点,那么当C返回转移请求时,只有A节点会将索引重置,因为节点B换成了并行节点就不会继续将请求往上抛,所以这时的D节点不会做重置处理….
    换了一个B节点就会直接影响到D节点,我不知道这么做是否有什么特殊意义?如果确实不太合理的话又应该如何重新设计这个返回值呢?

    3:在实际开发中,能否直接将智能体和树绑定在一起?比如在input和output中就直接包含了智能体自身的引用,然后在叶节点中直接对智能体进行操作处理,拿你的那3个例子来说,我也试着做了一个一样的demo,但我没有用黑板(我不太了解这种方式),而是直接像我上面说的那样来处理,我发现当我那样做时逻辑更清晰代码沉余也少,不知道在什么情况下才能体现出用你的那种做法的好处?

    4:我发现同样的最终输出,可以通过N种不同的节点组合方式来实现,不过在不同的组合方式下,叶节点可能需要做一些细小的改变才行。这就有了一个问题:是先组合节点还是先实现节点?我感觉到每个叶节点的实现都会或多或少依赖最终的节点组合方式,假设是先设计树的每个节点的组合方式,然后根据这个树结构实现了每一个叶节点和需要用到的外部前提,这时,发现这个树结构不合理,需要交换或者改变某些节点在树结构中的位置,这时可能就会需要修改叶节点的代码或者外部前提的外码了,节点的实现和树的结构的耦合很高。有什么办法可以降低耦合吗?或者是我的做法不对?

    以上这4个问题比较让我困惑,希望博主能替我解答,非常感谢!!!

    1. 谢谢来信,我又仔细的看了一遍我的代码(很长时间没看了),这个代码是我从上个项目里提炼出来的,为了配合博客的文章,称不上一个库,只是一个范例。Loop那个节点我在项目里写好后后来没有用到,所以一直没发现这个bug,万分感谢。

      1. activenode就是用来debug用的,用来打印出当前运行的节点,可以不在每个节点存,而是全局保存一个,这样确实更好
      2. 当时是为了在BevNodeTerminal::_DoExit里传入一个exit的标记,因为在实践中发现,有时需要通过这个exit标记来做一些不同的逻辑,在我实际项目中有更多的error返回值,k_BRS_ERROR_Transition是其中的一种,这个标记表示这个不是叶节点自己结束的(就是自己返回finish),而是被父节点的逻辑切换的
      3. 对的,直接把智能体的指针放在里面作为变量传入就行了,我在博客里的行为树例子中就是这样做的,定义inputparam和outputparam是希望行为树的工作仅仅依赖于输入,产生输出。
      4. 叶节点的设计目标是希望不依赖于它在行为树中的结构,每个叶节点的实现和行为其实与也应该仅与2个“变量”相关,输入(input),输出(output),某种程度上来说,它不应该关心前提,因为前提(Precondition)的组织和设计是和树的结构相关。所以定义了一个外部前提的概念,他不属于节点实现的一部分,而是和节点“装配”的,因为这个是和行为树的结构相关的。我在项目中,发现节点和树的结构没有什么耦合度,不知道你碰到的情况是什么问题,你可以检查你的叶节点实现,是不是仅仅考虑输入和输出(就和函数的概念很像)。
      我一般设计行为树,是先列出智能体有多少的行为要做,然后开始设计结构和前提,然后把行为树搭起来,再一个个实现叶节点,可以分给多个人去做,因为实现叶节点的人,其实只要知道这个节点做什么就可以了,通过输入,产生输出

      欢迎继续讨论

  2. hi,Finney 非常感谢你慷慨的分享!我正在为我的独立FLASH游戏寻找合适的AI架构,本来打算用状态机,不过现在我改变主意了,综合评价,行为树确实在逻辑清晰和大规模状态控制下更胜一筹。 谢谢你提供了这么棒的一个库!它应该能很好的为我的游戏服务:)

    1. 嗯,行为树其实挺简单的,很容易做,如果你是flash游戏的,我有一个同事,把我写的行为树的C++代码改成了AS的,并且他开源了,你可以参考一下,https://github.com/hbbalfred/guardians/tree/master/src/engine/bevtree

    2. 嗯,谢谢!我自己也已经将你的C++版本改写成as3版本了,还做了一些小改动:)
      不过我也发现了一些问题,后续我会将问题整理下发上来,希望你能帮助我消除一些我的疑问!
      另外我想问一下博主,这个行为树的库,你在实际项目中有用过吗?

  3. Finney :tick的返回值主要是用来通知外部,行为树当前的运行状态,因为很多情况是,一个行为节点内容在一帧里是没有办法做完的,需要多帧去做,这样tick的返回值就会返回“还在运行”,或者“已经完成”,还可以返回一些错误。至于是否要关心行为树的状态,这个是需要看外部的逻辑的,你也可以完全忽略这个返回值。

    谢谢解答

  4. Finney :可以这样说,A和B都有一个运行的条件,A是a>5的时候运行,B是a>1的时候运行,第一帧的时候a=3,这时检查A的条件,发现不满足,然后检查B的条件发现满足了,那这一帧就运行B(由于是带优先级的选择节点,所以每次都是先检查A,再检查B),然后在第二帧的时候,a=6,这时检查A的条件,发现满足了,所以这一帧就运行A,因为上一次是运行的B,所以会调用B的Transition方法做一些清理的工作。这就是优先级的意义,A的优先级永远比B高

    谢谢解释 我还有一个问题
    tick的返回值 运行状态 有什么用?

    1. tick的返回值主要是用来通知外部,行为树当前的运行状态,因为很多情况是,一个行为节点内容在一帧里是没有办法做完的,需要多帧去做,这样tick的返回值就会返回“还在运行”,或者“已经完成”,还可以返回一些错误。至于是否要关心行为树的状态,这个是需要看外部的逻辑的,你也可以完全忽略这个返回值。

  5. 比如,在一个带优先级的选择节点下有节点A,和节点B,节点A的优先级高于节点B,当前运行的节点是B,然后发现节点A可以运行了,但带优先级的选择节点就会选择去运行节点A,这时就会调用节点B的Transition方法

    —————-
    请问 ‘然后发现’ 这个应该怎么理解 是下一次tick么? 那又为什么是 ‘当前运行的节点是b’

    求教

    1. 可以这样说,A和B都有一个运行的条件,A是a>5的时候运行,B是a>1的时候运行,第一帧的时候a=3,这时检查A的条件,发现不满足,然后检查B的条件发现满足了,那这一帧就运行B(由于是带优先级的选择节点,所以每次都是先检查A,再检查B),然后在第二帧的时候,a=6,这时检查A的条件,发现满足了,所以这一帧就运行A,因为上一次是运行的B,所以会调用B的Transition方法做一些清理的工作。这就是优先级的意义,A的优先级永远比B高

  6. 想问个问题,对于Parallel Node,应该理解成每个子节点都执行一遍;那么对于我想实现同时作几件事情,比如同时刮风、下雨,感觉这个类型的节点并不合适,因为我觉得不是间隔执行刮风、下雨两个动作就可以的。这种情况我认为更需要一个新的刮风下雨的action node或者让Parallel Node可以实现多线程同步。但是这样就破坏了算法整体的设定了。请问有什么好办法么?

    1. 我的理解其实是怎么来定义“同时”这样一个概念,在单线程的逻辑里,游戏是以帧为单位更新的,画面也是以帧为单位来呈现的,所以可以认为在一帧里做的事情,都是“同时”的。你说的和我想的一样,我也觉得行为树的多线程不是很可行,而且没什么必要。

  7. 请问有没有考虑过把行为树再进一步抽象,分离成树的逻辑判断以及数的节点数据,因为我看到过一张图,感觉很这个树结构很适合用xml格式存储。如果能实现的话,就相当于一个小型的AI引擎了,每个AI对象都由一个xml表来定义,其中每个节点的前提和行动另行存储。

    1. 嗯,行为树很适合用配置文件来配置,我们用过lua来作为AI的配置文件,lua较之xml的优势是,可以包含一定的逻辑。我一直很想做一个行为树的编辑器和调试器,把AI数据化,不过一直没时间做,有兴趣,可以一起讨论。

发表评论

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

Copyright © 2011-2017 AI分享站    登录