Gruppieren von Entitäten derselben Komponente in einem linearen Speicher

11

Wir gehen vom grundlegenden System-Komponenten-Entitäten-Ansatz aus .

Lassen Sie uns Assemblagen (Begriff aus diesem Artikel abgeleitet) nur aus Informationen über Komponententypen erstellen . Dies geschieht dynamisch zur Laufzeit, genau wie wir einer Entität nacheinander Komponenten hinzufügen / entfernen würden, aber nennen wir es einfach genauer, da es sich nur um Typinformationen handelt.

Dann konstruieren wir Entitäten , die für jede von ihnen eine Assemblage angeben . Sobald wir die Entität erstellt haben, ist ihre Assemblage unveränderlich, was bedeutet, dass wir sie nicht direkt an Ort und Stelle ändern können, aber dennoch die Signatur der vorhandenen Entität für eine lokale Kopie (zusammen mit dem Inhalt) erhalten, die richtigen Änderungen daran vornehmen und eine neue Entität erstellen können davon.

Nun zum Schlüsselkonzept: Wenn eine Entität erstellt wird, wird sie einem Objekt namens Assemblage Bucket zugewiesen. Dies bedeutet, dass sich alle Entitäten derselben Signatur im selben Container befinden (z. B. in std :: vector).

Jetzt durchlaufen die Systeme einfach jeden Eimer ihres Interesses und erledigen ihre Arbeit.

Dieser Ansatz hat einige Vorteile:

  • Komponenten werden in wenigen (genau: Anzahl der Buckets) zusammenhängenden Speicherblöcken gespeichert - dies verbessert die Speicherfreundlichkeit und es ist einfacher, den gesamten Spielstatus zu sichern
  • Systeme verarbeiten Komponenten linear, was eine verbesserte Cache-Kohärenz bedeutet - Tschüss-Wörterbücher und zufällige Speichersprünge
  • Das Erstellen einer neuen Entität ist so einfach wie das Zuordnen einer Assemblage zum Bucket und das Zurückschieben der erforderlichen Komponenten auf ihren Vektor
  • Das Löschen einer Entität ist so einfach wie ein Aufruf von std :: move, um das letzte Element gegen das gelöschte auszutauschen, da die Reihenfolge in diesem Moment keine Rolle spielt

Geben Sie hier die Bildbeschreibung ein

Wenn wir viele Entitäten mit völlig unterschiedlichen Signaturen haben, verringern sich die Vorteile der Cache-Kohärenz, aber ich denke nicht, dass dies in den meisten Anwendungen passieren würde.

Es gibt auch ein Problem mit der Ungültigmachung von Zeigern, sobald Vektoren neu zugewiesen werden - dies könnte durch Einführung einer Struktur wie der folgenden gelöst werden:

struct assemblage_bucket {
    struct entity_watcher {
        assemblage_bucket* owner;
        entity_id real_index_in_vector;
    };

    std::unordered_map<entity_id, std::vector<entity_watcher*>> subscribers;

    //...
};

Wenn wir also aus irgendeinem Grund in unserer Spielelogik eine neu erstellte Entität verfolgen möchten, registrieren wir im Bucket einen entity_watcher . Sobald die Entität beim Entfernen std :: move'd sein muss, suchen wir nach ihren Beobachtern und aktualisieren sie ihre real_index_in_vectorzu neuen Werten. In den meisten Fällen wird für jede Entitätslöschung nur eine einzige Wörterbuchsuche durchgeführt.

Gibt es weitere Nachteile bei diesem Ansatz?

Warum wird die Lösung nirgends erwähnt, obwohl sie ziemlich offensichtlich ist?

BEARBEITEN : Ich bearbeite die Frage, um "die Antworten zu beantworten", da die Kommentare nicht ausreichen.

Sie verlieren die Dynamik steckbarer Komponenten, die speziell entwickelt wurden, um sich von der statischen Klassenkonstruktion zu lösen.

Ich nicht. Vielleicht habe ich es nicht klar genug erklärt:

auto signature = world.get_signature(entity_id); // this would just return entity_id.bucket_owner->bucket_signature or so
signature.add(foo_component);
signature.remove(bar_component);
world.delete_entity(entity_id); // entity_id would hold information about its bucket owner
world.create_entity(signature); // automatically assigns new entity to an existing or a new bucket

Es ist so einfach, nur die Signatur einer vorhandenen Entität zu übernehmen, sie zu ändern und erneut als neue Entität hochzuladen. Steckbare, dynamische Natur ? Natürlich. Hier möchte ich betonen, dass es nur eine "Assemblage" - und eine "Bucket" -Klasse gibt. Buckets werden datengesteuert und zur Laufzeit in einer optimalen Menge erstellt.

Sie müssten alle Buckets durchgehen, die möglicherweise ein gültiges Ziel enthalten. Ohne eine externe Datenstruktur könnte die Kollisionserkennung ebenso schwierig sein.

Nun, deshalb haben wir die oben genannten externen Datenstrukturen . Die Problemumgehung ist so einfach wie die Einführung eines Iterators in der Systemklasse, der erkennt, wann zum nächsten Bucket gesprungen werden muss. Das Springen wäre für die Logik rein transparent.

Patryk Czachurski
quelle
Ich habe auch den Artikel von Randy Gaul über das Speichern aller Komponenten in Vektoren gelesen und ihre Systeme sie einfach verarbeiten lassen. Ich sehe dort zwei große Probleme: Was ist, wenn ich nur eine Teilmenge von Entitäten aktualisieren möchte (denken Sie beispielsweise an das Keulen). Aus diesem Grund werden Komponenten wieder mit Entitäten gekoppelt. Für jeden Komponenteniterationsschritt muss überprüft werden, ob die Entität, zu der sie gehört, für eine Aktualisierung ausgewählt wurde. Das andere Problem besteht darin, dass einige Systeme mehrere verschiedene Komponententypen verarbeiten müssen, um den Vorteil der Cache-Kohärenz wieder zu verringern. Irgendwelche Ideen, wie man mit diesen Problemen umgeht?
Tiguchi

Antworten:

7

Sie haben im Wesentlichen ein statisches Objektsystem mit einem Pool-Allokator und mit dynamischen Klassen entworfen.

Ich habe ein Objektsystem geschrieben, das in meiner Schulzeit fast identisch mit Ihrem "Assemblages" -System funktioniert, obwohl ich in meinen eigenen Entwürfen immer eher "Assemblagen" als "Blaupausen" oder "Archetypen" bezeichne. Die Architektur war eher ein Problem als naive Objektsysteme und hatte keine messbaren Leistungsvorteile gegenüber einigen der flexibleren Designs, mit denen ich sie verglichen habe. Die Möglichkeit, ein Objekt dynamisch zu ändern, ohne es erneut ändern oder neu zuweisen zu müssen, ist äußerst wichtig, wenn Sie an einem Spieleditor arbeiten. Designer möchten Komponenten per Drag & Drop auf Ihre Objektdefinitionen ziehen. Möglicherweise muss der Laufzeitcode in einigen Designs sogar Komponenten effizient ändern, obwohl mir das persönlich nicht gefällt. Abhängig davon, wie Sie Objektreferenzen in Ihrem Editor verknüpfen,

In den meisten nicht trivialen Fällen wird die Cache-Kohärenz schlechter als gedacht. Ihr KI-System zum Beispiel kümmert sich nicht um RenderKomponenten, sondern bleibt als Teil jeder Entität beim Durchlaufen dieser Komponenten hängen. Die Objekte, über die iteriert wird, sind größer, und Cacheline-Anforderungen ziehen unnötige Daten ein, und mit jeder Anforderung werden weniger ganze Objekte zurückgegeben. Es ist immer noch besser als die naive Methode, und die Objektzusammensetzung der naiven Methode wird sogar in großen AAA-Engines verwendet. Sie brauchen also wahrscheinlich keine bessere, aber denken Sie zumindest nicht, dass Sie sie nicht weiter verbessern können.

Ihr Ansatz ist für einige am sinnvollstenKomponenten, aber nicht alle. Ich mag ECS ​​nicht besonders, weil es befürwortet, jede Komponente immer in einem separaten Container abzulegen, was für Physik oder Grafik oder so weiter Sinn macht, aber überhaupt keinen Sinn, wenn Sie mehrere Skriptkomponenten oder zusammensetzbare KI zulassen. Wenn Sie das Komponentensystem nicht nur für integrierte Objekte verwenden lassen, sondern auch für Designer und Gameplay-Programmierer, um das Objektverhalten zu komponieren, kann es sinnvoll sein, alle KI-Komponenten (die häufig interagieren) oder alle Skripte zu gruppieren Komponenten (da Sie sie alle in einem Stapel aktualisieren möchten). Wenn Sie das leistungsstärkste System wünschen, benötigen Sie eine Mischung aus Komponentenzuordnungs- und Speicherschemata und nehmen sich Zeit, um endgültig herauszufinden, welches für den jeweiligen Komponententyp am besten geeignet ist.

Sean Middleditch
quelle
Ich sagte: Wir können die Signatur einer Entität nicht ändern, und ich meinte, wir können sie nicht direkt an Ort und Stelle ändern, aber wir können trotzdem nur eine vorhandene Assemblage auf eine lokale Kopie übertragen, Änderungen daran vornehmen und erneut als neue Entität hochladen - und diese Operationen sind ziemlich billig, wie ich in der Frage gezeigt habe. Noch einmal - es gibt nur EINE "Bucket" -Klasse. "Assemblages" / "Signaturen" / "Nennen wir es wie wir wollen" können zur Laufzeit dynamisch erstellt werden, wie bei einem Standardansatz. Ich würde sogar so weit gehen, eine Entität als "Signatur" zu betrachten.
Patryk Czachurski
Und ich sagte, Sie wollen sich nicht unbedingt mit der Verdinglichung befassen. "Erstellen einer neuen Entität" kann möglicherweise bedeuten, dass alle vorhandenen Handles für die Entität getrennt werden, je nachdem, wie Ihr Handle-System funktioniert. Ihr Anruf, ob sie billig genug sind oder nicht. Ich fand es nur ein Schmerz im Hintern, mit dem ich umgehen musste.
Sean Middleditch
Okay, jetzt habe ich deinen Standpunkt dazu. Wie auch immer, ich denke, selbst wenn das Hinzufügen / Entfernen etwas teurer wäre, geschieht dies gelegentlich so, dass es sich immer noch lohnt, den Zugriff auf die Komponenten in Echtzeit erheblich zu vereinfachen. Der Aufwand für "Änderungen" ist also vernachlässigbar. Ist es in Bezug auf Ihr KI-Beispiel nicht immer noch wert, dass diese wenigen Systeme ohnehin Daten von mehreren Komponenten benötigen?
Patryk Czachurski
Mein Punkt dort war, dass KI ein Ort war, an dem Ihr Ansatz besser ist, aber für andere Komponenten ist dies nicht unbedingt der Fall.
Sean Middleditch
4

Was Sie getan haben, sind überarbeitete C ++ - Objekte. Der Grund, warum dies offensichtlich ist, ist, dass wenn Sie das Wort "Entität" durch "Klasse" und "Komponente" durch "Mitglied" ersetzen, dies ein Standard-OOP-Design ist, das Mixins verwendet.

1) Sie verlieren die Dynamik steckbarer Komponenten, die speziell entwickelt wurden, um sich von der statischen Klassenkonstruktion zu lösen.

2) Die Speicherkohärenz ist innerhalb eines Datentyps am wichtigsten, nicht innerhalb eines Objekts, das mehrere Datentypen an einem Ort vereint. Dies ist einer der Gründe, warum Komponenten- + Systeme erstellt wurden, um die Fragmentierung des Klassen- + Objektspeichers zu vermeiden.

3) Dieses Design wird auch auf den C ++ - Klassenstil zurückgesetzt, da Sie die Entität als kohärentes Objekt betrachten, wenn in einem Komponenten- + Systemdesign die Entität lediglich ein Tag / eine ID ist, um das Innenleben für den Menschen verständlich zu machen.

4) Es ist für eine Komponente genauso einfach, sich selbst zu serialisieren wie für ein komplexes Objekt, mehrere Komponenten in sich selbst zu serialisieren, wenn nicht sogar einfacher, als Programmierer den Überblick zu behalten.

5) Der nächste logische Schritt auf diesem Weg besteht darin, Systeme zu entfernen und diesen Code direkt in die Entität einzufügen, wo sie alle Daten enthält, die sie zum Arbeiten benötigt. Wir können alle sehen, was das bedeutet =)

Patrick Hughes
quelle
2) Vielleicht verstehe ich das Caching nicht vollständig, aber sagen wir, es gibt ein System, das mit beispielsweise 10 Komponenten funktioniert. In einem Standardansatz bedeutet die Verarbeitung jeder Entität, zehnmal auf RAM zuzugreifen, da Komponenten an zufälligen Stellen im Speicher verteilt sind, selbst wenn Pools verwendet werden - da unterschiedliche Komponenten zu unterschiedlichen Pools gehören. Wäre es nicht "wichtig", die gesamte Entität auf einmal zwischenzuspeichern und alle Komponenten ohne einen einzigen Cache-Fehler zu verarbeiten, ohne auch nur Wörterbuchsuchen durchführen zu müssen? Außerdem habe ich eine Bearbeitung vorgenommen, um den 1) Punkt
abzudecken
@ Sean Middleditch hat eine gute Beschreibung dieser Caching-Aufschlüsselung in seiner Antwort.
Patrick Hughes
3) Sie sind in keiner Weise kohärente Objekte. Da Komponente A direkt neben Komponente B im Speicher liegt, handelt es sich nur um "Speicherkohärenz", nicht um "logische Kohärenz", wie John hervorgehoben hat. Eimer könnten bei ihrer Erstellung sogar Komponenten in der Signatur in jede gewünschte Reihenfolge mischen, und die Prinzipien würden weiterhin beibehalten. 4) Es kann genauso einfach sein, den Überblick zu behalten, wenn wir über genügend Abstraktion verfügen. Es handelt sich lediglich um ein Speicherschema, das mit Iteratoren und möglicherweise einer Byte-Offset-Zuordnung versehen ist und die Verarbeitung so einfach wie bei einem Standardansatz macht.
Patryk Czachurski
5) Und ich denke, nichts in dieser Idee weist auf diese Richtung. Es ist nicht so, dass ich Ihnen nicht zustimmen möchte, ich bin nur neugierig, wohin diese Diskussion führen könnte, obwohl sie wahrscheinlich sowieso zu einer Art "Messung" oder der bekannten "vorzeitigen Optimierung" führen wird. :)
Patryk Czachurski
@PatrykCzachurski, aber Ihre Systeme funktionieren nicht mit 10 Komponenten.
user253751
3

Es ist nicht so wichtig, wie Entitäten zusammenzuhalten, wie Sie vielleicht denken, weshalb es schwierig ist, sich einen anderen gültigen Grund als "weil es eine Einheit ist" vorzustellen. Da Sie dies jedoch aus Gründen der Cache-Kohärenz im Gegensatz zur logischen Kohärenz tun, ist dies möglicherweise sinnvoll.

Eine Schwierigkeit, die Sie haben könnten, ist die Interaktion zwischen Komponenten in verschiedenen Buckets. Es ist nicht besonders einfach, etwas zu finden , auf das Ihre KI schießen kann. Sie müssten beispielsweise alle Eimer durchgehen, die möglicherweise ein gültiges Ziel enthalten. Ohne eine externe Datenstruktur könnte die Kollisionserkennung ebenso schwierig sein.

Um Entitäten aus logischen Gründen zusammen zu organisieren, muss ich Entitäten möglicherweise nur zu Identifikationszwecken in meinen Missionen zusammenhalten. Ich muss wissen, ob Sie gerade Entitätstyp A oder Typ B erstellt haben, und ich komme darum herum, indem Sie ... Sie haben es erraten: Hinzufügen einer neuen Komponente, die die Assemblage identifiziert, die diese Entität zusammensetzt. Selbst dann sammle ich nicht alle Komponenten für eine große Aufgabe zusammen, ich muss nur wissen, was es ist. Ich denke nicht, dass dieser Teil schrecklich nützlich ist.

John McDonald
quelle
Ich muss zugeben, dass ich Ihre Antwort nicht ganz verstehe. Was meinst du mit "logischer Kohärenz"? Über Schwierigkeiten bei Interaktionen habe ich eine Bearbeitung vorgenommen.
Patryk Czachurski
"Logische Kohärenz" wie in: Es ist "logisch sinnvoll", alle Komponenten, aus denen eine Tree-Entität besteht, nahe beieinander zu halten.
John McDonald