9
\$\begingroup\$

I'm making a game that uses component-based game objects, and I am having a hard time implementing a way for each component to communicate with its game object. Rather than explain everything at once, I will explain each part of relevant sample code:

class GameObjectManager {
    public:
        //Updates all the game objects
        void update(Time dt);

        //Sends a message to all game objects
        void sendMessage(Message m);

    private:
        //Vector of all the game objects
        std::vector<GameObject> gameObjects;

        //vectors of the different types of components
        std::vector<InputComponent> input;
        std::vector<PhysicsComponent> ai;
        ...
        std::vector<RenderComponent> render;
}

The GameObjectManager holds all the game objects and their components. It is also responsible for updating the game objects. It does this by updating the component vectors in a specific order. I use vectors instead of arrays so that there is virtually no limit to the number of game objects that can exist at once.

class GameObject {
    public:
        //Sends a message to the components in this game object
        void sendMessage(Message m);

    private:
        //id to keep track of components in the manager
        const int id;

        //Pointers to components in the game object manager
        std::vector<Component*> components;
}

The GameObject class knows what its components are and can send messages to them.

class Component {
    public:
        //Receives messages and acts accordingly
        virtual void handleMessage(Message m) = 0;

        virtual void update(Time dt) = 0;

    protected:
        //Calls GameObject's sendMessage
        void sendMessageToObject(Message m);

        //Calls GameObjectManager's sendMessage
        void sendMessageToWorld(Message m);
}

The Component class is pure virtual so that classes for the different types of components can implement how to handle messages and update. It also is able to send messages.

Now the problem arises on how the components can call the sendMessage functions in GameObject and GameObjectManager. I came up with two possible solutions:

  1. Give Component a pointer to its GameObject.

However, since the game objects are in a vector, the pointers could quickly become invalidated (The same could be said of the vector in GameObject, but hopefully the solution to this problem can also solve that one). I could put the game objects in an array, but then I would have to pass in an arbitrary number for the size, which could easily be unnecessarily high and waste memory.

  1. Give Component a pointer to the GameObjectManager.

However, I do not want components to be able to call the manager's update function. I am the only person working on this project, but I do not want to get in the habit of writing potentially dangerous code.

How can I resolve this problem while keeping my code safe and cache friendly?

\$\endgroup\$
6
\$\begingroup\$

Your communication model seems fine, and option one would work okay if only you could store those pointers safely. You can solve that problem by picking a different data structure for component storage.

A std::vector<T> was a reasonable first choice. However, the container's iterator invalidation behavior is a problem. What you want is a data structure that is fast and cache-coherent to iterate over, and which also preserves iterator stability when inserting or removing items.

You can build such a data structure. It consists of a linked-list of pages. Each page has a fixed capacity, and holds all its items in one array. A count is used to indicate how many items in that array are active. A page also has a free list (allowing reuse of cleared entries) and a skip list (allowing you to skip over cleared entries while iterating.

In other words, conceptually something like:

struct Page {
   int count;
   int capacity;           // Optional if every page is a fixed size.
   T * m_storage;
   bool * m_skip;          // Skip list; can be bit-compressed.
   std::stack<int> m_free; // Can be replaced with a specialized stack.

   Page * next;
   Page * prior;           // Optional, allows reverse iteration
};

I unimaginatively call this data structure a book (because it's a collection of pages you iterate though), but the structure has various other names.

Matthew Bentley calls it a "colony." Matthew's implementation uses a jump-counting skip field (apologies for the MediaFire link, but it's how Bentley himself hosts the document) which is superior to the more typical boolean-based skip list in these sorts of structures. Bentley's library is header-only and easy to drop in to any C++ project, so I'd advise you to simply use that versus rolling your own. There are a lot of subtleties and optimizations I'm glossing over here.

Because this data structure never moves items once they are added, pointers and iterators to that item remain valid until that item itself is deleted (or the container itself is cleared). Because it stores chunks of contiguously-allocated items, iteration is fast and mostly-cache-coherent. Insertion and removal are both reasonable.

It's not perfect; it's possible to ruin cache coherency with a usage pattern that involves deleting heavily from effectively random spots in the container and then iterating over that container before subsequent inserts have backfilled items. If you are in that scenario often, you will be skipping potentially-large regions of memory at a time. However in practice I think this container is a reasonable choice for your scenario.

Other approaches, which I will leave for other answers to cover, might include a handle-based approach or a slot-map sort of structure (where you have an associative array of integer "keys" to integer "values," the values being indices in a backing array, which allows you to iterate over a vector by still access by "index" with some extra indirection).

\$\endgroup\$
  • \$\begingroup\$ Hi! Is there any resources where I can learn more about alternatives to "colony" that you mentioned in the last paragraph? Are they implemented anywhere? I've been researching this topic for some time and I'm really interested. \$\endgroup\$ – Rinat Veliakhmedov Apr 19 '17 at 23:57
5
\$\begingroup\$

Being 'cache friendly' is a preoccupation big games have. This seems to be premature optimization to me.


One way to solve this without being 'cache friendly' would be to create your object on the heap instead of on the stack: use new and (smart)pointers for your objects. This way, you'll be able to reference your objects and their reference will not be invalidated.

For a more cache friendly solution, you could manage the de/allocation of objects yourself, and use handles to these objects.

Basically, at the initialization of your program, an object reserves a chunk of memory on the heap (let's call it MemMan), then, when you want to create a component, you tell MemMan that you need a component of size X, it'll reserve it for you, create a handle and keep internally where in it's allocation is the object for that handle. It'll return the handle, and that the only thing you'll keep about the object, never a pointer to its location in memory.

As you need the component, you'll ask MemMan to access this object, which it will gladly do. But don't keep the reference to it because....

One of the jobs of MemMan is to keep the objects close one to another in memory. Once every few game frames, you can tell MemMan to rearrange objects in memory (or it could do it automatically when you create/delete objects). It'll update its handle-to-memory-location map. Your handles will always be valid, but if you kept a reference to the memory space (a pointer or a reference), you'll find only despair and desolation.

Textbooks says that this way of managing your memory has at least 2 advantages:

  1. less cache misses because objects are close one to another in memory and
  2. it reduces the number of memory de/allocation calls you'll make to the OS, which are said to take some time.

Keep in mind that the way you use MemMan and how you'll organize the memory internally is really dependant on how you'll use your components. If you'll iterate through them based on their type, you'll want to keep components by type, if you iterate through them based on their game object, you'll need to find a way to make sure they're close one to another based on that, etc...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.