c++ - 如何使用C++中的插槽图/对象池模式管理数百万个游戏对象？

Question

我正在为名为Tibia的视频游戏开发游戏服务器。

基本上，最多可以有数百万个对象，其中随着玩家与游戏世界进行交互，最多可以有数千个删除和重新创建。

事实是，原始创建者使用了“插槽映射/对象池”，在删除对象时会在其上重新使用指针。这是极大的性能提升，因为除非需要，否则无需进行大量的内存重新分配。

当然，我正在尝试自己实现这一目标，但是我的广告位图出现了一个巨大的问题:

根据我在网上找到的信息，这只是一些关于插槽图如何工作的解释:

对象类是每个游戏对象的基类，我的插槽 map /对象池正在使用此对象类来保存每个分配的对象。

例子:

struct TObjectBlock
{
     Object Object[36768];
};

插槽映射的工作方式是，服务器首先在 TObjectBlock 列表中分配36768个对象，并为每个对象赋予它们唯一的ID ObjectID，当服务器需要创建一个新对象。

例子:

Object 1 (ID: 555) is deleted, it's ID 555 is put in a free object ID list, an Item creation is requested, ID 555 is reused since it's on the free object list, and there is no need to reallocate another TObjectBlock in the array for further objects.

我的问题:如何使用“玩家”，“生物”，“物品”，“瓷砖”来支持此版位图？我似乎没有想出解决此逻辑问题的方法。

我正在使用一个虚拟类来管理所有对象:

struct Object
{
    uint32_t ObjectID;
    int32_t posx;
    int32_t posy;
    int32_t posz;
};

然后，我将自己创建对象:

struct Creature : Object
{
     char Name[31];
};

struct Player : Creature
{

};

struct Item : Object
{
     uint16_t Attack;
};

struct Tile : Object
{

};

但是现在，如果我要使用广告位图，则必须执行以下操作:

Object allocatedObject;
allocatedObject.ObjectID = CreateObject(); // Get a free object ID to use
if (allocatedObject.ObjectID != INVALIDOBJECT.ObjectID)
{
      Creature* monster = new Creature();
      // This doesn't make much sense, since I'd have this creature pointer floating around!
      monster.ObjectID = allocatedObject.ObjectID;
}

将一个新的对象指针设置为已分配的对象唯一ID几乎没有多大意义。

使用此逻辑我有哪些选择？

Answer 1

我相信您在这里有很多纠结的概念，您需要将它们弄乱才能完成这项工作。

首先，您实际上在击败该模型的主要目的。您所显示的内容对 cargo 邪教编程有严重的不良影响。如果您对此很认真的话，则至少不应在不重载的情况下对对象进行new编码。您应该为给定的对象类型分配一个大的内存块，并从“分配”中提取该内存块-是从重载的new还是通过内存管理器类创建的。这意味着每种对象类型都需要单独的内存块，而不是单个“对象”块。

整个想法是，如果您想避免实际内存的分配-取消分配，则需要重用该内存。要构造一个对象，您需要足够的内存来容纳它，并且您的类型长度不​​相同。在您的示例中，只有Tile与Object的大小相同，因此只有这样才能共享相同的内存(但不应该)。其他类型都不能放置在对象存储器中，因为它们更长。每种类型都需要单独的池。

其次，对象ID不应影响事物的存储方式。一旦考虑了第一点，就不可能存在ID共享而不是内存共享的情况。但是必须明确指出-内存块中的位置在很大程度上是任意的，而ID则不是。

为什么？假设您拿了对象40，“删除”了它，然后创建了一个新对象40。现在，我们说程序中有很多错误的部分引用了原始ID40。它去寻找原始40，应该出错，但是找到了新40。您刚刚创建了一个完全无法跟踪的错误。尽管指针可能发生这种情况，但ID发生的可能性更大，因为很少有系统会对ID的使用情况进行检查。间接使用ID进行访问的主要原因是通过易于捕获不良用法来提高访问的安全性，因此，通过使ID可重用，就可以使它们与存储指针一样不安全。

用于处理此问题的实际模型应看起来像操作系统如何执行类似的操作(有关此内容的更多信息，请参见下面的分隔线...)。也就是说，遵循这样的模型:

创建某种类型的数组(例如 vector )，该数组要存储的类型-实际类型，而不是指向它的指针。不是Object(这是通用基础)，而是类似Player的东西。

将大小调整为所需的大小。

创建一个size_t堆栈(用于索引)，并将数组中的每个索引插入堆栈。如果创建了10个对象，则按0 1 2 3 4 5 6 7 89。

每当您需要一个对象时，请从堆栈中弹出一个索引，然后使用该数组单元中的内存。

如果索引用完，请增加 vector 的大小并推送新创建的索引。

使用对象时，通过弹出的索引间接。

本质上，您需要一个类来管理内存。

一种替代模型是将指针直接插入具有匹配指针类型的堆栈中。这样做有很多好处，但是也很难调试。该系统的主要好处是可以轻松地将其集成到现有系统中；但是，大多数编译器已经做了类似的工作...

话虽如此，我建议反对这一点。从表面上看，这似乎是一个好主意，但在非常有限的系统上，这似乎是一个好主意，但是按照该定义，现代操作系统不是“有限的系统”。虚拟内存已经解决了这样做的最大原因，内存碎片(您没有提到)。许多编译器分配器将尝试通过从内存池中进行提取来或多或少地执行您在标准库容器中要执行的操作，并且使用起来要容易得多。

我曾经像这样实现过一个系统，但是出于许多充分的理由，我放弃了该系统，转而使用了无序指针映射的集合。如果发现与此模型相关的性能或内存问题，我计划更换分配器。这使我可以消除在测试/优化之前管理内存的问题，并且不需要在每个级别进行古怪的系统设计来处理抽象。

当我说“古怪”时，请相信我，当我说间接池堆栈设计比我列出的烦恼多得多时。