Wahl des richtigen Containers für dynamisches 2D-Array
-
Hallöle,
Ich bastle gerade ein bisschen an einem Minecraft-Klon herum. Wie in Minecraft besteht eine Welt bei mir aus Chunks, also zusammenfassungen von Blöcken. Diese haben die volle Welthöhe, aus diesem Grund fällt die dritte Dimension schon einmal weg.
Allerdings muss ich auch die Chunks in irgendeiner Datenstruktur halten, und dabei bin ich mir nicht sicher, was ich nehmen soll. Die Welt soll jedenfalls in der Lage sein, in alle 4 Richtungen dynamisch zu wachsen.
Möglichkeit 1)
Meiner derzeitige Lösung ist, die Welt ab dem Ursprung (0, 0) (Chunks haben natürlich auch ihre eigenen Koordinaten) in 4 Quadranten aufzuteilen. Für jeden Quadrant lege ich dann einen vector<vector<chunk>> an, der die entsprechneden Chunks hält.Vorteil: Durch die Aufteilung muss ich nur noch am Ende der Sequenz einfügen, weshalb ich vector verwenden kann.
Nachteil: Wenn ich einen beliebigen Chunk haben möchte, muss ich zuerst rausfinden, in welchem der 4 Quadranten sich der Chunk befindet, und danach, wenn nicht in Quadrant 1, die Koordinaten umrechnen, um auf den richtigen Index zu kommen.Möglichkeit 2)
Man verwendet eine einzige deque<deque<chunk>> und speichert mit, an welchem Index der Mittelpunkt der Welt liegt. Da ich deque so gut wie gar nicht kenne und auch keine Ahnung habe, wie sie implementiert ist, weiß ich über mögliche Vorteile und Nachteile nicht bescheid.Als kleiner Hinweis sei noch gesagt, dass ein Chunk günstig movebar ist und im Prinzip intern nur einen Zeiger hält, weshalb eine Verschiebung innerhalb der Datenstruktur günstig ist.
Ich würde gerne wissen, falls ihr euch für eine der beiden Möglichkeiten entscheidet, welche wäre das und warum, und falls nicht, was ihr vorschlagt.
Grüße,
PI
-
Hab deine Anforderungen nur kurz überflogen, aber bei Spielen werden oft http://de.wikipedia.org/wiki/Quadtree und ähnliche verwendet.
-
Wenn ich das richtig verstanden habe, funktioniert ein Quadtree nach dem "Teile und Herrsche"-Prinzip. Das ist dann jedoch nicht was ich suche, da die Chunks immer gleich groß sind. Außerdem benötige ich Random Access, das hätte ich noch dazu sagen sollen.
-
314159265358979 schrieb:
Wenn ich das richtig verstanden habe, funktioniert ein Quadtree nach dem "Teile und Herrsche"-Prinzip. Das ist dann jedoch nicht was ich suche, da die Chunks immer gleich groß sind.
Quadtrees und Octrees verwendet man, um große Teile der Welt bei Sichtbarkeits- und Kollisionstests ausschließen zu können.
Um so eine oder eine ähnliche Struktur kommst Du kaum herum sobald die Welt etwas größer wird.Du musst bei der Wahl der Datenstruktur auch im Hinterkopf behalten, wie alles gerendert wird. Wenn Du z.B. ein tolles Objektmodell ausarbeitest, dieses aber nicht schnell ein einen Vertex-Buffer übertragen kannst, ist es nutzlos.
"Wenn ich einen beliebigen Chunk haben möchte, muss ich zuerst rausfinden [...]"
"[...]Random Access[...]"Von welcher Information ausgehend möchtest Du auf einen bestimmten Chunk schließen?
-
Von seiner Koordinate.
-
Anhand der Benutzereingabe z.B. bei Auswahl eines Chunks?
Dann findet man den Chunk schnell genug im Baum.Erst den Baum absteigen und die verbleibende Liste des Blattes durchwandern. Für die Auswahl ist sowieso etwas wie Color-Picking notwendig (zweiter Renderpass).
EDIT: Ich kenne Minecraft nicht. Aber imho setzt der Benutzer nach und nach seine Würfel in die Welt. Ich würde es mit einem dynamischen Quadtree/Octree versuchen und auf Blattebene alles in ein Array/Vector packen.
-
Bei meiner Methode habe ich allerdings konstante Laufzeit, die Frage ist, inwiefern sich die Art, wie die deque intern aufgebaut ist, darauf auswirken würde. Zugegebenermaßen habe ich relativ wenig Ahnung von Grafikprogrammierung, dafür bin ich aber auch nicht wirklich zuständig. Muss ich wohl mal nachfragen.
-
314159265358979 schrieb:
Bei meiner Methode habe ich allerdings konstante Laufzeit
Das nutzt wenig, wenn die Frames in den Keller gehen, wenn Du immer alles rendern musst. Deine Methode ist einfach eine Ansammlung der Vertexdaten und erlaubt kein Frustum- oder Occlusion-Culling.
Bei Grafikprogrammierung muss man immer einen Kompromiss finden und an geeigneten Stellen abstriche machen.
EDIT:
Und in einer Blockwelt in der alles Axis-Aligned ist, könnte man auch in konstanter Zeit auf das Blatt im Baum schließen. Nur so am Rande.
-
Okay okay, bin ja schon still
-
Wie wär's mit 16x16 Blöcken von 16x16 Blöcken von 16x16 Blöcken von 16x16 Blöcken von ... naja so lange wie nötig halt.
-
Was für einen Unterschied würde das machen?
-
* Du brauchst weniger Speicher für "leere" Bereiche der Karte.
Stell dir mal vor die Karte ist ein riesen grosser Ring mit viel Nichts in der Mitte. Blöcke die "voll mit Nichts" sind kannst du einfach weglassen - wie in einem Zerotree.* Du kannst auch Bereiche "optimiert" abspeichern die nicht komplett leer sind, sondern z.B. voll mit Wasser/Sand/... - so lange alle "Chunks" komplett gleich sind.
* Es gibt keine Reallocations. Die Welt hat von Anfang an immer die max. Ausdehnung. Bloss dass am Anfang die äusseren Bereiche alle "leer" sind. D.h. der Root-Knoten deines Baums aus 16x16 Blöcken hat - bis auf die innersten Blöcke - überall spezielle "Empty" Child-Nodes reingehängt.
Wenn etwas dazukommt, dann müssen ein paar neue Knoten in den Baum reingehängt werden - die bestehenden müssen aber nie verschoben werden.* Es müsste cachefreundlicher sein. Wobei du mit der Block-Grösse experimentieren müsstest. Vielleicht sind 4x4 oder 8x8 Blöcke besser.
* Da die Struktur bereits hierarchisch ist, bietet es sich an einen hierarchischen Index einzubauen (oder parallel dazu aufzuziehen). z.B. kannst du für jeden Node den min. und max. Z-Wert der darin enthaltenen Chunks speichern. Damit kannst du Picking/Ray-Casting ungemein beschleunigen.
-
@hustbaer
Ist das dann so gemeint, dass Blöcke die einmal sichtbar waren und dann durch Bewegung des Spielers außerhalb des sichtbaren Bereichs kommen durch "Empty" Child ersetzt werden?Ich hätte noch eine Verbesserungsidee.
Es gibt ja einen Algorithmus, der die Welt initialisiert. Dann könnte jeder Chunk als "unverändert" abgespeichert werden und der Inhalt mit dem Generator erzeugt werden. Der Chunk wird dann als "geändert" gespeichert wenn der Spieler eine Änderung vorgenommen hat. Wenn dann nur Änderungen (des Spielers) gespeichert werden, die von der initialen Welt abweicht, müsste dies eine Menge Speicher sparen, weil die meisten Spieler nur einen kleinen Teil der Welt bebauen.
-
Meister Stratege schrieb:
@hustbaer
Ist das dann so gemeint, dass Blöcke die einmal sichtbar waren und dann durch Bewegung des Spielers außerhalb des sichtbaren Bereichs kommen durch "Empty" Child ersetzt werden?Nö, mit Sichtbarkeit hat das nix zu tun, sondern mit "Inhalt".
So wie ich Pi's Beschreibung verstanden habe sind grosse Teile der Welt "leer", bis man was reinbaut. Wobei "leer" jetzt heissen kann da ist ne Wasseroberfläche oder wirklich leer oder ... irgendwas was man halt nicht abspeichern muss, sondern no-the-fly beim Rendern generieren (ohne grossen Aufwand natürlich, sonst zahlt's sich ja nicht aus).Ich hätte noch eine Verbesserungsidee.
Es gibt ja einen Algorithmus, der die Welt initialisiert. Dann könnte jeder Chunk als "unverändert" abgespeichert werden und der Inhalt mit dem Generator erzeugt werden. Der Chunk wird dann als "geändert" gespeichert wenn der Spieler eine Änderung vorgenommen hat. Wenn dann nur Änderungen (des Spielers) gespeichert werden, die von der initialen Welt abweicht, müsste dies eine Menge Speicher sparen, weil die meisten Spieler nur einen kleinen Teil der Welt bebauen.Zum Speichern auf Disk wäre das vielleicht was.
Aber während das Game läuft im RAM? Klar, Speicher könnte man damit auch sparen, aber dafür würde man vermutlich viel zu viel Rechenleistung verbraten wenn man für jedes Frame die nicht geänderten Teile der Welt neu "erzeugen" muss, damit man weiss was man rendern kann.
-
Grundsätzlich kann es sein, dass ein Spieler beispielsweise nur immer geradeaus in eine Richtung läuft, in diesem Fall ist der Rest der Welt leer, die Chunks werden also gar nicht ernst generiert. Sobald ein Chunk generiert wurde, wird er allerdings auch nicht mehr rausgelöscht.
-
314159265358979 schrieb:
Grundsätzlich kann es sein, dass ein Spieler beispielsweise nur immer geradeaus in eine Richtung läuft, in diesem Fall ist der Rest der Welt leer, die Chunks werden also gar nicht ernst generiert. Sobald ein Chunk generiert wurde, wird er allerdings auch nicht mehr rausgelöscht.
Warum nicht? Den könnte man auf der Platte abspeichern, und so ne Menge RAM einsparen.
Wenn du einen fiesen Spieler hast, läuft der sonst im Zick Zack die Welt ab und alles bleibt im Ram vorhanden.Ich denke "Meister Stratege" hat nicht gemeint, dass es in jedem Frame neu berechnet werden soll. Ich denke er bezog das eher auf Chunks die weiter weg sind als die maximale Sichtweite. Diese sollten so lange abgespeichert werden, bis der Spieler wieder nahe genug rankommt, dass sie überhaupt sichtbar sein könnten. (Eventuel laden kurz bevor sie sichtbar werden können)
Dann könnten die Chunks mit dem genartor neu erzeugt werden, mit den geladenen Änderungsinformationen versehen werden und angezeigt werden. Sie bleiben solange in der Datenstruktur wie sie in der möglichen Sichtweite des Spielers sind.
Damit könnte die Welt um ein vielfaches Größer sein, als es der RAM eigentlich zulassen würde.
-
Mit rausgelöscht meine ich ganz gelöscht. Ich verwende natürlich schon einen Cache und halte nur Chunks bis zu einem gewissen Radius im RAM. Die nicht geladenen Chunks liegen unsortiert in einer Datei, wobei ich aber eine Index-Tabelle mit Offsets halte. Dadurch muss ich bei keinem Schreibvorgang Daten verschieben.
-
Auch wenn es sich zuerst komisch anhört. Es könnte wirklich besser sein die Chunks vollständig in jedem Frame mit dem Genarator und den (wenigen) Änderungsinformationen neu zu berechnen.
Wenn dies vollständig in der Grafikkarte pssiert könnte es wirklich schneller sein.
-
(Ich bin nciht mehr sicher wegen der Größe der Chunks,Maps etc deswegen habe ich die Werte geraten).
Minecrafts Methode um die Welten abzuspeichern ist überhaupt nicht effizient. Die Chunks sind 32x32xHöheDerWelt(128)
Dabei wird Leere auch mit abgespeichert. Wenn man nun sich zu einem Ort teleportiert wo keine Chunks geladen wurden, dann werden von 0,0 bis 32,32 Chunks geladen...das sieht natürlich blöd aus und vor allem, ist das erneut ineffizient.
Ich denke Notch und Jeb ändern dass nicht, weil all ihre Welt-Erstellungs-Algorithmen auf diesem System aufbauen.
Was ich machen würde ist jeden Chunk in der Höhe nochmal zu unterteilen (wie jemand schon vor mir gesagt hat in 32x32x32 Blöcke z.B) und nur die abspeichern, die wirklich einen Inhalt haben.
Der Vorteil davon ist, man kann abhängig von der Höhe des Spielers die Teile der Welt laden. Wenn ein Spieler z.B in einer Höhle ist, interessiert es nicht was über oder unter ihm zunächst ist. Dies kann später noch nachgeladen werden.
-
Patrickssj6 schrieb:
(Ich bin nciht mehr sicher wegen der Größe der Chunks,Maps etc deswegen habe ich die Werte geraten).
Minecrafts Methode um die Welten abzuspeichern ist überhaupt nicht effizient. Die Chunks sind 32x32xHöheDerWelt(128)
Dabei wird Leere auch mit abgespeichert. Wenn man nun sich zu einem Ort teleportiert wo keine Chunks geladen wurden, dann werden von 0,0 bis 32,32 Chunks geladen...das sieht natürlich blöd aus und vor allem, ist das erneut ineffizient.
Ich denke Notch und Jeb ändern dass nicht, weil all ihre Welt-Erstellungs-Algorithmen auf diesem System aufbauen.
Was ich machen würde ist jeden Chunk in der Höhe nochmal zu unterteilen (wie jemand schon vor mir gesagt hat in 32x32x32 Blöcke z.B) und nur die abspeichern, die wirklich einen Inhalt haben.
Der Vorteil davon ist, man kann abhängig von der Höhe des Spielers die Teile der Welt laden. Wenn ein Spieler z.B in einer Höhle ist, interessiert es nicht was über oder unter ihm zunächst ist. Dies kann später noch nachgeladen werden.
Zu erkennen, dass ein Spieler in einer Höle ist, ist aber sehr rechenaufwendig.
Es muss ja getestet werden ob nicht doch in irgendeiner Blickrichtung eine Sicht nach draußen möglich ist. Dann doch lieber alles laden was in der möglichen Sichtweite ist.
