Wahl des richtigen Containers für dynamisches 2D-Array
-
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.
-
Grafikfetischist schrieb:
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.Es gibt in meinem Spiel nicht "den Algorithmus". Generierungsalgorithmen können über shared libraries hinzugefügt und entfernt werden. Auch den Default-Algo werde ich als sharedlib erstellen. Damit wird es wohl nicht möglich sein, diese auf der Graka laufen zu lassen.
Patrickssj6 schrieb:
Die Chunks sind 32x32xHöheDerWelt(128)
Fast. 16x16x128
Patrickssj6 schrieb:
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.
Das kann ich mir nicht vorstellen. Ich habe mich schon mal zum testen an den Rand der Map geportet, wo durch Rundungsfehler bei Fließkommazahlen die Physik etwas rumspinnt. Die Map war sofort da. Selbst wenn, ich mache das nicht so.
-
Patrickssj6 schrieb:
Dabei wird Leere auch mit abgespeichert.
Dass die Leere mit abgespeichert wird, ist der Sinn und macht das Ganze überhaupt erst möglich. Denn sonst müsstest du für jeden Block die Position speichern.
-
cooky451 schrieb:
Patrickssj6 schrieb:
Dabei wird Leere auch mit abgespeichert.
Dass die Leere mit abgespeichert wird, ist der Sinn und macht das Ganze überhaupt erst möglich. Denn sonst müsstest du für jeden Block die Position speichern.
Naja, ist jetzt Auslegungssache was man unter "Leere mit abspeichern" versteht.
---
Ich meinte es auf jeden Fall so (die Sache mit der Höhe ignoriere ich mal):
Basis-Block: hält z.B. 8x8 Elemente. Kann nicht weiter unterteilt werden. Ob für "leere" Elemente auch *sämtliche* Daten mit abgespeichert werden, oder bestimmte Dinge nicht (die in den "belegten" Elementen dann über Zeiger referenziert werden) ist (mir) dabei erstmal egal.
Wie genau der Basis-Block seine Elemente hält (also ob über Zeiger oder direkt als fixed-size Array-Member mit allen nötigen Daten) müsste man sich dann noch überlegen, bzw. etwas experimentieren.L2-Block: hält 16x16 Basis-Blöcke über ein fixed Size 2D Zeiger-Array. In dem 2D Zeiger-Array können Nullpointer drinstehen - d.h. dann dass der ganze Basis-Block der dort wäre "leer" ist, und daher weggelassen wurde.
L3-Block: hält 16x16 L2-Blöcke - nach dem gleichen Schema wie der L2-Block seine Basis-Blöcke verwaltet.
Das ganze kann man quasi beliebig weit fortsetzen, da ab einem bestimmten Level eh immer nur ein "Kind-Block" non-null ist.
Ich bin mir auch nicht 100% sicher ob das wirklich so schlau ist. Ist nur der beste Ansatz der mir auf die Schnelle eingefallen ist.
-
Das kann ich mir nicht vorstellen. Ich habe mich schon mal zum testen an den Rand der Map geportet, wo durch Rundungsfehler bei Fließkommazahlen die Physik etwas rumspinnt. Die Map war sofort da. Selbst wenn, ich mache das nicht so.
Dann berechne das doch so, als ob es jeweils nur die Blöcke gibt, die in der theoretischen Sichtweite liegen. Hierbei wählst du einen der mittleren Blöcke als Nullpunkt für die Physikberechnung. Dann hast du keine Probleme mit zu großen Gleitkommazahlen.
Für Blöcke die zu weit weg sind, wird dann zwar keine Physik berechnet... aber da sollte mangels Anwenderinterakion nicht viel passieren.Um auch dieses Problem zu beheben kann man bei jedem Block berechnen wann zuletzt die Physik berechnet wurde. Wenn der Block wieder näher kommt kann man dann die fehlenden Berechnungen nachholen. So scheint dann auch die gesamte Welt physikberechnet zu sein.
