游戏AI行为决策——Behavior Tree（行为树）
- 作者：admin
- /
- 时间：昨天 10:17
- /
- 浏览：80 次
- /
- 分类：厚积薄发
【USparkle专栏】如果你深怀绝技，爱“搞点研究”，乐于分享也博采众长，我们期待你的加入，让智慧的火花碰撞交织，让知识的传递生生不息！
一、前言
行为树，是目前游戏中应用较为广泛的一种行为决策模型。这离不开它成熟的可视化编辑工具，例如Unity商城中的「Behaviour Designer」，甚至是虚幻引擎也自带此类编辑工具。而且它的设计逻辑并不复杂，其所利用的树状结构，很符合人的思考方式。
接下来，我们会先对它的运作逻辑进行介绍，然后再试图用代码实现它。树状结构在不借助可视化工具的情况下是不容易呈现清楚的，这里我借鉴了Steve Rabin的《Game AI Pro》1中行为树的实现方式，利用代码缩进稍稍实现了一些可视化（本教程使用C#代码实现）。下面我们就开始吧！
二、运动逻辑
1. 根节点驱动
如果你已经了解「有限状态机（FSM）」的话，你应该知道，有限状态机在运作时常常会停留在一个状态中，不断执行该状态的逻辑，直至接受到状态转移的指令才变化到其它状态。而行为树则是会不断从根节点向下搜索，即「根节点驱动」，来找到合适的「动作」执行，执行完毕后会再回到根节点重复这个过程。以下面这个「怪物攻击玩家」行为树为例：
假设「攻击」动作的逻辑是「向玩家挥一拳」，现在怪物发现玩家且玩家在攻击范围内。那么，按照行为树的逻辑，它会经过「战斗 ➡ 试图攻击 ➡ 攻击」一路下来，最终向玩家挥出一拳。
至此，「攻击」就算是完成了，若是在状态机中，攻击也算是一种状态的话，怪物必然会停留于此，等待下一帧时再挥出一拳。但在行为树中呢？它确实也会在下一帧时再挥出一拳，只是会再经过「战斗 ➡ 试图攻击 ➡ 攻击」这个过程，也就是前面所说的，从根节点再次出发。
你可能也发现了，这明显是多此一举的行为，它确实可以算是行为树的小缺点。但其实行为树的深度通常并不会太深，多几次布尔判断或小遍历倒也不打紧；而且有一种事件驱动的行为树实现方法，能以“空间换时间”的手段改善这种情况，感兴趣的同学可以去了解一下。
2. 特殊的节点
行为树的一大特点，就是将条件与行为本身进行了分离。
什么意思呢？我们仍以上面那张图为例，只是稍稍修改下表现方式（也更接近行为树真正的样子）：
好像多了几个圈？那现在，请你将这些圈也视为和「攻击」一样类型的节点。这样一来，我们将「判断逻辑」、「顺序遍历（图中的红色箭头）」、「动作」都用节点来表示了。这有什么好处呢？好处就在于我们可以将它们进行各种各样的组合！比如，如果有一个怪物比较胆小，遇到玩家后会逃跑，我们就可以用图中的「发现玩家」+「移动到该位置（逃跑的位置）」来实现；也可以配合新的节点来组合，比如「已知玩家最后出现的位置」+ 新节点：「朝指定位置开火」，就可以实现远程追击。
总之，正是因为行为树有一系列特殊的节点，使得开发者可以降低各个行为之间的关联（也就是解耦），再配合上树状结构的特点，开发者可以灵活地进行组装，实现节点的重复利用，避免写重复的代码，提高了开发效率。（用过有限状态机写游戏AI的同学一定能体会到这点的好处。）
三、代码实现
现在，我们就一起来实现行为树，先看看我们有哪些要实现的（它们的具体含义后面会解释）：
组合节点（Composite），指有多个子节点的特殊节点，具体包括：
a. 顺序器（Sequence）
b. 选择器（Selector）
c. 并行器（Parallel）
d. 过滤器（Filter）
e. 主动选择器（ActiveSelector）
f. 监视器（Monitor）修饰节点（Decorator），指仅有一个子节点的特殊节点，具体包括：
a. 取反器（Inverter）
b. 重复执行器（Repeat）动作节点，指可以自定义的节点，比如「攻击」、「巡视」之类的。
1. 基础准备
正式实现它们之前，我们应当准备它们的基类，毕竟它们都是节点，有一些共性的东西可以提取出来，这样可以减少一些重复的代码。
/// <summary>
/// 运行结果状态的枚举
/// </summary>
publicenumEStatus
{
//失败，成功，运行中，中断，无效
Failure, Success, Running, Aborted, Invalid
}
/// <summary>
/// 行为树节点基类
/// </summary>
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<Behavior> children;//用双向链表构建子节点列表
publicComposite()
{
children = newLinkedList<Behavior>();
}
//移除指定子节点
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<Behavior> 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，我们可以根据需求自行设置并行器成功或失败的标准，一般可分为「全都」和「只要有一个」。
看看代码就知道了：
public classParallel : Composite
{
protected Policy mSuccessPolicy;//成功的标准
protected Policy mFailurePolicy;//失败的标准
/// <summary>
/// Parallel节点成功与失败的要求，是全部成功/失败，还是一个成功/失败
/// </summary>
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<Behavior> nodeStack;//构建树结构用的栈
private readonly BehaviorTree bhTree;//构建的树
publicBehaviorTreeBuilder()
{
bhTree = newBehaviorTree(null);//构造一个没有根的树
nodeStack = newStack<Behavior>();//初始化构建栈
}
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<Behavior> nodeStack;
private readonly BehaviorTree bhTree;
publicBehaviorTreeBuilder()
{
bhTree = newBehaviorTree(null);
nodeStack = newStack<Behavior>();
}
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/
这是侑虎科技第1825篇文章，感谢作者狐王驾虎供稿。欢迎转发分享，未经作者授权请勿转载。如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群：793972859）
作者主页：https://home.cnblogs.com/u/OwlCat
再次感谢狐王驾虎的分享，如果您有任何独到的见解或者发现也欢迎联系我们，一起探讨。（QQ群：793972859）