行为树（Behavior Tree）实践（2）
上次提到了一些行为树的基本概念，包括行为节点，控制节点（选择，序列，并行），这次来更多，更深入的讨论行为树的一些东西，如果对行为树不是很了解，请参看这里。
一、关于选择节点的讨论
我们说过选择节点的定义是通过判断子节点的前提条件来选择一个节点执行，这就牵涉到判断顺序的问题，是自左向右，还是随机选择，或者其他的一些规则等等，这样就延伸出各种各样的选择节点。
- 带优先级的选择节点（Priority Selector）：这种选择节点每次都是自左向右依次选择，当发现找到一个可执行的子节点后就停止搜索后续子节点。这样的选择方式，就存在一个优先级的问题，也就是说最左边的节点优先级最高，因为它是被最先判断的。对于这种选择节点来说，它的子节点的前提设定，必须是“从窄到宽”的方式，否则后续节点都会发生“饿死”的情况，也就是说永远不会被执行到，为了更清楚的说明，看下面第一张图，这三个子节点在一个带优先级的选择节点下，它们的前提会被依次判断，可以看到这个三个子节点的前提从左向右，一个比一个更严格，如果我们现在a为9，按照下图的定义会执行第一个子节点，如果a为7，则会执行第二个子节点，如果a=11，则会执行第三个子节点。下面的第二张图演示了一种节点“饿死”（Starvation）的情况，我们看到第一个子节点的前提，比第二个子节点更宽泛，只要a<10，那自左向右判断的话，永远会进第一个节点，所以，如果要用到带优先级的选择节点，则必须检查每一个子节点的前提，以防止节点饿死的情况.
- 不带优先级的选择节点（Non-priority Selector）：这种选择节点的选择顺序是从上一个执行过的子节点开始选择，如果前提满足，则继续执行此节点，如果条件不满足，则从此节点开始，依次判断每一个子节点的前提，当找到一个满足条件的子节点后，则执行该节点。这种方式，是基于一种称之为“持续性”的假设，因为在游戏中，一个行为一般不会在一帧里结束，而是会持续一段时间，所以有时为了优化的目的，我们可以优先判断上一个执行的节点，当其条件不满足时，再寻找下一个可执行的节点。这种寻找方式不存在哪个节点优先判断的问题，所以对于前提的设置的要求，就是要保证“互斥”（Exclusion）。如果我们用上面第一张图来说明，如果我们把控制节点换成不带优先级的选择节点，可以看到，当a=3时，第二个子节点会被执行，下一次当a变成9时，由于不是从头依次判断前提的，所以，我们还是会选择第二个节点，而不是我们可能期望的第一个节点。正确的做法见下图，注意每一个子节点的前提是“互斥的”。所以对于不带优先级的选择节点，它子节点的排列顺序就不是那么重要了，可以任意排列。
- 带权值的选择节点（Weighted Selector）：对于这种选择节点，我们会预先为每一个分支标注一个“权值”（Weight Value），然后当我们选择的时候，采用随机选择的方式来选，随机时会参考权值，并且保证已经被测试过的节点的不会再被测试，直到有一个节点的前提被满足，或者测试完所有的节点。带权值的选择节点对于子节点前提由于随机的存在，所以子节点的前提可以任意，而不会发生“饿死”的情况，一般来说，我们通常会把所以子节点的前提设为相同，以更好的表现出权值带来的概率上的效果。当所有子节点的权值一样时，这种选择节点就成为了随机选择节点（Random Selector），带权值的选择节点对于需要丰富AI行为的地方，非常适用，比如养成类游戏中，小狗表示开心的时候，可能会有各种各样的表现，我们就可以用这种选择节点，添加各种子节点行为来实现。
这些就是常用的选择节点类型，我们可以根据需要，定义更多的选择节点的选择行为，其实我们可以看到，不同的选择行为对于子节点前提的要求会有略微的不同，这是在我们搭建行为树的时候需要注意的地方。
二、关于并行节点结束条件的讨论
我们每个节点都会有一个运行状态，来表示当前行为是否结束。对于控制节点来说，它的运行状态就是其子节点的运行状态，选择节点和序列节点比较好处理，因为对于这两种控制节点来说，每时刻，只会有一个子节点在运行，只要返回在运行的这个子节点的状态即可。但对于并行节点来说，它同时刻会有多个子节点运行，那我们如何来处理并行节点的运行状态问题呢？一般有两种：
- 与：只有所有的子节点都运行结束，才返回结束。
- 或：只要有一个子节点运行结束，就返回结束。
为什么要需要有节点的运行状态呢？
- 序列控制节点中，需要用运行状态来控制序列的执行
- 外部世界需要了解行为的运行状态，来决定是否要更新决策（如果行为树在决策层）/请求（如果行为树在行为层），关于AI分层，请参考这里
对于第二点，可以举个例子，比如我们有一个行为是“走到A点”，假设这个行为是不可被打断的，那当我们在走向A点的过程中，行为树的运行状态就是“正在执行”，当到达A点时，行为树就返回“已完成”，这样，对外部来说，当我们看到行为树是“正在执行”的时候，我们就不需要做任何新的行为（为了优化，或者为了行为抖动等等），当看到“已完成”的时候，我们就可以做新的决策或者行为了。这样一个运行状态还有助于我们检测行为树的状态，帮助调试。
三、关于具体实现的讨论
行为树的实现可以有多种多样，我这边提出一些建议，一般来说，行为树每个节点需要有进入（Enter），离开（Exit），运行（Execute）等部分，需要有行为节点（ActionNode），控制节点（ControlNode），前提（Precondition）等基类，然后，还需要定义行为树的输入（InputParam）和输出（OutputParam），一般来说，我们希望行为树是一个黑盒，也就是说，它仅依赖于预定义的输入。输入可以是黑板（Blackboard），工作池（Working Memory）等等数据结构，输出可以是请求（Request），或者其他自定义的数据结构，如下图:
代码的话，就不写了，因为blog没有代码插件，写代码效果不是很好，以后我会在TsiU里面发布一个行为树的库的版本。
四、关于绘制和调试的讨论
看到行为树的定义后，作为程序员的直觉，我们很自然的就会想到，这好像应该能做一个工具来辅助行为树的创建和调试，我们可以把预定义好的前提和节点，在一个可视化的编辑器里搭建成行为树，然后再导出成数据给游戏用。对于调试来说，我们可以让工具和游戏通信，然后实时的检测行为树的运行状况，比如当前在哪个分支中等等。由于行为树的逻辑是可见的，并且是静态的，所以我们看其选择的路径，我们就可以知道AI为什么会作出这样的决策了。当我刚接触到行为树的时候，就在想做这样一个编辑器，但迫于项目压力，一直没有时间做（工作量还是挺大的），有兴趣，有时间的朋友，可以考虑做一个。顺便说一句，我现在对于行为树的搭建都是在代码中完成的，虽然没有数据驱动那么“先进”，但通过宏定义，排版等方式，还是能非常清晰的表示树的整体结构。
关于行为树，我想这个系列就到这里了。在使用行为树的过程中，可能还会碰到这样和那样的问题，包括我自己在实践中的一些经验，我想就先不包括在这个系列里了，以后再单独拿出来聊，这个系列作为行为树的入门，希望对大家有所帮助，欢迎指教和讨论。