游戏AI行为决策——行为树

前言

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

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

运作逻辑

1.根节点驱动

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

假设「攻击」动作的逻辑是「向玩家挥一拳」，现在怪物发现玩家且玩家在攻击范围内。那么，按照行为树的逻辑，它会经过「战斗 \(\rightarrow\) 试图攻击 \(\rightarrow\) 攻击」一路下来，最终向玩家挥出一拳 (￣ε(#￣)☆╰╮o(￣皿￣///)。

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

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

2.特殊的节点

行为树的一大特点，就是将条件与行为本身进行了分离。
什么意思呢？我们仍以上面那张图为例，只是稍稍修改下表现方式（也更接近行为树真正的样子）：

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

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

代码实现

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

1. 组合节点（Composite），指有多个子节点的特殊节点，具体包括：
   1. 顺序器（Sequence）
   2. 选择器（Selector）
   3. 并行器（Parallel）
   4. 过滤器（Filter）
   5. 主动选择器（ActiveSelector）
   6. 监视器（Monitor）
2. 修饰节点（Decorator），指仅有一个子节点的特殊节点，具体包括：
   1. 取反器（Inverter）
   2. 重复执行器（Repeat）
3. 动作节点，指可以自定义的节点，比如「攻击」、「巡视」之类的

1.基础准备

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

/// <summary>
/// 运行结果状态的枚举
/// </summary>
public enum EStatus
{
    //失败，成功，运行中，中断，无效
    Failure, Success, Running, Aborted, Invalid
}

/// <summary>
/// 行为树节点基类
/// </summary>
public abstract class Behavior
{
    public bool IsTerminated => IsSuccess || IsFailure;//是否运行结束
    public bool IsSuccess => status == EStatus.Success;//是否成功
    public bool IsFailure => status == EStatus.Failure;//是否失败
    public bool IsRunning => status == EStatus.Running;//是否正在运行
    protected EStatus status;//运行状态
    public Behavior()
    {
        status = EStatus.Invalid;
    }
    //当进入该节点时才会执行一次的函数，类似FSM的OnEnter
    protected virtual void OnInitialize() {}

    //该节点的运行逻辑，会时时返回执行结果的状态，类似FSM的OnUpdate
    protected abstract EStatus OnUpdate();

    //当运行结束时才会执行一次的函数，类似FSM的OnExit
    protected virtual void OnTerminate() {}

    //节点运行，从中应该更能了解上述三个函数的功能
    //它会返回本次调用的结果，为父节点接下来的运行提供依据
    public EStatus Tick()
    {
        if(!IsRunning)
            OnInitialize();
        status = OnUpdate();
        if(!IsRunning)
            OnTerminate();
        return status;
    }

    //添加子节点
    public virtual void AddChild(Behavior child) {}
    
    //重置该节点的运作
    public void Reset()
    {
        status = EStatus.Invalid;
    }
    
    //强行打断该节点的运作
    public void Abort()
    {
        OnTerminate();
        status = EStatus.Aborted;
    }
}

2.组合节点

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

using System.Collections.Generic;

public abstract class Composite : Behavior
{
    protected LinkedList<Behavior> children;//用双向链表构建子节点列表
    public Composite()
    {
        children = new LinkedList<Behavior>();
    }
    //移除指定子节点
    public virtual void RemoveChild(Behavior child)
    {
        var res = children.Find(child);
        if(res != children.Last)
        {
            children.Remove(res);
        }
    }
    public void ClearChildren()//清空子节点列表
    {
        children.Clear();
    }
    public override void AddChild(Behavior child)//添加子节点
    {
        //默认是尾插入，如：0插入「1，2，3」中，就会变成「1，2，3，0」
        children.AddLast(child);
    }
}

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

1.顺序器

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

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

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

2.选择器

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

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

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

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

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

3.并行器

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

可这样就有问题了：

1. 怎么「同时」运行，要用多线程吗？
2. 同时执行必然会返回多个结果，该如何确定最终返回运行结果呢？

对于问题1，是不用多线程的，我们只要在一帧中把所有子节点都执行一次，就算是「同时」执行了。
对于问题2，我们可以根据需求自行设置并行器成功或失败的标准，一般可分为「全都」和「只要有一个」。
看看代码就知道了：

public class Parallel : Composite
{
    protected Policy mSuccessPolicy;//成功的标准
    protected Policy mFailurePolicy;//失败的标准
    /// <summary>
    /// Parallel节点成功与失败的要求，是全部成功/失败，还是一个成功/失败
    /// </summary>
    public enum Policy
    {
        RequireOne, RequireAll,
    }
    //构造函数初始化时，会要求给定成功和失败的标准
    public Parallel(Policy mSuccessPolicy, Policy mFailurePolicy)
    {
        this.mSuccessPolicy = mSuccessPolicy;
        this.mFailurePolicy = mFailurePolicy;
    }
    protected override EStatus OnUpdate()
    {
        int successCount = 0, failureCount = 0;//记录执行成功和执行失败的节点数
        var b = children.First;//从第一个子节点开始
        var size = children.Count;
        for (int i = 0; i < size; ++i)
        {
            var bh = 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 void OnTerminate()
    {
        foreach(var b in children)
        {
            if(b.IsRunning)
                b.Abort();
        }
    }
}

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

4.过滤器

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

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

public class Filter : Sequence
{
    public void AddCondition(Behavior condition)//添加条件，就用头插入
    {
        children.AddFirst(condition);
    }
    public void AddAction(Behavior action)//添加动作，就用尾插入
    {
        children.AddLast(action);
    }
}

5.主动选择器

假设，某人在沙漠荒野求生时，口渴了，迫不得已只能喝某代谢液体。但喝到一半突然出现了当地热心村民，并为他带来了一大桶甘甜的井水。那他会把剩下的“冰红茶”喝完后才接受村民的好意吗？

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

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

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

6.监视器

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

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

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

public class Monitor: Parallel
{
    public Monitor(Policy mSuccessPolicy, Policy mFailurePolicy)
     : base(mSuccessPolicy, mFailurePolicy)
    {
    }
    public void AddCondition(Behavior condition)
    {
        children.AddFirst(condition);
    }
    public void AddAction(Behavior action)
    {
        children.AddLast(action);
    }
}

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

3.修饰节点

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

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

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

1.取反器

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

它的实现也很简单：

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;
    }
}

2.重复执行器

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

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

public class Repeat : Decorator
{
    private int conunter;//当前重复次数
    private int limit;//重复限度
    public Repeat(int limit)
    {
        this.limit = limit;
    }
    protected override void OnInitialize()
    {
        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 class BehaviorTree
{
    public bool HaveRoot => root != null;
    private Behavior root;//根节点
    public BehaviorTree(Behavior root)
    {
        this.root = root;
    }
    public void Tick()
    {
        root.Tick();
    }
    public void SetRoot(Behavior root)
    {
        this.root = root;
    }
}

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

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

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

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

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

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

再添加同理：

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

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

通过AddBehavior和Back，我们就可以设置树的结构啦。什么？你问如果我又想给1添加子节点该怎么办？拜托￣へ￣，现在是编译阶段呢？你就直接在调用Back之前的代码里，加上给1节点添加子节点的代码呗。

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

public class Test0 : MonoBehaviour
{
    BehaviorTreeBuilder builder;
    private void Awake()
    {
        builder = new BehaviorTreeBuilder();
    }
    private void Start()
    {
        builder.Repeat(3)
                    .Sequence()
                        .DebugNode("Ok,")//由于动作节点不进栈，所以不用Back
                        .DebugNode("It's ")
                        .DebugNode("My time")
                    .Back()
                .End();
        builder.TreeTick();
    }
}

嗯？Repeat那些是什么？实际上就是对添加节点的包装，以下是该类的完整代码:

public partial class BehaviorTreeBuilder
{
    private readonly Stack<Behavior> nodeStack;
    private readonly BehaviorTree bhTree;
    public BehaviorTreeBuilder()
    {
        bhTree = new BehaviorTree(null);
        nodeStack = new Stack<Behavior>();
    }
    private void AddBehavior(Behavior behavior)
    {
        if (bhTree.HaveRoot)
        {
            nodeStack.Peek().AddChild(behavior);
        }
        else
        {
            bhTree.SetRoot(behavior);
        }
        if (behavior is Composite || behavior is Decorator)
        {
            nodeStack.Push(behavior);
        }
    }
    public void TreeTick()
    {
        bhTree.Tick();
    }
    public BehaviorTreeBuilder Back()
    {
        nodeStack.Pop();
        return this;
    }
    public BehaviorTree End()
    {
        nodeStack.Clear();
        return bhTree;
    }
    //---------包装各节点---------
    public BehaviorTreeBuilder Sequence()
    {
        var tp = new Sequence();
        AddBehavior(tp);
        return this;
    }
    public BehaviorTreeBuilder Seletctor()
    {
        var tp = new Selector();
        AddBehavior(tp);
        return this;
    }
    public BehaviorTreeBuilder Filter()
    {
        var tp = new Filter();
        AddBehavior(tp);
        return this;
    }
    public BehaviorTreeBuilder Parallel(Parallel.Policy success, Parallel.Policy failure)
    {
        var tp = new Parallel(success, failure);
        AddBehavior(tp);
        return this;
    }
    public BehaviorTreeBuilder Monitor(Parallel.Policy success, Parallel.Policy failure)
    {
        var tp = new Monitor(success, failure);
        AddBehavior(tp);
        return this;
    }
    public BehaviorTreeBuilder ActiveSelector()
    {
        var tp = new ActiveSelector();
        AddBehavior(tp);
        return this;
    }
    public BehaviorTreeBuilder Repeat(int limit)
    {
        var tp = new Repeat(limit);
        AddBehavior(tp);
        return this;
    }
    public BehaviorTreeBuilder Inverter()
    {
        var tp = new Inverter();
        AddBehavior(tp);
        return this;
    }
}

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

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

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

内容到这也差不多了，个人其实还并没有正式用过这个行为树来做游戏 （所以出现问题请狠狠地拷打我，我倒也不是嫌弃它（毕竟买不起插件捏இ௰இ，好歹有个能用的），只是还有其它的行为决策方法我比较青睐，比如「分层任务网络（HTN）」，个人就用的比较多。在我个人的一些游戏中就有使用到，有时间的话，也可以和大家交流下它的运行和实现。

完毕！\ (￣︶￣*\ ))

本栏目推荐文章
• 微软企业库Unity学习笔记(一)
• 微软企业库Unity学习笔记(二)
• 认知行为疗法-中对认知的理解
• 如何让Visual Studio Tools for Unity插件用于调试你自己的Mono嵌入应用程序
• Unity 获取当前系统时间并在UI界面中显示
• Dating Java8系列之通过行为参数化传递代码
• 【Unity】用Graphics.DrawMeshNow在场景中画个三角形
• 设计模式—行为型模式之状态模式
• Unity3d_Rewired官方文档翻译：要点（四）：Rewired Editor->All Maps、Layout Rules、Map Enabler
• Unity3d_Rewired官方文档翻译：要点（二）：Rewired Editor->Setting、Tools

行为 Unity行为unity 鸟群 鱼群 行为unity 行为 行为分析 行为wpf 行为eplan 行为 密码 消费行为 vuerouter行为 行为htn