优化模式 | Fl0w3r

Twitter@Rgznsk_

引言

游戏开发一直是热门的领域，掌握良好的游戏编程模式是开发人员的应备技能，本书细致地讲解了游戏开发需要用到的各种编程模式，并提供了丰富的示例。本章关于优化模式的介绍。

虽然越来越快的硬件解除了大部分软件在性能上的顾虑，对游戏来说却并非如此。玩家总是想要更丰富、真实、激动人心的体验。到处都是争抢玩家注意力——还有金钱——的游戏，能将硬件的功能发挥至极致的游戏往往获胜。

优化游戏性能是一门高深的艺术，要接触到软件的各个层面。底层程序员掌握硬件架构的种种特质。同时，算法研究者争先恐后地证明谁的过程是最有效率的。

这里，我描述了几个加速游戏的中间层模式。数据局部性介绍了计算机的存储层次以及如何使用其以获得优势。脏标识帮你避开不必要的计算。对象池帮你避开不必要的内存分配。空间分区加速了虚拟世界和其中元素的空间布局。

数据局部性

意图

合理组织数据，充分使用CPU的缓存来加速内存读取。

动机

我们被欺骗了。他们一直向我们展示CPU速度每年递增的图表，就好像摩尔定律不是观察历史的结果，而是某种定理。无需吹灰之力，软件凭借着新硬件就可以奇迹般地加速。

芯片确实越来越快（就算现在增长的速度放缓了），但硬件巨头没有提到某些事情。是的，我们可以更快地处理数据，但不能更快地获得数据。

处理器和RAM的发展速度从1980开始不同。如你所见，CPU飞跃式发展，RAM读取速度被远远甩到了后面。
这个数据来自Computer Architecture: A Quantitative Approach 由John L. Hennessy, David A. Patterson, Andrea C. Arpaci-Dusseau基于Tony Albrecht的“Pitfalls of Object-Oriented Programming”写就。

为了让你超高速的CPU刮起指令风暴，它需要从内存获取数据加载到寄存器。如你所知，RAM没有紧跟CPU的速度增长，差远了。

借助现代的硬件，要消耗上百个周期才能从RAM获得一比特的数据。如果大部分指令需要的数据都需要上百个周期去获取，那么为什么我们的CPU没有在99%的时间空转着等待数据？

事实上，等待内存读取确实会消耗很长时间，但是没有那么糟糕。为了解释为什么，让我们看一看这一长串类比……

数据仓库

想象一下，你是小办公室里的会计。你的任务是拿盒文件，然后做一些会计工作——把数据加起来什么的。你必须根据一堆只有会计能懂的晦涩逻辑，取出特定标记的文件盒并工作。

我也许不应该在例子中用我一无所知的职业打比方。

由于辛勤地工作，天生的悟性，还有进取心，你可以在一分钟内处理一个文件盒。但是这里有一个小小的问题。所有这些文件盒都存储在分离的仓库中。想要拿到一个文件盒，需要让仓库管理员带给你。他开着叉车在传送带周围移动，直到找到你要的文件盒。

严格地说，这会消耗他一整天才能完成。不像你，他下个月就不会被雇佣了。这就意味着无论你有多快，一天只能拿到一个文件盒。剩下的时间，你只能坐在那里，质疑自己怎么选了这个折磨灵魂的工作。

一天，一组工业设计师出现了。他们的任务是提高操作的效率——比如让传送带跑得更快。在看着你工作几天后，他们发现了几件事情：

通常，当你处理文件盒时，下一个需要处理的文件盒就在仓库同一个架子上。
叉车一次只取一个文件盒太愚蠢了。
在你的办公室角落里还是有些空余空间的。

他们想出来一个巧妙的办法。无论何时你问仓库要一个盒子，他都会带给你一托盘的盒子。他给你想要的盒子，以及它周围的盒子。他不知道你是不是想要这些（而且，根据工作条件，他根本不在乎）；他只是尽可能地塞满托盘，然后带给你。

访问刚刚访问的事物旁边的位置，描述这种行为的术语是引用局部性。

无视工作场地的安全，他直接将叉车开到你的办公室，然后将托盘放在办公室的角落。

当你需要新盒子，你需要做的第一件事就是看看它在不在办公室角落的托盘里。如果在，很好！你只需要几分钟拿起它然后继续计算数据。如果一个托盘中有五十个盒子，而幸运的你需要所有盒子，你可以以五十倍的速度工作。

但是如果你需要的盒子不在托盘上，就需要新的一托盘的盒子。由于你的办公室里只能放一托盘的盒子，你的仓库朋友只能将旧的拿走，带给你一托盘全新的盒子。

CPU的托盘

奇怪的是，这就是现代CPU运转的方式。如果还不够明显，你是CPU。你的桌子是CPU的寄存器，一盒文件就是寄存器能放下的数据。仓库是机器的RAM，那个烦人的仓库管理员是从主存加载数据到寄存器的总线。

如果我在三十年前写这一章，这个比喻就到此为止了。但是芯片越来越快，而RAM，好吧，“没有跟上”，硬件工程师开始寻找解决方案。他们想到的是CPU缓存技术。

现代的电脑在芯片内部有一小块存储器。 CPU从那上面取数据比从内存取数据快得多。它很小，因为需要放在芯片上，它很快，因为使用的（静态RAM，或称SRAM）内存更贵。

现代硬件有多层缓存，就是你听到的“L1”，“L2”，“L3”之类的。每一层都更大也更慢。在这章里，我们不关心内存是不是多层的，但了解一下还是很有必要的。

这一小片内存被称为缓存（特别地，芯片上的被称为L1级缓存），在比喻中，它是由托盘扮演的。无论何时芯片需要从RAM取一字节的数据，它自动将一整块内存读入然后将其放入缓存——通常是64到128字节。这些一次性传输的字节被称为cache line。

如果你需要的下一字节数据就在这块上， CPU从缓存中直接读取，比从RAM中读取快得多。成功从缓存中找到数据被称为“缓存命中”。如果不能从中获得而得去主存里取，这就是一次缓存不命中。

我在类比中掩盖了（至少）一个细节。在办公室里，只能放一个托盘，或者一个cache line。真实的缓存包含多个cache line。关于这点的细节超出了本书的范围，搜索“缓存关联性”来了解相关内容。

当缓存不命中时，CPU空转——它不能执行下一条指令，因为它没有数据。它坐在那里，无聊地等待几百个周期直到取到数据。我们的任务是避免这一点。想象你在优化一块性能攸关的游戏代码，长得像这样：

for (int i = 0; i < NUM_THINGS; i++)
{
  sleepFor500Cycles();
  things[i].doStuff();
}

你会做的第一个改动是什么？对了。将那个无用的，代价巨大的函数调用拿出来。这个调用等价于一次缓存不命中的代价。每次跳到内存，都会延误你的代码。

等等，数据是性能？

当着手写这一章时，我花费了一些时间制作一个类似游戏的小程序，用于收集缓存使用的最好情况和最坏情况。我想要缓存速度的基准，这样可以得到缓存失效造成的性能浪费情况。

当看到一些工作的结果时，我惊到了。我知道这是一个大问题，但眼见为实。两个程序完成完全相同的计算，唯一的区别是它们会造成缓存不命中的数量。较慢的程序比较快的程序慢五十倍。

这里有很多警告。特别地，不同的计算机有不同的缓存设置，所以我的机器可能和你的不同，专用的游戏主机与个人电脑不同，而二者都与移动设备不同。
你得自己测测看。

这让我大开眼界。我一直从代码的角度考虑性能，而不是数据。一个字节没有快慢，它是静态的。但是因为缓存的存在，组织数据的方式直接影响了性能。

现在真正的挑战是将这些打包成一章内可以讲完的东西。优化缓存使用是一个很大的话题。我还没有谈到指令缓存呢。记住，代码也在内存上，而且在执行前需要加载到CPU上。有些更熟悉这个主题的人可以就这个问题写一整本书。

事实上，有人确实写了一本书：Data-Oriented Design，作者Richard Fabian.

既然你已经在阅读这本书了，我有几个基本技术来帮你考虑数据结构是如何影响性能的。

这可以归结成很简单的事情：芯片读内存时总是获得一整块cache line。你能从cache line读到越多你要的东西，速度就越快。所以目标是组织数据结构，让要处理的数据紧紧相邻。

这里有一个核心假设：单线程。如果在多线程上处理邻近数据，让它在多个不同的cache line上更好。如果两个线程争夺同一cache line上的数据，两个核都得花些时间同步缓存。

换言之，如果你正处理Thing，然后Another然后Also，你需要它们这样呆在内存里：

注意，不是Thing，Another，和Also的指针，而是一个接一个的真实数据。 CPU读到Thing，也会读取Another和Also（取决于数据的大小和cache line的大小）。当你开始下一个时，它们已经在缓存上了。芯片很高兴，你也很高兴。

模式

现代的CPU有缓存来加速内存读取。它可以更快地读取最近访问过的内存的毗邻内存。通过提高内存局部性来提高性能——保证数据以处理顺序排列在连续内存上。

何时使用

就像大多数优化方案，使用数据局部性的第一准则是在遇到性能问题时使用。不要将其应用在代码库不经常使用的角落上。优化代码不会让你过得更轻松，因为其结果往往更加复杂，更加缺乏灵活性。

就本模式而言，还得确认你的性能问题确实由缓存不命中引发。如果代码是因为其他原因而缓慢，这个模式帮不上忙。

简单的估算方案是手动添加指令，检查代码中两点间消耗的时间，寄希望于精确的计时器。为了找到糟糕的缓存使用，你需要使用更加复杂的东西。你想要知道有多少缓存不命中，又是在哪里发生的。

幸运的是，有现成的工具做这些。在数据结构上做大手术前，花一些时间了解这些工具是如何工作，理解它们抛出的一大堆数据（令人惊讶地复杂）是很有意义的。

不幸的是，这些工具大部分不便宜。如果在一个主机开发团队，你可能已经有了使用它们的证书。
如果没有，一个极好的替代选项是Cachegrind。它在模拟的CPU和缓存结构上运行你的程序，然后报告所有的缓存交互。

话虽这么说，缓存不命中仍会影响游戏的性能。虽然不应该花费大量时间提前优化缓存的使用，但是在设计过程中仍要思考数据结构是不是对缓存友好。

记住

软件体系结构的特点之一是抽象。这本书的很多章节都在谈论如何解耦代码块，这样可以更容易地进行改变。在面向对象的语言中，这几乎总是意味着接口。

在C++中，使用接口意味着通过指针或者引用访问对象。但是使用指针就意味在内存中跳跃，这就带来了这章想要避免的缓存不命中。

接口的另一半是虚方法调用。这需要CPU查找对象的虚函数表，找到调用方法的真实指针。所以，你又一次追踪指针，造成缓存不命中。

为了讨好这个模式，你需要牺牲一些宝贵的抽象。你越围绕数据局部性设计程序，就越是在放弃继承、接口和它们带来的好处。没有银弹，只有挑战性的权衡。这就是乐趣所在！

示例代码

如果你真的要一探数据局部性优化的深处，那么你会发现有无数的方法去分割数据结构，将其切为CPU更好处理的小块。为了热热身，我会先从一些最通用的分割方法开始。我们会在游戏引擎的特定部分介绍它们，但是（像其他章节一样）记住这些通用方法也能在其他部分使用。

连续数组

让我们从处理一系列游戏实体的游戏循环开始。实体使用了组件模式，被分解到不同的领域——AI，物理，渲染。这里是GmaeEntity类。

class GameEntity
{
public:
  GameEntity(AIComponent* ai,
             PhysicsComponent* physics,
             RenderComponent* render)
  : ai_(ai), physics_(physics), render_(render)
  {}

  AIComponent* ai() { return ai_; }
  PhysicsComponent* physics() { return physics_; }
  RenderComponent* render() { return render_; }

private:
  AIComponent* ai_;
  PhysicsComponent* physics_;
  RenderComponent* render_;
};

每个组件都有相对较少的状态，也许只有几个向量或一个矩阵，然后会有方法去更新它。这里的细节无关紧要，但是想象一下，大概是这样的：

就像名字暗示的，这些是更新方法模式的例子。甚至render()也是这个模式，只是换了个名字。

class AIComponent
{
public:
  void update() { /* 处理并修改状态…… */ }

private:
  // 目标，情绪，等等……
};

class PhysicsComponent
{
public:
  void update() { /* 处理并修改状态…… */ }

private:
  // 刚体，速度，质量，等等……
};

class RenderComponent
{
public:
  void render() { /* 处理并修改状态…… */ }

private:
  // 网格，纹理，着色器，等等……
};

游戏循环管理游戏世界中一大堆实体的指针数组。每个游戏循环，我们都要做如下事情：

为每个实体更新他们的AI组件。
为每个实体更新他们的物理组件。
为每个实体更新他们的渲染组件。

很多游戏引擎以这种方式实现：

while (!gameOver)
{
  // 处理AI
  for (int i = 0; i < numEntities; i++)
  {
    entities[i]->ai()->update();
  }

  // 更新物理
  for (int i = 0; i < numEntities; i++)
  {
    entities[i]->physics()->update();
  }

  // 绘制屏幕
  for (int i = 0; i < numEntities; i++)
  {
    entities[i]->render()->render();
  }

  // 其他和时间有关的游戏循环机制……
}

在你听说CPU缓存之前，这些看上去完全无害。但是现在，你得看到这里有隐藏着的不对之处。这不是在颠簸缓存，这是在四处乱晃然后猛烈地敲击。看看它做了什么：

游戏实体的数组存储的是指针，所以为了获取游戏实体，我们得转换指针。缓存不命中。
然后游戏实体有组件的指针。又一次缓存不命中。
然后我们更新组件。
再然后我们退回第一步，为游戏中的每个实体做这件事。

令人害怕的是，我们不知道这些对象是如何在内存中布局的。我们完全任由内存管理器摆布。随着实体的分配和释放，堆的组织会更乱。

每一帧，游戏循环得追踪这些指针来获取数据。

如果我们的目标是在游戏地址空间中四处乱转，完成“256MB内存四晚廉价游”，这也许是一个很好的决定。但是我们的目标是让游戏跑得尽可能快，而在主存四处乱逛不是一个好办法。记得sleepFor500Cycles()函数吗？上面的代码效率和它也差不多了。

描述浪费时间转换指针这一行为的术语是“追逐指针”，它并不像听上去那么有趣。

我们能做得更好。第一个发现是，之所以跟着指针去寻找游戏实体，是因为可以立刻跟着另一个指针去获得组件。 GameEntity本身没有有意义的状态和有用的方法。组件才是游戏循环需要的。

众多实体和组件不能像星星一样散落在黑暗的天空中，我们得脚踏实地。我们将每种组件存入巨大的数组：一个数组给AI组件，一个给物理，另一个给渲染。

就像这样：

AIComponent* aiComponents =
    new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents =
    new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents =
    new RenderComponent[MAX_ENTITIES];

让我强调一点，这些都是组件的数组，而不是指向组件的指针。数据都在那里一个接着一个排列。游戏循环现在可以直接遍历它们了。

使用组件时，我最不喜欢的就是组件这个单词的长度。

while (!gameOver)
{
  // 处理AI
  for (int i = 0; i < numEntities; i++)
  {
    aiComponents[i].update();
  }

  // 更新物理
  for (int i = 0; i < numEntities; i++)
  {
    physicsComponents[i].update();
  }

  // 绘制屏幕
  for (int i = 0; i < numEntities; i++)
  {
    renderComponents[i].render();
  }

  // 其他和时间有关的游戏循环机制……
}

我们消除了所有的指针追逐。不在内存中跳来跳去，而是直接在三个数组中做直线遍历。

在这里做得更好的一个技巧是新代码中有更少的->操作符。如果你想要提高数据局部性，找找那些你可以摆脱的间接跳转。

这将一股字节流直接泵到了CPU饥饿的肚子里。在我的测试中，这个改写后的更新循环是之前性能的50倍。

有趣的是，我们并没有在这里放弃太多的封装。是的，游戏循环直接更新游戏组件而不是通过游戏实体，但在此之前它已经确保了以正确的顺序运行。即使如此，每个组件的内部还是具有很好的封装性。它们的封装性取决于自身的数据和方法。我们只是改变了使用它们的方法。

这也不意味着我们摆脱了GameEntity。它拥有它组件的指针这一状态仍然得以保持。它的组件指针现在只是指到了这个数组之中。对游戏的其他部分，如果你还是想传递一个“游戏实体”，一切照旧。重要的是性能攸关的游戏循环部分回避了这点，直接获取数据。

打包数据

假设我们在做粒子系统。根据上节的建议，将所有的粒子放在巨大的连续数组中。让我们用管理类封装它。

ParticleSystem类是对象池的一个例子，通常为单一类型对象而构建。

class Particle
{
public:
  void update() { /* 重力，等等…… */ }
  // 位置，速度，等等……
};

class ParticleSystem
{
public:
  ParticleSystem()
  : numParticles_(0)
  {}

  void update();
private:
  static const int MAX_PARTICLES = 100000;

  int numParticles_;
  Particle particles_[MAX_PARTICLES];
};

系统中的基本更新方法看起来是这样的：

void ParticleSystem::update()
{
  for (int i = 0; i < numParticles_; i++)
  {
    particles_[i].update();
  }
}

但实际上不需要同时更新所有的粒子。粒子系统维护固定大小的对象池，但是粒子通常不是同时在屏幕上活跃。最简单的解决方案是这样的：

for (int i = 0; i < numParticles_; i++)
{
  if (particles_[i].isActive())
  {
    particles_[i].update();
  }
}

我们给Particle一个标志位来追踪其是否在使用状态。在更新循环时，我们检查每个粒子的这个标志位。这会将粒子其他部分的数据也加载到缓存中。如果粒子没有在使用，那么跳过它去检查下一个。这时粒子加载到内存中的其他数据都是浪费。

活跃的粒子越少，要在内存中跳过的部分就越多。越这样做，在两次活跃粒子有效更新之间发生的缓存不命中就越多。如果数组很大又有很多不活跃的粒子，我们又在颠簸缓存了。

如果连续数组中的对象不是连续处理的，实际上这个办法也没有太多效果。如果有太多不活跃的对象需要跳过，就又回到了问题的起点。

理解底层代码的程序员也可以看出这里的问题。使用if为每个粒子检查会引起分支预测错误和流水线暂停。在现代CPU中，一条简单的“指令”实际消耗多个时钟周期。为了保持CPU繁忙，指令流水线化，在前面的指令处理完成之前就开始处理后续指令。
为了实现流水线，CPU需要猜测接下来要执行哪一条指令。在顺序结构的代码中，这很简单；但是加入控制流，就难了。当它为if执行指令，它是猜粒子是活跃的然后执行update()调用，还是猜它不活跃呢？
为了回答这一点，芯片做分支预测——它看看之前的代码选择了哪条分支然后照做。但是当循环不断在活跃的和不活跃的粒子之间转换，预测就失败了。
当它失败，CPU取消它推测的代码（流水线更新），从头开始。这在机器上波及广泛，这就是为什么有时候你看到开发者在热点代码避免控制流。

鉴于本节的标题，你大概可以猜出答案是什么了。我们不监测活跃与否的标签，我们根据标签排序粒子。将所有活跃的粒子放在列表的前头。如果知道了这些粒子都是活跃的，就不必再检查这些标识位了。

还可以很容易地追踪有多少活跃的粒子。这样，更新循环变成了这种美丽的东西：

for (int i = 0; i < numActive_; i++)
{
  particles[i].update();
}

现在没有跳过任何数据。加载入缓存的每一字节都是需要处理的粒子的一部分。

当然，我可没说每帧都要对整个数组做快排。这将抵消这里的收益。我们想要的是保持数组的顺序。

假设数组已经排好序了——开始时确实如此，因为所有粒子都不活跃——它变成未排序的时候即是粒子被激活或者被反激活时。我们可以很轻易地处理这两种情况。当一个粒子激活时，我们让它占据第一个不活跃粒子的位置，将不活跃粒子移动到激活序列的尾端，完成一次交换：

void ParticleSystem::activateParticle(int index)
{
  // 不应该已被激活！
  assert(index >= numActive_);

  // 将它和第一个未激活的粒子交换
  Particle temp = particles_[numActive_];
  particles_[numActive_] = particles_[index];
  particles_[index] = temp;

  // 现在多了一个激活粒子
  numActive_++;
}

为了反激活粒子，只需做相反的事情：

void ParticleSystem::deactivateParticle(int index)
{
  // 不应该已被激活！
  assert(index < numActive_);

  // 现在少了一个激活粒子
  numActive_--;

  // 将它和最后一个激活粒子交换
  Particle temp = particles_[numActive_];
  particles_[numActive_] = particles_[index];
  particles_[index] = temp;
}

很多程序员（包括我在内）已经对于在内存中移动数据过敏了。将一堆数据移来移去的消耗感觉比发送指针要大得多。但是如果你加上了解析指针的代价，有时候这种估算是错误的。在有些情况下，如果能够保证缓存命中，在内存中移动数据消耗更小。

在你做这种决策前要记得验证这点。

将粒子根据激活状态保持排序——就不需要给每个粒子都添加激活标志位了。这可以由它在数组中的位置和numActive_计数器推断而得。这让粒子对象更小，意味着在cache lines中能够打包更多数据，能跑得更快。

但是并非万事如意。你可以从API看出，我们放弃了一定的面向对象思想。 Particle类不再控制其激活状态了。你不能在它上面调用activate()因为它不知道自己的索引。相反，任何想要激活粒子的代码都需要接触到粒子系统。

在这个例子中，将ParticleSystem和Particle这样牢牢绑一起没有问题。我将它们视为两个物理类的的组合概念。这意味着粒子只在特定的粒子系统中有意义。在这种情况下，很可能是粒子系统在复制和销毁粒子。

冷/热分割

这里是最后一种取悦缓存的技术例子。假设某些游戏实体有AI控件。其中包括一些状态——现在正在播放的动画，正在前往的方向，能量等级，等等——这些东西每帧都会发生变化。就像这样：

class AIComponent
{
public:
  void update() { /* ... */ }

private:
  Animation* animation_;
  double energy_;
  Vector goalPos_;
};

但它也有一些罕见事件的状态。它存储了一些数据，描述它遭到猎枪痛击后会掉落什么战利品。掉落数据在实体的整个生命周期只会使用一次，就在它结束的前一霎那：

class AIComponent
{
public:
  void update() { /* ... */ }

private:
  // 之前的字段……
  LootType drop_;
  int minDrops_;
  int maxDrops_;
  double chanceOfDrop_;
};

假设我们遵循前面的章节，那么当我们更新AI组件时，就穿过了一序列打包好的连续数组。那个数据包含所有掉落物的信息。这让每个组件都变得更大了，这就减少了我们能够加载到cache line中的组件个数。每帧的每个组件都会将战利品数据加载到内存中去，即使我们根本不会去使用它。

这里的解决方案被称为“冷/热分割”。这个点子源于将数据结构划分为两个分离的部分。第一部分保存“热”数据，那些每帧都要调用的数据。剩下的片段被称为“冷”数据，在那里存储使用的次数较少的数据。

这里的热部分是AI组件的主体。它是使用最多的部分，所以我们不希望解析指针去找到它。冷组件可以被归到一边去，但是我们还是需要访问它，因此我们在热组件中包含一个指向它的指针，就像这样：

class AIComponent
{
public:
  // 方法……
private:
  Animation* animation_;
  double energy_;
  Vector goalPos_;

  LootDrop* loot_;
};

class LootDrop
{
  friend class AIComponent;
  LootType drop_;
  int minDrops_;
  int maxDrops_;
  double chanceOfDrop_;
};

现在我们每帧都要遍历AI组件，加载到内存的数据只包含必需的数据（以及那个指向冷数据的指针）。

我们可以继续去除指针，为冷热数据维护平行数组。仍能够为组件找到冷数据，因为两者在各自数组中索引值是相同的。

你可以看到事情是怎么变得模棱两可的。在我的例子中，哪些是冷数据，哪些是热数据是很明确的，但是在真实的游戏中一般很少可以这么明显地分割。如果你有一部分数据，实体在一种状态下会经常使用，另一种状态则不会，那该怎么办？如果实体只在特定关卡时使用一块特定的数据，又该怎么办？

做这种优化有时就是在走钢丝。很容易陷入其中，消耗无尽的时间把数据挪来挪去看看性能如何。需要通过实践来掌握在哪里付出努力。

设计决策

这章更接近于介绍一种思维定势——将数据的组织模式作为游戏性能的关键部分。实际上具体的设计空间是开放的。你可以让数据局部性影响整个架构，或者只在局部几个核心数据结构上使用这个模式。

最需要关心的问题是在何时何地使用这个模式，但是这里还有其他几个问题需要回答。

Noel Llopis的著名文章让很多人围绕缓存设计游戏，他称之为“面向数据的设计”。

你如何处理多态？

到了现在，我们避开了子类和虚方法。我们假设有打包好的同类对象。这种情况下，我们知道它们有同样的大小。但是多态和动态调用也是有用的工具。我们如何调和呢？

别这么干

最简单的解决方案是避免子类，至少在做内存优化的部分避免使用。无论如何，软件工程师文化已经和大量使用继承渐行渐远了。

一种保持多态的灵活性而不使用子类的方法是借助于类型对象模式。

简洁安全。你知道在处理什么类，所有的对象都是同样大小。
更快动态调用意味着在跳转表中寻找方法，然后跟着指针寻找特定的代码。这种消耗在不同硬件上区别很大，但动态调用总会带来一些代价。

就像往常一样，万事无绝对。在大多数情况下，虚方法调用中C++编译器需要一次重定向。但是在某些情况下，如果可以知道接受者的具体类型，编译器可以去虚拟化，然后静态地调用正确的方法。去虚拟化在一些just-in-time虚拟机比如Java和JavaScript中更为常见。

不灵活 当然，使用动态调用的原因就是它提供了在不同对象间展示不同的行为的强大能力。如果游戏想要不同的实体使用独特的渲染、移动或攻击，虚方法是处理它的好办法。把它换成包含巨大的switch的非虚方法会超级慢。

为每种类型使用分离的数组：

我们使用多态，这样即使不知道对象的类型，也能引入行为。换言之，有了一包混合的东西，我们想要其中每个对象在接到通知时去做自己的事情。

但是这提出来一个问题：为什么开始的时候要把它们混在一起呢？取而代之，为什么不为每种类型保持一个单独的集合呢？

对象被紧密地排列着。每个数组只包含同类的对象，这里没有填充或者其他的古怪。
静态调度。一旦获得了对象的类型，你不必在所有时候使用多态。你可以使用常规的非虚方法调用。
得追踪每个集合。如果你有很多不同类型，为每种类型分别管理数组可是件苦差事。
得明了每一种类型。由于你为每种类型管理分离的集合，你无法解耦类型集合。多态的魔力之一在于它是开放的——与一个接口交互的代码可以与实现此接口的众多类型解耦。

使用指针的集合：

如果你不太担心缓存，这是自然的解法。只要一个指针数组指向基类或者接口类型，你就获得了想要的多态，对象可以想多大就多大。

灵活。这样构建集合的代码可以与任何支持接口的类工作。完全开放。
对缓存不友好。当然，我们在这里讨论其他方案的原因就是指针跳转导致的缓存不友好。但是，记住，如果代码不是性能攸关的，这很有可能是行得通的。

游戏实体是如何定义的？

如果与组件模式串联使用此模式，你会获得多个数组，包含组成游戏实体的组件。游戏循环会在那里直接遍历它们，所以实体本身就不是那么重要了，但是在其他你想要与“实体”交互的代码库部分，一个概念上的实体还是很有用的。

这里的问题是它该如何被表示？如何追踪这些组件？

如果游戏实体是拥有它组件指针的类：

这是第一个例子中的情况。纯OOP解决方案。你得到了GameEntity类，以及指向它拥有的组件的指针。由于它们只是指针，我们并不知道这些组件是如何在内存中组织的。

你可以将实体存储到连续数组中。既然游戏实体不在乎组件在哪里，你可以将组件好好打包，组织在数组中来优化遍历。
拿到一个实体，可以轻易地获得它的组件。就在一次指针跳转后的位置。
在内存中移动组件很难。当组件启用或者关闭时，你可能想要在数组中移动它们，保证启用的组件位于前列。如果在实体中有指针指向组件时直接移动该组件，一不小心指针就会损毁。你得保证同时更新指向组件的指针。

如果游戏实体是拥有组件ID的类：

使用裸指针的挑战在于在内存中移动它很难。你可以使用更加直接的方案：使用ID或者索引来查找组件。

ID的实际查找过程是由你决定的，它可能很简单，只需为每个实体保存独特的ID，然后遍历数组查找，或者更加复杂地使用哈希表，将ID映射到组件现有的位置。

更复杂。 ID系统不是高科技，但是还是需要比指针多做些事情。你得实现它然后排除漏洞，这里需要消耗内存。
更慢。很难比直接使用指针更快。需要使用搜索或者哈希来帮助实体找到它的组件。
你需要访问组件“管理器”。基本思路是用抽象的ID标识组件。你可以使用它来获得对应组件对象的引用。但是为了做到这点，你需要让ID有办法找到对应的组件。这正是包裹着整个连续组件数组的类所要做的。
通过裸指针，如果你有游戏实体，你可以直接找到组件，而这种方式你需要接触游戏实体和组件注册器。

你也许在想，“我会把它做成单例！问题解决！”好吧，在某种程度上是这样的。不过，你也许想要先看看这章。

如果游戏实体本身就是一个ID：

这是某些游戏引擎使用的新方式。一旦实体的行为和状态被移出放入组件，还剩什么呢？事实上，没什么了。实体干的唯一事情就是将组件连接在一起。它的存在只是为了说明：这个AI组件和这个物理组件还有这个渲染组件合起来，定义了一个存在于游戏世界中的实体。

这很重要，因为组件要相互交互。渲染组件需要知道实体位于何处，而位置信息也许是物理组件的属性。 AI组件想要移动实体，因此它需要对物理组件施加力。每个组件都需要以某种方式获得同一实体中的其他组件。

有些聪明人意识到你唯一需要的东西就是ID。不是实体知道组件，而是组件知道实体。每个组件都知道拥有它的实体的ID。当AI组件需要它所属实体的物理组件时，它只需要找到那个拥有同样ID的物理组件。

你的实体类整个消失了，取而代之的是围绕数字的华丽包装。

实体很小。当你想要传递游戏实体的引用时，只需一个简单的值。
实体是空的。当然，将所有东西移出实体的代价是，你必须将所有东西移出。不能再拥有组件独有的状态和行为，这样更加依赖于组件模式。
不必管理实体的生命周期。由于实体只是内置值类型，不需要被显式分配和释放。当它所有的组件都被释放时，对象就隐式“死亡”了。
查找实体的某一组件也许会很慢。这和前一方案有相同的问题，但是是在另一个方向上。为了找某个实体的组件，你需要给ID做对象映射。这一过程消耗也许很大。
但是，这一次是性能攸关的。在更新时，组件经常与它的兄弟组件交互，因此你需要经常地查找组件。解法是让组件在数组中的索引作为实体的“ID”。
如果每个实体都是拥有相同组件的集合，那么组件数组就是完全同步的。组件数组三号位的AI组件与在物理组件数组三号位的组件相关联。
但是，记住，这强迫你保持这些数组平行。如果你想要用不同的方式排序或者打包它们就会变得很难。你也许需要一些没有物理组件或者没有渲染组件的实体。而它们仍保证与其他组件同步，没有办法独自排序物理组件数组和渲染组件数组。

参见

这一章大部分围绕着组件模式。这种模式的数据结构绝对是为缓存优化的最常见例子。事实上，使用组件模式让这种优化变得容易了。由于实体是按“领域”（AI，物理，等等）更新的，将它们划出去变成组件，更容易将它们保存为对缓存友好的合适大小。
但是这不意味你只能为组件使用这个模式！任何需要接触很多数据的关键代码，考虑数据局部性都是很重要的。
Tony Albrecht的《Pitfalls of Object-Oriented Programming》也许是最广为人知的内存友好游戏设计指南。它让很多人（包括我！）明白了数据结构对性能而言是多么重要。
几乎同时，Noel Llopis关于同一话题写了一篇非常有影响力的博客。
这一模式几乎完全得益于同类对象的连续存储数组。随着时间的推移，你也许需要向那个数组增加或删除对象。对象池模式正是关于这一点。
游戏引擎Artemis是首个也是最著名的为游戏实体使用简单ID的游戏框架。

脏标识

意图

将工作延期至需要其结果时才去执行，避免不必要的工作。

动机

很多游戏有场景图。那是一个巨大的数据结构，包含了游戏世界中所有的对象。渲染引擎使用它决定在屏幕的哪里画东西。

最简单的实现中，场景图只是对象列表。每个对象都有模型，或者其他的原始图形，以及变换。变换描述了对象在世界中的位置，方向，拉伸。为了移动或者旋转对象，只需简单地改变它的变换。

如何存储和操作变换的内容很不幸超出了本书讨论范围。简单地总结下，是个4x4的矩阵。你可以通过矩阵相乘来组合两个变换，获得单一变换——举个例子，平移之后旋转对象。
它如何工作，以及为什么那样工作是留给读者的练习。

当渲染系统描绘对象，它取出对象的模型，对其应用变换，然后将其渲染到游戏世界中。如果我们有场景包而不是场景图，那就是这样了，生活很简单。

但是，大多数场景图都是分层的。场景图中的对象也许拥有锚定的父对象。这种情况下，它的变换依赖于父对象的位置，而不是游戏世界上的绝对位置。

举个例子，想象游戏世界中有一艘海上的海盗船。桅杆的顶端有瞭望塔，瞭望塔中有海盗，海盗肩上有鹦鹉。船本身的变换定位船在海上的位置。瞭望塔的变换定位它在船上的位置，诸如此类。

编程艺术！

这样的话，当父对象移动时，子节点也自动地跟着移动。如果改变了船的自身变换，瞭望塔，海盗和鹦鹉都会随之变动。如果当船移动时，就得手动调整每个对象的变换来防止滑动，那可相当令人头疼。

老实说，当你在海上，你确实需要手动调整姿势来防止滑动。也许我应该选一个不会滑动的例子。

但是为了在屏幕上真正地描绘鹦鹉，我需要知道它在世界上的绝对位置。我会调用父节点相关的变换对对象的自身变换进行变换。为了渲染对象，我需要知道对象的世界变换。

自身变换和世界变换

计算对象的世界变换很直接——从根节点开始通过父节点链一直追踪到对象，将经过的所有变换绑在一起。换言之，鹦鹉的世界变换如下：

我们每帧需要为游戏世界的每个对象计算世界变换，因此哪怕每个模型只有一部分矩阵乘法，它也处于代码影响性能的关键位置上。保持它们及时更新是有技巧的，因为当父对象移动时，它影响自己的世界变换，并递归影响所有子节点。

如果对象没有父对象，它的自身变换和世界变换是一样的。

最简单的方法是在渲染时计算变换。每一帧，我们从最高层递归遍历整个场景图。我们计算每个对象的世界变换然后立刻绘制它。

但这完全是在浪费CPU！很多游戏世界的对象不是每帧都在移动。想想那些构成关卡的静态几何图形。在没有改变的情况下每帧计算它们的世界变换是一种浪费。

缓存世界变换

明显的解决方案是缓存它。在每个对象中，我们存储它的自身变换和世界变换。当我们渲染时使用预计算的世界变换。如果对象从未移动，缓存的变换永远是最新的变换，每个人都很开心。

当一个对象确实移动了，简单的解决方式是之后就更新世界变换。但是不要忘记层次性！当父节点移动时，我们得计算它的世界变换并递归计算它所有的子对象。

想象游戏中忙碌的时刻。在一帧中，船在海上颠簸，瞭望塔在风中摇晃，海盗被甩到了边缘，而鹦鹉撞上了他的脑袋。我们改变了四个自身变换。如果每次自身变换都立即更新世界变换，会发生什么？

我只移动四个对象，但我们做了十次世界变换计算。那就有六次在被渲染器使用前浪费了。我们计算了鹦鹉的世界变换四次，但它只需渲染一次。

你可以看到在标记了★的行上，我们重复计算了四次鹦鹉的世界变换，但我们只需要最后的那次。

问题在于世界变换也许会依赖于多个自身变换。由于我们每次变化就立即重新计算，当自身变换依赖的多个世界变换在同一帧发生变化时，我们就对同一变换做了多次重新计算。

延期重计算

我们会通过解耦自身变换和世界变换的更新来解决这个问题。这让我们先在一次批处理中改变自身变换，在这些改变完成之后，在渲染它之前，重新计算它们世界变换。

有趣的是，不少软件架构是故意稍微偏离了一点。

为了做到这点，我们为图中的每个对象添加标识。 “标识”和“位”在编程中密切相关——都代表处在两种状态之一的一小块数据。我们称之为“真”和“假”，或者有时称为“设置”和“清除”。我之后会交替使用它们。

当自身变换改变了，我们设置它。当我们需要对象的世界变换时，我们检查这个位。如果它被设置了，计算世界变换然后清除标识。那个标识代表着，“世界变换过时了吗？” 由于它们没有被清除，这种“过时的杂乱”被称为“脏”。也就是脏标识。“脏位”也是这个模式通常使用的名字，但是我决定使用不那么下流的称呼。

维基百科的编辑者没有我这样的自制力，使用了dirty bit.

如果我们运用这个模式，然后移动之前例子中所有对象，那么游戏最终是这样的：

这就是你能希望得到的最好结果了——每个受影响对象的世界变换只被计算一次。使用仅仅一位数据，这个模式为我们做了以下事情：

它将对象的父节点链上的众多的自身变换变化归并成对象上的一次计算。
它避免了在没有移动的对象上重新计算。
还有一个小小的意外收获：如果对象在渲染前被删除了，不必再计算它的世界变换。

模式

一组原始数据随着时间变化而改变。使用代价昂贵的过程推定一组导出数据。用一个“脏”标识追踪导出数据是否与原始数据保持一致。它在原始数据改变时被设置。 如果导出数据被请求时，该标识被设置了，那么重新计算并清除标识 否则的话，使用之前缓存的导出数据。

何时使用

与这本书中的其他模式相比，这个模式解决了一个非常特殊的问题。同时，就像其他优化一样，只在性能问题足够大时，再使用这一模式增加代码的复杂度。

脏标识在两种任务上应用：“计算”和“同步”。在两种情况下，从原始数据变换到导出数据消耗很多时间，或者有很多其他方面的消耗。

在我们的场景图例子中，这个过程非常缓慢是因为需要执行很多数学运算。在同步上使用这个模式是另一个应用场景，导出数据在别的地方——在磁盘上或者在网络另一头的终端机上——从点A传输到点B消耗很大。

这里是一些其他的应用场景：

原始数据的变化速度远高于导出数据的使用速度。 避免在导出数据使用前原始数据多次变化带来的不必要计算。如果你总在原始数据变化后立即使用导出数据，这个模式无法帮忙。
增量更新十分困难。 假设海盗船只能携带特定数量的战利品。我们需要获取携带事物的总重量。我们可以使用这个模式，然后为总重量设立脏标识。每次添加或者移除一些战利品，我们设置这个标识。当我们需要总量时，将所有战利品的重量加起来，然后清除标识。
但是更简单的解决方法是保存计算总量。当我们添加或删除事物，直接从现在的总重量添加或者删除它的重量。如果我们可以承担得起消耗，保持导出数据的更新，那么更好的选择是不用这个模式，每次需要时重新计算导出数据。

这听起来脏标识很少有能使用的时候，但你总会找到一两个部分它能帮得上忙。直接在你的游戏代码库中搜索“dirty”，通常会发现这个模式的使用之处。

根据我的研究，也能找到很多对“dirty”黑魔法的抱怨注释。

记住

哪怕是在说服自己这个模式在这里很恰当之后，这里还有一些瑕疵可能会让你不爽。

延期太久是有代价的

这个模式将某些耗时的工作延期到真正需要结果的时候，但是当它要的时候，通常是现在就要。但是我们使用这个模式的原因是计算很耗时！

在例子中，这不是问题，因为我们还是可以在一帧之内计算世界坐标，但是可以想象其他情况下，工作需要消耗可观时间。如果玩家想要结果时才开始计算，这会引起不愉快的卡顿。

延期的另一个问题是，如果有东西出错了，你可能根本无法弥补。当你使用这个模式将状态持久化时，问题更加突出。

举个例子，文本编辑器知道文档有“没保存的修改”。在文件标题栏的小点或者星号就是可见的脏标识。原始数据是在内存中打开的文档，推导数据是在磁盘上的文件。

很多程序直到文档关闭或者应用退出才保存到磁盘上。在大多数情况下这很好，但是如果一不小心踢到了插线板，你的主要工作也就随风而逝了。

在后台自动保存备份的编辑器弥补了这一失误。自动保存的频率保持在崩溃时不丢失太多数据和频繁保存文件之间。

每次状态改变你都得保证设置标识。

由于推导数据是从原始数据推导而来的，它本质上是缓存。无论何时缓存了数据，都是需要保证缓存一致性的——在缓存与原始数据不同步时通知之。在这个模式上，这意味着在任何原始数据变化时设置脏标识。

Phil Karlton有句名言：“计算机科学中只有两件难事：缓存一致性和命名。”

一处遗漏，你的程序就使用了错误的推导数据。这引起了玩家的困惑和非常难以追踪的漏洞。当使用这个模式时，你也得注意，任何修改了原始数据的代码都得设置脏标识。

一种解决它的方法是将原始数据的修改隐藏在接口之后。任何想要改变状态的代码都要通过API，你可以在API那里设置脏标识来保证不会遗漏。

得将之前的推导数据保存在内存中。

当推导数据被请求而脏标识没有设置时，就使用之前计算出的数据。这很明显，但这需要在内存中保存推导数据，以防之后再次使用。

如果你用这个模式将原始状态同步到其他地方，这不是问题。那样的话，推导数据通常不在内存里。

如果你没有使用这个模式，可在需要时计算推导数据，使用完后释放。这避免将其存储回内存的开销，而代价是每次使用都需要重新计算。

就像很多优化一样，这种模式以内存换速度。通过在内存中保存之前计算的结果，避免了在它没有改变的情况下重新计算。这种交易在内存便宜而计算昂贵时是划算的。当你手头有更多空闲的时间而不是内存的时候，最好在需求时重新计算。

相反，压缩算法做了反向的交易：它们优化空间，代价是解压时额外的处理时间。

示例代码

假设我们满足了超长的需求列表，看看在代码中是如何应用这个模式的。就像我之前提到的那样，矩阵运算背后的数学知识超出了本书的范围，因此我将其封装在类中，假设在某处已经实现了：

class Transform
{
public:
  static Transform origin();

  Transform combine(Transform& other);
};

这里我们唯一需要的操作就是combine()，这样可以将父节点链上所有的自身变换组合起来获得对象的世界变换。同样有办法来获得原点变换——通常使用一个单位矩阵，表示没有平移，旋转，或者拉伸。

下面，我们勾勒出场景图中的对象类。这是在应用模式之前所需的最低限度的东西：

class GraphNode
{
public:
  GraphNode(Mesh* mesh)
  : mesh_(mesh),
    local_(Transform::origin())
  {}

private:
  Transform local_;
  Mesh* mesh_;

  GraphNode* children_[MAX_CHILDREN];
  int numChildren_;
};

每个节点都有自身变换描述了它和父节点之间的关系。它有代表对象图形的真实网格。（将mesh_置为NULL来处理子节点的不可见节点。）最终，每个节点都包含一个有可能为空的子节点集合。

通过这样，“场景图”只是简单的GraphNode，它是所有的子节点（以及孙子节点）的根。

GraphNode* graph_ = new GraphNode(NULL);
// 向根图节点增加子节点……

为了渲染场景图，我们需要的就是从根节点开始遍历节点树，然后使用正确的世界变换为每个节点的网格调用函数：

void renderMesh(Mesh* mesh, Transform transform);

我们不会直接在这里实现，但在真正的实现中它会做渲染器为了将网格绘制在世界上给定的位置所需要的一切。如果对场景图中的每个节点都正确有效地调用，这就愉快地完成了。

尚未优化的遍历

让我们开始吧，我们做一个简单的遍历，在渲染需要时去计算所有的世界位置。这没有优化，但它很简单。我们添加一个新方法给GraphNode：

void GraphNode::render(Transform parentWorld)
{
  Transform world = local_.combine(parentWorld);

  if (mesh_) renderMesh(mesh_, world);

  for (int i = 0; i < numChildren_; i++)
  {
    children_[i]->render(world);
  }
}

使用parentWorld将父节点的世界变换传入节点。这样，需要获得这个节点的世界变换只需要将其和节点的自身变换相结合。不需要向上遍历父节点去计算世界变换，因为我们可以在向下遍历时计算。

我们计算了节点的世界变换，将其存储到world，如果有网格，渲染它。最后我们遍历进入子节点，传入这个节点的世界变换。无论如何，这是一个紧密的，简单的遍历方法。

为了绘制整个场景图，我们从根节点开始整个过程。

graph_->render(Transform::origin());

让我们变脏

所以代码做了正确的事情——它在正确的地方渲染正确的网格——但是它没有高效地完成。它每帧在图中的每个节点上调用local_.combine(parentWorld)。让我们看看这个模式是如何修复这一点的。首先，我们给GraphNode添加两个字段：

class GraphNode
{
public:
  GraphNode(Mesh* mesh)
  : mesh_(mesh),
    local_(Transform::origin()),
    dirty_(true)
  {}

  // 其他方法……

private:
  Transform world_;
  bool dirty_;
  // 其他字段……
};

world_字段缓存了上一次计算出来的世界变换，dirty_当然就是脏标识字段。注意标识初始为true。当我们创建新节点时，我们还没有计算它的世界变换。初始时，它与自身变换不是同步的。

我们需要这个模式的唯一原因是对象可以移动，因此让我们添加对这点的支持：

void GraphNode::setTransform(Transform local)
{
  local_ = local;
  dirty_ = true;
}

这里重要的部分是同时设置脏标识。我们忘了什么吗？是的——子节点！

当父节点移动时，它所有子节点的世界坐标也改变了。但是这里，我们不设置它们的脏标识。我们可以那样做，但是那要递归，很缓慢。我们可以在渲染时做点更聪明的事。让我们看看：

void GraphNode::render(Transform parentWorld, bool dirty)
{
  dirty |= dirty_;
  if (dirty)
  {
    world_ = local_.combine(parentWorld);
    dirty_ = false;
  }

  if (mesh_) renderMesh(mesh_, world_);

  for (int i = 0; i < numChildren_; i++)
  {
    children_[i]->render(world_, dirty);
  }
}

这与原先的原始实现很相似。关键改变是我们在计算世界变换之前去检查节点是不是脏的，然后将结果存在字段中而不是本地变量中。如果节点是干净的，我们完全跳过了combine()，使用老的但是正确的world_值。

这里有一个微妙的假设：if检查比矩阵乘法快。直观上，你当然会这么想，检测一位当然比一堆浮点计算要快。
但是，现代CPU超级复杂。它们严重依赖于流水线——入队的一系列连续指令。像我们这里的if造成的分支会引发分支预测失败，强迫CPU消耗周期在填满流水线上。
数据局部性一章有更多现代CPU是如何试图加快运行的细节，以及如何避免这样颠簸它们。

这里的技巧是dirty参数。如果父节点链上有任何节点是脏的，那么就是true。当我们顺着层次遍历下来时，parentWorld用同样的方式更新它的世界变换，dirty追踪父节点链是否有脏。

这让我们避免递归地调用setTransform()标注每个子节点的dirty_标识。相反，我们在渲染时将父节点的脏标识传递给子节点，然后看看是否需要重新计算它的世界变换。

这里的结果正是我们需要的：改变节点的自身变换只是一些声明，渲染世界时只计算从上一帧以来所需的最小数量的世界变换。

设计决策

这种模式非常具体，所以只需注意几点：

什么时候清空脏标识？

当结果被请求时：

如果不需要结果，可以完全避免计算。如果原始数据变化的速度比推导数据获取的速度快得多，这效果很明显。
如果计算消耗大量时间，这会造成可察觉的卡顿。将工作推迟到玩家想要结果的时候会严重影响游戏体验。这部分工作一般足够快，不会构成问题，但是如果构成问题，你就需要提前做这些工作。

在精心设计的检查点处：

有时候，会有某个时间点适合这么做，或在游戏过程中某个自然适合处理推迟计算的时机去做。例如，只有海盗船驶入港口才会去保存游戏。如果同步点不是游戏的机制，我们会将这些工作隐藏在加载画面或者过场动画之后。

这种工作不会影响到玩家体验。不像前一个选项，你总会在游戏紧张运行时打断玩家的注意力。
在工作时丧失了控制权。这和前一个选项相反。你在处理时能进行微观控制，确保有效且优雅地处理它。
你不能保证玩家真的到了检查点或者满足了定义的条件。如果他们在游戏中迷失了，或者游戏进入了奇怪的状态，最终工作会推迟得超乎预料的晚。

在后台处理：

通常情况下，你在第一次更改时启动固定时长的计时器，然后在计时器到时间后处理之间的所有变化。

在人机交互界，用术语hysteresis描述程序接受用户的输入和响应之间的故意延迟。

可以控制工作进行的频率。通过调节计时器，可以保证它发生得像预期一样频繁（或者不频繁）。
更多的冗余工作。如果原始状态在计时器运行之间只改变了很少的部分，最终处理的大部分都是没有改变的数据。
需要支持异步工作。在“后台”处理数据意味着玩家可以同时继续做事。这就意味着你将会需要线程或者其他并行支持，这样游戏在处理数据的同时仍然可以继续游玩。
由于玩家很可能与处理中的状态交互，你也需要考虑保持并行修改的安全性。

脏追踪的粒度有多细？

假设我们的海盗游戏允许玩家建造并个性化自己的船。船在线时会自动保存，这样玩家可以在离线后重新恢复。我们使用脏标识记录船的哪块甲板被修改了并需要发送到服务器。每一块发送给服务器的数据都包括了修改的数据和一些描述改动发生在何处的元数据。

如果粒度更细：

假设你为甲板上的每个小木板都拍上一个脏标识。

你只需处理真正改变的数据。你只将船上修改了的数据发送到服务器。

如果粒度更粗：

或者，我们可以为每层甲板关联一个脏标识。改变它上面的任何东西都会让整个甲板变脏。

我可以说些这里不合时宜的糟糕笑话，但我克制住了。

最终需要处理没有变化的数据。在甲板上添加一个桶，就要将整层甲板发送到服务器。
用在存储脏标识上的内存更少。为甲板上添加十个桶只需要一位来追踪。
固定开销花费的时间更少。当处理某些修改后的数据时，通常处理数据之前有些固定的工作要做。在这个例子中，是确认船上改动在哪里的元数据。处理的块越大，那么要处理的数量就越少，这就意味着有更小的开销。

参见

在游戏之外，这个模式在像Angular的浏览器方向框架中是很常见的。它们使用脏标识来追踪哪个数据在浏览器中被改变了，需要将其推向服务器。
物理引擎追踪哪些对象在运动中哪些在休息。由于休息的骨骼直到有力施加在上面才会移动，在被碰到时才会需要处理。 “正在移动”就是一个脏标识，标注哪个对象上面有力施加并需要物理解析。

对象池

意图

放弃单独地分配和释放对象，从固定的池中重用对象，以提高性能和内存使用率。

动机

我们在处理游戏的视觉效果。当英雄释放了法术，我们想要在屏幕上爆发闪光。这需要调用粒子系统，产生动态的闪烁图形，显示动画直到图形消失。

由于一次简单的魔杖挥舞就能产生成百上千的粒子，系统需要能够快速地生成它们。更重要的是，我们需要保证创建和销毁这些粒子不会造成内存碎片。

碎片的诅咒

为游戏主机或者移动设备编程在许多方面比为普通的计算机编程更像是嵌入式编程。内存紧张，玩家希望游戏能如磐石般稳定运行，压缩内存的管理器很难有效。在这种环境下，内存碎片是致命的。

碎片意味着在堆中的空余空间被打碎成了很多小的内存碎片，而不是大的连续内存块。 总共的 可用内存也许很大，但是最长的连续空间可能难以忍受地小。假设我们有十四个空余字节，但是被一块正在使用的内存分割成了两个七字节的碎片。而我们尝试分配十二字节的对象，那么就会失败。屏幕上不会有更多的闪烁火花了。

这有点像在已经停了很多车的繁忙街道上停车。如果它们挤在一起，尽管空间还是有剩余的，但空闲地带变成了车之间的碎片空间。

哪怕碎片化发生得不频繁，它也仍会逐渐把堆变成有空洞和裂隙的不可用泡沫，最终完全无法运行游戏。

这里展现了堆是怎么碎片化的，以及即使在理论上有足够的可用内存，内存也会分配失败。
大多数主机游戏制作商要求游戏通过“浸泡测试”，即让游戏在demo模式运行上几天。如果游戏崩溃了，他们不允许游戏发售。浸泡测试失败有时是因为发生罕见的漏洞，但碎片增长或者内存泄露是造成游戏停止的大部分原因。

兼得鱼和熊掌

由于碎片化和可能很慢的内存分配，游戏中何时何处管理内存通常需要十分小心。一个简单又有效的办法是——游戏开始时取一大块内存，然后直到游戏结束才去释放它。但是这对要在游戏运行时创建和销毁事物的系统来说是痛苦的。

使用对象池能让我们兼得鱼和熊掌。对内存管理器，我们只需要将一大块内存分出来，保持在游戏运行时不释放它。对于池的使用者，我们可以简单地构造析构我们想要的内容对象。

模式

定义一个池对象，其包含了一组可重用对象。其中每个可重用对象都支持查询“使用中”状态，说明它是不是“正在使用”。池被初始化时，它就创建了整个对象集合（通常使用一次连续的分配），然后初始化所有对象到“不在使用中”状态。

当你需要新对象，向池子要一个。它找到一个可用对象，初始化为“使用中”然后返回。当对象不再被需要，它被设置回“不在使用中”。通过这种方式，可以轻易地创建和销毁对象而不必分配内存或其他资源。

何时使用

这个模式广泛应用于可见的事物上，比如游戏实体和视觉效果，但是它也可在不那么视觉化的数据结构上使用，比如正在播放的声音。在以下情况中使用对象池：

需要频繁创建和销毁对象。
对象大小相仿。
在堆上进行对象内存分配十分缓慢或者会导致内存碎片。
每个对象都封装了像数据库或者网络连接这样很昂贵又可以重用的资源。

记住

你通常依赖垃圾回收机制或者new和delete来处理内存管理。通过使用对象池，你是在说，“我知道如何更好地处理这些字节。” 这就意味着处理内存的责任落到了你头上。

池可能在不需要的对象上浪费内存

对象池的大小需要根据游戏的需求设置。当池子太小时，很明显需要调整（没有什么比崩溃更能获得你的注意力了）。但是也要小心确保池子没有太大。更小的池子提供了空余的内存做其他有趣的事情。

同时只能激活固定数量的对象

在某种程度上这是好事。将内存按不同的对象类型划分单独的池保证了这点。举个例子，一连串爆炸不会让粒子系统消耗掉所有可用内存，然后阻碍创建新敌人这样的关键事件。

尽管如此，这也意味着试图从池子重用对象可能会失败，因为它们都在使用中。这里有几个常见对策：

完全阻止这点。这是通常的“修复”：增加对象池的大小，这样无论用户做什么，它们都不会溢出。对于重要对象，比如敌人或游戏道具，这通常是正确的选择。也许没有“正确的”方法来处理玩家抵达关底时创建巨大Boss内存不足的问题，所以最聪明的办法就是保证这不发生。
这个的副作用是强迫你为那些只在一两个罕见情况下需要的对象分配过多的内存。因此，固定大小的对象池也许不对所有的游戏状态都适用。举个例子，某些关卡也许需要更多的效果而其他的需要声音。在这种情况下，考虑为每个场景调整对象池的大小。
就不要创建对象了。这听起来很糟，但是对于像粒子系统这样的情况很有道理。如果所有的粒子都在使用，那么屏幕已经充满了闪动的图形。用户不会注意到下个爆炸不如现在的这个一样引人注目。
强制干掉一个已有的对象。想想正在播放声音的内存池，假设需要播放新声音而对象池满了。你不想简单地忽视新声音——用户会注意到魔法剑有时会发出戏剧般的声音，有时顽固地一声不吭。更好的解决方法是找到播放中最轻的声音，然后用新声音替代之。新声音会覆盖掉前一个声音。
大体上，如果已有对象的消失要比新对象的出现更不引人察觉，这也许是正确的选择。
增加池的大小。如果游戏允许你使用一点内存上的灵活性，我们也许会在运行时增加池子的大小或者创建新的溢出池。如果用这种方式获取内存，考虑下在增加的内存不再需要时，池是否需要缩回原来的大小。

每个对象的内存大小是固定的

多数对象池将对象存储在一个数组中。如果你所有的对象都是同样的类型，这很好。但是，如果你想要在同一个对象池中存储不同类型的对象，或者存储子类的实例，你需要保证池中的每个位置对最大的可能对象都有足够的内存。否则，超过预期大小的对象会占据下一个对象的内存空间，导致内存崩坏。

同时，如果对象大小是变化的，你是在浪费内存。每个槽都需要能存储最大的对象。如果对象很少那么大，每放进去一个小对象都是在浪费内存。这很像是通过机场安检时，使用最大允许尺寸的箱子，而里面只放了钥匙和钱包。

当你发现自己在用这种方式浪费内存，考虑将池根据对象的大小分割为分离的池 ——大箱子给大行李，小箱子给口袋里的东西。

重用对象不会自动清除。

很多内存管理系统拥有debug特性，会清除或释放所有内存成特定的值，比如0xdeadbeef。这帮助你找到使用未初始化变量或使用已被释放内存造成的痛苦漏洞。

这是一种实现有效率的内存管理的常用模式。管理者拥有一系列池，池的块大小不相同。当你申请分配一块，它会从合适块大小的池中取出一块，然后分配给你。

由于对象池重用对象不再经过内存管理系统，我们失去了这层安全网。更糟的是，为“新”对象使用的内存之前存储的是同样类型的对象。这使你很难分辨出创建新对象时的未初始化问题：那个存储新对象的内存已经保存了来自于上个生命周期中的几乎完全正确的数据。

由于这点，特别注意在池里初始化对象的代码，保证它完全地初始化了对象。甚至很值得加个在对象回收时清空对象槽的debug选项。

未使用的对象会保留在内存中

如果你将其清空为0x1deadb0b，我会很荣幸的。

对象池在支持垃圾回收的系统中很少见，因为内存管理系统通常会为你处理这些碎片。但是对象池仍然是避免构建和析构的有用手段，特别是在有更慢CPU和更简陋垃圾回收系统的移动设备上。

如果你使用有垃圾回收的对象池系统，注意潜在的冲突。由于池不会在对象不再使用时真正地析构它们，如果对象仍然保留任何对其他对象的引用，也会阻止垃圾回收器回收它。为了避免这点，当池中对象不再使用，清除它对其他对象的所有引用。

示例代码

现实世界的粒子系统通常应用重力，风，摩擦，和其他物理效果。我们简陋的例子只在直线上移动粒子几帧，然后销毁粒子。这不是工业级的代码，但足够说明如何使用对象池。

我们应该从最简单的可能实现开始。首先是小小的粒子类：

class Particle
{
public:
  Particle()
  : framesLeft_(0)
  {}

  void init(double x, double y,
            double xVel, double yVel, int lifetime)
  {
    x_ = x; y_ = y;
    xVel_ = xVel; yVel_ = yVel;
    framesLeft_ = lifetime;
  }

  void animate()
  {
    if (!inUse()) return;

    framesLeft_--;
    x_ += xVel_;
    y_ += yVel_;
  }

  bool inUse() const { return framesLeft_ > 0; }

private:
  int framesLeft_;
  double x_, y_;
  double xVel_, yVel_;
};

默认的构造器将粒子初始化为“不在使用中”。之后对init()的调用初始化粒子到活跃状态。粒子随着时间播放动画，一帧调用一次animate()函数。

对象池需要知道哪个粒子可以被重用。它通过粒子的inUse()函数获知这点。这个函数利用了粒子生命时间有限这点，并使用变量framesLeft_来决定哪些粒子在被使用，无需存储分离的标识。

对象池类也很简单：

class ParticlePool
{
public:
  void create(double x, double y,
              double xVel, double yVel, int lifetime);

  void animate()
  {
    for (int i = 0; i < POOL_SIZE; i++)
    {
      particles_[i].animate();
    }
  }

private:
  static const int POOL_SIZE = 100;
  Particle particles_[POOL_SIZE];
};

create()函数允许外部代码创建新粒子。游戏每帧调用animate()一次，让对象池中的粒子轮流显示动画。

animate()方法是更新方法模式的一个例子。

粒子本身被存储在对象池类中一个固定大小的数组里。在这个简单的实现中，池的大小在类声明时被硬编码了，但是也可以使用动态大小的数组或使用由外部定义的模板变量。

创建新粒子很直观：

void ParticlePool::create(double x, double y,
                          double xVel, double yVel,
                          int lifetime)
{
  // 找到一个可用粒子
  for (int i = 0; i < POOL_SIZE; i++)
  {
    if (!particles_[i].inUse())
    {
      particles_[i].init(x, y, xVel, yVel, lifetime);
      return;
    }
  }
}

我们遍历对象池找到第一个可用粒子。当我们找到后，初始化它然后就完成了。注意在这个实现中，如果这里没有找到任何可用的粒子，就不创建新的粒子。

做一个简单粒子系统的所有东西都在这里了，当然，没有包含渲染粒子。我们现在可以创建对象池然后使用它创建粒子。当时间到了，粒子会自动失效。

这足够承载一个游戏了，但是敏锐的读者也许会注意到创建新粒子（可能）需要遍历整个集合，直到找到一个空闲槽。如果池很大很满，这可能很慢。让我们看看可以怎样改进这一点。

空闲列表

创建一个粒子的复杂度是O(n) ，上过算法课的人都知道。

如果不想浪费时间在查找空闲粒子上，明显的解决方案是不要失去对它们的追踪。我们可以存储指向每个未使用粒子的单独指针列表。然后，当需要创建粒子时，我们从列表中移除第一个指针，然后重用它指向的粒子。

不幸的是，这回要我们管理一个和对象池同样大小的单独数组。无论如何，在我们创建池时，所有的粒子都未被使用，所以列表初始会包含池中每个对象的指针。

如果无需牺牲任何内存就能修复性能问题那就好了。方便的是，这里已经有可以借用的内存了——那些未使用粒子自身的内存。

当粒子未被使用时，它的大部分的状态都是无关紧要的。它的位置和速度没有被使用。唯一需要的是表示自身是否激活的状态。在我们的例子中，那是framesLeft_成员。其他的所有位都可以被重用。这里是改进后的粒子：

class Particle
{
public:
  // ...

  Particle* getNext() const { return state_.next; }
  void setNext(Particle* next) { state_.next = next; }

private:
  int framesLeft_;

  union
  {
    // 使用时的状态
    struct
    {
      double x, y;
      double xVel, yVel;
    } live;

    // 可重用时的状态
    Particle* next;
  } state_;
};

我们将除framesLeft_外的所有成员变量移到live结构中，而该结构存储在unionstate_中。这个结构保存粒子在播放动画时的状态。当粒子被重用时，union的其他部分，next成员被使用了。它保留了一个指向这个粒子后面的可用粒子的指针。

Unions近些年不那么常见了，所以你可能不熟悉这些语法。如果你在游戏团队中，你可能会遇见“内存大师”，当游戏遇到不可避免的内存耗尽问题时，他们就挺身而出。问问他们关于unions的事。他们知道所有有关union的事情，还有其他有趣的位压缩技巧。

我们可以使用这些指针构建链表，将池中每个未使用的粒子都连在一起。我们有可用粒子的列表，而且无需使用额外的内存。我们使用了死亡粒子本身的内存来存储列表。

这种聪明的技术被称为freelist。为了让其工作，我们需要保证指针正确地初始化，在粒子创建和销毁时好好被管理了。并且，当然，我们要追踪列表的头指针：

class ParticlePool
{
  // ...
private:
  Particle* firstAvailable_;
};

当首次创建对象池时，所有的粒子都是可用的，所以空余列表应该贯穿整个对象池。对象池构造器设置了这些：

ParticlePool::ParticlePool()
{
  // 第一个可用的粒子
  firstAvailable_ = &particles_[0];

  // 每个粒子指向下一个
  for (int i = 0; i < POOL_SIZE - 1; i++)
  {
    particles_[i].setNext(&particles_[i + 1]);
  }

  // 最后一个终结的列表
  particles_[POOL_SIZE - 1].setNext(NULL);
}

现在为了创建新粒子，我们直接跳到首个可用的粒子：

O(1) 复杂度，孩子！这才叫编码！

void ParticlePool::create(double x, double y,
                          double xVel, double yVel,
                          int lifetime)
{
  // 保证池没有满
  assert(firstAvailable_ != NULL);

  // 将它从可用粒子列表中移除
  Particle* newParticle = firstAvailable_;
  firstAvailable_ = newParticle->getNext();

  newParticle->init(x, y, xVel, yVel, lifetime);
}

我们需要知道粒子何时死亡，这样可将其放回到空闲列表中，所以我们将animate()改为在粒子不再活跃时返回true：

bool Particle::animate()
{
  if (!inUse()) return false;

  framesLeft_--;
  x_ += xVel_;
  y_ += yVel_;

  return framesLeft_ == 0;
}

当那发生时，简单地将其放回列表：

void ParticlePool::animate()
{
  for (int i = 0; i < POOL_SIZE; i++)
  {
    if (particles_[i].animate())
    {
      // 将粒子加到列表的前部
      particles_[i].setNext(firstAvailable_);
      firstAvailable_ = &particles_[i];
    }
  }
}

这样就成了，一个小对象池，拥有常量时间的构造和删除。

设计决策

如你所见，对象池最简单的实现非常平凡：创建对象数组，在需要它们时重新初始化。实际的代码很少会那么简单，这里还有很多方式让池更加的通用，安全，或容易管理。在游戏中实现对象池时，你需要回答以下问题：

对象和池耦合吗？

写对象池时第一个需要思考的问题：对象本身是否需要知道它们在池子中。大多数情况下它们需要，但是那样你就不大可能写一个通用对象池类来保存任意对象。

如果对象与池耦合：

实现更简单。你可以在对象中简单地放个“在使用中”标识或者函数，就完成了。
你可以保证对象只能被对象池创建。在C++中，做这事最简单的方法是让池对象是对象类的友类，将对象的构造器设为私有。
class Particle
{
friend class ParticlePool;

private:
Particle()
: inUse_(false)
{}

bool inUse_;
};

class ParticlePool
{
Particle pool_[100];
};
在类间保持这种关系来确保使用者无法创建对象池没有追踪的对象。
你也许可以避免显式存储“使用中”的标识。很多对象已经保存了可以告诉外界它有没有在使用的状态。举个例子，粒子的位置如果不在屏幕上，也许它就可以被重用。如果对象类知道它在对象池中，那它可以提供一个inUse()来查询这个状态。这省下了对象池存储“在使用中”标识的多余内存。

如果对象没有和对象池耦合：

可以保存多种类型的对象。这是最大的好处。通过解耦对象和对象池，你可以实现通用的、可重用的对象池类。

必须在对象的外部追踪“使用中”状态。做这点最简单的方式是创建分离的位字段：

template <class TObject>
class GenericPool
{
private:
  static const int POOL_SIZE = 100;

  TObject pool_[POOL_SIZE];
  bool    inUse_[POOL_SIZE];
};

谁负责初始化重用对象？

为了重用一个已经存在的对象，它必须用新状态重新初始化。这里的关键问题是你需要在对象池的内部还是外部重新初始化。

如果在对象池的内部重新初始化：

对象池可以完全封装管理对象。取决于对象需要的其他能力，你可以让它们完全处于池的内部。这保证了其外部代码不会引用到已重用的对象。

对象池与对象是如何初始化的相绑定。池中对象也许提供了不同的初始化函数。如果对象池控制了初始化，它的接口需要支持所有的初始化函数，然后转发给对象。

class Particle
{
  // 多种初始化方式……
  void init(double x, double y);
  void init(double x, double y, double angle);
  void init(double x, double y, double xVel, double yVel);
};

class ParticlePool
{
public:
  void create(double x, double y)
  {
    // 转发给粒子……
  }

  void create(double x, double y, double angle)
  {
    // 转发给粒子……
  }

  void create(double x, double y, double xVel, double yVel)
  {
    // 转发给粒子……
  }
};

如果外部代码初始化对象：

对象池的接口更简单。无需提供覆盖每种对象初始化的多种函数，对象池只需要返回新对象的引用：

class Particle
{
public:
  // 多种初始化方法
  void init(double x, double y);
  void init(double x, double y, double angle);
  void init(double x, double y, double xVel, double yVel);
};

class ParticlePool
{
public:
  Particle* create()
  {
    // 返回可用粒子的引用……
  }
private:
  Particle pool_[100];
};

调用者可以使用对象暴露的任何方法进行初始化：

ParticlePool pool;

pool.create()->init(1, 2);
pool.create()->init(1, 2, 0.3);
pool.create()->init(1, 2, 3.3, 4.4);

外部代码需要处理无法创建新对象的失败。前面的例子假设create()总能成功地返回一个指向对象的指针。但如果对象池已经满了，返回的会是NULL。安全起见，你需要在初始化之前检查这一点。
Particle* particle = pool.create();
if (particle != NULL) particle->init(1, 2);

参见

这看上去很像是享元模式。两者都控制了一系列可重用的对象。不同在于“重用”的含义。享元对象分享实例间同时拥有的相同部分。享元模式在不同上下文中使用相同对象避免了重复内存使用。
对象池中的对象也被重用了，但是是在不同的时间点上被重用的。 “重用”在对象池中意味着对象在原先的对象用完之后分配内存。对象池没有期待对象会在它的生命周期中分享什么。
将内存中同样类型的对象进行整合，能确保在遍历对象时CPU缓存总是满的。数据局部性模式介绍了这一点。

空间分区

意图

将对象根据它们的位置存储在数据结构中，来高效地定位对象。

动机

游戏让我们能拜访其他世界，但这些世界通常和我们的世界没有太多不同。它们通常有和我们宇宙同样的基础物理和可理解性。这就是我们为什么会认为这些由比特和像素构建的东西是真实的。

我们这里注意的虚拟事实是位置。游戏世界有空间感，对象都在空间的某处。它用很多种方式证明了这点。最明显的是物理——对象移动，碰撞，交互——但是还有其他方式。音频引擎也许会考虑声源和玩家的距离，越远的声音响声越小。在线交流也许局限在较近的玩家之间。

这意味着游戏引擎通常需要回答这个问题，“哪些对象在这个位置周围？” 如果每帧都需要回答这个问题，这就会变成性能瓶颈。

在战场上的单位

假设我们在做实时战略游戏。双方成百上千的单位在战场上撞在一起。战士需要挥舞刀锋向最近的那个敌人砍去。最简单的处理方法是检查每对单位，然后看看它们互相之间的距离：

void handleMelee(Unit* units[], int numUnits)
{
  for (int a = 0; a < numUnits - 1; a++)
  {
    for (int b = a + 1; b < numUnits; b++)
    {
      if (units[a]->position() == units[b]->position())
      {
        handleAttack(units[a], units[b]);
      }
    }
  }
}

这里使用的是双重循环，每个循环都会遍历战场上的所有单位。这就是意味着每帧进行的检测对数会随着单位数量的平方增长。每个附加单位都需要和之前所有单位的进行检查。如果有大量单位，这就完全失控了。

内层循环实际没有遍历所有的单位。它只遍历那些外部循环还没有拜访的对象。这避免了比较一对单位两次：A与B一次，B与A一次。如果我们已经处理了A和B之间的碰撞，我们不必为B和A再做一次。
用大O术语，这还是O(n²) 的。

描绘战线

我们这里碰到的问题是没有指明数组中潜藏的对象顺序。为了在某个位置附近找到单位，我们需要遍历整个数组。现在，我们简化一下游戏。不使用二维的战场，想象这是个一维的战线。

在这种情况下，我们可以通过根据单位在战线上的位置排序数组元素来简化问题。一旦我们那样做，我们可以使用像二分查找之类的东西找到最近的对象而不必扫描整个数组。

二分查找有O(log n) 的复杂度，意味着找所有战斗单位的复杂度从O(n²)降到O(n log n)。像pigeonhole sort可将其降至O(n) 。

这里的经验很明显：如果我们根据位置在数据结构中存储对象，就可以更快地找到它们。这个模式便是将这个思路应用到多维空间上。

模式

对于一系列对象，每个对象都有空间上的位置。将它们存储在根据位置组织对象的空间数据结构中，让你有效查询在某处或者某处附近的对象。当对象的位置改变时，更新空间数据结构，这样它可以继续找到对象。

何时使用

这是存储活跃的、移动的游戏对象的常用模式，也可用于静态美术和世界地理。复杂的游戏中，不同的内容有不同的空间分区。

这个模式的基本要求是一系列有位置的对象，而你做了太多的通过位置寻找对象的查询，导致性能下降。

记住

空间分区的存在是为了将O(n)或者O(n²) 的操作降到更加可控的数量级。你拥有的对象越多，这就越重要。相反的，如果n足够小，也许不需要担心这个。

由于这个模式需要通过位置组织对象，可以改变位置的对象更难处理。你需要重新组织数据结构来追踪在新位置的对象，这增加了更多的复杂性并消耗CPU循环。确保这种交易是值得的。

想象一下哈希表，其中对象的键可以自动改变，那你就知道为什么这难以处理。

空间分区也会因为记录划分的数据结构而使用额外的内存。就像很多优化一样，它用内存换速度。如果内存比时钟周期更短缺，这会是个错误的选择。

示例代码

模式总会变化——每种实现都略有不同，空间分区也不例外。不像其他的模式，它的每种变化都很好地被记录下来了。学术界发表文章证明各种变化各自的性能优势。由于我只关注模式背后的观念，我会给你展示最简单的空间分区：固定网格。

看看本章的最后一节，那里有游戏中常用的空间分区方法列表。

一张网格纸

想象整个战场。现在，叠加一张方格大小固定的网格在上面，就好像一张网格纸。不是在单独的数组中存储我们的对象，我们将它们存到网格的格子中。每个格子存储一组单位，它们的位置在格子的边界内部。

当我们处理战斗时，我们只需考虑在同一格子中的单位。不是将游戏中的每个单位与其他所有单位比较，我们将战场划分为多个小战场，每个格子中的单位都较少。

一网格相邻单位

好了，让我们编码吧。首先，一些准备工作。这是我们的基础Unit类。

class Unit
{
  friend class Grid;

public:
  Unit(Grid* grid, double x, double y)
  : grid_(grid),
    x_(x),
    y_(y)
  {}

  void move(double x, double y);

private:
  double x_, y_;
  Grid* grid_;
};

每个单位都有位置（2D表示），以及一个指针指向它存在的Grid。我们让Grid成为一个friend类，因为，就像将要看到的，当单位的位置改变时，它需要和网格做复杂的交互，以确保所有事情都正确地更新了。

这里是网格的表示：

class Grid
{
public:
  Grid()
  {
    // 清空网格
    for (int x = 0; x < NUM_CELLS; x++)
    {
      for (int y = 0; y < NUM_CELLS; y++)
      {
        cells_[x][y] = NULL;
      }
    }
  }

  static const int NUM_CELLS = 10;
  static const int CELL_SIZE = 20;
private:
  Unit* cells_[NUM_CELLS][NUM_CELLS];
};

注意每个格子都是一个指向单位的指针。下面我们扩展Unit，增加next和prev指针：

class Unit
{
  // 之前的代码……
private:
  Unit* prev_;
  Unit* next_;
};

这让我们将对象组织为双向链表，而不是数组。

每个网格中的指针都指向网格中的元素列表的第一个，每个对象都有个指针指向它前面的对象，以及另一个指针指向它后面的对象。我们很快会知道为什么要这么做。

进入战场

我们需要做的第一件事就是保证新单位创建时被放置到了网格中。我们让Unit在它的构造函数中处理这个：

在这本书中，我避免使用任何C++标准库内建的集合类型。我想让理解例子所需的知识越少越好，然后，就像魔术师的“我的袖子里什么也没有”，我想明晰代码中确实在发生什么。细节很重要，特别是那些与性能相关的模式。
但这是我解释模式的方式。如果你在真实代码中使用它们，使用内建在几乎每种程序语言中的集合避免麻烦。人生苦短，不要浪费在编写链表上。

Unit::Unit(Grid* grid, double x, double y)
: grid_(grid),
  x_(x),
  y_(y),
  prev_(NULL),
  next_(NULL)
{
  grid_->add(this);
}

add()方法像这样定义：

void Grid::add(Unit* unit)
{
  // 检测它在哪个网格中
  int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
  int cellY = (int)(unit->y_ / Grid::CELL_SIZE);

  // 加到网格的对象列表前段
  unit->prev_ = NULL;
  unit->next_ = cells_[cellX][cellY];
  cells_[cellX][cellY] = unit;

  if (unit->next_ != NULL)
  {
    unit->next_->prev_ = unit;
  }
}

世界坐标除以网格大小转换到了网格空间。然后，缩短为int消去了分数部分，这样可以获得网格索引。

除了链表带来的繁琐，基本思路是非常简单的。我们找到单位所在的网格，然后将它添加到列表前部。如果那儿已经存在列表单位了，我们把新单位链接到旧单位的后面。

刀剑碰撞

一旦所有的单位都放入网格中，我们就可以让它们开始交互。使用这个新网格，处理战斗的主要方法看上去是这样的：

void Grid::handleMelee()
{
  for (int x = 0; x < NUM_CELLS; x++)
  {
    for (int y = 0; y < NUM_CELLS; y++)
    {
      handleCell(cells_[x][y]);
    }
  }
}

它在每个网格上面遍历并调用handleCell()。就像你看到的那样，我们真的已经将战场分割为分离的小冲突。每个网格之后像这样处理它的战斗：

void Grid::handleCell(Unit* unit)
{
  while (unit != NULL)
  {
    Unit* other = unit->next_;
    while (other != NULL)
    {
      if (unit->x_ == other->x_ &&
          unit->y_ == other->y_)
      {
        handleAttack(unit, other);
      }
      other = other->next_;
    }

    unit = unit->next_;
  }
}

除了遍历链表的指针把戏，注意它和我们原先处理战斗的原始方法完全一样。它对比每对单位，看看它们是否在同一位置。

不同之处是，我们不必再互相比较战场上所有的单位——只与那些近在一个格子中的相比较。这就是优化的核心。

冲锋陷阵

我们解决了性能问题，但同时制造了新问题。单位现在陷在它的格子中。如果将单位移出了包含它的格子，格子中的单位就再也看不到它了，但其他单位也看不到它。我们的战场有点过度划分了。

简单分析一下，似乎我们让性能更糟了。我们从对单位的双重循环变成了对格子内单位的三重循环。这里的技巧是内部循环现在只在很少的单位上运行，这足够抵消在格子上的外部循环的代价。
但是，这依赖于我们格子的粒度。如果它们太小，外部循环确实会造成影响。

为了解决这点，需要在每次单位移动时都做些工作。如果它跨越了格子的边界，我们需要将它从原来的格子中删除，添加到新的格子中。首先，我们给Unit添加一个改变位置的方法：

void Unit::move(double x, double y)
{
  grid_->move(this, x, y);
}

显而易见，AI代码可以调用它来控制电脑的单位，玩家也可以输入代码调用它来控制玩家的单位。它做的只是交换格子的控制权，之后：

void Grid::move(Unit* unit, double x, double y)
{
  // 看看它现在在哪个网格中
  int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
  int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);

  // 看看它移动向哪个网格
  int cellX = (int)(x / Grid::CELL_SIZE);
  int cellY = (int)(y / Grid::CELL_SIZE);

  unit->x_ = x;
  unit->y_ = y;

  // 如果它没有改变网格，就到此为止
  if (oldCellX == cellX && oldCellY == cellY) return;

  // 将它从老网格的列表中移除
  if (unit->prev_ != NULL)
  {
    unit->prev_->next_ = unit->next_;
  }

  if (unit->next_ != NULL)
  {
    unit->next_->prev_ = unit->prev_;
  }

  // 如果它是列表的头，移除它
  if (cells_[oldCellX][oldCellY] == unit)
  {
    cells_[oldCellX][oldCellY] = unit->next_;
  }

  // 加到新网格的对象列表末尾
  add(unit);
}

这块代码很长但也很直观。第一步检查我们是否穿越了格子的边界。如果没有，需要做的事情就是更新单位的位置，搞定。

如果单位已经离开了现在的格子，我们从格子的链表中移除它，然后再添加到网格中。就像添加一个新单位，它会插入新格子的链表中。

这就是为什么我们使用双向链表——我们可以通过设置一些指针飞快地添加和删除单位。每帧都有很多单位移动时，这就很重要了。

短兵相接

这看起来很简单，但我们某种程度上作弊了。在我展示的例子中，单位在它们有完全相同的位置时才进行交互。西洋棋和国际象棋中这是真的，但是对于更加实际的游戏就不那么准确了。它们通常需要将攻击距离引入考虑。

这个模式仍然可以好好工作，与检查位置匹配不同，我们这样做：

if (distance(unit, other) < ATTACK_DISTANCE)
{
  handleAttack(unit, other);
}

当范围被牵扯进来，需要考虑一个边界情况：在不同网格的单位也许仍然足够接近，可以交互。

这里，B在A的攻击半径内，即使中心点在不同的网格。为了处理这种情况，我们不仅需要比较同一网格的单位，同时需要比较邻近网格的对象。为了达到这点，首先我们让内层循环摆脱handleCell()：

void Grid::handleUnit(Unit* unit, Unit* other)
{
  while (other != NULL)
  {
    if (distance(unit, other) < ATTACK_DISTANCE)
    {
      handleAttack(unit, other);
    }

    other = other->next_;
  }
}

现在有函数接受一个单位和一列表的其他单位看看有没有碰撞。让handleCell()使这个函数：

void Grid::handleCell(int x, int y)
{
  Unit* unit = cells_[x][y];
  while (unit != NULL)
  {
    // 处理同一网格中的其他单位
    handleUnit(unit, unit->next_);

    unit = unit->next_;
  }
}

注意我们同样传入了网格的坐标，而不仅仅是对象列表。现在，这也许和前面的例子没有什么区别，但是我们会稍微扩展一下：

void Grid::handleCell(int x, int y)
{
  Unit* unit = cells_[x][y];
  while (unit != NULL)
  {
    // 处理同一网格中的其他单位
    handleUnit(unit, unit->next_);

    // 同样检测近邻网格
    if (x > 0 && y > 0) handleUnit(unit, cells_[x - 1][y - 1]);
    if (x > 0) handleUnit(unit, cells_[x - 1][y]);
    if (y > 0) handleUnit(unit, cells_[x][y - 1]);
    if (x > 0 && y < NUM_CELLS - 1)
    {
      handleUnit(unit, cells_[x - 1][y + 1]);
    }

    unit = unit->next_;
  }
}

这些新增handleCell()调用在八个邻近格子中的四个格子中寻找这个单位是否与它们有任何对抗。如果任何邻近格子的单位离边缘近到单位的攻击半径内，就找到碰撞了。

我们只查询一半的近邻格子，这原因和之前是一样的：内层循环从当前单位之后的单位开始——避免每对单位比较两次。考虑如果我们检查全部八个近邻格子会发生什么。

有单位的格子是U，它查找的邻近格子是X。

假设我们有两个在邻近格子的单位近到可以互相攻击，就像前一个例子。这是我们检查全部8个格子会发生的事情：

当找谁打了A时，我们检查它的右边找到了B。所以记录一次A和B之间的攻击。
当找谁打了B时，我们检查它的左边找到了A。所以记录第二次A和B之间的攻击。

只检查一半的近邻格子修复了这点。检查哪一半倒无关紧要。

我们还需要考虑另外的边界情况。这里，我们假设最大攻击距离小于一个格子。如果我们有较小的小格子和较长的攻击距离，我们也许需要扫描几行外的近邻格子。

设计决策

空间划分的优秀数据结构相对较少，可以一一列举进行介绍。但是，我试图根据它们的本质特性来组织。我期望当你学习四叉树和二分空间查找（BSPs）之类时，可以帮助你理解它们是如何工作，为什么工作，以帮你选择。

划分是层次的还是平面的？

我们的网格例子将空间划分成平面格子的集合。相反，层次空间划分将空间分成几个区域。然后，如果其中一个区域还包含多个对象，再划分它。这个过程递归进行，直到每个区域都有少于最大数量的对象在其中。

如果是平面划分：

更简单。平面数据结构更容易想到也更容易实现。
我在每章中都提到了这个设计要点，这是有理由的。尽可能使用简单的选项。大多数软件工程都是与复杂度做斗争。
内存使用量确定。由于添加新对象不需要添加新划分，空间分区的内存使用量通常在之前就可以确定。
在对象改变位置时更新得更快。当对象移动，数据结构需要更新，找到它的新位置。使用层次空间分区，可能需要在多层间调整层次结构。

如果是层次性的：

能更有效率地处理空的区域。考虑之前的例子，如果战场的一边是空的。我们需要分配一堆空白格子，这些格子浪费内存，每帧还要遍历它们。
由于层次空间分区不再分割空区域，大的空区域保存在单个划分上。不需要遍历很多小空间，那里只有一个大的。
它处理密集空间更有效率。这是硬币的另一面：如果你有一堆对象堆在一起，无层次的划分很没有效率。你最终将所有对象都划分到了一起，就跟没有划分一样。层次空间分区会自适应地划成小块，让你同时只需考虑少数对象。

划分依赖于对象集合吗？

在示例代码中，网格空间大小事先被固定了，我们在格子里追踪单位。另外的划分策略是自适应的——它们根据现有的对象集合在世界中的位置划分边界。

目标是均匀地划分，每个区域拥有相同的单位数量，以获得最好性能。考虑网格的例子，如果所有的单位都挤在战场的一个角落里。它们都会在同一格子中，找寻单位间攻击的代码退化为原来的O(n²) 问题。

如果划分与对象无关：

对象可以增量添加。添加对象意味着找到正确的划分然后放入，这点可以一次性完成，没有任何性能问题。
对象移动得更快。通过固定的划分，移动单位意味着从格子移除然后添加到另一个。如果划分它们的边界跟着集合而改变，那么移动对象会引起边界移动，导致很多其他对象也要移到其他划分。
划分也许不均匀。当然，固定的缺点就是对划分缺少控制。如果对象挤在一起，你就在空区域上浪费了内存，这会造成更糟的性能。

这可与如红黑树或AVL树这样的二叉搜索树相类比：当你添加事物时，你也许最终需要重排树，并重排一堆节点。

如果划分适应对象集合：

像BSPs和k-d树这样的空间划分切分世界，让每部分都包含接近相同数目的对象。为了做到这点，划分边界时，你需要计算每边各有多少对象。层次包围盒是另外一种为特定集合对象优化的空间分区。

你可以保证划分是平衡的。这不仅提供了优良的性能表现，还提供了稳定的性能表现：如果每个区域的对象数量保持一致，你可以保证游戏世界中的所有查询都会消耗同样的时间。一旦你需要固定帧率，这种一致性也许比性能本身更重要。
一次性划分一组对象更加有效率。当对象集合影响了边界的位置，最好在划分前将所有对象放在前面。这就是为什么美术和地理更多地使用这种划分。

如果划分与对象无关，但层次与对象相关：

有一种空间分区需要特殊注意，因为它拥有固定分区和适应分区两者的优点：四叉树。

四叉树划分二维空间。它的三维实现是八叉树，获取“空间”，分割为8个正方体。除了有额外的维度，它和平面划分一样工作。

四叉树开始时将整个空间视为单一的划分。如果空间中对象数目超过了临界值，它将其切为四小块。这些块的边界是确定的：它们总是将空间一切为二。

然后，对于四个区域中的每一个，我们递归地做相同的事情，直到每个区域都有较少数目的对象在其中。由于我们递归地分割有较多对象的区域，这种划分适应了对象集合，但是划分本身没有移动。

你可以在这里从左向右看到分区的过程：

对象可以增量增加。添加新对象意味着找到并添加到正确的区域。如果区域中的对象数目超过了最大限度，就划分区域。区域中的其他对象也划分到新的小区域中。这需要一些小小的工作，但是工作总量是固定的：你需要移动的对象数目总是少于数目临界值。添加对象从来不会引发超过一次划分。
删除对象也同样简单。你从它的格子中移除对象，如果它的父格子中的计数少于临界值，你可以合并这些子分区。
移动对象很快。当然，如上所述，“移动”对象只是添加和移除，两者在四叉树中都很快。
分区是平衡的。由于任何给定的区域的对象数目都少于最大的对象数量，哪怕对象都堆在一起，你也不会有包含太多对象的分区。

参见

在这里，我试图不讨论特定的空间分区结构细节来保证这章的高层概况性（而且节约篇幅！），但你的下一步应该是学习一下常见的结构。尽管名字很恐怖，但它们都令人惊讶地直观。常见的有：
每种空间分区数据结构基本上都是将一维数据结构扩展成更高维度的数据结构。知道它的相互关系有助于分辨它是不是问题的好解答：
- 网格是连续的桶排序。
- BSPs，k-d trees和包围盒是线性搜索树。
- 四叉树和八叉树是多叉树。

引言

数据局部性

意图

动机

数据仓库

CPU的托盘

等等，数据是性能？

模式

何时使用

记住

示例代码

连续数组

打包数据

冷/热 分割

设计决策

你如何处理多态？

游戏实体是如何定义的？

参见

脏标识

意图

动机

自身变换和世界变换

缓存世界变换

延期重计算

模式

何时使用

记住

延期太久是有代价的

每次状态改变你都得保证设置标识。

得将之前的推导数据保存在内存中。

示例代码

尚未优化的遍历

让我们变脏

设计决策

什么时候清空脏标识？

脏追踪的粒度有多细？

参见

对象池

意图

动机

碎片的诅咒

兼得鱼和熊掌

模式

何时使用

记住

池可能在不需要的对象上浪费内存

同时只能激活固定数量的对象

每个对象的内存大小是固定的

重用对象不会自动清除。

未使用的对象会保留在内存中

示例代码

空闲列表

设计决策

对象和池耦合吗？

谁负责初始化重用对象？

参见

空间分区

意图

动机

在战场上的单位

描绘战线

模式

何时使用

记住

示例代码

一张网格纸

一网格相邻单位

进入战场

刀剑碰撞

冲锋陷阵

短兵相接

设计决策

划分是层次的还是平面的？

划分依赖于对象集合吗？

参见

冷/热分割