Alternative zum 2D-Array in einer gekachelten Kartenstruktur

Nach langer Suche bin ich überrascht, dass diese Frage noch nicht gestellt wurde. Wie gehen Sie in einem 2D-Spiel mit gekachelten Karten mit der Karte um? Ich würde mich freuen, Ihre Meinung in einer beliebigen Sprache zu haben, obwohl ich mehr an C ++ - Implementierungen interessiert bin.

Ein 2D-Array, ein 2D-Vektor, eine Klasse, die eine verknüpfte Liste mit Ad-hoc-Datenverarbeitung für Koordinaten verarbeitet, eine Boost :: Matrix ...? Welche Lösung verwenden Sie und warum?

Eine Sache, die ich für eine Karte im RPG-Stil getan habe - das heißt, Häuser, die Sie betreten können, Dungeons usw. haben vier Hauptstrukturen: eine Karte, ein Gebiet, eine Zone und ein Plättchen.

Eine Fliese ist offensichtlich eine Fliese.
Eine Zone oder ein Block oder was auch immer ist eine Fläche von X x Y-Kacheln. Dies hat ein 2D-Array.
Ein Bereich ist eine Sammlung von Zonen. Jeder Bereich kann unterschiedliche Zonengrößen haben - die Überwelt kann eine 32x32-Zone verwenden, während ein Haus eine 10x20-Zone haben kann. Diese werden in Wörterbüchern gespeichert (damit ich Zone (-3, -2) haben kann).
Eine Karte ist eine Sammlung von Bereichen, die alle miteinander verknüpft sind.

Ich hatte das Gefühl, dass dies mir mehr Flexibilität ermöglichte, als eine riesige Karte zu haben.

Ich werde erklären, was ich für einen bestimmten Fall von gekachelten Karten mache: Dies ist für effektiv unendliche Karten, bei denen die Welt bei Bedarf generiert wird, aber Sie müssen Änderungen daran speichern:

Ich definiere eine Zellengröße "N" und teile die Welt in Quadrate / Würfel "NxN" oder "NxNxN" auf.

Eine Zelle hat einen eindeutigen Schlüssel. Ich generiere meine durch Hashing oder direktes Verwenden der formatierten Zeichenfolge: "% i,% i,% i", x, y, z (wobei x, y, z die Weltkoordinaten des Zellanfangs geteilt durch N sind)

Das Speichern der Kachelindizes in Arrays ist unkompliziert, da Sie wissen, dass Sie NxN-Kacheln oder NxNxN-Kacheln haben. Sie wissen auch, wie viele Bits Ihr Kacheltyp aufnimmt. Verwenden Sie einfach ein lineares Array. Dies erleichtert auch das Laden und Speichern / Freigeben der Zellen.

Jeder Accessor muss lediglich den Schlüssel für die Zelle generieren (um sicherzustellen, dass er geladen / generiert wurde, und dann den Zeiger darauf abrufen) und dann einen Unterindex verwenden, um in diese Zelle zu schauen. um den Kachelwert an diesem bestimmten Punkt zu finden.

Wenn ich die Zelle anhand ihres Schlüssels extrahiere, verwende ich derzeit eine Karte / ein Wörterbuch, da ich im Allgemeinen ganze Zellen auf einmal verarbeite (ich möchte nicht wissen, wie schlimm ein Treffer wäre, wenn ich eine Wörterbuchsuche pro Kachel durchführen würde, eek).

Ein weiterer Punkt, ich behalte keine Mobs / Spieler in den Zellendaten. Das aktiv dynamische Zeug braucht ein eigenes System.

Die Frage wurde wahrscheinlich nicht gestellt, weil Sie keine Alternative brauchen. Für mich ist es:

Tile tiles[MAP_HEIGHT][MAP_WIDTH]; wenn die Größe fest ist.

std::vector<Tile> tiles(MAP_HEIGHT*MAP_WIDTH); Andernfalls.

Es würde vom Spielstil und der Karte ehrlich abhängen. Für eine relativ kleine rechteckige Kachelkarte würde ich mich wahrscheinlich nur an ein 2D-Array halten. Wenn die Karte sehr unregelmäßig geformt wäre (viele leere Lücken), wäre wahrscheinlich ein Wrapper um verknüpfte Listen, der eine O (1) -Indizierung bietet, meine Wahl.

Ein ganzzahlig indiziertes Array ergibt ein 2147483647 ^ 2 2d-Array. Das ist ziemlich groß, übertrifft aber das, was Sie in den Speicher laden würden. Wenn die Karte groß sein soll, müssen Sie sie auch in Blöcke unterteilen. Jeder Block hat eine feste Größe und enthält ein Unterarray von Kacheln, die nach Bedarf geladen / entladen werden können, um den Arbeitsspeicher niedrig zu halten.

Wenn es nur ein einfaches gekacheltes Spiel in einem Raster ist, wie ein rundenbasiertes Strategiespiel, dann so etwas:

struct Tile
{
    // Stores the first entity (enemy, NPC, item, etc) on the tile.
    int first_entity;
    ...
};

struct Entity
{
    // Stores the next entity on the same tile or
    // the next free entity index to reclaim if
    // this entity has been freed/removed.
    int next;
    ...
};

struct Row
{
    // Stores all the tiles on the row.
    vector<Tile> tiles;

    // Stores all the entities on the row.
    vector<Entity> entities;

    // Points to the first free entity index
    // to reclaim on insertion.
    int first_free;
};

struct Map
{
    // Stores all the rows in the map.
    vector<Row> rows;
};

Einige Leute fragen sich vielleicht, warum ich für jede Kartenzeile separate Vektoren speichere. Es dient dazu, die räumliche Lokalität zu verbessern, wenn wir die auf einer bestimmten Kachel stehenden Objekte durchqueren. Wenn wir einen separaten Vektor pro Zeile speichern, passen möglicherweise alle Entitäten für diese Zeile in L1 oder L2, wohingegen sie möglicherweise nicht einmal in L3 passen, wenn wir einen Entitätscontainer für alle Entitäten in der gesamten Karte gespeichert haben. Das ist immer noch recht billig im Vergleich zum Speichern eines separaten Vektors pro Kachel.

Um beispielsweise die Kachel zu erhalten (102, 72), machen wir Folgendes:

Row& row = map.rows[72];
Tile& tile = row.tiles[102];

Um die Objekte auf der Kachel zu durchlaufen, gehen wir wie folgt vor:

int entity = tile.first_entity;
while (entity != -1)
{
    // Do something with the entity on the tile.
    ...

    // Advance to the next entity on the tile.
    entity = row.entities[entity].next;
}

Damit die Implementierung vom Typ "Separater Container pro Zeile" am meisten davon profitiert, sollten Ihre Kachelzugriffsmuster natürlich versuchen, alle interessierenden Spalten für eine Zeile zu verarbeiten, bevor Sie zur nächsten wechseln, und nicht so sehr im Zick-Zack von einer Zeile zur nächsten das nächste und wieder zurück.

Das Einfügen einer Entität in eine Kachel würde folgendermaßen aussehen:

int Map::insert_entity(Entity ent, int col_idx, int row_idx)
{
     Row& row = rows[row_idx];

     int ent_idx = row.first_free;
     if (ent_idx != -1)
     {
          row.first_free = row.entities[ent_idx].next;
          row.entities[ent_idx] = ent;
     }
     else
     {
          ent_idx = static_cast<int>(row.entities.size());
          row.entities.push_back(ent);
     }

     Tile& tile = row.tiles[col_idx];
     row.entities[ent_idx].next = tile.first_entity;
     tile.first_entity = ent_idx;
     return ent_idx;
}

... und entfernen:

void Map::remove_entity(int ent_idx, int col_idx, int row_idx)
{
     Row& row = rows[row_idx];
     Tile& tile = row.tiles[col_idx];
     if (tile.first_entity = ent_idx)
         tile.first_entity = row.entities[ent_idx].next;

     row.entities[ent_idx].next = row.first_free;
     row.first_free = ent_idx;
}

Der Hauptgrund, warum mir diese Lösung gefällt, ist, dass wir vermeiden, zu viele Vektoren zu speichern (z. B. ein Vektor pro Kachel: zu viele für große Karten), aber nicht so wenige, dass das Durchlaufen der Entitäten auf einer bestimmten Kachel zu epischen Schritten über die Speicheradresse führt Platz und viel Cache fehlen. Ein Entitätsvektor pro Zeile sorgt dort für eine gute Balance.

Dies setzt voraus, dass Dinge wie Gebäude und Feinde sowie Gegenstände und Schatztruhen und Spieler auf den Plättchen stehen und dass ein Großteil der in der Spiellogik aufgewendeten Zeit darin besteht, auf die auf diesen Plättchen stehenden Entitäten zuzugreifen und zu überprüfen, auf welchen Entitäten sich diese befinden eine bestimmte Fliese. Andernfalls würde ich einen 1D-Array-Ansatz mit einem einzelnen Vektor für alle Kacheln verwenden, da dies am effizientesten wäre, wenn nur auf Kacheln zugegriffen wird. Sie können dann eine Kachel erhalten, indem Sie: tiles[row*num_cols+col]Im Zweifelsfall ein eindimensionales Array verwenden, da Sie damit die Dinge in einer einfachen sequentiellen Reihenfolge ohne verschachtelte Schleifen durchlaufen können und nur eine Heap-Zuordnung benötigen, um das gesamte Objekt zuzuweisen.

Im Allgemeinen ist das separate dynamische Array pro Zeile etwas, das ich gefunden habe, um Cache-Fehler in Fällen zu reduzieren, in denen Ihr Raster Elemente darin speichert. Wenn dies nicht der Fall ist und Ihr Raster wie ein Bild mit Pixeln ist, ist es natürlich nicht sinnvoll, ein separates dynamisches Array pro Zeile zu verwenden. Als kürzlich durchgeführter Benchmark, bei dem ich etwas Rasterartiges auf diese Weise optimiert habe (bevor nur ein riesiges Array für alles verwendet wurde; ich habe es so optimiert, dass ein separates dynamisches Array pro Zeile gespeichert wird, nachdem in vtune viele Cache-Fehler aufgetreten sind):

Vor:

--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {1.799000 secs}
mem use after 'insert': 479,508,224 bytes

8560 cells, 1000000 rects
finished test_grid: {1.919000 secs}

Nach:

--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {0.310000 secs}
mem use after 'insert': 410,546,720 bytes

8560 cells, 1000000 rects
finished test_grid: {0.361000 secs}

Und ich habe die gleiche Strategie wie oben beschrieben angewendet. Als Bonus können Sie auch feststellen, dass die Speichernutzung geringer ist, da die Vektoren, in denen die Entitäten gespeichert sind, tendenziell enger passen, wenn Sie eine pro Zeile anstelle einer für die gesamte Karte speichern.

Beachten Sie, dass der obige Test zum Einfügen einer Million Entitäten in das Raster auch nach der Optimierung eine lange Zeit und viel Speicher benötigt. Das liegt daran, dass jede Entität, die ich einfüge, viele Kacheln benötigt, durchschnittlich etwa 100 Kacheln pro Entität (durchschnittliche Größe 10 x 10). Ich füge also jede der Millionen Entitäten in durchschnittlich 100 Rasterkacheln ein, was eher dem Einfügen von 100 Millionen Entitäten als einer dürftigen 1 Million Entitäten entspricht. Es ist Stresstest eines pathologischen Falls. Wenn ich nur eine Million Entitäten einfüge, die jeweils 1 Kachel belegen, kann ich dies in Millisekunden tun und nur etwa 16 Megabyte Speicher verwenden.

In meinem Fall muss ich oft sogar pathologische Fälle effizient machen, da ich in VFX arbeite, anstatt zu spielen. Ich kann Künstlern nicht sagen: "Machen Sie Ihre Inhalte für diese Engine so."denn der Sinn von VFX ist es, die Künstler den Inhalt erstellen zu lassen, wie sie wollen. Sie optimieren es dann, bevor sie in ihre Lieblings-Engine exportieren, aber ich muss mich mit den nicht optimierten Dingen befassen, was bedeutet, dass ich die pathologischen Fälle oft effizient behandeln muss, wie ein Octree, der seitdem effizient mit massiven Dreiecken umgehen muss, die die gesamte Szene überspannen Die Künstler erstellen solche Inhalte häufig (weitaus häufiger als erwartet). Der obige Test testet also etwas, das niemals passieren sollte, und deshalb dauert es fast eine Drittelsekunde, um eine Million Entitäten einzufügen, aber in meinem Fall passieren diese Dinge "niemals passieren" die ganze Zeit. Der pathologische Fall ist für mich also kein seltener Fall.

Als Nebenbonus können Sie damit auch Entitäten für mehrere Zeilen gleichzeitig mithilfe von Multithreading ohne Sperren gleichzeitig einfügen und entfernen, da Sie dies jetzt sicher tun können, da jede Zeile über einen separaten Entitätscontainer verfügt, sofern zwei Threads dies nicht versuchen Einfügen / Entfernen von Inhalten in / aus derselben Zeile gleichzeitig.

Ich spiele mit einer 3D-Engine, in der die Welt ein Netz ist.

Ich importiere einige 2D-Karten + Kachelsätze, die zuvor erstellt wurden.

Und wenn ich das tue, konvertiere ich es in ein 3D-Netz und füge alle Kacheln zu einer einzigen Textur zusammen.

Dies zieht wesentlich schneller.

Ich würde die Karte vielleicht in einem 1D-Array von w * h behalten, wenn ich das Kachelkonzept beibehalten müsste, aber meine Antwort ist, dass es befreiend ist, über die 2Dness hinauszugehen.

Wenn Sie während der Verwendung der GPU-Zeichnung Leistungsprobleme haben, kann die Beibehaltung der grafischen Darstellung als einzelne Textur - mit einem Netz, wenn die Höhe variabel ist - die Geschwindigkeit im Vergleich zum einzelnen Zeichnen jeder Kachel erheblich beschleunigen.