How to manage millions of game objects with a Slot Map / Object Pool pattern in C++?

Question

I'm developing a game server for a video game called Tibia.

Basically, there can be up to millions of objects, of which there can be up to thousands of deletes and re-creations as players interact with the game world.

The thing is, the original creators used a Slot Map / Object Pool on which pointers are re-used when an object is removed. This is a huge performance boost since there's no need to do much memory reallocation unless needed.

And of course, I'm trying to accomplish that myself, but I've come into one huge problem with my Slot Map:

Here's just a few explanation of how Slot Map works according to a source I found online:

Object class is the base class for every game object, my Slot Map / object Pool is using this Object class to save every allocated object.

Example:

struct TObjectBlock
{
     Object Object[36768];
};

The way the slot map works is that, the server first allocates, say, 36768 objects in a list of TObjectBlock and gives them a unique ID ObjectID for each Object which can be re-used in a free object list when the server needs to create a new object.

Example:

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.

My problem: How can I use "Player" "Creature" "Item" "Tile" to support this Slot Map? I don't seem to come up with a solution into this logic problem.

I am using a virtual class to manage all objects:

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

Then, I'd create the objects themselves:

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

struct Player : Creature
{

};

struct Item : Object
{
     uint16_t Attack;
};

struct Tile : Object
{

};

But now if I was to make use of the slot map, I'd have to do something like this:

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;
}

It pretty much doesn't make much sense to set a whole new object pointer the already allocated object unique ID.

What are my options with this logic?

Answer 1

I believe you have a lot of tangled concepts here, and you need to detangle them to make this work.

First, you are actually defeating the primary purpose of this model. What you showed smells badly of cargo cult programming. You should not be newing objects, at least without overloading, if you are serious about this. You should allocate a single large block of memory for a given object type and draw from that on "allocation" - be it from an overloaded new or creation via a memory manager class. That means you need separate blocks of memory for each object type, not a single "objects" block.

The whole idea is that if you want to avoid allocation-deallocation of actual memory, you need to reuse the memory. To construct an object, you need enough memory to fit it, and your types are not the same length. Only Tile in your example is the same size as Object, so only that could share the same memory (but it shouldn't). None of the other types can be placed in the objects memory because they are longer. You need separate pools for each type.

Second, there should be no bearing of the object ID on how things are stored. There cannot be, once you take the first point into consideration, if the IDs are shared and the memory is not. But it must be pointed out explicitly - the position in a memory block is largely arbitrary and the IDs are not.

Why? Let's say you take object 40, "delete" it, then create a new object 40. Now let's say some buggy part of the program referenced the original ID 40. It goes looking for the original 40, which should error, but instead finds the new 40. You just created an entirely untrackable error. While this can happen with pointers, it is far more likely to happen with IDs, because few systems impose checks on ID usage. A main reason for indirecting access with IDs is to make access safer by making it easy to catch bad usage, so by making IDs reusable, you make them just as unsafe as storing pointers.

The actual model for handling this should look like how the operating system does similar operations (see below the divide for more on that...). That is to say, follow a model like this:

1. Create some sort of array (like a vector) of the type you want to store - the actual type, not pointers to it. Not Object, which is a generic base, but something like Player.
2. Size that to the size you expect to need.
3. Create a stack of size_t (for indexes) and push into it every index in the array. If you created 10 objects, you push 0 1 2 3 4 5 6 7 8 9.
4. Every time you need an object, pop an index from the stack and use the memory in that cell of the array.
5. If you run out of indexes, increase the size of the vector and push the newly created indexes.
6. When you use objects, indirect via the index that was popped.

Essentially, you need a class to manage the memory.

An alternative model would be to directly push pointers into a stack with matching pointer type. There are benefits to that, but it is also harder to debug. The primary benefit to that system is that it can easily be integrated into existing systems; however, most compilers do similar already...

---

That said, I suggest against this. It seems like a good idea on paper, and on very limited systems it is, but modern operating systems are not "limited systems" by that definition. Virtual memory already resolves the biggest reason to do this, memory fragmentation (which you did not mention). Many compiler allocators will attempt to more or less do what you are trying to do here in the standard library containers by drawing from memory pools, and those are far more manageable to use.

I once implemented a system just like this, but for many good reasons have ditched it in favor of a collection of unordered maps of pointers. I have plans to replace allocators if I discover performance or memory problems associated with this model. This lets me offset the concern of managing memory until testing/optimization, and doesn't require quirky system design at every level to handle abstraction.

When I say "quirky", believe me when I say that there are many more annoyances with the indirection-pool-stack design than I have listed.