spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ach so, ok. Mein erster Gedanke wäre gewesen die von mir genannten Strukturen erst zur Laufzeit in das 2D Raster um zu rechnen. Also ein Objekt schaffen das sich wie ein z.B. ein Vektor/Array verhält aber einfach nur die Daten aus den Listen verwendet um entsprechend umrechnet.

Für sowas würde sich tatsächlich ein Baum anbieten. Beispielsweise könnte man einen Binärbaum benutzten: Immer wenn ein Tile außerhalb der aktuellen Levelgröße erzeugt wird, verdoppelt man die Größe des Levels in dieser Richtung, in dem die Struktur des bestehenden Baumes kopiert und zusammen unter ein neues Wurzelelement gehangen wird. Das ist zwar speicherintensiver, dürfte sich aber, wenn man die Blätter des Baumes nicht als einzelne Tiles sondern kleine Patches von z.B. 32x32 Tiles oder so nimmt, kaum ins Gewicht fallen. Um beim Speichern kann man es immer noch in ein Array überführen.

Und der Zugriff über die Position des Tiles geht dann halt nicht mehr in konstanter Zeit, sondern wächst logarithmisch mit der Anzahl der Ebenen im Baum. Das ist für einen Editor durchaus vertretbar.

Ist allerdings im Vergleich zu 'nem einfachen Array ein gewaltiger Aufwand, besonders wenn du noch nicht so viel Erfahrung hast. Könnte aber auch eine gute Gelegenheit sein, gleich was über Datenstrukturen (in diesem Fall eben Bäume) zu lernen.

Ich hatte da eher an so etwas gedacht:

Denn wo z.B. eine Reihe leer ist, kann es auch keinen Spalteneintrag geben… folglich auch kein Asset.

Ich denke der Baum ist für sowas eher overhead. Welchen Vorteil würde man daraus ziehen das ganze in so eine Baumstruktur zu packen? Gut ich müsste die alten Elemente nicht umkopieren so wie es zum Beispiel bei einem std::vector der Fall wäre, dafür wäre aber der Aufwand meiner Meinung nach zu groß. Und die Laufzeit sollte einigermaßen egal sein, so würde ich wenn eher zu einer Liste greifen. Für einen Editor sollte die normalerweise mehr als ausreichend sein und dort muss nicht mehr Speicher geholt werden als gebraucht wird. Oder hätte der Baum in diesem Fall einen Vorteil den ich grad nicht sehe?

Also den Vorteil von einem richtigen Baum würde ich jetzt darin sehen, dass man einfacher „komplexe“ Strukturen wieder verwenden könnte. Wie z.B. ein Haus das aus mehreren Tiles besteht. Das geht zumindest nicht so ohne weiteres mit der flachen Struktur wie die die ich genannt hatte.

Ich würde sagen, kommt auf die durchschnittliche geplante Größe der Map an. Wenn die sehr groß werden kann, könnte das Umkopieren schon zu einem Problem werden. Aber ich gebe euch recht, es lohnt sich nicht bei relativ kleinen Maps. Allerdings sollte man beim Umkopieren eher die Größe in einer Dimension verdoppeln als bei jedem neuen Klick eine Zeile oder Spalte anzuhängen.

Wobei man bei der Lösung die ich oben sagte ja einfach Indices auf Koordinaten verwenden könnte. Anstatt etwas um zu kopieren müsste man dann nur einen Index einfügen anstatt alles um zu kopieren.

Dafür hast Du ein new pro Tile und cache-feindliche Zugriffsmuster bei jedem Drüberiterieren. Und der Speicher-Overhead einer Map ist auch nicht zu verachten, speziell im Vergleich zu den Nutzdaten, die hier ja nur ein Tile wären.

Nimm ein 2D-Array, oder bau Dir eins aus einem std::vector. Das Vergrößern und Verkleinern ist dann eine Reallokation und Umkopieren, aber das taucht bis zu einer Größe von ein paar Hundert Tiles ins Quadrat nichtmal im Profiler auf. Das Array kannst Du stressfrei auch mit einem internen Koordinaten-Offset ausstatten, so dass Deine Map auch ins Negative wachsen kann. Und dann vergrößerst Du nur in größeren Schritten wie z.B. 16 Tiles auf einmal, und alles ist gut.

Denk aber unbedingt an die multiplen Layer. Nach meiner Erfahrung sind die eher alle als die Map-Größe. Bei Splatter haben wir 8 Tile-Layer, plus einen Layer Trümmer zwischen L3 und L4, einen Layer für editor-platzbierbare Decals (ebenso L3-L4) und einen Objektlayer (ganz oben drauf >L7), wo dann obendrauf aber nochmal extra der Spieler und Partikel draufgepinselt werden. Und selbst das Konstrukt ist bisweilen eng geworden.

Die Layeranzahl könnte man ja im Prinzip auch beliebig gestalten. Tiled unterstützt afair 100 Layer. Da wird man ja erst mal nicht unbedingt beschränkt.

std::map benutzt vor allem auch einen Baum intern. Nur dass du dann pro Tile ein Blatt im Baum hättest, was ganz schrecklich ineffizient wäre.