最近一直在忙新项目的准备，甚少涉及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: }
- 定义自己的输入和输出参数（BevInputData，BevOutputData）
- 创建行为树，保存根节点指针（m_BevTreeRoot）
- 测试是否有可以运行的节点，如有则更新
（待续…）
————————————————————————
作者：Finney
Blog：AI分享站(http://www.aisharing.com/)
Email：finneytang@gmail.com
本文欢迎转载和引用，请保留本说明并注明出处
————————————————————————
说的很好，我这段时间正好有个儿童智能产品在研发，苦于没有思路，现在有思路了。我会经常关注你。非常感谢！
兄弟,不会c/c++怎么办啊?
学
TsiU AIToolkit(C#) 里发现个BUG，僵尸复活后没有吧isdead设为false。导致某些情况下行走状态还在播攻击动画。
m_BevTreeRoot->Tick， Tick这方法怎么实现的 她得遍历整个树？
我的实现里，tick是不遍历的，在evaluate的时候，已经把需要进哪一个节点都定好了
博主好! 关于你的行为树库，我有以下几个疑惑的地方想请教下你：
首先汇报代码中的一处小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个问题比较让我困惑，希望博主能替我解答，非常感谢！！！
谢谢来信，我又仔细的看了一遍我的代码（很长时间没看了），这个代码是我从上个项目里提炼出来的，为了配合博客的文章，称不上一个库，只是一个范例。Loop那个节点我在项目里写好后后来没有用到，所以一直没发现这个bug，万分感谢。
1. activenode就是用来debug用的，用来打印出当前运行的节点，可以不在每个节点存，而是全局保存一个，这样确实更好
2. 当时是为了在BevNodeTerminal::_DoExit里传入一个exit的标记，因为在实践中发现，有时需要通过这个exit标记来做一些不同的逻辑，在我实际项目中有更多的error返回值，k_BRS_ERROR_Transition是其中的一种，这个标记表示这个不是叶节点自己结束的（就是自己返回finish），而是被父节点的逻辑切换的
3. 对的，直接把智能体的指针放在里面作为变量传入就行了，我在博客里的行为树例子中就是这样做的，定义inputparam和outputparam是希望行为树的工作仅仅依赖于输入，产生输出。
4. 叶节点的设计目标是希望不依赖于它在行为树中的结构，每个叶节点的实现和行为其实与也应该仅与2个“变量”相关，输入（input），输出（output），某种程度上来说，它不应该关心前提，因为前提（Precondition）的组织和设计是和树的结构相关。所以定义了一个外部前提的概念，他不属于节点实现的一部分，而是和节点“装配”的，因为这个是和行为树的结构相关的。我在项目中，发现节点和树的结构没有什么耦合度，不知道你碰到的情况是什么问题，你可以检查你的叶节点实现，是不是仅仅考虑输入和输出（就和函数的概念很像）。
我一般设计行为树，是先列出智能体有多少的行为要做，然后开始设计结构和前提，然后把行为树搭起来，再一个个实现叶节点，可以分给多个人去做，因为实现叶节点的人，其实只要知道这个节点做什么就可以了，通过输入，产生输出
欢迎继续讨论
嗯，知道了， 非常感谢！！
hi,Finney 非常感谢你慷慨的分享！我正在为我的独立FLASH游戏寻找合适的AI架构，本来打算用状态机，不过现在我改变主意了，综合评价，行为树确实在逻辑清晰和大规模状态控制下更胜一筹。 谢谢你提供了这么棒的一个库！它应该能很好的为我的游戏服务:)
嗯，行为树其实挺简单的，很容易做，如果你是flash游戏的，我有一个同事，把我写的行为树的C++代码改成了AS的，并且他开源了，你可以参考一下，https://github.com/hbbalfred/guardians/tree/master/src/engine/bevtree
嗯，谢谢！我自己也已经将你的C++版本改写成as3版本了，还做了一些小改动:)
不过我也发现了一些问题，后续我会将问题整理下发上来，希望你能帮助我消除一些我的疑问！
另外我想问一下博主，这个行为树的库，你在实际项目中有用过吗？
谢谢解答
谢谢解释 我还有一个问题
tick的返回值 运行状态 有什么用?
tick的返回值主要是用来通知外部，行为树当前的运行状态，因为很多情况是，一个行为节点内容在一帧里是没有办法做完的，需要多帧去做，这样tick的返回值就会返回“还在运行”，或者“已经完成”，还可以返回一些错误。至于是否要关心行为树的状态，这个是需要看外部的逻辑的，你也可以完全忽略这个返回值。
比如，在一个带优先级的选择节点下有节点A，和节点B，节点A的优先级高于节点B，当前运行的节点是B，然后发现节点A可以运行了，但带优先级的选择节点就会选择去运行节点A，这时就会调用节点B的Transition方法
—————-
请问 ‘然后发现’ 这个应该怎么理解 是下一次tick么? 那又为什么是 ‘当前运行的节点是b’
求教
可以这样说，A和B都有一个运行的条件，A是a>5的时候运行，B是a>1的时候运行，第一帧的时候a=3，这时检查A的条件，发现不满足，然后检查B的条件发现满足了，那这一帧就运行B（由于是带优先级的选择节点，所以每次都是先检查A，再检查B），然后在第二帧的时候，a=6，这时检查A的条件，发现满足了，所以这一帧就运行A，因为上一次是运行的B，所以会调用B的Transition方法做一些清理的工作。这就是优先级的意义，A的优先级永远比B高
想问个问题，对于Parallel Node，应该理解成每个子节点都执行一遍；那么对于我想实现同时作几件事情，比如同时刮风、下雨，感觉这个类型的节点并不合适，因为我觉得不是间隔执行刮风、下雨两个动作就可以的。这种情况我认为更需要一个新的刮风下雨的action node或者让Parallel Node可以实现多线程同步。但是这样就破坏了算法整体的设定了。请问有什么好办法么？
我的理解其实是怎么来定义“同时”这样一个概念，在单线程的逻辑里，游戏是以帧为单位更新的，画面也是以帧为单位来呈现的，所以可以认为在一帧里做的事情，都是“同时”的。你说的和我想的一样，我也觉得行为树的多线程不是很可行，而且没什么必要。
请问有没有考虑过把行为树再进一步抽象，分离成树的逻辑判断以及数的节点数据，因为我看到过一张图，感觉很这个树结构很适合用xml格式存储。如果能实现的话，就相当于一个小型的AI引擎了，每个AI对象都由一个xml表来定义，其中每个节点的前提和行动另行存储。
嗯，行为树很适合用配置文件来配置，我们用过lua来作为AI的配置文件，lua较之xml的优势是，可以包含一定的逻辑。我一直很想做一个行为树的编辑器和调试器，把AI数据化，不过一直没时间做，有兴趣，可以一起讨论。