在我的玩具项目中，需要有一定智能的NPC来辅助人类攻击防御塔。
通常实现智能会采用状态机，行为树，GOAP等技术。
GOAP技术我没有研究过，行为树在早些年大致了解过一些。因为觉得行为树性能太差，不可能取代状态机实现，之后就再也没有研究过了。
随着这些年我性能强迫症的好转，再加上听到行为树的次数逐年增加，我打算趁机仔细研究一下。
我找来《Behavior Trees in Robotics and AI》仔细读了一遍。这本书详细介绍了行为树，并且对比了行为树和状态机之间的优劣。
根据《Behavior Trees in Robotics and AI》描述，行为树一般有4种控制节点（Sequence, Fallback, Parallel, Decorator)和两种执行节点（Action和Condition)。只有执行节点才能成为叶子节点。
先来简单描述一下最重要的两种控制节点, Sequence和Fallback。
Sequence节点: 当执行Sequence节点时，从左往右顺序执行子节点，直到某一个子节点返回Failure或Running状态，伪码如下：
//Algorithm 1: Pseudocode of a Sequence node with N children
for i 1 to N do
childStatus <- Tick(child(i))
if childStatus = Running then
return Running
else if childStatus = Failure then
return Failure
return SuccessFallback节点：当执行Fallback节点时，从左往右顺序执行子节点，直到某一个子节点返回Success or Running状态，伪码如下：
//Algorithm 2: Pseudocode of a Fallback node with N children
for i 1 to N do
childStatus <- Tick(child(i))
if childStatus = Running then
return Running
else if childStatus = Success then
return Success
return FailureAction和Condition节点，是我们具体的业务逻辑，不是本次优化的重点。
对比行为树和状态机可以发现，行为树比状态机额外多出的开销， 就是在执行执行节点之前，必须要先穿过控制节点。
如果我们在运行时能避过控制节点，只执行执行节点，那行为树和状态机的开销差别就只是多了几次函数调用而已。
仔细思考过之后， 我认为这是可能的。
结合上面对Sequence和Fallback节点的定义。我们不难发现，在编程语言中，Sequence就是and(与)逻辑，而Fallback就是or(或)逻辑。
整棵行为树的控制节点就是用来描述if-else的逻辑，叶子节点是相应的业务逻辑。从这个角度来看，行为树和语法树有颇多相似之处。
不难发现，整棵树的执行路径，其实依赖于特定执行节点的特定返回值。
某一个执行节点（叶子节点）返回Failure或Success, 整棵行为树下一步要执行的执行节点是固定的。
某个执行节点返回Running， 整棵树就停止执行。在下一Tick之后从头执行，这种情况比较简单，暂时不需要考虑。
来看一棵简单的行为树：
如果 Action 1 Done 返回Success，下一步将要执行的执行节点（叶子节点）就是 Actino 2 Done。
如果 Action 1 Done 返回Failure, 下一步将要执行的执行节点（叶子节点）就是 Action 1。
这种逻辑可以递归到所有的执行节点。
这样，我们只需要两张跳转表（Success跳转表，Failure跳转表)，就可以在运行时，以状态机的开销来实现行为树的功能。
以上面的行为树为例，我们可以生成如下跳转表：
local tree = {
["Action 1 Done"] = {
["Success"] = "Action 2 Done",
["Failure"] = "Action 1"
},
["Action 1"] = {
["Success"] = "Action 2 Done",
["Failure"] = nil, --nil 代表整棵树执行结束
},
["Action 2 Done"] = {
["Success"] = nil,
["Failure"] = "Action 2"
},
["Action 2"] = {
["Success"] = nil,
["Failure"] = nil,
}
}在运行时，我们首先执行整棵行为树的第一个节点"Action 1 Done"。
如果"Action 1 Done"返回Success, 根据表tree可知，下一步需要执行的是"Action 2 Done"。
如果"Action 2 Done"返回Failure, 根据表tree可知，下一步需要执行的是"Action 2"。
这样我们仅需要生成一个跳转表，就可以在运行时抹掉所有控制节点所带来的开销。
最终，我花了200行代码实现了根据行为树生成上述跳转表的逻辑。
PS.我把生成跳转表的行为称之为编译。如果控制节点是Parallel或Decorator类型，或者有记忆功能。在编译过程中，需要将其保留，不能将其编译掉。不然无法完成和行为树等价的逻辑。
