行为树
一个决策系统或者流程控制系统，在状态较少的情况下可以使用有限状态机。如果系统存在决策日趋复杂的可能性，那么简单的有限状态机并不是一个很好的选择，在使用它的过程中，你可能会感到越来越力不从心，这是有限状态机本身的局限性造成的。
在之前的有限状态机一文中，我们提到了它的缺陷。在使用有限状态机之前，我们需要列出所有可能的状态转换并设计出一张转换表，状态越多，这张表也就越复杂，出现遗漏的可能性也就越大，很多时候由于我们考虑不周，可能会导致现有的工作需要重新检查和修改，费时费力。下图是 Behavior Designer 官方文档中列出的一个意大利面条式的有限状态机：
什么是行为树？
行为树（Behavior Tree），简称 BT，一般用于游戏 AI，概括来说就是一棵用于控制 AI 行为的树结构。在我们要决策当前的 AI 需要执行哪个行为时，我们就会从它的行为树的根节点开始，自顶向下（或者自左向右）一层一层地对每个节点进行检查，也就是进行树的遍历。
行为树的节点类型有很多种，常见的包括：根节点、复合节点、行为节点和修饰节点，很多成熟的行为树框架中可能还会包含条件节点。需要强调的是，节点一般会有四种状态：Success、Failure、Running 和 Error，其中 Running 状态表示该节点的执行结果还不能立刻获知，比如在游戏中角色进行“向目标移动”的动作，很显然这并不是一个瞬时动作，所以在没有最终到达目的地之前都会一直返回 Running 状态。
复合节点
复合节点（Composite Node）也可以叫做控制节点，它有一个父节点和一个或者多个子节点，它的作用是控制子节点的执行方式，比如按照一定的顺序执行或者随机执行。根据执行方式的不同，常用的复合节点有三种：选择节点（Selector Node）、顺序节点（Sequence Node）和并行节点（Parallel Node）。当然，也有一些不常用的控制节点类型，比如随机选择节点、随机顺序节点、次数限制节点、权重选择节点等等。需要注意的是，复合节点需要向上级提供执行结果，它既可以控制行为节点，同时也能控制复合节点，这样就可以做到决策的复合。
顺序节点
就像它的名字一样，顺序节点会按照一定的顺序（通常是从左到右或者从上到下）执行它的子节点。只有当一个子节点执行成功并向它返回 Success 之后，下一个子节点才会开始执行，当所有的子节点都执行成功，该顺序节点才算执行成功，同时它也会向自己的父节点返回 Success；如果一个子节点执行失败并返回 Failure，那么整个迭代就会停止，这也就意味着该顺序节点执行失败，此时它会向自己的父节点返回 Failure。
顺序节点通常用于执行一连串具有前后依赖关系的行为，其中一个行为失败必然导致后续的行为失去继续执行的意义，比如“进门”这个过程：
一个正确的“进门”过程应该是这样的：顺序节点 -> walk to door(Success) -> 顺序节点（Running）-> open door(Success) -> 顺序节点（Running）-> walk through door(Success) -> 顺序节点（Running）-> close door(Success) -> 顺序节点（Running）-> 向父节点返回 Success。
如果角色因为一些原因未能成功走到门前，比如被其他物体挡住去路，那么后面的这些动作也就失去了执行的意义，这时走向门的这个动作失败并返回，顺序节点会向父节点报告失败，此时父节点就可以根据这个结果进行一些处理。
选择节点
如果把顺序节点理解为一个“与门”，那么选择节点就是一个“或门”。与顺序节点相同，选择节点也会按照一定的顺序执行子节点，但是与顺序节点不同，只要有一个子节点执行成功，那么选择节点就算执行成功并向父节点报告成功的消息。如果有一个子节点执行失败，那么选择节点会继续执行下一个子节点，只有当所有的子节点都执行失败之后，选择节点才算执行失败，此时它会向父节点报告失败的消息。
选择节点通常用于表示一个行为会有多种实现方式，比如攻击这个行为，可能会有劈、斩、砍三种不同的实现方式，选择节点可以选择这三种方式中的任意一种执行。更进一步的，我们可以定义一个优先级，优先级高的行为会先执行。回到“进门”的那个例子，我们增加一些复杂性：
我们将角色开门这个动作进行了更加细化的安排，角色可以选择直接开门或者使用钥匙开门，当然如果角色脾气不太好，也有可能会选择直接把门打烂。
并行节点
并行节点意味着它会并发地执行所有的子节点，而在何种情况下向父节点报告执行结果则与并行节点所采用的具体策略有关。比如它可以是 Parallel Selector 类型的，那么只要有一个子节点执行成功就代表它执行成功；也有可能是 Parallel Sequence 类型的，那么只要有一个子节点执行失败就代表它执行失败。或者是 Parallel Hybird 类型的，那么只有在指定数量的子节点执行失败或者执行成功之后才会决定最终的执行结果。当然，还有很多其他的策略，这里就不一一列举了。
并行节点通常用于表示同一时刻一个事物会有多种行为同时执行，比如一个人物可以一边移动一边攻击。
行为节点
行为节点是叶子节点，它是具体动作的执行者，如果拿代码来做类比的话，那么复合节点和修饰节点就好比能够改变代码执行的流程控制语句：if、else、while 等等，而行为节点就是那些在控制语句范围内被调用的方法。
有些行为是可以在“瞬间”完成的，比如 2D 精灵的转身，而有些行为需要持续一段时间才能完成。因此，在这些持续行为节点中，我们需要先执行持续行为，然后挂起行为树，直到持续时间结束再恢复行为树的执行。为了实现这个目的，一般的做法是一颗行为树维护一个协程，在需要时通过协程等待持续行为的完成，从而避免阻塞当前线程。
条件节点
有些行为节点可能需要一个前提条件，只有在前提条件得到满足的情况下才能够执行，当然有的行为节点并没有前提条件。现在比较成熟的做法是将前提条件抽象分离出来作为一种新的节点类型——条件节点，将它作为叶子节点混入行为树中，提供条件的判断结果，并交给复合节点来决策。
修饰节点
修饰节点可以有子节点，但是它只能拥有一个叶子节点。它的作用有很多，包括修改子节点的执行结果，终止子节点的执行以及重复执行子节点等等。一个比较常见的修饰节点就是逆变节点（Inverter），它可以将子节点的执行结果逆转，比如子节点返回了 Success，那么修饰节点就会向父节点返回 Failure。
还有很多其他类型的修饰节点，比如成功节点（Succeeder），它不管子节点的结果如何都会向父节点返回成功的结果，这在我们知道子节点一定会失败，而它的父节点又是顺序节点的情况下非常有用，这样我们就可以避免因为子节点失败而导致整个迭代停止。
数据上下文
行为树的节点间是存在通信需求的，比如一个顺序节点，它包含两个子节点，一个是选择目标，另一个是攻击。这里就存在节点通信的需求，即攻击节点需要获取选择目标节点的结果，也就是“攻击目标”来发起攻击。那么这个“攻击目标”应该存储在哪里呢？一般情况下，我们都会选择存储在与这个行为树绑定的黑板上，也就是行为树对应的数据上下文当中。
有限状态机与行为树
行为树从本质上讲，是将所有的行为分离出来作为行为节点，然后使用各种控制节点、条件节点和修饰节点将这些行为组合在一起，最终形成一套 AI 的行为决策系统。这么来说，行为树与有限状态机还是有很多相似之处的，或者我们可以理解为行为树对有限状态机做了一些改进和优化。
与有限状态机相比，行为树可以方便地把复杂的 AI 知识条目组织得非常直观，复合节点迭代子节点的方式就像是在处理一个预设的优先策略队列，这与我们正常的思考模式相符合：先最优再次优。由于行为树中的行为逻辑和状态数据相互分离，因此节点的可重用性很高，几乎所有的节点都可以复用，我们可以通过重组不同的节点来实现不同的行为树，同时这也使得行为树更容易实现可视化的 AI 设计工作。
但是行为树的缺陷也很明显，由于每次都需要从根节点开始层层遍历树，所以使用行为树可能会比有限状态机消耗更多的 CPU 资源，尤其是在行为树深度较深时会更加明显。
虽然行为树与有限状态机相比有诸多优势，但是这并不代表我们应该全面抛弃有限状态机。如果我们不需要一个特别复杂的 AI，我们可以考虑继续使用状态机。很多时候我们还可以将两者结合，由状态机负责 AI 的身体状态，而行为树负责 AI 的决策，但是这样的话，行为树在做决策之前还需要考虑状态机的状态，可能会使系统变得更加复杂。
参考
Hierarchical Finite State Machine (HFSM) & Behavior Tree (BT)