CC BY 4.0 （除特别声明或转载文章外）
前两周一直在忙于ai的优化，之前的ai实现有一点类似状态机的做法，写起了有点不太简洁优雅，可维护性比较低。 加之之前对行为树有一点了解，所以寻思将之前的ai改为行为树的方式。
在动手之前，自己也参考了网上很多关于行为树的介绍，以及行为树相关项目。
关于行为树的介绍：
主要参考了育碧大神finney关于行为树介绍的文章。大神的博客里面有很多关于ai设计的文章，干货十足。
另外，可以参考资料《The Behavior Tree Starter Kit》，出自《Game AI Pro》第一版第二部分（Section 2: Architecture）的第六章节。 对应的代码在github上。我会抽个时间翻译一下。
行为树的相关项目：
我看过的项目主要有两个：
- 饥荒的ai实现
- 腾讯的开源项目Tencent Behaviac
饥荒的脚本是lua实现，而且是未编译成字节码的，所以可以看到整个游戏的lua层代码，其中就包括了饥荒整个ai框架。
ai相关的主要代码在：behaviours、brains和stategraphs 这三个文件夹，其中stategraphs是状态机的实现，也有参考意义。 我也是将里面行为树部分移除出来，并做了一些修改运用到我们的游戏中。
什么是行为树
先看一个简单的怪物行为树： 
行为树是一种树形结构，它其实可以看成是一个分层状态机从网状图拉成了一个树。一颗树包含了中间节点和叶子节点， 中间节点控制决策的走向，叶子节点则负责展现行为。
行为树的节点
行为树节点主要分为：
- 组合节点（序列节点、选择节点、并行节点等）
- 装饰节点（有且仅有一个子节点）
- 条件节点
- 动作节点
组合节点和装饰节点只能作为行为树的中间节点，而条件节点和动作节点作为树的叶子节点。 所以，条件和动作节点称为行为节点（Behavior Node），组合和装饰节点称为决策节点（Decider Node）。
在详细介绍每个节点之前，首先要了解节点的状态。行为树的每个节点的运行状态只会有两种：
- 运行中（running）
- 运行完毕（success/failed）
父节点通过每个子节点的运行状态，来决定自己的状态。
如何理解running状态？
举个例子，假如人吃饭是一个行为，但是吃饭需要花一段时间，所以当人执行吃饭的行为时，这个吃饭的节点就处于running中， 直到吃完后，才会变成success状态（吃饭成功），或者吃到一半时发现菜里有屎，变成failed状态（吃饭失败）。
当然，如果是瞬时动作，可以不需要running。
组合节点
- 序列节点
它实现的是and的逻辑，例如：r = x and y and z,则先执行x，如果x为true，则继续执行y，如果x为false，则直接返回false，以此类推 执行该节点时，它会一个接一个运行， 如果子节点状态为success，则执行下一个子节点； 如果子节点状态为running，则把自身设置为running，并等待返回其他结果（success或failed）； 如果子节点状态为failed，则把自身设置为failed，并返回； 如果所有节点都为success，则把自身设置为success并返回。 原则：只要一个子节点返回”失败”或”运行中”，则返回；若返回”成功”，则执行下一个子节点。
- 选择节点
它实现的是or的逻辑，例如：r = x or y or z,则先执行x，如果x为false，则继续执行y，如果x为true，则直接返回true，以此类推 执行该节点时，它会一个接一个运行， 如果子节点状态为success，则把自身设置为success并返回； 如果子节点状态为running，则把自身设置为running，并等待返回其他结果（success或failed）； 如果子节点状态为failed，则会执行下一个子节点； 如果所有没子节点都不为success，则把自身设置为failed并返回。 原则：只要一个子节点返回”成功”或”运行中”，则返回；若返回”失败”，则执行下一个子节点。
- 并行节点
看上去是同时执行所有的子节点，但是真正的逻辑还是一个一个执行子节点。 可以自己设定并行节点的退出条件，比如：如果子节点失败，则并行节点返回，并将自身状态也设为失败。
装饰节点
顾名思义，它只是对它的子节点的运行状态做一些修饰，比如取反、限制次数等。
条件节点
条件节点根据比较结果返回成功或失败，但永远不会返回正在执行（Running）
动作节点
即真正的行为，可能一些行为需要特殊实现，所以，可以根据需要自行定制。
行为树的实现
我移植的行为树实现，已经放在了github repo, 但是在实现上稍微有一些区别。在饥荒原版的实现中，ai固定思考的频率是变动的，而我将它改为了固定频率。
什么意思呢？
首先，要明白饥荒行为树的执行流程。
行为树根节点（PriorityNode）有一个最大思考间隔_period，每次思考（执行）一次后，如果思考耗时未超过_period，则有两种处理方式：
- 如果思考后的结果为running，则根节点会记录这个running的子节点，并在思考后计算出下一次思考的间隔时间，那么下一次则直接从这个running的子节点开始思考；
- 如果思考后的结果为成功或者失败，则在下一个逻辑帧时从根节点重新思考。
如果思考超过了最大思考间隔，则从根节点重新思考一次，不管上次思考的结果是否是running。
举个例子：
假设 _period=1000 ms, 游戏的逻辑帧为10ms, 并且按照下面的思考流程：
- 第一次思考的时间戳是0，思考完后有一个子节点A返回running，并且需要在300ms后进行下一次思考；
等待300ms后，开始第二次思考（此时时间戳为300），直接从A开始执行，这里需要注意，返回的结果不同，下次思考的流程也会不同；
- 若思考后返回success，并且下一个逻辑帧（10ms后）又需要从头重新思考；
- 若思考后返回running，并且需要等待800ms，那么，300+800>1000，所以下次思考的间隔时间为（0+1000）-300=700ms。
换句话说，最大思考间隔的作用是，防止某个子节点一直running，而导致其他满足条件的子节点得不到运行的机会。
而我改成固定频率，是担心ai思考过于频繁，还是上面的例子，在第二次思考后，如果返回成功，下一次思考还是需要等待700ms，而不是在下一次逻辑帧从头重新思考。