游戏AI与行为树

游戏AI介绍

游戏场景内有很多不由玩家操纵的实体，一般称之为non-player character，简写为我们常见的NPC。通常可以分为剧情NPC、战斗NPC和服务NPC等，有时也会有兼具多种功能的NPC。NPC与玩家之间是存在交互的，否则就跟场景里放置的静态组件没有差别了。这些交互都是为此NPC的设计目的服务的，最简单的交互就是出现若干按钮来提供购买、维修、寄存等服务。再进一步的交互就是根据预设的事件来触发NPC的特定表演，例如商贩NPC在下雨开始后播放收摊动作并消失，打更NPC按照既定路线巡逻并定期执行时间播报。当交互进一步演化时就会将玩家考虑进来，例如常见的怪物也是NPC的一种，他们与玩家是敌对关系，当玩家进入其战斗范围之后将触发怪物进入战斗状态，开始攻击玩家直到一方死亡。这个控制NPC与玩家之间交互的系统称之为游戏AI。

在AI逻辑比较简单的时候，我们可以直接用代码来实现NPC的逻辑驱动，以上面介绍的商贩NPC为例，其逻辑实现可以简化为下面的代码:

class pedlar: public npc
{
   bool m_is_hiding = false;
   void tick(float delta)
   {
      if(m_is_hiding)
      {
         if(check_is_raining())
         {
            play_hide_animation();
            add_invisible_buff();
            m_is_hiding = true;
         }
      }
      else
      {
         if(!check_is_raining())
         {
            m_is_hiding = false;
            remove_invisible_buff();
            play_unhide_animation();
         }
      }
   }
}

简单的AI可以通过编写针对性的代码来实现，但是当AI配置逐渐复杂之后，这种由代码写死的游戏逻辑就会变得非常难以维护。所以基本上所有的游戏AI实现都是由代码提供一些基础接口，然后基于AI任务配置文件来驱动NPC的交互表现。为了统一化所有NPC的交互表现配置，一般会把游戏AI拆分为三个部分：

感知部分这部分负责接收玩家的交互指令以及感知周围环境的信息，天气变化、时间变化、警戒范围内的玩家进出都属于交互指令，周围有哪些玩家及相应的血量信息属于环境信息，这些感知的查询一般是底层提供好若干接口来方便调用
决策部分这部分负责根据环境状态来决定当前的任务是什么，例如接收到天在下雨的事件之后商贩要决定收摊，深夜来临之后更夫要开始巡逻，玩家进入境界圈之后怪物要开始战斗，决策部分的实现一般使用的是状态机
行为部分则部分负责推动任务的表现，商贩收摊时需要播放收摊动画然后在让自己隐身，更夫巡逻时要按照路径进行移动并定期报时，怪物战斗时要追逐玩家并释放技能，行为部分的实现一般使用的是行为树

游戏AI中的状态机

状态机在游戏AI中是最容易被理解的概念，他用来维护NPC的行为模式以及模式之间的切换。举个例子来说，常见怪物的状态机有三种状态：

patrol状态，用来处理怪物的巡逻，这个是状态机的默认状态
fight状态，用来处理遇到敌人的战斗
return状态，用来处理战斗结束之后的处理，例如先回到出生点，然后重置AI来重新以默认状态开始执行

在这个小怪的跳转表，主要处理两个事件enter_battle和exit_battle：

patrol状态遇到enter_battle事件切换到fight状态
fight状态遇到exit_battle事件切换到return 状态

这样一个基本的小怪AI就配置完成了。

关于状态机的具体实现，我们在之前谈论过了，这里便不再详解。不过游戏AI里的状态机与之前谈论过的登录状态机又有很多不一样的地方。其中最大的差异点就是游戏AI的状态机都是由数据文件进行配置的，状态之间的切换以及状态内的行为都是由这些数据文件来指定的。而登录状态机则是在代码里写死的，通过代码即可阅读出登录状态机里的各个状态切换逻辑。游戏AI状态机由于其灵活性，继续使用Excel来创建状态转换矩阵这种做法感觉有点不够直观，所以一般都会有专用的状态机编辑器来实现状态机的查看与编辑功能：

状态机编辑

有了这个状态机编辑器之后，我们就可以很方便的看出每个状态之间是否有联系，对应的转换规则是什么。

不过当状态集合变得非常大之后，即使有状态机编辑器我们也很难进行状态的维护，整个状态切换成网状之后就是神仙难救：

复杂状态机

这个时候就需要将若干相似状态进行归类成组，组内的状态机节点只需要考虑与同组之间的状态切换，然后组内的所有节点共享相同的到其他组的状态切换，这种有分组的状态机就是层次状态机：

层次状态机

基于行为树的AI

行为树概念

行为树(behavior tree)的概念最早来源halo这款游戏里的ai控制结构，它通过类似于决策树的树形决策结构来选择当前环境下应该做出的具体行为。由于这种ai控制结构在配置、调试、复用之上的便利，行为树的使用也逐渐成为了现在游戏的主流ai配置方式。unreal现在自带了行为树功能，而unity也有很多行为树相关的插件。下图就是unreal中配置完成的一个简单的行为树结构：

ue行为树样例

行为树样例

下面我们来简单解释一下这颗行为树的功能。unreal的行为树的执行流是从上到下，从左到右，每个节点执行之后都会有相应的返回值true 或者false, 返回之后控制权转移给当前节点的父节点，来确定下一步的执行：

行为树在执行时的第一个入口是ROOT节点，所有的行为树都会有此root节点，当root节点执行完成之后，会重新开始一次执行，类似于无终止条件的循环。
进入root节点之后，进入Ai State这个Selector节点，依次从左到右执行他的三个子节点，当任一节点执行返回true的时候则不再执行后续的子节点，直接返回true给父节点。这个节点的逻辑就是让被控制的Entity进入追逐玩家状态还是进入巡逻状态。
chase player节点是一个sequence，这个节点被一个decorator节点修饰，导致只有在has line of sight返回true的时候才能进入执行，如果decorator返回false则执行流回到Ai State节点。它的三个子节点会从左到右依次执行，用来控制Entity去追打玩家的具体步骤：
1. Rotate to face BB entry，朝向目标
2. BTT_ChasePlayer 设置自己进入追击状态，追击速度为500
3. Move To，移动到敌人位置
所以这个状态内，被控制的Entity会首先朝向敌对目标，然后设置自己为速度500的追逐状态，追逐到目标之后，返回true, 如果其中任意一个节点返回false，则后续子节点不再执行，当前节点也返回false。
Patrol节点是一个不带decorator的Sequence，他执行的时候也是从左到右执行三个子节点：
1. BTT_FindRandomPatrol 设置自己为以自己为中心的随机巡逻状态，巡逻速度为125，巡逻半径为1000，获取半径上的一个随机点
2. Move To 移动上一个节点确定的位置
3. Wait 等待4-5秒
所以这个Patrol的执行内容就是，以125的速度走到以自身为中心的半径1000的圆的任意一点，走到之后等待4-5秒，然后返回。
最后的等待1s是为了两个状态都无法进入的时候的fallback，避免root节点空跑占用cpu。

行为树定义

整个行为树就类似于我们写的一个函数调用，他的树形结构就类似于传说中的图形化编程。一颗行为树最终运行时，还依赖于他的执行环境，例如范围内有没有目标就可以让这棵样例行为树控制的Entity呈现出不同的表现。这些行为树的运行环境，我们可以抽象为一个KeyValue的容器，叫做黑板Blackboard，代表行为树的内部存储的所有参数。当一颗行为树在特定的黑板环境中运行时，行为树的控制权不断地在树形结构中转移，类似于程序计数器Program Counter。运行时某一特定时刻的拥有控制权的节点集合则定义为行为树的格局Configuration。

因此一颗行为树的运行时描述，包括如下三个方面：

行为树的自身结构，所有节点的逻辑关系和相关参数： Structure
行为树的执行环境，一个键值对的集合： Blackboard
行为树的活动节点集合： Configuration

行为树的结构是以树的形式来组织的，每个节点都有相应的节点类型，配合相关参数承载不同的功能。在不同的行为树之中，对于节点的划分也是各有不同。总的来说，一个行为树的结构描述都具有如下几个部分：

行为树是一个树结构，根节点就是Root节点，作为行为树的入口，节点类型为Root,每个行为树有且只有一个Root类型节点；
所有的叶子节点的类型一定是Action，同时Action类型的节点一定不能作为非叶子节点来使用。
非叶子节点也称为组合节点Composition，可以有一个或多个子节点，Root节点一定只有一个子节点

Action节点类型和Composition的节点类型可以做进一步的细分。

每种类型的的组合节点能拥有的子节点数量与节点类型有关，一个节点的所有子节点是一个有序列表，有些节点可以附加特定参数来执行，有些节点则不需要参数。一颗行为树可以以叶子节点的形式被另外一颗行为树进行调用，就相当于一棵树挂接到了另外一棵树上一样。

行为树的运行

在明确了行为树的定义之后，行为树的控制表现还依赖于它在特定环境下的执行路径。为了推理行为树的执行路径，我们需要对行为树的运行规则做规定。这里我们把一个节点标记为N, 他的子节点列表标记为N.children，第i个子节点为N.children[i] ,他的父节点标记为N.parent，节点的运行标记为N.run()，运行完成之后返回true或者false，代表节点执行成功或者失败。

对于Action节点来说，因为他是叶子节点，不带控制功能，所以他是不影响执行流的。能影响执行流的节点只能是Composition节点。在具体的行为树节点类型定义中，常见的Composition节点细分见下：

Sequence节点，他的执行流程就是顺序执行所有的子节点，当一个子节点执行结果为false的时候终止执行并返回false，如果没有子节点返回false则返回true。他的run函数定义如下:

   bool run()
   {
   	for(std::uint32_t i = 0 ;i < children.size(); i++)
   	{
   		if(!children[i].run())
   		{
   			return false;
   		}
   	}
   	return true;
   }

Select节点，他的执行流程就是顺序执行所有的子节点，当一个子节点执行结果为true的时候终止执行并返回true，如果没有子节点返回true则返回false。他的run函数定义如下:

   bool run()
   {
   	for(std::uint32_t i = 0 ;i < children.size(); i++)
   	{
   		if(children[i].run())
   		{
   			return true;
   		}
   	}
   	return false;
   }

IfElse节点，他拥有三个子节点，当第一个子节点返回true的时候执行第二个子节点并返回此子节点的返回值，否则执行第三个节点并返回这个节点的返回值。他的run函数定义如下:

   bool run()
   {
   	if(children[0].run())
       {
           return children[1].run();
       }
       else
       {
           return children[2].run();
       }
   }

While节点，他有两个子节点，当第一个子节点执行返回true的时候，执行第二个子节点然后重新开始执行流程，如果第一个子节点返回false则执行完成，并返回true。他的run函数定义如下：

   bool run()
   {
       while(children[0].run())
       {
           children[1].run();
       }
       return true;
   }

Root节点，他只有一个子节点，当子节点返回的时候，返回子节点的返回值：

   bool run()
   {
      return children[0].run();
   }

在UnrealEngine的行为树定义中还有一类非常重要的Decorator节点，这个Decorator节点可以附着在任意非Root节点上作为被修饰节点的进入判定前置条件。这个Decorator的行为我们可以通过Sequence节点模拟出来，只需要将decorator里面的判断函数作为Action节点去执行，对于被任意装饰器修饰的节点都可以转换为含有装饰器判断节点和具体执行节点的Sequence节点进行替换。在Unreal中，他优先采用decorator方式的理由如下：

在行为树的标准模型中，条件语句是任务叶节点，除了成功和失败，它不会执行任何其他操作。虽然没有什么可以阻止您执行传统的条件语句任务，但是强烈建议使用我们的装饰器(Decorator)系统处理条件语句。使条件语句成为装饰器而非任务有几个显著的优点。

首先，条件语句装饰器使行为树UI更直观、更易于阅读。由于条件语句位于它们所控制的分支树的树根，如果不满足条件语句，您可以立即看到行为树的哪个部分是“关闭的”。

而且，由于所有的树叶都是操作任务，因此更容易看到行为树对实际操作的排序。在传统模型中，条件语句位于树叶之间，因此您需要花费更多的时间来确定哪些树叶是条件语句，哪些树叶是操作。

条件语句装饰器的另一个优点是，很容易让这些装饰器充当行为树中关键节点的观察者（等待事件）。这个功能对于充分利用行为树的事件驱动性质至关重要。

行为树的驱动方式

在标准行为树中，节点的运行是由tick-driven的，每间隔一段时间开始从root节点开始执行。当特定外部事件需要响应的时候，有时会按需调用root节点的执行。由于这个行为树在执行的时候，对于上次的执行结果是无记忆的，所以Entity的状态机要处理好各种追击、攻击、受击、巡逻状态的强制切换，避免表现异常。最坏情况下一次执行会遍历所有的节点，如果tick间隔过小，则行为树执行会消耗大量cpu。同时如果一段时间内执行的路径结果都相同，行为树就相当于空跑浪费cpu。所以在标准行为树模型里面，如何动态的选择tick间隔是优化的重点。

为了解决这种tick间隔带来的问题，行为树的模型演进出了基于事件驱动(event-driven)的行为树。这里行为树的更新不再是基于tick,而是基于任务的完成和外部事件的dispatch。同时每个Action节点开始有了状态，他的执行可能不再是调用之后立即返回，而是开始了一个需要一定时间才能执行的过程，当过程执行结束之后才返回执行结果。同时，任意的一个过程现在都需要支持中断操作，以支持外部环境的改变引发的更高优先级任务的处理。

以追逐目标这个例子来说：

在tick驱动的行为树中，我们需要定期从根节点执行，查询我们是否已经离目标点足够近，如果足够近则执行已经到达目标的分支，否则执行追逐逻辑。到发起追逐到追逐完成期间，可能多次执行行为树。
在事件驱动的行为树中，一旦进入了Move To节点，则会发起一个寻路过程，同时节点标记为running状态。在寻路到目标之后过程返回，控制权移交到当前节点的父节点，然后进行下一步的操作。一个完整的流程不涉及到行为树的其他节点，相对tick驱动的行为树来说，行为树的决策消耗大大降低了。

在寻路过程中，目标可能已经死亡或者传送了导致目标丢失，此时我们需要终止当前过程的执行。在事件驱动的行为树中，为了实现对外部事件的响应功能，常见的可选方案有如下两个：

为过程添加前置条件，在过程执行期间定期检查前置条件是否满足，如果不满足则中断当前过程的执行并返回false。
为行为树添加Parallel节点和WaitEvent节点，
1. Parallel节点执行时，会顺序执行所有的子节点，而不会阻塞在子节点的过程调用上，如果任一子节点返回，则所有的其他节点都会被打断，同时Parallel节点返回true。为了支持这个结构，我们需要对原有的行为树调用结构进行修正，因为这里暂时不再给出他的run函数定义。
2. WaitEvent节点执行时，会注册对特定事件的回调，然后阻塞不返回。当行为树接收到特定事件之后，对应的回调句柄被调用，相关的WaitEvent节点返回true。
通过在Parallel节点下同时挂载多个节点，就可以达到在执行特定过程的时候对外部事件进行响应的功能。

主流的行为树实现采用是Parallel方案，但是引入Parallel方案也带来了新的问题，就是策划可能配置出多个过程同时进行的Parallel节点。试想一下同时开启两个对不同目标点的寻路所带来的后果，Entity的状态表现会非常的糟糕。Parallel结构里面不能同时开启多个持续性过程，一般来说是一个主要目标过程附加一些WaitEvent或者WaitTimer的阻塞过程，这些附加的阻塞过程不会干扰主要目标过程，他们的执行也是一些辅助性的工作。

所以在Unreal中，特别提到了Simple Parallel节点。

简单平行节点只有两个子项：一个必须是单个任务节点（拥有可选的装饰器），另一个可以是完整的子树。可以将简单平行节点理解为“执行A的同时，也在执行B"。例如“攻击敌人，同时也朝敌人移动。“从基本上而言，A是主要任务，B是在等待A完成期间的次要任务或填充任务。

行为树与状态机

但是如果遇到了需要终止当前主要任务的事件，则Parallel结构也是不够用的。例如在巡逻过程中遇到敌人，我们需要立即进入战斗状态，此时需要中断当前任务的执行来开启新的任务。类似的还有在不断的放技能过程中如果发现自己的血量低于了特定百分比则进入狂暴状态。为了处理这种紧急事件的打断，实现方案是在行为树的上层加一个状态机来进行管理。

状态机有一个默认状态，在每个状态中执行特定任务的行为树，同时状态与状态之间有一个基于事件的跳转表。当Entity的AI接受到一个外部事件的时候，当前状态所执行的行为树优先处理这个事件，查看当前阻塞的WaitEvent的节点是否有对此事件的监听:

如果有，则行为树来处理这个事件
如果行为树没有对这个事件进行处理，则状态机来查看当前状态下是否有对于这个事件的新状态跳转。如果有对应的跳转，终止当前行为树的执行，跳转到对应的状态，开启新状态下的行为树的执行

行为树的黑板

行为树的流程控制节点的逻辑基本都是固定的，都是直接在代码中直接实现。而行为树的动作节点逻辑则是包罗万象各有不同，例如等待一段时间、移动到特定点、跟随特定目标、给自身加buff等。动作节点可能立即就执行完，也可能发起一个异步任务。而且这些动作节点基本都是需要传入一些参数去执行的，其参数个数与类型各不一样，例如等待一段时间节点需要一个浮点值作为等待的时间，移动到特定点这个节点需要两个参数，分别是目标坐标和目标半径。所以在实现动作节点的时候，一般会将动作节点的执行函数声明为这样的虚函数：

std::optional<bool> run(const std::vector<json>& args)

这里用vector<json>来存储这个节点执行所需的所有参数，然后返回值的optional<bool>可以表明当前节点是否立即返回，如果optional<bool>.has_value()为true则代表这是一个同步执行，否则代表这个节点发起了一个异步任务还未执行完。

确定好了执行函数的签名之后，我们需要继续考虑这些函数所需参数如何传递的问题。最简单的函数传递方式就是在行为树文件里提供好每个action节点所需的参数的json数组，但是这样的参数传值设计完全无法应对执行环境的动态性。例如移动到指定玩家的一定距离内这个节点需要两个参数，分别是目标玩家的id和到达半径radius。到达半径radius可以设置为一个经验值，例如150cm，但是目标玩家的id需要在运行时才能决定具体的值，在行为树编辑的时候我们完全无法确定其值到底是什么。所以这种在行为树编辑阶段就确定好所有节点的执行参数的设计是完全不可行的，我们需要一种传递运行时才能确定的参数值的方法。行为树黑板BlackBoard这个概念就自然而然的演化出来了，这个对象就是一个运行时变量存储的容器，其类型可以简单的抽象为map<string,json>。每个运行行为树的entity在执行行为树的时候都会创建一个BlackBoard对象，这个对象作为数值容器既可以被行为树内部节点来读写，也能被外部环境来读写，从而实现一种行为树内部与外部环境通信的机制。在有了黑板系统之后，函数参数的传递就分为了两种情况：

参数传入的值是立即值，即1, false, "hello"这种，在参数被求值时其字符串可以直接序列化为json的值
参数传入的值是黑板值，即一个字符串，代表这个值在黑板中的名字，当这个参数被求值时需要从黑板中以这个字符串作为key去获取对应值

此时我们需要对应的调整动作节点的执行，需要再封装一层run_wrapper来做传入参数的求职然后再调用到run函数:

struct action_arg
{
   std::string value;
   bool is_blackboard;
}

json get_blackboard(const std::string& key);

std::optional<bool> run_wrapper(const std::vector<actions_arg>& args)
{
   std::vector<json> real_args;
   for(const auto& one_arg: args)
   {
      if(one_arg.is_blackboard)
      {
         real_args.push_back(get_blackboard(one_arg.value));
      }
      else
      {
         real_args.push_back(json::parse(one_arg.value));
      }
   }
   return run(real_args)l
}

举个例子来说，行为树寻找仇恨最大目标并移动到其附近再攻击的逻辑可以通过黑板这样来实现：

store_combat_target_to_blackboard(action_arg{"target_key", false});
move_to_target(action_arg{"target_key", true}, 100);
hit_target(action_arg{"target_key", true})

这样我们就用黑板解决了运行时参数绑定的问题，同时在事件传递之外额外提供了一种外部来修改行为树运行逻辑的方式。

黑板概念还可以继续进行演化，例如群体黑板以及场景黑板：

群体黑板用来在一组NPC中共享，例如一组附近的怪物共享攻击目标，双boss战时的技能指令共享
场景黑板用来存储场景全局信息的以及一些全局状态改变通知

深入理解游戏服务端:从网络通信到无缝迁移