超越有限状态机

作者:indienova
2016-04-14
13 36 0

导言

来自 Bethesda 的 Jean Simonet 是一名经验丰富的系统与 AI 程序员。在这篇文章中,他紧接上一篇文章的内容,继续探讨协程在游戏编程中的应用。本文已经过授权,如需转载,请注明原文和译文来源。

正文

本文是另一篇教程《凌驾时间的逻辑》的姐妹篇。在上一篇中,我介绍了为什么协程这样的新语言特性可以让游戏程序员编写出更健壮也更具可读性的有限状态机代码。而本文中,我们将深入研究协程的实现,谈及它的诸多特性及应用,这些内容将不仅仅局限于有限状态机本身。本文还会专门谈及并发与同步问题。

我已将文中的示例代码以 MIT 证书开源发布到了 GitHub 上,你可以随意地将其运用到自己的项目中。代码以 .NET 3.5 编写(这也是 Unity 支持的版本)。

Coroutines 代码示例

Jean Simonet 查看

首先,我们来通过一个例子演示一下协程卓越的可重用性。接着我们将深入研究该代码框架的实现,并解答一些在游戏代码中应用协程会遇到的普遍问题。

简单的炮塔

我们不妨先继续完善上一篇教程中曾出现过的炮塔,具体的代码参见 GitHub 库。

炮塔的行为概括说来如下所列:

它会搜寻指定半径范围内的目标(这里指一名玩家),当锁定目标后,它会同时做两件事:追踪目标以及发射炮弹。一旦追丢了目标(比方说玩家逃离了追踪半径范围),它会恢复默认朝向,并重新开始搜寻目标。下面是相关的代码片段,我们来深入剖析一番!

public class Turret
  : MonoBehaviour
{
  [...] // 检查器配置变量

  // 唯一的状态是根协程节点
  Coroutines.Corountine _Main;

  // 初始化
  void Start()
  {
    _Main = new coroutines.Corountine(Main());
  }

  // 每帧调用一次
  void Update()
  {
    // 更新根节点
    _Main.Update();
  }

  // 根协程节点
  IEnumerable Main()
  {
    // 存储默认的炮塔朝向,我们将会把该变量传入炮塔空闲时执行的协程
    float startYAngle = transform.rotation.eulerAngles.y;

    while(true)
    {
      // 搜寻目标
      Transform target = null;

      yield return ControlFlow.ExecuteWhileRunning(
        // 核心代码,搜寻目标并将其存放在 target 变量中
        FindTargetInRadius(_LockOnRadius, trgt => target = trgt),

	// 如果还处于搜寻状态就执行
	Idle(startYAngle));

      // 此处我们应当有一个非空的目标!
      // 追踪目标并朝它射击
      yield return ControlFlow.ExecuteWhile(
        // 条件
        () => Vector3.Distance(target.postion, transform.postion) < _LockOffRadius,

        // 条件为真时追踪目标
        TrackTarget(taget),

        // 条件为真时发射炮弹
        FireProjectiles());
    }
}

我们会先留意到 Main() 协程的类型是 IEnumerable。在上一篇教程中,我曾提及,该函数将生成迭代器代码块,并返回类型为 Coroutines.Instruction 的结果,正是函数返回的这些中间指令实现了框架的逻辑。

默认情况下,代码框架会枚举迭代器代码块,这是真正的协程代码执行的地方。这些逻辑只有在协程代码被生成(yield-ed)后才会执行。取决于具体的返回值,可能会执行一到多件事务。

示例中的 ControlFlow.ExecuteWhileRunning()ControlFlow.ExecuteWhile() 这两条指令显而易见属于控制流方法:主要用于在特定条件下执行其他协程(子协程)。我们利用 ExecuteWhile()Call() 来将协程组合起来使用,现在让我们稍微深入地研究一下它们的用法吧。

协程指令

为了理解这些协程指令的原理,我们先分析一个简单的例子:

static IEnumerable WaitForSecondsCr(float seconds)
{
    //等待一段时间过去
    float startTime = Time.time;
    while(Time.time - startTime < seconds)
    {
        yield return null;
    }
}    

这是一个用于延时的工具协程。一旦被调用,它会循环检查流逝的时间,同时生成(yield) null. 当经过传入参数所设时间后,它会直接中止。而 null 传达给代码框架的意思则是:“直到下一帧为止,请让程序保持休眠吧”。(请留神:这里出现的概念与 Unity 的协程完全一致,真方便啊!)

协程也能调用 Call 指令,用来传入其他协程。我们就是用这种方法(传入 FireProjectiles())实现了炮塔等待间歇时发射炮弹的功能。

IEnumerable Fireprojectiles()
{
    while(true)
    {
	// 创建一枚投掷物,使它移动并给予它向前的冲量!
	var proj = GameObject.Instantiate(_ProjectilePrefab);
	proj.transform.postion = _ProjectileExit.postion;
	proj.InitialForce = transform.forward * _ProjectileInitialVelocity;

	// 等待下一次发射
	yield return ControlFlow.Call(WaitForSecondsCr(1.0f));
    }
}

ControlFlow.Call(...)是一个会返回指令的派生类的工具方法,在代码框架中还有特别用途:这里它意味着“先执行参数所传入的协程(存放于指令中),等它结束后再继续执行原来的函数”。

正如你所期待的那般,还有返回其他不同功能的指令的控制流方法。ControlFlow.ExecuteWhile(...) 就是其中一例:

ExecuteWhile 指令会将一定数量的(子)协程和一个判断条件作为参数传入,这会告诉框架“如果满足判断条件就并行得执行所有的协程”。在深入研究该方法的代码前,我们来稍微回顾与解释一下运行时的原理。

永远都是图

框架在表象下构建了一个图形拓扑结构。运行时会先执行用户代码,直到用户代码生成指令,这时运行时就会转而执行对应的指令。根据用户代码所生成的指令不同,运行时会创建出许多种不同的子节点。最常见的是运行 IEnumerator 迭代器的协程节点。

Coroutine Runtime Graph

虽说图形拓扑的节点由用户代码来生成与储存,但我们仍然需要手动初始化一个根协程节点。在我们的例子中,根节点由炮塔类中的 _Main 方法声明。

public class Turret
  : MonoBehaviour
{
  [...] // 检查器配置变量

  // 唯一的状态是根协程节点
  Coroutines.Corountine _Main;

  // 初始化
  void Start()
  {
    _Main = new Coroutines.Corountine(Main());
  }

  // 每帧调用一次
  void Update()
  {
    // 更新根节点
    _Main.Update();
  }

  [...]

}

框架中并不存在全局的协程管理器。如果想要使用协程,你需要手动创建和更新实例。

接着,框架就能够依据用户代码生成的指令如期创建图形拓扑。如果用户指示它调用(Call)实例的子协程,运行时就会创建一个新的协程作为当前协程的子协程,并转而先执行它。

为了创建接口我们需要引入 ICoroutine 节点。

public interface ICoroutine
    : System.IDisposable  
{
    bool IsRunning { get; }
    void Update();
    void Reset();
}

一个基本的协程图节点应当能够实现如下几点功能:

  • 能够被更新,毋庸多言,这是实现功能必须的。
  • 能够指示它何时应当运行或中止,这个值可以用于决定是否返回到父协程节点。
  • 能够被重置,不管出现任何情况都能重置回默认的状态。
  • 能够被移除,这一点尤为关键,当这些节点完成其功能,我们需要它们以一种可预测的方式被移除。拥有这样的功能也能让节点池系统的实现变得更加容易,因为我们清楚直到不再使用的节点就会被自动删除掉。

协程节点

协程节点是整套代码框架的核心。节点正是用户代码被执行的地方。协助程节点也是解析我之前提到的那些“指令”的地方。用示意图来表示其关系:

Coroutine Child Node

实际使用时,它会存放下面这样的数据:

public class Coroutine
    : ICoroutine
{
    // 存放枚举变量资源
    IEnumerable _Source;

    // 存放协程的运行实例
    IEnumerable _StateData;

    // 存放生成的子节点
    ICoroutine _Subroutine;

    // 当前节点的状态
    enum CorountineState
    {
	[...] //存放是否使用迭代器,是否更新子协程状态等状态数据
    }

    CorountineState _ExecutionState;
}

协程节点只有在知道哪一个是最初的 IEnumerable 的时候才能在重置后恢复默认状态。理所当然的,它会存储 IEnumerator 来记录它所处的协程(而我们的目标正是让 IEnumerator 自动生成有限状态机)。这样,它至少需要两个成员变量:状态数据与子协程。

倘若控制流指令并没有生成其他协程并使框架创建子节点,那么默认状态下的子节点的值将会是 null。子节点不为 null 时,CallInstuction 指令(前文中我们介绍过它)的 Coroutine.Update() 方法会设置一个标志变量,指示框架暂时不执行迭代器(用户代码)而是创建并执行子节点中的方法。当子节点运行完毕后,标志变量会被复位,框架继续执行迭代器(用户代码)。多数情况下,子协程会创建一个同样基于迭代器的协程节点,但有时也会创建像 ExecuteWhile(...) 这样不同类型的节点。

循环节点(The While Node)

While Node

循环节点中应当包含下面两件东西:

  • 用于决定是否执行子节点的判断条件(换言之即某个返回布尔量的函数);
  • 子节点,只有才判断条件为真时才能正常运行。
// 只要主条件为真就运行子节点
// 只要主条件为假就停止运行子节点
public class While
    : ICoroutine
{
    System.Func _MasterCondition;
    ICoroutine _SlaveSubroutine; // 不必拥有状态,因为它不会被结束!

    enum WhileNodeState
    {
	Running,
	Complete,
	Disposed
    }

    WhileNodeState _CurrentState;

    [...]
}

循环节点也可以包含状态数据变量,但并非必须。循环节点中的状态数据主要用于明确节点的运行状态,以免需要反复查看主节点的判断条件。

循环节点中的 Update() 方法用途非常直观:循环节点会检查每次更新时的判断条件,如果返回值为真就运行子协程。否则,就中止子协程(通过调用 Dispose() 方法来重置到初始状态),并决定是否需要结束循环。

需要注意到的是,循环节点判断条件的时机并非是被调用之时,而是在每次更新之时。以我们的炮塔为例,你会发现传给循环节点的判断条件实际上是一个 lambda 表达式(称其为匿名闭包亦可)。

      // 此处我们应当有一个非空的目标!
      // 追踪目标并朝它射击
      yield return ControlFlow.ExecuteWhile(
        // 判断条件
        () => Vector3.Distance(target.postion, transform.postion) < _LockOffRadius,

        // 条件为真时追踪目标
        TrackTarget(taget),

        // 条件为真时发射炮弹
        FireProjectiles());
    }
}

ExecuteWhile() 是如何一次运行多个节点的呢? 下一节的内容将为你揭开这个秘密。

并行节点(The Concurrent Node)

ExecuteWhile() 是一个能够接受不定数量参数的工具方法(即所谓的可变长参数函数)。让我们来研究一下它的用法:

// 条件为真时,一次运行多个协程
public static CallInsturction ExecuteWhile(System.Func masterCondition,
       	      		      Params IEnumerable[] slaveSubroutines)
{
    // 创建一个并行节点,以传入子协程参数作为子节点
    // 当所有子节点结束运行后并行节点才会结束运行
    var subroutines = new List();
    foreach (var subroutineSource in slaveSubroutines)
    {
	subroutines.Add(new Corountine(subroutineSource));
    }
    var concurrentNode = new Concurrent(Utils.Any, subroutines);

    // 将并行节点和判断条件传入循环节点
    return new CallInstruction(new While(concurrentNode, masterCondition));
}

ExecuteWhile() 会像这样运行:首先,它会创建一个以多个子协程为参数的并行节点,接着,它会创建一个带判断条件的循环节点。最后,通过 CallInstruction 运行循环节点,先前创建的并行节点将作为循环节点的子节点。

简而言之,我们的 ExecuteWhile() 方法创建了一个如图所示的炮塔:

While Concurrent

是不是觉得这玩意儿看起来有点像行为树呢?没什么可奇怪的,我们就是在构建一个行为树。实际上,往上图中加入更多的节点也毫无难度,比方说,我们可以轻而易举地实现优先级节点。但是,首先我们还是继续深入研究一下并行节点吧,它可比一打眼看上去要复杂。嗯,比方说,图中的 Any() 代表着什么意思呢?

其实《驾驭时间的逻辑》一文对这个问题有过提示:只要开始考虑并行问题,就不可避免需要解决仲裁问题。我们首先需要回答的问题是:并行节点的“运行”状态究竟是指什么?只要它的子节点处于“运行”状态它就处于“运行状态”吗?还是只要有一个子节点结束它就也跟着结束呢?

显然需要分情况而定,得看我们到底想要哪种效果。因此,我们需要的是一种能够指定如何仲裁节点是否处于“运行”状态的方法。这正是 Any() 的职责所在。它会告诉协程节点,只要尚存运行的子节点,并行节点就应该保持运行。

Concurrent (ICoroutine)

IsRunning_Arbitration() 以布尔量数组为参数,返回值也是一个布尔量。而 ExecuteWhile() 的参数 Any() 的方法用途相当于 逻辑非。当然,实现其他行为也不复杂,比方说,指定只有当所有子协程都处于运行状态时才保持并行节点运行。

炮塔代码中一开始调用的 ExecuteWhileRunning(masterCoroutine, slaveCoroutine) 方法实际上也是一种特殊的循环节点,这种情况下,主节点的状态取决于是否运行子节点。

移除节点(Disposing Coroutines)

现在,我们已经大致了解了 ExecuteWhile() 的原理,那么,一旦我们停止更新子节点,会发生什么事呢?如果这个子节点会使用一些游戏素材(比如它实现的是一个粒子效果)又会怎么样呢?有办法让它自己中止吗?或者这个协程会一直滞留在内存的某个角落,直到迎来垃圾回收?

这就轮到 IDisposable 接口大显神威了(更具体点儿,是通过 C# 枚举器来实现的)。实际上,IDisposable 接口的实现是为了专门的用途。假如你使用了 IEnumerator 来读取文件,那么当你的代码执行完毕后,无论文件是否被完整读取,你都会希望可以确保文件已经被关掉。

因此,在设计 C# 迭代器时(这正是我们赖以实现协程和自动生成的有限状态机的基础),设计者发挥卓越的思路为我们提供了下列便利(引用自 MSDN 的文章):

如果你在迭代器中使用了 try ... finally 语法,那么 finnally 代码块会在下面的几种条件下运行:

  • 上一个 try 代码块被执行后(毫无稀奇之处);
  • 当出现了 try 中未能处理的异常;
  • 使用 yield break 中断了 try 代码块;
  • 迭代器被移除时正在运行 try 中的代码。

在枚举器尚未运行结束时就提前中止它就会出现最后一种情况。

总而言之,当我们移除迭代器时,finally 代码块就会被执行!并且,协程框架也会保证只有当节点被移除或者重置的时候才会出现上述情况,这样一来,我们就能保证,即使被意外中断,也有法子让用户代码重置回默认状态。

看看炮塔的代码,我们会留意到 TrackTarget() 协程看起来像这个样子:

IEnumerable TrackTarget(Transform target)
{
    // 追踪玩家时,打开追踪灯
    _TrackingLight.enabled = true;
    try
    {
	// 持续追踪目标
	while(true)
	{
	    // 确定指向目标的转角
	    Quaternion targetRot = Quaternion.LookRotation(target.position - transform.position, Vector3.up);
	    // 平缓地旋转炮塔
	    transform.rotation = Quaternion.RotateTowards(transform.rotation,
							  targetRot,
	    		       	 			  _MaxRotationSpeed * Time.deltaTime);
	    yield return null;
	}
    }
    finally
    {
	// 如果追踪过程被打断(比如玩家离开了追踪范围),就关掉追踪灯
	_TrackingLight.enabled = false;
    }
}

尽管这个协程看起来像是一个无限死循环,但是,当我们打开追踪灯后,我们还是可以确保在协程中止后能关掉它。

注意:千万别被关键词 finally 吓住,我们并没有触发什么异常。当然,抛出异常错误时,也会执行 finally 中的代码,但是,对于协程中止或结束的正常情况而言,这种写法并不会因为频繁调用异常栈而导致额外的开销。

根据需要使用多个 try/finally 或者嵌套使用也都不成问题,这样一来,我们就能够保证需要清理的数据都可以被重置成默认状态。

IEnumerable SomeCoroutine()
{
    // 创建游戏对象
    var go1 = GameObject.Instantiate(...);
    try
    {
	// 如果协程在延时时中断,只有 go1 会被清除
	yield return Utils.WaitForSeconds(3.0f);

	// 创建另一个游戏对象
	var go2 = GameObject.Instantiate(...);
	try
	{
	    while(true)
	    {
		// 如果正在执行该循环时协程中止,go1 与 go2 都会被清除
		[...]

		yield return null;
	    }
	}
	finally
	{
	    GameObject.Destroy(go2);
	}
    }
    finally
    {
        GameObject.Destroy(go1);
    }
}

向调用位置返回值

最后一项课题:协程应当如何向调用它们的语句返回数据。不幸的是,协程并不直接支持这项功能。(起码 .NET 3.5 并不支持 async/await 等特性)。虽说这非一件无足挂齿的小功能,但是,由于协程处理的大都是一些中间数据,因此也没必要过分强调它们的返回值。

为了向父协程返回数据,我们又得再一次依赖闭包的力量(或者说 lambda 表达式的力量)。留意之前的炮塔代码,特别是 FindTargetInradius() 协程的部分,我们可以看出它是基于什么原理。

IEnumerable FindTargetInRadius(float radius, System.Action targetFound)
{
    // 目前只有一个潜在的目标,因此...
    var playerObj = GameObject.FindGameObjectWithTag("Player");
    if (playerObj != null)
    {
	while (Vector3.Distance(playerObj.transform.postion, transform.postion) > radius)
	{
	    yield return null;
	}

	// 找到目标啦!
	targetFound(playerObj.transform);
    }
    // 其他需要留神的玩意儿...
}

FindTargetInRadius() 接受两个参数,其中一个为搜寻半径,另一个参数是返回 void 的函数,负责控制炮塔的动作。当找到目标后,它就会执行针对锁定目标的动作。这段代码位于 Main() 协程之中,如下所示:

        // 搜寻目标
	Transform target = null;

	yield return ControlFlow.ExecuteWhileRunning(
	    // 核心代码,搜寻目标并将其存放在 target 变量中
            FindTargetInRadius(_LockOnRadius, trgt => target = trgt),

	    // 如果还处于搜寻状态就执行
	    Idle(startYAngle));

你能看到,搜寻目标是一个局部变量,而 FindTargetInRadius() 的参数 Lambda 表达式也被赋给一个局部的变量。这种写法看起来有点绕弯,但这是编译器允许的一种简写方式,并不糟糕。

其他节点与应用

当然,这套框架真正的价值在于,通过简单的扩展与修改,它就能轻松满足许多游戏的开发需要。实际上,对那些希望学会如何开发基于图的复杂AI系统的人而言,这套框架是非常好的起点。它向我们展示了一套优雅的方案,让我们有机会探究怎样组合和同步游戏中的各种过程与行为。

今后的文章里,我还会更细致地讲解这方面的问题。行为图是目前相当流行的 AI 系统写法,而能够并发和同步执行的协程与之非常接近。今后我们还会介绍一些比较传统的 AI 系统写法,比如分级有限状态机。也会涉猎诸如投票算法,包容体系等其他 AI 系统的架构;总而言之,由异步代码构成的拓扑图正是所有这些架构的最佳表现方式。

原文刊载于GamaSutra