事件队列

游戏设计模式Decoupling Patterns

意图

解耦消息或事件的发送时间和处理它的时间。

动机

除非还住在少数几个没通网的石头底下，否则你很可能已经听说过“事件队列”了。 如果没有，也许“消息队列”、“事件循环”或“消息泵”能让你觉得耳熟。 为了唤醒你的记忆，让我们了解几个此模式的常见应用吧。

GUI事件循环

如果你做过任何用户界面编程，就会对事件再熟悉不过了。 每当用户与你的程序交互——点击按钮，下拉菜单，或者按个键——操作系统就会生成一个事件。 它会将这个对象扔给你的应用程序，你的工作就是获取它然后将其与有趣的行为相挂钩。

为了接收这些消息，在你代码深处的某个地方有一个事件循环。它大体上是这样的：

while (running)
{
  Event event = getNextEvent();
  // 处理事件……
}

调用getNextEvent()会将一点未处理的用户输入拉入你的应用程序。 你将它导向事件处理器，之后应用就像被施了魔法一样活了过来。 有趣的部分是应用在它想要的时候获取事件。 当用户敲打外设时，操作系统不会立即跳转到你应用中的某处代码。

这就意味着当用户输入进来时，它需要到某处去， 这样操作系统在设备驱动报告输入和应用去调用getNextEvent()之间不会漏掉它。 这个“某处”是一个队列。

一个事件队列。操作系统入队Shift键，下方向键，上方向键，以及点击事件，getNextEvent()函数可以让它们出队。

当用户输入抵达时，操作系统将其添加到未处理事件的队列中。 当你调用getNextEvent()时，它从队列中获取最旧的事件然后交给应用程序。

中心事件总线

大多数游戏不是像这样事件驱动的，但游戏拥有自己的事件队列作为其神经系统的骨干是很常见的。 你通常会听到用“中心”、“全局”或“主”来描述它。 它被用于想要保持解耦的游戏系统之间的高层通信。

假设游戏有新手教程系统，在某些特定游戏事件后显示帮助框。 举个例子，当玩家第一次干掉一只邪恶的小怪兽，你想要一个显示着“按X拿起战利品！”的小气泡。

你的游戏玩法和战斗代码本身可能已经够复杂了。 你最不想做的就是在里面塞进一堆触发教程的检查。 相反，你可以使用中心事件队列。 任何游戏系统都可以发事件给队列，这样战斗代码可以在砍倒敌人时发出“敌人死亡”事件。

类似地，任何游戏系统都能从队列接收事件。 教程引擎在队列中注册自己，然后表明它想要收到“敌人死亡”事件。 用这种方式，敌人死了的消息从战斗系统传到了教程引擎，而不需要这两个系统直接知道对方的存在。

一个战斗代码和教程代码都可以读写的中心事件队列。

我本想把这个作为本章其余部分的例子，但我一般不喜欢这样庞大的全局系统。 事件队列不必用于在整个游戏引擎的各部分之间通信。它们在单个类或领域内也同样有用。

你说什么？

所以说点别的，让我们给游戏加点声音吧。 人类主要是视觉动物，但听觉与我们的情感和对物理空间的感知紧密相连。 正确模拟的回声可以让漆黑的屏幕感觉上是巨大的洞穴，而一段时机恰好的小提琴慢板能让你的心弦产生共鸣。

为了让游戏变得有声有色，我们从最简单的解决方法开始，看看结果如何。 添加一个小小的“音频引擎”，其中有使用标识符和音量就可以播放声音的API：

class Audio
{
public:
  static void playSound(SoundId id, int volume);
};

它负责加载合适的声音资源，找到可用的频道来播放它，然后启动它。 这章不是关于某个平台真实的音频API，所以我会变出一个API，并假设它在别处已经实现了。 使用它，我们像这样写方法：

void Audio::playSound(SoundId id, int volume)
{
  ResourceId resource = loadSound(id);
  int channel = findOpenChannel();
  if (channel == -1) return;
  startSound(resource, channel, volume);
}

我们签入以上代码，创建一些声音文件，然后像神奇的音效小仙女一样，在代码库中到处撒满playSound()调用。 举个例子，在UI代码中，当选中菜单项改变时，我们就播放一小声“啵”：

class Menu
{
public:
  void onSelect(int index)
  {
    Audio::playSound(SOUND_BLOOP, VOL_MAX);
    // 其他代码……
  }
};

这样做了之后，我们注意到有时候你改变菜单项目，整个屏幕就会冻住几帧。 我们遇到了第一个问题：

我们的playSound()方法是同步的——直到扬声器里传出“啵啵”声，它才会返回调用者。 如果声音文件要从光盘上加载，那就得花费一定时间。 与此同时，游戏的其他部分被卡住了。

先把这个放一边，我们继续。 在AI代码中，我们增加了一个调用，在敌人承受玩家伤害时发出痛苦的哀嚎。 没有什么比在虚拟的生物身上施加痛苦更能温暖玩家心灵的了。

这能行，但是有时英雄使出强力攻击，会在同一帧击中两个敌人。 这让游戏同时要播放两遍哀嚎。 如果你了解一些音频的知识，那么就知道要把两个不同的声音混合在一起，就要加和它们的波形。 当这两个是同一波形时，它与一个声音播放两倍响是一样的。那会很刺耳。

在Boss战中有个相关的问题，当有一堆小怪跑动并制造混乱时。 硬件只能同时播放一定数量的声音。当数量超过限度时，声音就被忽视或者切断了。

为了处理这些问题，我们需要审视声音调用的整个集合，对它们进行聚合和排定优先级。 不幸的是，音频API独立处理每一个playSound()调用。 它就像通过针眼观察请求，一次只能看到一个。

与接下来落到我们头上的问题相比，这些问题只是小烦恼。 到现在为止，我们已经把playSound()调用撒满了代码库中许多不同的游戏系统。 但是游戏引擎是在现代多核机器上运行的。 为了使用多核带来的优势，我们将系统分散在不同线程上——渲染在一个，AI在另一个，诸如此类。

由于我们的API是同步的，它在调用者的线程上运行。 当从不同的游戏系统调用时，我们从多个线程同时使用API。 看看示例代码，能找出任何线程同步吗？反正我是找不着。

这尤其糟糕，因为我们本来打算为音频分配一个单独的线程。 当其他线程都忙着互相踩来踩去、把事情搞得一团糟时，它却完全闲置地待在那里。

音频引擎把对playSound()的调用理解为“放下所有事情，现在就播放声音！”。立即就是问题所在。 其他游戏系统在它们方便时调用playSound()，但这不一定是音频引擎方便处理该请求的时候。 为了解决这点，我们需要将接收请求和处理请求解耦。

模式

队列以先入先出的顺序存储一系列通知或请求。 发送通知时，将请求放入队列并返回。 处理请求的系统之后稍晚从队列中获取请求并处理。 这解耦了发送者和接收者，既静态又在时间上。

何时使用

如果你只是想解耦消息的接收者和发送者，像观察者模式 和命令模式都可以用较小的复杂度进行处理。 只有当你想要在时间上解耦某些东西时，才需要队列。

用推和拉来考虑。 有一块代码A需要另一块代码B去做些事情。 对A自然的处理方式是将请求推给B。

同时，对B自然的处理方式是在它运行周期中方便的时刻将请求拉入。 当一端有推模型另一端有拉模型，你需要在它们之间设置缓冲区。 这就是队列比简单的解耦模式多提供的部分。

队列把控制权交给了从中拉取的代码——接收者可以延迟处理、合并请求或完全丢弃它们。 但队列做这些事是通过将控制权从发送者那里拿走完成的。 发送者能做的只是把请求扔进队列，然后听天由命。 当发送者需要回复时，队列不是好的选择。

记住

与本书中一些更朴素的模式不同，事件队列很复杂，往往会对游戏架构产生广泛影响。 这就意味着你得仔细考虑如何——或者要不要——使用它。

中心事件队列是一个全局变量

这个模式的一个常见用途是充当某种“纽约中央车站”，游戏的所有部分都可以通过它传递消息。 这是一块强大的基础设施，但是强大并不总是意味着好。

这花了不少时间，但我们大多数人都是吃过苦头才明白全局变量不是好东西。 当有一块状态可被程序的任何部分随意摆弄时，各种微妙的相互依赖就会悄悄出现。 这个模式将状态封装在一个不错的小协议里，但是它还是全局的，仍然带着随之而来的全部危险。

世界的状态可能在你脚下改变

假设在某个虚拟小怪一命呜呼时，一些AI代码将“实体死亡”事件发送到队列中。 这个事件在队列里待了不知多少帧，直到最终排到最前面并被处理。

同时，经验系统想要追踪女英雄的杀敌数，并奖励她可怕的效率。 它接收每个“实体死亡”事件，确定被击杀实体的种类以及击杀难度，以便发放合适的奖励。

这需要游戏世界的多种不同状态。 我们需要死亡的实体，才能知道它有多难对付。 我们也许想检查它的周围，看看附近还有什么障碍物或小怪。 但是如果事件直到稍后才被接收，这些东西可能已经消失了。 实体可能已被释放，附近的其他敌人也可能已经走开。

当你收到事件时，得小心，不能假设当前的世界状态反映了事件被触发时的世界状态。 这就意味着排队的事件往往比同步系统中的事件携带更多数据。 对于后者，通知只需说“某事发生了”，接收者可以四处查看细节。 使用队列时，这些短暂的细节必须在事件发送时就被捕获，以方便之后使用。

你可能会陷入反馈循环

任何事件系统和消息系统都得担心环路：

  1. A发送了一个事件
  2. B接收然后发送事件作为回应。
  3. 这个事件恰好是A关注的，所以它收到了。为了回应，它发送了一个事件。
  4. 回到 2。

当消息系统是同步的，你很快就能发现循环——它们造成了栈溢出并让游戏崩溃。 使用队列时，异步性会展开栈，所以即使多余的事件在队列里来回晃荡，游戏仍然可以继续运行。 避免这个的通用方法就是避免在处理事件的代码中发送事件。

示例代码

我们已经看到一些代码了。它不完美，但是有正确的基本功能——我们想要的公共API和正确的底层音频调用。 剩下需要做的就是修复它的问题。

第一个问题是我们的API是阻塞的。 当一段代码播放声音时，在playSound()完成加载资源并真正让扬声器震动之前，它不能做任何其他事情。

我们想要推迟这项工作，这样 playSound() 可以很快地返回。 为了达到这一点，我们需要具体化播放声音的请求。 我们需要一个小结构来存储待处理请求的细节，这样我们就能把它保留到以后使用：

struct PlayMessage
{
  SoundId id;
  int volume;
};

接下来，我们需要给Audio一些存储空间来追踪这些待处理的播放消息。 现在，你的算法教授也许会告诉你用上激动人心的数据结构， 比如Fibonacci heap或者skip list，或者，老天，至少用个链表吧。 但在实践中，存储一堆同类事物的最好方法几乎总是一个普通的老式数组：

所以让我们开干吧：

class Audio
{
public:
  static void init()
  {
    numPending_ = 0;
  }

  // 其他代码……
private:
  static const int MAX_PENDING = 16;

  static PlayMessage pending_[MAX_PENDING];
  static int numPending_;
};

我们可以调整数组大小以覆盖最坏的情况。 为了播放声音，简单地将新消息插到最后：

void Audio::playSound(SoundId id, int volume)
{
  assert(numPending_ < MAX_PENDING);

  pending_[numPending_].id = id;
  pending_[numPending_].volume = volume;
  numPending_++;
}

这让playSound()几乎是立即返回，当然我们仍得播放声音。 那段代码需要放在某个地方，而那个地方就是update()方法：

class Audio
{
public:
  static void update()
  {
    for (int i = 0; i < numPending_; i++)
    {
      ResourceId resource = loadSound(pending_[i].id);
      int channel = findOpenChannel();
      if (channel == -1) return;
      startSound(resource, channel, pending_[i].volume);
    }

    numPending_ = 0;
  }

  // 其他代码……
};

现在，我们需要从某个方便的地方调用它。 这个“方便”取决于你的游戏。 它可能意味着从主游戏循环中调用，或从一个专用的音频线程调用。

这可行，但是这假定了我们在对update()的单一调用中可以处理每个声音请求。 如果你做了像在声音资源加载后处理异步请求的事情，这就没法工作了。 为了让update()一次处理一个请求，它需要能在从缓冲区中拉出请求的同时保留其余部分。 换言之，我们需要一个真实的队列。

环形缓冲区

有很多种方式能实现队列，但我最喜欢的是环形缓冲区。 它保留了数组的所有优点，同时能让我们不断从队列的前方移除事物。

现在，我知道你在想什么。 如果我们从数组的前方移除东西，不是需要将所有剩下的部分都移动一次吗？这不是很慢吗？

这就是当年老师逼我们学链表的原因——你可以从链表中移除节点，而无需移动其他东西。 好吧，其实你可以用数组实现一个队列而无需移动东西。 我会带你走一遍，但是首先让我们明确一些术语：

由于 playSound() 向数组的末尾添加了新的请求，头部开始指向元素0而尾部向右增长。

一数组事件。头部指向第一个元素，尾部向右增长。

让我们开始编码。首先，我们稍微调整一下字段，让这两个标记在类中显式化：

class Audio
{
public:
  static void init()
  {
    head_ = 0;
    tail_ = 0;
  }

  // 方法……
private:
  static int head_;
  static int tail_;

  // 数组……
};

在 playSound() 的实现中，numPending_被tail_取代，但是其他都是一样的：

void Audio::playSound(SoundId id, int volume)
{
  assert(tail_ < MAX_PENDING);

  // Add to the end of the list.
  pending_[tail_].id = id;
  pending_[tail_].volume = volume;
  tail_++;
}

更有趣的变化在update()中：

void Audio::update()
{
  // 如果这里没有待处理的请求
  // 那就什么也不做。
  if (head_ == tail_) return;

  ResourceId resource = loadSound(pending_[head_].id);
  int channel = findOpenChannel();
  if (channel == -1) return;
  startSound(resource, channel, pending_[head_].volume);

  head_++;
}

我们处理头部的请求，然后通过将头部指针向右移动来丢弃它。 我们通过查看头部和尾部之间是否有距离来检测空队列。

现在，我们获得了一个队列——我们可以向尾部添加元素，从头部移除元素。 不过这里有个明显的问题。随着请求经过队列，头部和尾部不断向右爬行。 最终tail_碰到了数组的尾部，欢乐时光结束了。 妙就妙在这里。

像之前一样的数组，但是现在头部在向右移动，在左侧留下空白格子。

注意当尾部移动时，头部 也是如此。 这就意味着在数组开始部分的元素不再被使用了。 所以我们所做的就是，当尾部越过末尾时，把它绕回到数组的开头。 这就是为什么它被称为环形缓冲区，它表现得像是一个环形的数组。

数组绕了一圈，现在头部可以回到开始时指向的地方了。

实现这个非常简单。 当我们入队一个项目时，只需要确保尾部在到达末尾时绕回到数组的开头：

void Audio::playSound(SoundId id, int volume)
{
  assert((tail_ + 1) % MAX_PENDING != head_);

  // 添加到列表的尾部
  pending_[tail_].id = id;
  pending_[tail_].volume = volume;
  tail_ = (tail_ + 1) % MAX_PENDING;
}

用对数组大小取模的增量替换tail_++，就能把尾部绕回来。 另一个改变是断言。我们得保证队列不会溢出。 只要队列中的请求少于MAX_PENDING个，头部和尾部之间就会有一小段未使用的单元间隙。 如果队列满了，这些空隙就会消失，尾部会像一条倒着转的古怪衔尾蛇一样撞上头部，然后开始覆盖它。 断言保证了这不会发生。

在update()中，头部也绕回了：

void Audio::update()
{
  // 如果没有待处理的请求，就啥也不做
  if (head_ == tail_) return;

  ResourceId resource = loadSound(pending_[head_].id);
  int channel = findOpenChannel();
  if (channel == -1) return;
  startSound(resource, channel, pending_[head_].volume);

  head_ = (head_ + 1) % MAX_PENDING;
}

这样就好了——一个没有动态分配、不用搬移元素、拥有简单数组的缓存友好性的队列完成了。

合并请求

现在有队列了，我们可以转向其他问题了。 首先，多个播放同一声音的请求最终会导致声音过大。 由于我们知道哪些请求在等待处理，需要做的所有事就是：如果请求与某个已经待处理的请求匹配，就把它合并掉：

void Audio::playSound(SoundId id, int volume)
{
  // 遍历待处理的请求
  for (int i = head_; i != tail_;
       i = (i + 1) % MAX_PENDING)
  {
    if (pending_[i].id == id)
    {
      // 使用较大的音量
      pending_[i].volume = max(volume, pending_[i].volume);

      // 无需入队
      return;
    }
  }

  // 之前的代码……
}

当我们收到两个播放同一声音的请求时，把它们合并成单个请求，保留其中音量最大的那个。 这种“聚合”相当原始，但是我们可以用同样的思路做很多有趣的批处理。

注意在请求入队时合并，而不是处理时。 这对队列来说更轻松，因为我们不会在最终会被合并的多余请求上浪费槽位。 实现起来也更简单。

然而，这确实把处理负担放到了调用者肩上。 对playSound()的调用返回前会遍历整个队列。 如果队列很长，那么会很慢。 在update()中合并也许更加合理。

这里有些要记住的要点。 我们能够聚合的“同时”请求窗口只有队列那么大。 如果我们处理请求更快、队列保持较小，那么我们把事情合并在一起的机会就更少。 同样地，如果处理慢了，队列满了，我们能找到更多的东西合并。

这个模式让请求者不必知道请求何时被处理，但当你把整个队列当作一个可以摆弄的活数据结构时，发出请求和处理请求之间的延迟就会明显影响行为。 在做这件事之前，确保你能接受这一点。

跨越线程

最后，最棘手的问题。 使用同步的音频API，调用playSound()的线程就是处理请求的线程。 这通常不是我们想要的。

在当今的多核硬件上，你需要不止一个线程来充分发挥芯片的能力。 在线程间分配代码的方法有无数种，但一个常见的策略是把游戏的每个领域都放到各自的线程上——音频、渲染、AI等等。

现在我们有了三个关键部分，可以很好地做到这一点：

  1. 请求音频的代码与播放音频的代码解耦。
  2. 有一个队列在两者之间进行传递。
  3. 队列与程序其余部分是封装的。

剩下要做的事情就是写修改队列的方法——playSound()和update()——使之线程安全。 通常，我会写点具体代码来完成这件事，但既然这是一本关于架构的书，我不想陷入某个特定API或锁机制的细节。

从高层看来，我们只需保证队列不会被并发修改。 由于playSound()只做很少的工作——基本上只是给几个字段赋值——它可以加锁而不会长时间阻塞处理。 在update()中，我们等待条件变量之类的东西，这样在有请求要处理之前就不会浪费CPU周期。

设计决策

很多游戏把事件队列作为其通信结构的关键部分，你可以花大量时间为消息设计各种复杂的路由和过滤。 但是，在你动手去造一座洛杉矶电话交换机那样的庞然大物之前，我劝你先从简单的开始。这里有几个起步时需要思考的问题：

队列中存储了什么？

到目前为止，我交替使用“事件”和“消息”，因为大多时候两者的区别并不重要。 无论你在队列中塞什么，都能获得相同的解耦和聚合能力，但两者存在一些概念上的差异。

谁能从队列中读取？

在例子中，队列是封装的，只有Audio类可以从中读取。 在用户界面的事件系统中，你可以随心所欲地注册监听器。 你有时会听到用术语“单播”和“广播”来区分它们，这两种风格都很有用。

谁能写入队列？

这是前一个设计决策的另一面。 这个模式适用于所有可能的读/写配置：一对一，一对多，多对一，多对多。

对象在队列中的生命周期如何？

使用同步通知时，直到所有接收者都处理完消息，执行才会返回到发送者。 这意味着消息本身可以安全地存在栈的局部变量中。 使用队列，消息比让它入队的调用活得更久。

如果你用的是带垃圾回收的语言，就不用太担心这一点。 把消息塞进队列，只要还需要它，它就会一直留在内存中。 而在C或C++中，得由你来保证对象活得足够长。

参见