java⾏为树_使⽤⾏为树（BehaviorTree）实现游戏AI ———————————————————————
谈到游戏AI，很明显智能体拥有的知识条⽬越多，便显得更智能，但维护
庞⼤数量的知识条⽬是个噩梦：使⽤有限状态机(FSM)，分层有限状态机(HFSM)，
决策树(Decision Tree)来实现游戏AI总有那么些不顺意。
试试Next-Gen AI的⾏为树(Behavior Tree)吧。
虽说Next-Gen AI，但距其原型提出已有约10年时间，⽽微软Halo系列估计
已⽤了超过8年了，Spore和⼀些著名游戏也早已使⽤⾏为树作为它们的AI结构。
如从未接触，那wikipedia(/wiki/Behavior_Trees)
绝对是⼊门好资料。
———————————————————————
先借⽤⽹上的⼀张图来诠释下⾏为树到底是怎么样的
———————————————————————
⾏为树(Behavior Tree)具有如下的特性：
它只有4⼤类型的Node：
* Composite Node  组合节点
* Decorator Node  修饰节点
* Condition Node  条件节点(叶节点)
* Action Node    动作节点(叶节点)
任何Node被执⾏后，必须向其Parent Node报告执⾏结果：成功 / 失败。
这简单的成功 / 失败汇报原则被很巧妙地⽤于控制整棵树的决策⽅向。
———————————————————————
先看Composite Node，其实它按复合性质还可以细分为3种：
* Selector Node
当执⾏本类型Node时，它将从begin到end迭代执⾏⾃⼰的Child Node：
如遇到⼀个Child Node执⾏后返回True，那停⽌迭代，
本Node向⾃⼰的Parent Node也返回True；否则所有Child Node都返回False，那本Node向⾃⼰的Parent Node返回False。
* Sequence Node
当执⾏本类型Node时，它将从begin到end迭代执⾏⾃⼰的Child Node：
如遇到⼀个Child Node执⾏后返回False，那停⽌迭代，
本Node向⾃⼰的Parent Node也返回False；否则所有Child Node都返回True，那本Node向⾃⼰的Parent Node返回True。
* Parallel Node
并发执⾏它的所有Child Node。
⽽向Parent Node返回的值和Parallel Node所采取的具体策略相关：
Parallel Selector Node: ⼀False则返回False，全True才返回True。
Parallel Sequence Node: ⼀True则返回True，全False才返回False。
Parallel Hybird Node: 指定数量的Child Node返回True或False后才决定结果。Parallel Node提供了并发，提⾼性能。
不需要像Selector/Sequence那样预判哪个Child Node应摆前，哪个应摆后，
常见情况是：
(1)⽤于并⾏多棵Action⼦树。
(2)在Parallel Node下挂⼀棵⼦树，并挂上多个Condition Node，
以提供实时性和性能。
Parallel Node增加性能和⽅便性的同时，也增加实现和维护复杂度。
PS：上⾯的Selector/Sequence准确来说是Liner Selector/Liner Sequence。
AI术语中称为strictly-order：按既定先后顺序迭代。
Selector和Sequence可以进⼀步提供⾮线性迭代的加权随机变种。
Weight Random Selector提供每次执⾏不同的First True Child Node的可能。Weight Random Sequence则提供每次不同的迭代顺序。
AI术语中称为partial-order，能使AI避免总出现可预期的结果。———————————————————————
再看Decorator Node，它的功能正如它的字⾯意思：它将它的Child Node执⾏
后返回的结果值做额外处理后，再返回给它的Parent Node。很有些AOP的味道。⽐如Decorator Not/Decorator FailUtil/Decorator Counter/Decorator Time…更geek的有Decorator Log/Decorator Ani/Decorator Nothing…
———————————————————————
然后是很直⽩的Condition Node，它仅当满⾜Condition时返回True。———————————————————————
最后看Action Node，它完成具体的⼀次(或⼀个step)的⾏为，视需求返回值。
nodeselector⽽当⾏为需要分step/Node间进⾏时，可引⼊Blackboard进⾏简单数据交互。———————————————————————
整棵⾏为树中，只有Condition Node和Action Node才能成为Leaf Node，⽽也
只有Leaf Node才是需要特别定制的Node；Composite Node和Decorator Node均⽤于控制⾏为树中的决策⾛向。(所以有些资料中也统称Condition Node和Action Node为Behavior Node，⽽Composite Nod
e和Decorator Node为Decider Node。)更强⼤的是可以加⼊Stimulus和Impulse，通过Precondition来判断masks开关。
通过上述的各种Nodes⼏乎可以实现所有的决策控制：if, while, and, or,
not, counter, time, random, weight random, util…———————————————————————
总的来说，⾏为树具有如下⼏种优点，确实是实现AI框架的利器，甚⾄是⼀种
通⽤的可维护的复杂流程管理利器：
> 静态性
越复杂的功能越需要简单的基础，否则最后连⾃⼰都玩不过来。
静态是使⽤⾏为树需要⾮常着重的⼀个要点：即使系统需要某些”动态”性。
其实诸如Stimulus这类动态安插的Node看似强⼤，
但却破坏了本来易于理解的静态性，弊⼤于利。
Halo3相对于Halo2对BT AI的⼀个改进就是去除Stimulus的动态性。
取⽽代之的做法是使⽤Behavior Masks，Encounter Attitude，Inhibitions。
原则就是保持全部Node静态，只是根据事件和环境来检查是否启⽤Node。
静态性直接带来的好处就是整棵树的规划⽆需再运⾏时动态调整，为很多优化
和预编辑都带来⽅便。
> 直观性
⾏为树可以⽅便地把复杂的AI知识条⽬组织得⾮常直观。
默认的Composite Node的从begin往end的Child Node迭代⽅式就像是处理⼀个
预设优先策略队列，也⾮常符合⼈类的正常思考模式：先最优再次优。
⾏为树编辑器对优秀的程序员来说也是唾⼿可得。
> 复⽤性
各种Node，包括Leaf Node，可复⽤性都极⾼。
实现NPC AI的个性区别甚⾄可以通过在⼀棵共⽤的⾏为树上不同的位置来
安插Impulse来达到⽬的。
当然，当NPC需要⼀个完全不同的⼤脑，⽐如70级⼤BOSS，
与其绞尽脑汁在⼀棵公⽤BT安插Impulse，不如重头设计⼀棵专属BT。
> 扩展性
虽然上述Node之间的组合和搭配使⽤⼏乎覆盖所有AI需求。
但也可以容易地为项⽬量⾝定做新的Composite Node或Decorator Node。
还可以积累⼀个项⽬相关的Node Lib，长远来说⾮常有价值。
--------------------------------本⼈补充---------------------------------------
每个节点都应该有以下三种状态：
Running,
Success,
Failed
Running状态⽤于表明该节点的结果不能⽴刻获知，⽐如游戏中的⾓⾊进⾏“向⽬标移动”这个动作，很显然这个动作不能在这⼀帧中⽴刻完成，当⾏为树运⾏到此节点时，并不能
获知是success或者failed，于是返回running，表⽰该节点正在运⾏中，并记录此节点
的位置，下⼀帧运⾏到此节点的⽗节点时，则从此节点继续运⾏，跳过之前的节点。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。