Comment puis-je prendre en charge la communication composant-objet en toute sécurité et avec un stockage de composants compatible avec le cache?

Je crée un jeu qui utilise des objets de jeu basés sur des composants, et j'ai du mal à implémenter un moyen pour chaque composant de communiquer avec son objet de jeu. Plutôt que d'expliquer tout à la fois, j'expliquerai chaque partie de l'exemple de code pertinent:

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

Le GameObjectManagercontient tous les objets du jeu et leurs composants. Il est également responsable de la mise à jour des objets du jeu. Il le fait en mettant à jour les vecteurs de composants dans un ordre spécifique. J'utilise des vecteurs au lieu de tableaux afin qu'il n'y ait pratiquement aucune limite au nombre d'objets de jeu pouvant exister à la fois.

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

La GameObjectclasse sait quels sont ses composants et peut leur envoyer des messages.

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

le Component classe est entièrement virtuelle afin que les classes pour les différents types de composants puissent implémenter comment gérer les messages et les mettre à jour. Il est également capable d'envoyer des messages.

Maintenant, le problème se pose sur la façon dont les composants peuvent appeler les sendMessagefonctions dans GameObjectet GameObjectManager. J'ai trouvé deux solutions possibles:

1. Donnez Componentun pointeur à son GameObject.

Cependant, comme les objets du jeu sont dans un vecteur, les pointeurs pourraient rapidement être invalidés (la même chose pourrait être dite du vecteur dans GameObject, mais j'espère que la solution à ce problème peut également résoudre celui-ci). Je pourrais mettre les objets du jeu dans un tableau, mais je devrais alors passer un nombre arbitraire pour la taille, qui pourrait facilement être inutilement élevé et gaspiller de la mémoire.

2. Donnez Componentun pointeur sur le GameObjectManager.

Cependant, je ne veux pas que les composants puissent appeler la fonction de mise à jour du gestionnaire. Je suis la seule personne à travailler sur ce projet, mais je ne veux pas prendre l'habitude d'écrire du code potentiellement dangereux.

Comment puis-je résoudre ce problème tout en gardant mon code sûr et compatible avec le cache?

Votre modèle de communication semble correct, et la première option fonctionnerait bien si seulement vous pouviez stocker ces pointeurs en toute sécurité. Vous pouvez résoudre ce problème en choisissant une structure de données différente pour le stockage des composants.

A std::vector<T>était un premier choix raisonnable. Cependant, le comportement d'invalidation de l'itérateur du conteneur est un problème. Ce que vous voulez, c'est une structure de données qui soit rapide et cohérente avec le cache pour itérer, et qui préserve également la stabilité de l'itérateur lors de l'insertion ou de la suppression d'éléments.

Vous pouvez créer une telle structure de données. Il se compose d'une liste de pages liées . Chaque page a une capacité fixe et contient tous ses éléments dans un même tableau. Un décompte est utilisé pour indiquer combien d'éléments de ce tableau sont actifs. Une page a également une liste libre (permettant la réutilisation des entrées effacées) et une liste de saut (vous permettant de sauter sur entrées effacées en itérer.

En d'autres termes, conceptuellement quelque chose comme:

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

J'appelle sans complexe cette structure de données un livre (car c'est une collection de pages que vous parcourez cependant), mais la structure a divers autres noms.

Matthew Bentley appelle cela une «colonie». La mise en œuvre de Matthew utilise un champ de saut de comptage de sauts (excuses pour le lien MediaFire, mais c'est ainsi que Bentley lui-même héberge le document) qui est supérieur à la liste de sauts basée sur les booléens plus typique dans ce type de structures. La bibliothèque de Bentley est uniquement en-tête et facile à intégrer dans n'importe quel projet C ++, je vous conseille donc de simplement l'utiliser plutôt que de lancer le vôtre. Il y a beaucoup de subtilités et d'optimisations que je passe en revue ici.

Étant donné que cette structure de données ne déplace jamais les éléments une fois qu'ils sont ajoutés, les pointeurs et les itérateurs vers cet élément restent valides jusqu'à ce que l'élément lui-même soit supprimé (ou que le conteneur lui-même soit effacé). Parce qu'il stocke des morceaux d'éléments alloués de manière contiguë, l'itération est rapide et principalement cohérente avec le cache. L'insertion et le retrait sont tous deux raisonnables.

Ce n'est pas parfait; il est possible de ruiner la cohérence du cache avec un modèle d'utilisation qui implique de supprimer fortement des emplacements effectivement aléatoires dans le conteneur, puis d'itérer sur ce conteneur avant que les insertions suivantes aient des éléments remplis. Si vous êtes souvent dans ce scénario, vous sauterez des zones de mémoire potentiellement volumineuses à la fois. Cependant, dans la pratique, je pense que ce conteneur est un choix raisonnable pour votre scénario.

D'autres approches, que je laisserai pour d'autres réponses à couvrir, pourraient inclure une approche basée sur des poignées ou une sorte de structure de carte de slot (où vous avez un tableau associatif de "clés" entières à des "valeurs" entières, "les valeurs étant des indices dans un tableau de support, qui vous permet d'itérer sur un vecteur en y accédant toujours par "index" avec une indirection supplémentaire).

Être «compatible avec le cache» est une préoccupation des grands jeux . Cela me semble être une optimisation prématurée.

Une façon de résoudre ce problème sans être «compatible avec le cache» serait de créer votre objet sur le tas plutôt que sur la pile: utilisez new des pointeurs (intelligents) pour vos objets. De cette façon, vous pourrez référencer vos objets et leur référence ne sera pas invalidée.

Pour une solution plus conviviale pour le cache, vous pouvez gérer vous-même la dé / allocation des objets et utiliser des poignées pour ces objets.

Fondamentalement, à l'initialisation de votre programme, un objet réserve un morceau de mémoire sur le tas (appelons-le MemMan), puis, lorsque vous voulez créer un composant, vous dites à MemMan que vous avez besoin d'un composant de taille X, c'est ' Je vais le réserver pour vous, créer une poignée et garder en interne où dans son allocation se trouve l'objet pour cette poignée. Il retournera la poignée, et que la seule chose que vous garderez sur l'objet, jamais un pointeur vers son emplacement en mémoire.

Comme vous avez besoin du composant, vous demanderez à MemMan d'accéder à cet objet, ce qu'il fera volontiers. Mais ne gardez pas la référence car ...

L'une des tâches de MemMan est de garder les objets proches les uns des autres en mémoire. Une fois toutes les quelques images de jeu, vous pouvez demander à MemMan de réorganiser les objets en mémoire (ou il pourrait le faire automatiquement lorsque vous créez / supprimez des objets). Il mettra à jour sa carte d'emplacement de poignée à mémoire. Vos poignées seront toujours valides, mais si vous gardiez une référence à l'espace mémoire (un pointeur ou une référence ), vous ne trouverez que désespoir et désolation.

Les manuels indiquent que cette façon de gérer votre mémoire présente au moins 2 avantages:

1. moins de cache manque car les objets sont proches les uns des autres en mémoire et
2. cela réduit le nombre d'appels de de / allocation de mémoire que vous ferez au système d'exploitation, ce qui prendrait un certain temps.

Gardez à l'esprit que la façon dont vous utilisez MemMan et la façon dont vous organiserez la mémoire en interne dépendent vraiment de la façon dont vous utiliserez vos composants. Si vous les parcourez en fonction de leur type, vous souhaiterez conserver les composants par type.Si vous les parcourez en fonction de leur objet de jeu, vous devrez trouver un moyen de vous assurer qu'ils sont proches l'un de l'autre. un autre basé sur ça, etc ...