如何使用C++中的Slot Map/Object Pool模式管理数百万个游戏对象？

Question

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

基本上,可以有多达数百万个对象,当玩家与游戏世界交互时,可以有多达数千个删除和重新创建.

问题是,原始创建者使用了一个插槽映射/对象池,当一个对象被移除时,指针被重复使用.这是一个巨大的性能提升,因为除非需要,否则不需要进行太多的内​​存重新分配.

当然,我正在努力实现这一目标,但我的Slot Map遇到了一个巨大的问题:

以下是根据我在网上找到的来源,Slot Map如何工作的一些解释:

Object类是每个游戏对象的基类,我的Slot Map/object Pool使用这个Object类来保存每个分配的对象.

例:

struct TObjectBlock
{
     Object Object[36768];
};

插槽映射的工作方式是,服务器首先在TObjectBlock列表中分配36768个对象,并为每个Object提供唯一的ID ObjectID,当服务器需要创建时,可以在空闲对象列表中重用它们一个新的对象.

例:

对象1(ID:555)被删除,它的ID 555被放入一个空闲对象ID列表中,请求创建一个项目,因为它在自由对象列表上而被重用ID 555,并且不需要重新分配另一个TObjectBlock用于其他对象的数组.

我的问题:如何使用"播放器""生物""项目""平铺"来支持此插槽地图？我似乎没有想出解决这个逻辑问题的方法.

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

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

我相信你在这里有很多纠结的概念,你需要解开它们才能使这项工作成功.

首先,你实际上是在击败这个模型的主要目的.你所展示的货物崇拜节目的味道很糟糕.new如果你认真对待,你不应该成为对象,至少没有超载.您应该为给定的对象类型分配一个大的内存块,并在"分配"中从中分配 - 无论是来自重载new还是通过内存管理器类创建.这意味着每个对象类型需要单独的内存块,而不是单个"对象"块.

整个想法是,如果要避免实际内存的分配 - 释放,则需要重用内存.要构造一个对象,您需要足够的内存来适应它,并且您的类型长度不​​同.只有Tile在你的例子是大小相同的Object,所以只有那些能够共享相同的内存(但它不应该).其他类型都不能放在对象内存中,因为它们更长.每种类型都需要单独的池.

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

为什么？假设你把对象40,"删除"它,然后创建一个新对象40.现在让我们说程序的一些有缺陷的部分引用了原始的ID 40.它会寻找原始的40,这应该是错误的,但是却找到了你只是创造了一个完全无法解决的错误.虽然这可以通过指针发生,但更有可能发生ID,因为很少有系统对ID使用情况进行检查.使用ID间接访问的一个主要原因是通过简化捕获不良用法来使访问更安全,因此通过使ID可重用,您使它们与存储指针一样不安全.

处理此问题的实际模型应该与操作系统执行类似操作的方式类似(请参阅下面的分数,了解更多内容......).也就是说,遵循这样的模型:

1. 创建一种你想要存储的类型的数组(如矢量) - 实际类型,而不是指向它的指针.不是Object,这是一个通用的基础,但类似的东西Player.
2. 根据您希望的尺寸调整尺寸.
3. 创建一个size_t(用于索引)的堆栈,并将其推入数组中的每个索引.如果您创建了10个对象,则按0 1 2 3 4 5 6 7 8 9.
4. 每次需要一个对象时,从堆栈中弹出索引并使用该数组的单元格中的内存.
5. 如果用完索引,请增加向量的大小并推送新创建的索引.
6. 当您使用对象时,通过弹出的索引进行间接.

基本上,您需要一个类来管理内存.

另一种模型是直接将指针推入具有匹配指针类型的堆栈.有一些好处,但它也更难调试.该系统的主要好处是可以轻松地将其集成到现有系统中; 但是,大多数编译器已经类似了...

那就是说,我建议不要这样做.它在纸面上似乎是一个好主意,并且在非常有限的系统上,但现代操作系统不是该定义的"有限系统".虚拟内存已经解决了这样做的最大原因,内存碎片(你没有提到).许多编译器分配器将尝试通过从内存池中抽取来或多或少地在标准库容器中执行您尝试执行的操作,并且这些更易于管理.

我曾经像这样实现了一个系统,但由于很多很好的理由,它抛弃了它,转而支持一系列无序的指针映射.如果我发现与此模型相关的性能或内存问题,我计划更换分配器.这让我可以抵消管理内存直到测试/优化的问题,并且不需要在每个级别进行古怪的系统设计来处理抽象.

当我说"古怪"时,相信我,当我说间接池堆栈设计比我列出的更多烦恼.