In welchem ​​Container können dynamische Spielobjekte am effizientesten gespeichert werden? [geschlossen]

20

Ich mache einen Ego-Shooter und kenne viele verschiedene Containertypen, aber ich würde gerne den Container finden, der am effizientesten für die Speicherung dynamischer Objekte ist, die häufig im Spiel hinzugefügt und gelöscht werden. EX-Geschosse.

Ich denke in diesem Fall wäre es eine Liste, so dass der Speicher nicht zusammenhängend ist und es keine Größenänderung gibt, die stattfindet. Aber dann denke ich auch darüber nach, eine Karte oder ein Set zu verwenden. Wenn jemand hilfreiche Informationen hat, würde ich mich freuen.

Ich schreibe das übrigens in c ++.

Außerdem habe ich eine Lösung gefunden, von der ich denke, dass sie funktionieren wird.

Zu Beginn werde ich einen Vektor mit einer großen Größe zuweisen. Sagen wir 1000 Objekte. Ich werde den zuletzt hinzugefügten Index in diesem Vektor verfolgen, damit ich weiß, wo sich das Ende der Objekte befindet. Dann erstelle ich auch eine Warteschlange, die die Indizes aller Objekte enthält, die aus dem Vektor "gelöscht" wurden. (Es wird kein tatsächliches Löschen durchgeführt, ich werde nur wissen, dass dieser Slot frei ist). Wenn also die Warteschlange leer ist, füge ich dem zuletzt hinzugefügten Index im Vektor +1 hinzu, ansonsten füge ich dem Index des Vektors hinzu, der sich am Anfang der Warteschlange befand.

msawayda
quelle
Gibt es eine bestimmte Sprache, auf die Sie abzielen?
Phill.Zitt
Diese Frage ist zu schwer zu beantworten, ohne viele weitere
Details
1
Tipp: Sie können die freie Liste im Speicher der gelöschten Elemente speichern (sodass Sie keine zusätzliche Warteschlange benötigen).
Jeff Gates
2
Gibt es eine Frage in dieser Frage?
Trevor Powell
Beachten Sie, dass Sie weder den größten Index verfolgen noch eine Reihe von Elementen vorab zuweisen müssen. All das übernimmt std :: vector für Sie.
API-Beast

Antworten:

33

Die Antwort ist immer, ein Array oder einen std :: vector zu verwenden. Typen wie eine verknüpfte Liste oder eine std :: map sind in Spielen normalerweise absolut horrend , und dies schließt definitiv Fälle wie Sammlungen von Spielobjekten ein.

Sie sollten die Objekte selbst (keine Zeiger auf sie) im Array / Vektor speichern.

Sie möchten zusammenhängendes Gedächtnis. Du willst es wirklich wirklich. Das Durchlaufen von Daten im nicht zusammenhängenden Speicher führt im Allgemeinen zu vielen Cache-Fehlern und verhindert, dass der Compiler und die CPU effektive Cache-Vorablesezugriffe durchführen können. Dies allein kann die Leistung beeinträchtigen.

Sie möchten auch Speicherzuordnungen und Freigabezuordnungen vermeiden. Sie sind sehr langsam, auch mit einem schnellen Speicherzuweiser. Ich habe gesehen, dass Spiele eine 10-fache FPS-Erhöhung erhalten, wenn nur ein paar hundert Speicherzuordnungen pro Frame entfernt wurden. Scheint nicht so schlimm zu sein, aber es kann sein.

Schließlich können die meisten Datenstrukturen, die Sie für die Verwaltung von Spielobjekten benötigen, auf einem Array oder einem Vektor wesentlich effizienter implementiert werden als auf einem Baum oder einer Liste.

Zum Entfernen von Spielobjekten können Sie beispielsweise Swap-and-Pop verwenden. Einfach zu implementieren mit etwas wie:

std::swap(objects[index], objects.back());
objects.pop_back();

Sie können Objekte auch einfach als gelöscht markieren und ihren Index in eine freie Liste setzen, wenn Sie das nächste Mal ein neues Objekt erstellen müssen, aber es ist besser, das Swap-and-Pop-Verfahren auszuführen. Damit können Sie eine einfache for-Schleife über alle Live-Objekte ausführen, ohne von der Schleife selbst abzweigen zu müssen. Für die Integration der Geschossphysik und dergleichen kann dies eine signifikante Leistungssteigerung sein.

Noch wichtiger ist, dass Sie mithilfe der Slot-Map-Struktur Objekte mit einem einfachen Paar von Tabellensuchen von einem stabilen Unique finden können.

Ihre Spielobjekte haben einen Index in ihrem Hauptarray. Sie können mit nur diesem Index sehr effizient nachgeschlagen werden (viel schneller als eine Karte oder sogar eine Hash-Tabelle). Der Index ist jedoch nicht stabil, da beim Entfernen von Objekten Swap and Pop ausgeführt wird.

Eine Slot-Map erfordert zwei Indirektionsebenen, aber beide sind einfache Array-Lookups mit konstanten Indizes. Sie sind schnell . Wirklich schnell.

Die Grundidee ist, dass Sie drei Arrays haben: Ihre Hauptobjektliste, Ihre Indirektionsliste und eine freie Liste für die Indirektionsliste. Ihre Hauptobjektliste enthält Ihre tatsächlichen Objekte, wobei jedes Objekt seine eigene eindeutige ID kennt. Die eindeutige ID besteht aus einem Index und einem Versions-Tag. Die Indirektionsliste ist einfach ein Array von Indizes zur Hauptobjektliste. Die freie Liste ist ein Stapel von Indizes in der Indirektionsliste.

Wenn Sie ein Objekt in der Hauptliste erstellen, finden Sie einen nicht verwendeten Eintrag in der Indirektionsliste (unter Verwendung der freien Liste). Der Eintrag in der Indirektionsliste zeigt auf einen nicht verwendeten Eintrag in der Hauptliste. Sie initialisieren Ihr Objekt an diesem Speicherort und setzen seine eindeutige ID auf den Index des ausgewählten Indirektionslisteneintrags und das vorhandene Versions-Tag im Hauptlistenelement plus eins.

Wenn Sie ein Objekt zerstören, tauschen Sie es wie gewohnt aus und erhöhen gleichzeitig die Versionsnummer. Anschließend fügen Sie der freien Liste auch den Indirektionslistenindex (Teil der eindeutigen ID des Objekts) hinzu. Wenn Sie ein Objekt als Teil des Swap-and-Pop verschieben, aktualisieren Sie auch seinen Eintrag in der Indirektionsliste an seinen neuen Speicherort.

Beispiel Pseudocode:

Object:
  int index
  int version
  other data

SlotMap:
  Object objects[]
  int slots[]
  int freelist[]
  int count

  Get(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
    else:
      return null

  CreateObject():
    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object
    object.initialize()

    count += 1

    return object

  Remove(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

In der Indirektionsebene können Sie einen stabilen Bezeichner (den Index in der Indirektionsebene, in der Einträge nicht verschoben werden) für eine Ressource festlegen, die während der Komprimierung verschoben werden kann (die Hauptobjektliste).

Mit dem Versions-Tag können Sie eine ID für ein Objekt speichern, das möglicherweise gelöscht wird. Zum Beispiel haben Sie die ID (10,1). Das Objekt mit Index 10 wird gelöscht (z. B. Ihre Kugel trifft auf ein Objekt und wird zerstört). Die Versionsnummer des Objekts an diesem Speicherort in der Hauptobjektliste ist erhöht und gibt (10,2). Wenn Sie versuchen, von einer veralteten ID erneut nach (10,1) zu suchen, gibt die Suche dieses Objekt über den Index 10 zurück, kann jedoch feststellen, dass sich die Versionsnummer geändert hat, sodass die ID nicht mehr gültig ist.

Dies ist die absolut schnellste Datenstruktur, die Sie mit einer stabilen ID haben können, die es Objekten ermöglicht, sich im Speicher zu bewegen, was für die Datenlokalität und die Cache-Kohärenz wichtig ist. Dies ist schneller als jede mögliche Implementierung einer Hash-Tabelle. Mindestens eine Hash-Tabelle muss einen Hash berechnen (mehr Anweisungen als eine Tabellensuche) und dann der Hash-Kette folgen (entweder eine verknüpfte Liste im schrecklichen Fall von std :: unordered_map oder eine offen adressierte Liste in jede nicht-dumme Implementierung einer Hash-Tabelle) und muss dann einen Wertvergleich für jeden Schlüssel durchführen (nicht teurer, aber möglicherweise billiger als die Versions-Tag-Prüfung). Eine sehr gute Hash-Tabelle (die in keiner Implementierung der STL enthalten ist, da die STL eine Hash-Tabelle vorschreibt, die für andere Anwendungsfälle optimiert, als Sie für eine Spielobjektliste benötigen) kann eine Indirektion ersparen.

Es gibt verschiedene Verbesserungen, die Sie am Basisalgorithmus vornehmen können. Verwenden Sie beispielsweise so etwas wie std :: deque für die Hauptobjektliste. Eine zusätzliche Indirektionsebene, mit der Objekte in eine vollständige Liste eingefügt werden können, ohne dass temporäre Zeiger, die Sie von der Slotmap erhalten haben, ungültig werden.

Sie können auch vermeiden, den Index innerhalb des Objekts zu speichern, da der Index aus der Speicheradresse des Objekts (this - objects) berechnet werden kann und noch besser nur zum Entfernen des Objekts benötigt wird. In diesem Fall haben Sie bereits die ID des Objekts (und damit auch Index) als Parameter.

Entschuldigung für die Zuschreibung; Ich glaube nicht, dass es die klarste Beschreibung ist, die es geben könnte. Es ist spät und es ist schwierig zu erklären, ohne mehr Zeit als ich für Codebeispiele aufzuwenden.

Sean Middleditch
quelle
1
Sie tauschen bei jedem Zugriff ein zusätzliches Deref und hohe Zuordnungs- / Freikosten (Swap) gegen "kompakten" Speicher aus. Nach meiner Erfahrung mit Videospielen ist das ein schlechter Handel :) YMMV natürlich.
Jeff Gates
1
Sie machen eigentlich nicht die Dereferenzierung, die in realen Szenarien häufig vorkommt. In diesem Fall können Sie den zurückgegebenen Zeiger lokal speichern, insbesondere wenn Sie die Deque-Variante verwenden oder wissen, dass Sie keine neuen Objekte erstellen, während Sie den Zeiger haben. Das Durchlaufen der Sammlungen ist eine sehr teure und häufige Operation. Sie benötigen die Stable-ID, möchten die Speicherkomprimierung für flüchtige Objekte (wie Aufzählungszeichen, Partikel usw.) und die Indirektion ist auf moderner Hardware sehr effizient. Diese Technik wird in mehr als einigen wenigen kommerziellen Hochleistungsmotoren verwendet. :)
Sean Middleditch
1
Nach meiner Erfahrung: (1) Videospiele werden nach der Leistung im schlechtesten Fall und nicht nach der Leistung im durchschnittlichen Fall bewertet. (2) Normalerweise haben Sie eine Iteration über eine Sammlung pro Frame, wodurch die Komprimierung einfach dazu führt, dass der schlimmste Fall weniger häufig auftritt. (3) Sie haben häufig viele Zuweisungen / Freigaben in einem einzigen Frame. Hohe Kosten bedeuten, dass Sie diese Fähigkeit einschränken. (4) Sie haben unbegrenzte Derefs pro Frame (in Spielen, an denen ich gearbeitet habe, einschließlich Diablo 3, war das Deref nach mäßiger Optimierung häufig das teuerste,> 5% der Serverlast). Ich möchte keine anderen Lösungen verwerfen, sondern nur auf meine Erfahrungen und Überlegungen hinweisen!
Jeff Gates
3
Ich liebe diese Datenstruktur. Ich bin überrascht, dass es nicht bekannter ist. Es ist einfach und löst alle Probleme, die mich seit Monaten auf den Kopf schlagen lassen. Danke für das Teilen.
Jo Bates
2
Jeder Neuling, der dies liest, sollte diesen Rat sehr vorsichtig sein. Dies ist eine sehr irreführende Antwort. "Die Antwort ist immer, ein Array oder std :: vector zu verwenden. Typen wie eine verknüpfte Liste oder eine std :: map sind in Spielen normalerweise absolut horrend, und dies schließt definitiv Fälle wie Sammlungen von Spielobjekten ein." ist stark übertrieben. Es gibt keine "IMMER" Antwort, sonst wären diese anderen Container nicht erstellt worden. Zu sagen, dass Karten / Listen "horrend" sind, ist auch eine Übertreibung. Es gibt VIELE Videospiele, die diese verwenden. "Most Efficient" ist nicht "Most Practical" und kann als subjektives "Best" missverstanden werden.
user50286
12

Array
mit fester Größe (linearer Speicher) mit interner freier Liste (O (1) alloc / free, stable indicies)
mit schwachen Referenzschlüsseln (die Wiederverwendung des Schlitzes macht den Schlüssel ungültig
)

struct DataArray<T>
{
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries
  };

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry
};

Behandelt alles von Kugeln über Monster bis hin zu Texturen und Partikeln. Dies ist die beste Datenstruktur für Videospiele. Ich denke, es kam von Bungie (damals in den Marathon- / Mythos-Tagen), ich habe es bei Blizzard erfahren und ich denke, es war in einem Spiel, das Juwelen programmiert. Es ist wahrscheinlich überall in der Spieleindustrie zu diesem Zeitpunkt.

F: "Warum kein dynamisches Array verwenden?" A: Dynamische Arrays verursachen Abstürze. Einfaches Beispiel:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

Sie können sich Fälle mit mehr Komplikationen vorstellen (wie tiefe Callstacks). Dies gilt für alle Array-ähnlichen Container. Wenn wir Spiele machen, haben wir genug Verständnis für unser Problem, um Größen und Budgets gegen Leistung einzutauschen.

Und ich kann es nicht genug sagen: Wirklich, das ist das Beste, was es je gab. (Wenn Sie nicht einverstanden sind, posten Sie Ihre bessere Lösung! Vorsichtsmaßnahme - muss die oben in diesem Beitrag aufgelisteten Probleme angehen: linearer Speicher / Iteration, O (1) Allokation / Frei, stabile Indizes, schwache Referenzen, null Overhead-Derefs oder habe einen tollen grund warum du keinen brauchst;)

Jeff Gates
quelle
Was meinst du mit dynamischem Array ? Ich frage dies, weil DataArrayscheint auch ein Array dynamisch in ctor zuzuweisen. So könnte es eine andere Bedeutung mit meinem Verständnis haben.
Eonil
Ich meine ein Array, dessen Größe / Größe sich während seiner Verwendung ändert (im Gegensatz zu seiner Konstruktion). Ein stl-Vektor ist ein Beispiel für das, was ich als dynamisches Array bezeichnen würde.
Jeff Gates
@ JeffGates Wirklich wie diese Antwort. Stimmen Sie voll und ganz zu, dass Sie Worst Case als Standardkosten für die Laufzeit akzeptieren. Das Sichern der kostenlosen verknüpften Liste unter Verwendung eines vorhandenen Arrays ist sehr elegant. Fragen Q1: Zweck von maxUsed? F2: Wozu dient das Speichern des Index in den niederwertigen Bits der ID für zugewiesene Einträge? Warum nicht 0? F3: Wie behandelt dies Entitätsgenerationen? Wenn dies nicht der Fall ist, würde ich vorschlagen, die niederwertigen Bits von Q2 für die Kurzzeitgenerierungszählung zu verwenden. - Vielen Dank.
Ingenieur
1
A1: Mit Max used können Sie Ihre Iteration begrenzen. Auch amortisieren Sie eventuelle Baukosten. A2: 1) Sie gehen oft von item -> id aus. 2) Es macht den Vergleich billig / offensichtlich. A3: Ich bin mir nicht sicher, was "Generationen" bedeuten. Ich interpretiere dies als "Wie unterscheidet man den in Position 7 zugewiesenen fünften Artikel vom sechsten Artikel?" wobei 5 und 6 die Generationen sind. Das vorgeschlagene Schema verwendet global einen Zähler für alle Steckplätze. (Wir starten diesen Leistungsindikator für jede DataArray-Instanz mit einer anderen Nummer, um die IDs leichter unterscheiden zu können.) Ich bin sicher, dass Sie die Nachverfolgung der Bits pro Element neu auslösen konnten, was wichtig war.
Jeff Gates
1
@JeffGates - Ich weiß, dass dies ein altes Thema ist, aber ich mag diese Idee wirklich. Könntest du mir ein paar Informationen über das Innenleben von void Free (T &) über void Free (id) geben?
TheStatehz
1

Darauf gibt es keine richtige Antwort. Es hängt alles von der Implementierung Ihrer Algorithmen ab. Gehen Sie einfach mit einem, den Sie für das Beste halten. Versuchen Sie nicht, in diesem frühen Stadium zu optimieren.

Wenn Sie häufig Objekte löschen und neu erstellen, sollten Sie sich ansehen, wie Objektpools implementiert werden.

Edit: Warum komplizieren Dinge mit Slots und was nicht. Warum nicht einfach einen Stapel verwenden und den letzten Gegenstand herausnehmen und wiederverwenden? Wenn Sie also einen hinzufügen, werden Sie ++ ausführen, wenn Sie einen einfügen, den Sie ausführen, um den Überblick über Ihren Endindex zu behalten.

Sidar
quelle
Ein einfacher Stapel behandelt nicht den Fall, dass Elemente in willkürlicher Reihenfolge gelöscht werden.
Jeff Gates
Um fair zu sein, war sein Ziel nicht ganz klar. Zumindest nicht für mich.
Sidar,
1

Das hängt von deinem Spiel ab. Die Container unterscheiden sich darin, wie schnell der Zugriff auf ein bestimmtes Element erfolgt, wie schnell ein Element entfernt und wie schnell ein Element hinzugefügt wird.


  • std :: vector - Schneller Zugriff und schnelles Entfernen und Hinzufügen zum Ende. Das Entfernen von Anfang und Mitte ist langsam.
  • std :: liste - Das Durchlaufen der Liste ist nicht viel langsamer als ein Vektor, aber der Zugriff auf einen bestimmten Punkt der Liste ist langsam (weil das Wiederholen im Grunde das einzige ist, was Sie mit einer Liste tun können). Das Hinzufügen und Entfernen von Elementen an beliebigen Stellen erfolgt schnell. Der meiste Speicheraufwand. Nicht kontinuierlich.
  • std :: deque - Schneller Zugriff und Entfernen / Hinzufügen zum Ende und Anfang ist schnell, aber in der Mitte langsam.

Normalerweise möchten Sie eine Liste verwenden, wenn Sie möchten, dass Ihre Objektliste nicht chronologisch sortiert ist und Sie daher neue Objekte einfügen müssen, anstatt sie anzuhängen, andernfalls eine Deque. Eine Deque hat die Flexibilität gegenüber einem Vektor erhöht, hat aber nicht wirklich einen großen Nachteil.

Wenn Sie wirklich viele Entitäten haben, sollten Sie sich Space Partitioning ansehen.

API-Biest
quelle
Nicht wahr, Re: Liste. Der Deque-Rat hängt vollständig von den Deque-Implementierungen ab, die sich in Geschwindigkeit und Ausführung stark unterscheiden.
Metamorphose