游戏AI行为决策——Behavior Tree（行为树）

【USparkle专栏】如果你深怀绝技，爱“搞点研究”，乐于分享也博采众长，我们期待你的加入，让智慧的火花碰撞交织，让知识的传递生生不息！

这是侑虎科技第1825篇文章，感谢作者狐王驾虎供稿。欢迎转发分享，未经作者授权请勿转载。如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群：793972859）

作者主页：

https://home.cnblogs.com/u/OwlCat

一、前言

行为树，是目前游戏中应用较为广泛的一种行为决策模型。这离不开它成熟的可视化编辑工具，例如Unity商城中的「Behaviour Designer」，甚至是虚幻引擎也自带此类编辑工具。而且它的设计逻辑并不复杂，其所利用的树状结构，很符合人的思考方式。

接下来，我们会先对它的运作逻辑进行介绍，然后再试图用代码实现它。树状结构在不借助可视化工具的情况下是不容易呈现清楚的，这里我借鉴了Steve Rabin的《Game AI Pro》[1]中行为树的实现方式，利用代码缩进稍稍实现了一些可视化（本教程使用C#代码实现）。下面我们就开始吧！

二、运动逻辑

1. 根节点驱动

如果你已经了解「有限状态机（FSM）」的话，你应该知道，有限状态机在运作时常常会停留在一个状态中，不断执行该状态的逻辑，直至接受到状态转移的指令才变化到其它状态。而行为树则是会不断从根节点向下搜索，即「根节点驱动」，来找到合适的「动作」执行，执行完毕后会再回到根节点重复这个过程。以下面这个「怪物攻击玩家」行为树为例：

假设「攻击」动作的逻辑是「向玩家挥一拳」，现在怪物发现玩家且玩家在攻击范围内。那么，按照行为树的逻辑，它会经过「战斗 ➡ 试图攻击 ➡ 攻击」一路下来，最终向玩家挥出一拳。

至此，「攻击」就算是完成了，若是在状态机中，攻击也算是一种状态的话，怪物必然会停留于此，等待下一帧时再挥出一拳。但在行为树中呢？它确实也会在下一帧时再挥出一拳，只是会再经过「战斗 ➡ 试图攻击 ➡ 攻击」这个过程，也就是前面所说的，从根节点再次出发。

你可能也发现了，这明显是多此一举的行为，它确实可以算是行为树的小缺点。但其实行为树的深度通常并不会太深，多几次布尔判断或小遍历倒也不打紧；而且有一种事件驱动的行为树实现方法，能以“空间换时间”的手段改善这种情况，感兴趣的同学可以去了解一下。

2. 特殊的节点

行为树的一大特点，就是将条件与行为本身进行了分离。

什么意思呢？我们仍以上面那张图为例，只是稍稍修改下表现方式（也更接近行为树真正的样子）：

好像多了几个圈？那现在，请你将这些圈也视为和「攻击」一样类型的节点。这样一来，我们将「判断逻辑」、「顺序遍历（图中的红色箭头）」、「动作」都用节点来表示了。这有什么好处呢？好处就在于我们可以将它们进行各种各样的组合！比如，如果有一个怪物比较胆小，遇到玩家后会逃跑，我们就可以用图中的「发现玩家」+「移动到该位置（逃跑的位置）」来实现；也可以配合新的节点来组合，比如「已知玩家最后出现的位置」+ 新节点：「朝指定位置开火」，就可以实现远程追击。

总之，正是因为行为树有一系列特殊的节点，使得开发者可以降低各个行为之间的关联（也就是解耦），再配合上树状结构的特点，开发者可以灵活地进行组装，实现节点的重复利用，避免写重复的代码，提高了开发效率。（用过有限状态机写游戏AI的同学一定能体会到这点的好处。）

三、代码实现

现在，我们就一起来实现行为树，先看看我们有哪些要实现的（它们的具体含义后面会解释）：

1. 组合节点（Composite），指有多个子节点的特殊节点，具体包括：

a. 顺序器（Sequence）

b. 选择器（Selector）

c. 并行器（Parallel）

d. 过滤器（Filter）

e. 主动选择器（ActiveSelector）

f. 监视器（Monitor）

2. 修饰节点（Decorator），指仅有一个子节点的特殊节点，具体包括：

a. 取反器（Inverter）

b. 重复执行器（Repeat）

3. 动作节点，指可以自定义的节点，比如「攻击」、「巡视」之类的。

1. 基础准备

正式实现它们之前，我们应当准备它们的基类，毕竟它们都是节点，有一些共性的东西可以提取出来，这样可以减少一些重复的代码。

/// /// 运行结果状态的枚举 /// publicenumEStatus {     //失败，成功，运行中，中断，无效     Failure, Success, Running, Aborted, Invalid } /// /// 行为树节点基类 /// publicabstractclassBehavior {     publicboolIsTerminated=> IsSuccess || IsFailure;//是否运行结束     publicboolIsSuccess=> status == EStatus.Success;//是否成功     publicboolIsFailure=> status == EStatus.Failure;//是否失败     publicboolIsRunning=> status == EStatus.Running;//是否正在运行     protected EStatus status;//运行状态     publicBehavior()     {         status = EStatus.Invalid;     }     //当进入该节点时才会执行一次的函数，类似FSM的OnEnter     protected virtual voidOnInitialize() {}     //该节点的运行逻辑，会时时返回执行结果的状态，类似FSM的OnUpdate     protectedabstract EStatus OnUpdate();     //当运行结束时才会执行一次的函数，类似FSM的OnExit     protected virtual voidOnTerminate() {}     //节点运行，从中应该更能了解上述三个函数的功能     //它会返回本次调用的结果，为父节点接下来的运行提供依据     public EStatus Tick()     {         if(!IsRunning)             OnInitialize();         status = OnUpdate();         if(!IsRunning)             OnTerminate();         return status;     }     //添加子节点     public virtual voidAddChild(Behavior child) {}     //重置该节点的运作     publicvoidReset()     {         status = EStatus.Invalid;     }     //强行打断该节点的运作     publicvoidAbort()     {         OnTerminate();         status = EStatus.Aborted;     } }

2. 组合节点

首先实现「组合节点」这个基类。

using System.Collections.Generic; publicabstractclassComposite : Behavior {     protected LinkedList children; //用双向链表构建子节点列表     publicComposite()     {         children = newLinkedList ();     }     //移除指定子节点     public virtual voidRemoveChild(Behavior child)     {         children.Remove(child);     }     publicvoidClearChildren()//清空子节点列表     {         children.Clear();     }     public override voidAddChild(Behavior child)//添加子节点     {         //默认是尾插入，如：0插入「1，2，3」中，就会变成「1，2，3，0」         children.AddLast(child);     } }

接下来就是具体类的实现了，我会对这些节点的功能作出解释（有参考虚幻引擎的行为树节点介绍），再进行代码实现。

a. 顺序器

逻辑上来讲（非代码结构），它长这样：

顺序器会按从左到右的顺序执行其子节点。当其中一个子节点执行失败时，将停止执行，也就是说，任一子节点失败，顺序器就会失败。只有所有子节点运行都成功，顺序器才算成功。

public classSequence : Composite {     protected LinkedListNode currentChild; //当前运行的子节点     protected override voidOnInitialize()     {         currentChild = children.First;//从第一个子节点开始     }     protected override EStatus OnUpdate()     {         while(true)         {             vars= currentChild.Value.Tick();//记录子节点运行返回的结果状态             /*             如果子节点运行，还没有成功，就直接返回该结果。             是「运行中」那就表明本节点也是运行中，有记录当前节点，下次还会继续执行；             是「失败」就表明本节点也运行失败了，下次会再经历OnInitialize，从头开始。             */             if( s != EStatus.Success)                 return s;             //如果运行成功，就换到下一个子节点             currentChild = currentChild.Next;             //如果全都成功运行完了，就返回「成功」             if(currentChild == null)                 return EStatus.Success;         }     } }

b. 选择器

从逻辑上讲，它的结构应该长这样：

每次只会选择一个可以运行的子节点来运行。

但从代码上来说，选择器的结构和顺序器完全一致，只是运行逻辑变化了：按从左到右的顺序执行其子节点。当其中一个子节点执行成功时，就停止执行，也就是说，任一子节点成功运行，就算运行成功。只有所有子节点运行都失败，选择器才算运行失败。

所以，只要简单地继承「顺序器」并修改它的OnUpdate逻辑，就能得到选择器啦！

public classSelector : Sequence {     protected override EStatus OnUpdate()     {         while(true)         {             vars= currentChild.Value.Tick();             if( s != EStatus.Failure)                 return s;             currentChild = currentChild.Next;             if(currentChild == null)                 return EStatus.Failure;         }     } }

c. 并行器

并行器，它会同时执行所有子节点。

可这样就有问题了：

1. 怎么「同时」运行，要用多线程吗？

2. 同时执行必然会返回多个结果，该如何确定最终返回运行结果呢？

对于问题1，是不用多线程的，我们只要在一帧中把所有子节点都执行一次，就算是「同时」执行了；

对于问题2，我们可以根据需求自行设置并行器成功或失败的标准，一般可分为「全都」和「只要有一个」。

看看代码就知道了：

public classParallel : Composite {     protected Policy mSuccessPolicy;//成功的标准     protected Policy mFailurePolicy;//失败的标准     ///     /// Parallel节点成功与失败的要求，是全部成功/失败，还是一个成功/失败     ///     publicenumPolicy     {         RequireOne, RequireAll,     }     //构造函数初始化时，会要求给定成功和失败的标准     publicParallel(Policy mSuccessPolicy, Policy mFailurePolicy)     {         this.mSuccessPolicy = mSuccessPolicy;         this.mFailurePolicy = mFailurePolicy;     }     protected override EStatus OnUpdate()     {         intsuccessCount=0, failureCount = 0;//记录执行成功和执行失败的节点数         varb= children.First;//从第一个子节点开始         varsize= children.Count;         for (inti=0; i < size; ++i)         {             varbh= b.Value;             if(!bh.IsTerminated)//如果该子节点还没运行结束，就运行它                 bh.Tick();             b = b.Next;             if(bh.IsSuccess)//该子节点运行结束后，如果运行成功了             {                 ++successCount;//成功执行的节点数+1                 //如果是「只要有一个」标准的话，那就可以返回结果了                 if(mSuccessPolicy == Policy.RequireOne)                     return EStatus.Success;             }             if(bh.IsFailure)//该子节点运行失败的情况同理             {                 ++failureCount;                 if(mFailurePolicy == Policy.RequireOne)                     return EStatus.Failure;             }         }         //如果是「全都」标准的话，就需要比对当前成功/失败个数与总子节点数         if(mFailurePolicy == Policy.RequireAll && failureCount == size)             return EStatus.Failure;         if(mSuccessPolicy == Policy.RequireAll && successCount == size)             return EStatus.Success;         return EStatus.Running;     }     //结束函数，只要简单地把所有子节点设为「中断」就可以了     protected override voidOnTerminate()     {         foreach(var b in children)         {             if(b.IsRunning)                 b.Abort();         }     } }

至此，基础的组合节点就讲完了，但还有一些常用的组合节点，它们是在这些基础的组合节点上稍稍变形而来的。

d. 过滤器

过滤器，由顺序器改造而来，就是在进入子节点之前，加了些条件判断，如果不满足任意一个，就不能执行后续的子节点，此即为「过滤」。

你会发现，它们甚至可以直接看作是在同一个列表里，只是「条件」都在前半段，真正要运行的子节点都在后半段。代码也确实是这么设计的：

public classFilter : Sequence {     publicvoidAddCondition(Behavior condition)//添加条件，就用头插入     {         children.AddFirst(condition);     }     publicvoidAddAction(Behavior action)//添加动作，就用尾插入     {         children.AddLast(action);     } }

e. 主动选择器

假设，某人正在砍树，但突然电锯故障了，迫不得已，他只能换斧头来砍树；但突然被扔在一旁的电锯又好起来了，那他还会继续费力的用斧子来砍树吗？

我想，只要他还没因为中暑把CPU干烧就不会这么做。但他如果是一个NPC的话，按照之前「选择器」的逻辑，确实会出现这种荒谬的行为。所以我们需要一个特殊的选择器，能始终执行最具优先级的子节点，甚至可以因此打断正在运行的低优先级的子节点。

我们只需对「选择器」的OnUpdate进行改造，在每次调用时，也从头到尾进行选择（默认高优先级的行为在前面）即可：

public classActiveSelector: Selector {     protected override EStatus OnUpdate()     {         varprev= currentChild;         base.OnInitialize();//注意这里，currentChild 会被赋值为children.First         varres= base.OnUpdate();//按Selector的OnUpdate执行，顺序遍历选择         /*         只要不是遍历结束或可执行节点不变，都应该中断上一次执行的节点，无论优先是高是低。         因为如果当前优先级比之前的高，理应中断之前的；         而如果比之前的低，那就证明之前高优先级的行为无法继续了，         否则怎么会轮到现在的低优先级的行为呢？所以也应中断它。         */         if(prev != null && currentChild != prev)             prev.Value.Abort();         return res;     } }

f. 监视器

监视器是对「并行器」的改造，改造的目的也是为了能持续检查并行行为的条件。

从逻辑上看，它有两个子树，一边负责条件，一边负责具体行为。这种分离方式是合理的，防止了同步和争用问题，因为只有一个子树将运行对世界进行更改的操作。

从代码上来说，其实它的改造方法和「过滤器」完全一致，因为我们完全可以把这两个子树看作一个，只是前半部分全是条件，后半部分全是具体动作而已：

public classMonitor: Parallel {     publicMonitor(Policy mSuccessPolicy, Policy mFailurePolicy)      : base(mSuccessPolicy, mFailurePolicy)     {     }     publicvoidAddCondition(Behavior condition)     {         children.AddFirst(condition);     }     publicvoidAddAction(Behavior action)     {         children.AddLast(action);     } }

终于，所有常用的组合节点我们都实现了，下面就该讲讲修饰节点了。

3. 修饰节点

修饰节点只有一个子节点，因为这样就足够了，想要多个条件只需要配合组合节点就可以实现。所以它的基类也十分简单：

public abstract class Decorator : Behavior {     protected Behavior child;     public override void AddChild(Behavior child)     {         this.child = child;     } }

修饰节点理论上可以扩展成各种「条件」，完全取决于开发者的需求。所以这里，我们就不在这方面展开，就说说几个比较实用的修饰器吧。

a. 取反器

简单地对子节点执行结果的「成功」或「失败」进行颠倒而已，但这小小的功能却能帮我们省去很多冗余的代码，比如有「存在敌人」的条件节点时，再想要「不存在敌人」的条件节点，就不必去写代码了，只需要在「存在敌人」前加上这样一个「取反器」就可以了。

它的实现也很简单：

public class Inverter : Decorator {     protected override EStatus OnUpdate()     {         child.Tick();         if(child.IsFailure)             return EStatus.Success;         if(child.IsSuccess)             return EStatus.Failure;         return EStatus.Running;     } }

b. 重复执行器

重复执行某（些）行为也是常见的动作需求，这些动作往往都是已实现的单一动作，例如，有了「点射」动作，我们就可以仅给它加上一个重复执行器，就可以实现「扫射」了。

重复执行器的逻辑也很直接：

public classRepeat : Decorator {     privateint conunter;//当前重复次数     privateint limit;//重复限度     publicRepeat(int limit)     {         this.limit = limit;     }     protected override voidOnInitialize()     {         conunter = 0;//进入时，将次数清零     }     protected override EStatus OnUpdate()     {         while (true)         {             child.Tick();             if(child.IsRunning)                 return EStatus.Running;             if(child.IsFailure)                 return EStatus.Failure;             //子节点执行成功，就增加一次计算，达到设定限度才返回成功             if(++conunter >= limit)                 return EStatus.Success;         }     } }

4. 动作节点

动作节点也是自由发挥的节点，具体功能随需求，但有一点要严格遵守——不能有子节点。

要实现动作节点，只要继承并重写节点基类就可以了，例如一个打印一些字的节点：

public class DebugNode : Behavior {     private string word;     public DebugNode(string word)     {         this.word = word;     }     protected override EStatus OnUpdate()     {         Debug.Log(word);         return EStatus.Success;     } }

5. 构建与运行

节点部分我们都讲完了，现在就开始实现树的构建与运行了。

我们先实现树：

public classBehaviorTree {     publicboolHaveRoot=> root != null;     private Behavior root;//根节点     publicBehaviorTree(Behavior root)     {         this.root = root;     }     publicvoidTick()     {         root.Tick();     }     publicvoidSetRoot(Behavior root)     {         this.root = root;     } }

很简短吧，实际上树只需要记录根节点就可以了，其余节点都会由各个节点用自己的子节点/子节点列表存储。这么说来，其实一个普通的节点，也可以视为一棵树吗？是的，只是将二者进行区分还是很有必要的，省得逻辑混乱。它的运行，也只是简单地递归调用子节点的Tick。当然，这只是对于简单实现的行为树来说是这样而已，至于更加成熟的实现方式（如之前提到的事件驱动的行为树）就不是这样了。

言归正传，那这只是一棵树而已，怎么向它增加节点呢？这里我们再单独造一个管理树逻辑的类：

public partial classBehaviorTreeBuilder {     private readonly Stack nodeStack; //构建树结构用的栈     private readonly BehaviorTree bhTree;//构建的树     publicBehaviorTreeBuilder()     {         bhTree = newBehaviorTree(null);//构造一个没有根的树         nodeStack = newStack (); //初始化构建栈     }     privatevoidAddBehavior(Behavior behavior)     {         if (bhTree.HaveRoot)//有根节点时，加入构建栈         {             nodeStack.Peek().AddChild(behavior);         }         else//当树没根时，新增得节点视为根节点         {             bhTree.SetRoot(behavior);         }         //只有组合节点和修饰节点需要进构建堆         if (behavior is Composite || behavior is Decorator)         {             nodeStack.Push(behavior);         }     }     publicvoidTreeTick()     {         bhTree.Tick();     }     public BehaviorTreeBuilder Back()     {         nodeStack.Pop();         returnthis;     }     public BehaviorTree End()     {         nodeStack.Clear();         return bhTree;     } }

这样就实现了树构建，还把调用也再包装了一层。用BehaviorTreeBuilder，就可以既构建又运行了。接下来，我们来详细说说里面的逻辑：

最开始用AddBehavior函数添加一个节点，它无疑会成为根：

再添加一个0，它会变成这样：

再添加同理：

而当我们想要为0添加第二个子节点时，只需要先调用Back，Back会使栈顶元素弹出：

之后，再调用添加函数，由于该函数是向栈顶元素添加子节点，所以就变成了：

通过AddBehavior和Back，我们就可以设置树的结构。如果又想给1添加子节点该怎么办？可以直接在调用Back之前的代码里，加上给1节点添加子节点的代码。

配合缩进，我们可以勉强实现可视化，至少有层次感：

public classTest0 : MonoBehaviour {     BehaviorTreeBuilder builder;     privatevoidAwake()     {         builder = newBehaviorTreeBuilder();     }     privatevoidStart()     {         builder.Repeat(3)                     .Sequence()                         .DebugNode("Ok,")//由于动作节点不进栈，所以不用Back                         .DebugNode("It's ")                         .DebugNode("My time")                     .Back()                 .End();         builder.TreeTick();     } }

这里的Repeat，实际上就是对添加节点的包装，以下是该类的完整代码:

public partial classBehaviorTreeBuilder {     private readonly Stack nodeStack;     private readonly BehaviorTree bhTree;     publicBehaviorTreeBuilder()     {         bhTree = newBehaviorTree(null);         nodeStack = newStack ();     }     privatevoidAddBehavior(Behavior behavior)     {         if (bhTree.HaveRoot)         {             nodeStack.Peek().AddChild(behavior);         }         else         {             bhTree.SetRoot(behavior);         }         if (behavior is Composite || behavior is Decorator)         {             nodeStack.Push(behavior);         }     }     publicvoidTreeTick()     {         bhTree.Tick();     }     public BehaviorTreeBuilder Back()     {         nodeStack.Pop();         returnthis;     }     public BehaviorTree End()     {         nodeStack.Clear();         return bhTree;     }     //---------包装各节点---------     public BehaviorTreeBuilder Sequence()     {         vartp=newSequence();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Seletctor()     {         vartp=newSelector();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Filter()     {         vartp=newFilter();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Parallel(Parallel.Policy success, Parallel.Policy failure)     {         vartp=newParallel(success, failure);         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Monitor(Parallel.Policy success, Parallel.Policy failure)     {         vartp=newMonitor(success, failure);         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder ActiveSelector()     {         vartp=newActiveSelector();         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Repeat(int limit)     {         vartp=newRepeat(limit);         AddBehavior(tp);         returnthis;     }     public BehaviorTreeBuilder Inverter()     {         vartp=newInverter();         AddBehavior(tp);         returnthis;     } }

你可能也注意到了，这个类是partial类，它还有另一部分内容，我将其与DebugNode写在同一处：

public classDebugNode : Behavior {     private string word;     publicDebugNode(string word)     {         this.word = word;     }     protected override EStatus OnUpdate()     {         Debug.Log(word);         return EStatus.Success;     } } public partial classBehaviorTreeBuilder {     public BehaviorTreeBuilder DebugNode(string word)     {         varnode=newDebugNode(word);         AddBehavior(node);         returnthis;     } }

个人还没想到好办法，这种包装确实好看，但要另写这样的函数属实有点繁琐。倒也可以修改AddBehavior类让它也返回BehaviorTreeBuilder，但这样在构建树时，代码会变得有些长，总之看个人选择。如果你的Test0能输出三次"Ok,It's My time"，那就说明你的构建没错。

内容到这也差不多了，个人其实还并没有正式用过这个行为树来做游戏，当然还有其它的行为决策方法我比较青睐，比如「分层任务网络（HTN）」，个人就用的比较多。在我个人的一些游戏中就有使用到，有时间的话，也可以和大家交流下它的运行和实现。

参考：

[1]《Game AI Pro》

https://www.gameaipro.com/

文末，再次感谢狐王驾虎 的分享， 作者主页：https://home.cnblogs.com/u/OwlCat， 如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群： 793972859 ）。

近期精彩回顾

【学堂上新】

【学堂上新】

【万象更新】

【万象更新】