Wie kann ich die Kommunikation von Komponente zu Objekt sicher und mit cachefreundlichem Komponentenspeicher unterstützen?

Ich mache ein Spiel, das komponentenbasierte Spielobjekte verwendet, und es fällt mir schwer, eine Möglichkeit für jede Komponente zu implementieren, mit ihrem Spielobjekt zu kommunizieren. Anstatt alles auf einmal zu erklären, werde ich jeden Teil des relevanten Beispielcodes erklären:

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

Das GameObjectManagerenthält alle Spielobjekte und deren Komponenten. Es ist auch für die Aktualisierung der Spielobjekte verantwortlich. Dazu werden die Komponentenvektoren in einer bestimmten Reihenfolge aktualisiert. Ich verwende Vektoren anstelle von Arrays, so dass die Anzahl der Spielobjekte, die gleichzeitig existieren können, praktisch unbegrenzt ist.

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

Die GameObjectKlasse kennt ihre Komponenten und kann Nachrichten an sie senden.

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

Die ComponentKlasse ist rein virtuell, sodass Klassen für die verschiedenen Komponententypen den Umgang mit Nachrichten und Aktualisierungen implementieren können. Es ist auch in der Lage, Nachrichten zu senden.

Nun stellt sich das Problem, wie die Komponenten die sendMessageFunktionen in GameObjectund aufrufen können GameObjectManager. Ich habe zwei mögliche Lösungen gefunden:

1. Geben Sie Componenteinen Zeiger auf seine GameObject.

Da sich die Spielobjekte jedoch in einem Vektor befinden, können die Zeiger schnell ungültig werden (das Gleiche gilt für den Vektor in GameObject, aber hoffentlich kann die Lösung dieses Problems auch diesen lösen). Ich könnte die Spielobjekte in ein Array einfügen, aber dann müsste ich eine beliebige Zahl für die Größe eingeben, die leicht unnötig hoch sein und Speicher verschwenden könnte.

2. Geben Sie Componenteinen Zeiger auf die GameObjectManager.

Ich möchte jedoch nicht, dass Komponenten die Aktualisierungsfunktion des Managers aufrufen können. Ich bin die einzige Person, die an diesem Projekt arbeitet, aber ich möchte nicht die Gewohnheit haben, potenziell gefährlichen Code zu schreiben.

Wie kann ich dieses Problem beheben, während mein Code sicher und cachefreundlich bleibt?

Ihr Kommunikationsmodell scheint in Ordnung zu sein, und Option 1 würde in Ordnung funktionieren, wenn Sie nur diese Zeiger sicher speichern könnten. Sie können dieses Problem lösen, indem Sie eine andere Datenstruktur für die Komponentenspeicherung auswählen.

A std::vector<T>war eine vernünftige erste Wahl. Das Iterator-Invalidierungsverhalten des Containers ist jedoch ein Problem. Was Sie möchten, ist eine Datenstruktur, die schnell und cache-kohärent durchlaufen werden kann und die auch die Iteratorstabilität beim Einfügen oder Entfernen von Elementen bewahrt.

Sie können eine solche Datenstruktur erstellen. Es besteht aus einer verknüpften Liste von Seiten . Jede Seite hat eine feste Kapazität und enthält alle Elemente in einem Array. Eine Zählung gibt an, wie viele Elemente in diesem Array aktiv sind. Eine Seite hat auch eine freie Liste (erlaubt die Wiederverwendung der gelöschten Einträge) und eine Sprungliste (so dass Sie überspringen über , während das Iterieren gelöscht Einträge.

Mit anderen Worten, konzeptionell so etwas wie:

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

Ich nenne diese Datenstruktur einfallslos ein Buch (weil es sich um eine Sammlung von Seiten handelt, die Sie iterieren), aber die Struktur hat verschiedene andere Namen.

Matthew Bentley nennt es eine "Kolonie". Matthew-Implementierung verwendet eine Sprungzählung Sprungfeld (Entschuldigung für den Mediafire Link, aber es ist , wie Bentley selbst beherbergt das Dokument) , die mit der typischeren boolean-basierten Sprungliste in dieser Art von Strukturen überlegen ist. Die Bentley-Bibliothek ist nur für Header geeignet und kann problemlos in jedes C ++ - Projekt eingefügt werden. Ich empfehle Ihnen daher, diese Bibliothek einfach zu verwenden und nicht Ihre eigene zu rollen. Es gibt viele Feinheiten und Optimierungen, die ich hier beschönige.

Da diese Datenstruktur Elemente nach dem Hinzufügen niemals verschiebt, bleiben Zeiger und Iteratoren auf dieses Element gültig, bis dieses Element selbst gelöscht wird (oder der Container selbst gelöscht wird). Da hier Teile zusammenhängend zugeordneter Elemente gespeichert werden, ist die Iteration schnell und größtenteils cache-kohärent. Das Einsetzen und Entfernen ist sinnvoll.

Es ist nicht perfekt; Es ist möglich, die Cache-Kohärenz mit einem Verwendungsmuster zu ruinieren, bei dem stark zufällige Stellen im Container gelöscht und dann über diesen Container iteriert werden, bevor nachfolgende Einfügungen Elemente nachfüllen. Wenn Sie sich häufig in diesem Szenario befinden, überspringen Sie potenziell große Speicherbereiche gleichzeitig. In der Praxis halte ich diesen Container jedoch für eine vernünftige Wahl für Ihr Szenario.

Andere Ansätze, die ich anderen Antworten überlassen werde, könnten einen handle-basierten Ansatz oder eine Slot-Map-Struktur umfassen (wobei Sie ein assoziatives Array von ganzzahligen "Schlüsseln" zu ganzzahligen "Werten" haben, wobei die Werte Indizes sind in einem Hintergrundarray, mit dem Sie über einen Vektor iterieren können, indem Sie weiterhin über "Index" mit einer zusätzlichen Indirektion zugreifen).

"Cache-freundlich" zu sein, ist ein Hauptanliegen großer Spiele . Dies scheint mir eine vorzeitige Optimierung zu sein.

Eine Möglichkeit, dies zu lösen, ohne "Cache-freundlich" zu sein, besteht darin, Ihr Objekt auf dem Heap anstatt auf dem Stapel zu erstellen: Verwenden Sie newund (intelligente) Zeiger für Ihre Objekte. Auf diese Weise können Sie auf Ihre Objekte verweisen, und ihre Referenz wird nicht ungültig.

Für eine cachefreundlichere Lösung können Sie die De- / Zuweisung von Objekten selbst verwalten und Handles für diese Objekte verwenden.

Grundsätzlich reserviert ein Objekt bei der Initialisierung Ihres Programms einen Speicherblock auf dem Heap (nennen wir es MemMan). Wenn Sie dann eine Komponente erstellen möchten, teilen Sie MemMan mit, dass Sie eine Komponente der Größe X benötigen. Ich werde es für Sie reservieren, ein Handle erstellen und intern behalten, wo in seiner Zuordnung das Objekt für dieses Handle ist. Das Handle wird zurückgegeben, und das einzige, was Sie über das Objekt behalten, ist niemals ein Zeiger auf seine Position im Speicher.

Wenn Sie die Komponente benötigen, werden Sie MemMan bitten, auf dieses Objekt zuzugreifen, was es gerne tut. Aber behalten Sie den Verweis nicht bei, weil ...

Eine der Aufgaben von MemMan ist es, die Objekte im Speicher nahe beieinander zu halten. Einmal alle paar Spielrahmen können Sie MemMan anweisen, Objekte im Speicher neu anzuordnen (oder dies kann automatisch erfolgen, wenn Sie Objekte erstellen / löschen). Es wird seine Handle-to-Memory-Standortzuordnung aktualisieren. Ihre Handles sind immer gültig, aber wenn Sie einen Verweis auf den Speicherplatz (einen Zeiger oder einen Verweis ) behalten , werden Sie nur Verzweiflung und Trostlosigkeit finden.

Laut Lehrbüchern hat diese Art der Speicherverwaltung mindestens zwei Vorteile:

1. Es fehlen weniger Cache-Fehler, da Objekte im Speicher und nahe beieinander liegen
2. Es reduziert die Anzahl der Aufrufe zur Speicherentfernung / -zuweisung, die Sie an das Betriebssystem senden, was einige Zeit in Anspruch nehmen soll .

Beachten Sie, dass die Art und Weise, wie Sie MemMan verwenden und wie Sie den Speicher intern organisieren, wirklich davon abhängt, wie Sie Ihre Komponenten verwenden. Wenn Sie sie basierend auf ihrem Typ durchlaufen, möchten Sie Komponenten nach Typ beibehalten. Wenn Sie sie basierend auf ihrem Spielobjekt durchlaufen, müssen Sie einen Weg finden, um sicherzustellen, dass sie nahe beieinander liegen eine andere basierend darauf, etc ...