游戏编程模式笔记——第十九章 对象池

“使用固定的对象池重用对象，取代单独地分配和释放对象，以此来达到提升性能和优化内存使用的目的。”

动机

一个魔棒就会生成数以百计的粒子，所以我们的系统需要非常快速地生成它们。更重要的是，我们需要确保创建和销毁它们时不会产生内存碎片。

碎片化的害处

为游戏机和移动设备编程在多方面都比传统的PC编程更接近于嵌入式编程。就像嵌入式编程一样，内存是稀缺的，用户希望游戏稳定运行，但是极少有高效的内存压缩管理器可以使用。在这样的环境下，内存碎片往往是致命的。
碎片化意味着我们空闲的堆空间分裂成了许多小的内存碎片，而不是一整块连续的内存块。或许这些小碎片构成的可访问内存总量很大，但其中最长的、连续的区域却小得可怜。假如我们有14字节的空闲空间，但它被一段已使用内存分割为了两个7字节的字段。假如我们尝试分配一个12字节的对象，那么便会失败。
大多数游戏制造商都要求游戏通过“侵泡测试”(“soak tests”)——他们将游戏置于demo模式连续地跑上好几天。多数情况下，碎片化的扩张或者内存泄露才是导致游戏宕机的原因。
即使碎片化的情况很少，它也仍然在削减着内存并使其成为一个千疮百孔而不可用的泡沫块，严重局限了整个游戏的表现力。

二者兼顾

由于碎片化，以及内存分配缓慢的缘故，在游戏中何时以及如何管理内存需要十分小心。一个常用而有效的办法是：在游戏启动时分配一大块内存，直到游戏结束时才释放它。但如此一来，在游戏运行过程中创建或销毁东西，对系统来说将是一个巨大的负担。
使用对象池使得我们能二者兼顾：对于内存管理器而言，我们仅分配一大块内存直到游戏结束时才释放它，对于内存池的使用者而言，我们可以按照自己的意愿来分配和释放对象。

对象池模式

定义一个保持着可重用对象集合的对象池类。其中的每个对象支持对其“使用(in use)”状态的访问，以确定这一对象目前是否“存活(alive)”。在对象池初始化时，它预先创建整个对象的集合（通常为一整块连续堆区域），并将它们都置为“未使用(not in use)”状态。
当你想要创建一个新对象时就向对象池请求。它将搜索到一个可用的对象，将其初始化为“使用中(in use)”状态并返回给你。当该对象不再被使用时，它将被置回“未使用(not in use)”状态。使用该方法，对象便可以在无需进行内存或其他资源分配的情况下进行任意的创建和销毁。

使用情境

这一设计模式被广泛地应用于游戏中的可见物体，如游戏实体对象、各种视觉特效，但同时也被适用于非可见的数据结构中，如当前播放的声音。我们在以下情况使用对象池：

• 当你需要频繁地创建和销毁对象时。
• 对象的大小一致时。
• 在堆上进行对象内存分配较慢或者会产生内存碎片时。
• 每个对象封装着获取代价昂贵且可重用的资源，如数据库、网络的连接。

使用须知

你一般依赖于一个垃圾回收器或只是简单地通过new和delete来进行内存管理。而通过使用对象池，你就是在告诉系统:“我更明白这些字节应该如何处理。”也就意味这个模式的规则完全由你来负责制定。

对象池可能在闲置的对象上浪费内存

对象池的大小需要根据游戏的需求量身定制。在确定大小时，分配过小的情况往往很明显，但也要注意不能让池子太大。一个适当小的内存池可以腾出空余的内存供其他模块使用。

任意时刻处于存活状态的对象数目恒定

在某些角度上说这是件好事。将内存划分为几个独立的对象池用于不同类型的对象管理，这一点会确保下面的情况不会发生：例如，一大连串的爆炸动画不会致使你的粒子系统把所有的可用内存全部占用，从而防止一些更严重的情况发生，比如无法创建新的敌人。
然而，这也意味着你要为如下情况做好准备：当你希望向对象池申请重用某个对象时，可能会失败，因为它们都在被使用。以下是一些针对此问题的常见对策：

• 阻止其发生。这也是最常见“修复方法”：约束对象池的大小，这样无论使用者如何分配都不会造成溢出。
  上述方法的副作用是，它会令你仅仅为了十分罕见的边际情况而腾出许多空闲的对象空间。鉴于此，单一的固定大小的对象池并不适用于所有的游戏状态。在此情况下，可以考虑针对不同的场景将池调整至不同尺寸。
• 不创建对象。这听起来很残忍，但它在诸如粒子系统中十分奏效。假如所有的粒子对象都处于使用状态，那么屏幕将可能被闪光的图元所覆盖。玩家将不会注意到下一次的爆炸效果是否和当前的效果一样炫。
• 强行清理现存对象。以一个音效对象池为例，并假设你想要播放新的一段音效但对象池满了。你并不希望直接忽略掉这个新的音效。解决方案是，检索当前播放的音效中最不引人注意的并以我们的新音效替换之。新的音效将掩盖旧音效的中断。
  一般来说，如果新对象的出现能让玩家无法察觉到有对象的消失，那么清理现存对象的方法会是一个好选择。
• 增加对象池的大小。假如游戏允许你调配更多的内存，那么你可以在运行时对对象池扩容，或者增设一个二级的溢出池。假如你通过上述任何一种方法获取到更多的内存，那么当这些额外空间不再被占用时你就必须考虑是否将池的大小恢复到扩容之前。

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

多数对象池在实现时将对象原地存入一个数组中。假如你的所有对象都属于同一类型，那么这没问题。然而假如你希望在池中存入不同类型的对象，或者子类型，那么你就必须保证对象池中的每个槽都有足够的内存能容纳最大的对象。否则一个未知的大对象将占去相邻对象的空间，并导致内存崩溃。
另外来讲，当你的内存大小不一时，将浪费内存，当你发现自己浪费许多内存时，可以考虑根据对象的尺寸将池划分为多个大小不同的池——大的装行李，小的装口袋里的杂物。

重用对象不会被自动清理

多数内存管理器都有一个排错特性：它们会将刚分配或者刚释放的内存置成某些特定值（比如0xdeadbeef）。这一做法将帮助你找到那些由“未初始化的变量”或者“使用了已释放的内存”引发的致命错误。
由于我们的对象池并不通过内存管理器来重用对象，所以我们丧失了这层安全保障。更可怕的是，这些“新”对象使用的内存先前存储着另一个同类型的对象。这将使你无法分辨自己是否在创建对象时已将他们初始化——这块存储新对象的内存可能在其先前的生命周期中已经包含了几乎完全相同的数据。
鉴于此，需要特别注意用于初始化对象池中新对象的代码是否完整地初始化了对象。甚至值得花些工夫为回收对象槽内存增设一个排错功能。

未使用的对象将占用内存

由于对象池在对象不再被使用时并不真正地释放它们，故他们仍将占用内存。假如它们包含了指向其他对象的引用，那么这也将阻碍回收器对它们进行回收。为避免这些问题，当对象池中的对象不再被需要时，应当清空对象指向其他任何对象的引用。

示例代码

让我们来模拟一个简单的粒子系统。让我们先从最简单的开始，首先是粒子类：

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

    void init(double x, double y, double xVel, double yVel, int lifetime);
    void animate();
    bool inUse() const { return framesLeft_ > 0; }
    
private:
    int framesLeft_;
    double x_,y_;
    double xVel, yVel; 
};

默认构造函数将粒子初始化为“未使用”状态。接下来调用init()将其状态置为“使用中”。粒子随着时间播放动画，并逐帧调用函数animate()。

void Particle::init(double x, double y, double xVel, double yVel, int lifetime)
{
    x_ = x;
    y_ = y;
    xVel_ = xVel;
    yVel_ = yVel;
    framesLeft_ = lifetime;
}
void Particle::animate()
{
    if( !inUse() ) return;

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

对象池需要知道哪些粒子可被重用——通过粒子实例的inUse()方法来获取粒子的状态。它利用粒子的生命周期有限这一点，使用变量_framesLeft来检查哪些粒子正在被使用，而不是使用一个单独的标志位。
对象池类也很简单:

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

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

create()函数使用外部代码创建新的粒子。游戏逐帧调用对象池的animate()方法，它会遍历池中所有粒子并调用它们的animate()函数。

void ParticlePool::animate()
{
    for( int i = 0; i < POOL_SIZE; i++)
    {
        particles_[i].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())
        {
            particle_[i].init(x,y,xVel, yVel, lifetime);
            return;
        } 
    }
}

注意在这个版本中，假如没有找到可用的粒子，则不再创建新的粒子。当粒子的生命周期结束时它们会自动地将自己闲置下来。
这个例子中创建一个新粒子需要在池内部遍历粒子数组直到找到一个空槽。假设这个池数组很大且几乎已满，则此时创建粒子将会十分缓慢。让我们来看看如何提升性能。
空闲表
如果我们不想浪费时间去检索空闲的粒子，那么显然我们得跟踪它们。我们可以单独维护一个指向每个未被使用粒子的指针列表。那么，当我们需要创建粒子时，我们只需移除这个列表的第一项并将这第一项指针指向的例子进行重用即可。
不幸的是，这可能要求我们管理如同整个对象池对象数组一样庞大的指针列表。方便的是，我们身边就有一些可利用的资源：正是那些未被利用的粒子自身。
当某个粒子未被使用时，它的大部分状态时异常的。它的位置和速度都未被使用。它唯一需要的状态就是用于自身是否被销毁的标记，也就是我们例子中的frameLeft成员。除此之外的其他空间都是可利用的，修改后的例子如下：

class Particle
{
public:
    // Previous stuff...
    Particle* getNext() const { return state_.next; }
    void setNext(Particle* next)    {
    
        state_.next = next;   
    }
private:
    int framesLeft_;

    union
    {
        // State when it's in use.
        struct
        {
            double x, y, xVel, yVel;
        } live;
    
        // State when it's available.
        Particle* next;
    } state_;   
};

我们把除了frameLeft之外的成员变量移动到一个live结构体中，并将它置入一个state联合体。该结构包括了粒子在播放动画时的状态。当粒子未被使用时，也就是联合体的其他情况，成员next将被激活。next存储了一个指向下一个可用粒子的指针。
我们可以利用这些指针(next成员)来创建一个对象池中未被使用的粒子列表。我们持有所需的可用粒子列表，且无需额外的内存——我们将那些已死亡粒子占用的空间划分过来以存储这个列表。
这个巧妙的解决办法被称作空闲表(free list)，为使其正常运作，我们需要确保正确地初始化指针以及在创建和销毁粒子时保持住指针。当然，我们也需要时刻跟踪这个列表的头指针：

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

当对象池首次被创建时，所有的粒子均处于可用状态，故我们的空闲表贯穿了整个对象池。对象池的构造函数如下:

ParticlePool::ParticlePool()
{
    // The first one is available
    firstAvailable_ = &particles_[0];

    // Each particle points to the next.
    for( int i = 0; i < POOL_SIZE - 1; i++)
    {
        particles_[i].setNext(&particles_[i +1]);
    }
    // The last one terminates the list.
    particles_[POOL_SIZE - 1].setNext(NULL);
}

现在创建一个新粒子时我们跳转到一个空闲的粒子:

void ParticlePool::create(double x, double y, double xVel, double yVel, int lifetime)
{
    // Make sure the pool isn't full.
    assert(firstAvailable_ != NULL);

    // Remove it from the available list.
    Particle* newParticle = firstAvailable_;
    firstAvailable_ = newParticle->getNext();

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

我们需要获知粒子何时死亡以将它置回空闲表中。

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())
        {
            // Add this particle to the front of the list.
            particles_[i].setNext(firstAvailable_);
            firstAvailable_ = &particles_[i];
        }
    }
}

O(1)的复杂度！

设计决策

最简单的对象池实现几乎没什么特别的：创建一个对象数组并在它们被需要时重新初始化。实际项目中的代码可不会这么简单。还有许多扩展对象池的方法，来使其更加通用、安全、便于管理。当你在自己的游戏中使用对象池时，你需要回答以下问题。

对象是否被加入对象池

首先要问的一个问题就是这些对象自身是否能知道自己处于一个对象池中。
假如对象与对象池耦合

• 实现很简单，你可以简单地为那些池中的对象增加一个“使用中”的标志位或者函数，这就能解决问题了。

• 你可以保证对象只能通过对象池创建，确保了开发者不会创建出脱离对象池管理的对象。在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]; 
  }

谁来初始化哪些被重用的对象

假如在对象池内部初始化重用对象

• 对象池完全可以封装它管理的对象。这取决于你定义的对象类的其他功能，你或许能够将它们置于对象池内部。这样可以确保外部代码不会引用到这些对象而引起意外的重用。
• 对象池与对象如何被初始化密切相关。一个置入对象池的对象可能会提供多个初始化函数。

假如对象在外部被初始化

• 此时对象池的接口会简单一些。对象池只需简单地返回新对象的引用既可。而无需像上面那样提供不同的初始化接口来处理对象不同的初始化方法。
• 外部编码可能需要处理新对象创建失败的情况。