Best Practice Verdammt große Objekte

[eMmiE]

Hi,

Problem: Ich habe eine Würfel Welt. Diese probiere ich mithilfe von "Voxeln" zu realisieren.
Hierzu speichere ich diese in ".txt"-ähnlichen Dateien ab.
Jetzt stehe ich nur vor einem Problem. Diese Dateien sind ziemlich groß und es wäre optimal zur Laufzeit Objekte mit 128*128*512 Voxeln auf Abruf zu haben.

Hier jetzt die Frage... Ist es zu realisieren, dass man bei so einer Programmführung 18 solcher Objekte hat? Oder sollte ich besser die Objekte kleiner machen? Dazu: Ändert das was daran, dass ich einen Java-Heap-Space Error krieg, selbst bei Flags: -Xms5000M -Xmx5000M?

 

[eMmiE]

@Voxel: Speichert 2 Zustände -> Lebenspunkte als short und Typ als short und drei longs

 

[rme]

Ist es wirklich wichtig, dass du zur Laufzeitig gleichzeitig auf all diese Objekte zugreifen kannst? Die Anzahl der Objekte übersteigt ja die Anzahl der sichtbaren Pixel, d.h. du hast deutlich mehr Objekte als Pixel?

Falls es wirklich sein muss, macht man das üblicherweise so: Speicher sie in einem schnell parsebaren Binärformat in einer Datei und lass dir die Datei in den Speicher mappen. Auf diese Weise kannst du in einer 64bit-VM mehrere Terabyte quasi im Speicher haben und das Betriebssystem kümmert sich darum, dass der Zugriff so schnell wie möglich ist, d.h. Caching etc. Dieser Speicher wird auch nicht vom Heap abgezogen, die Datei wird virtuel in den Speicherbereich deines Programms abgebildet.

Stichwort: Memory Mapped I/O: MappedByteBuffer (Java Platform SE 7 )

 

[eMmiE]

Ja, wesentlich mehr Objekte als Pixel.
Das mit dem speichern/laden ist eine gute Idee.

Meinst du, dass man noch auf 60fps hat?
Dann könnte man doch auch einen Thread machen, der durch diese Dinger iteriert und dann die jeweils nötigen Änderungen macht oder einfach immer nur die Voxel lädt, die gebraucht werden um das Dingsda darzustellen.
Meinst du beim immer dann laden, was man braucht, und im Hintergrund weitere Voxel laden kommt man noch auf 60 - 50 fps?

 

[rme]

Das Laden wird da nicht der Flaschenhals sein - es kommt drauf an, was du mit diesen Objekten vorhast. Allgemein klingt es aber nicht nach einer guten Idee, mehr sichtbare Objekte als Pixel zu haben.

"Laden, was man braucht" klingt nicht so, als ob du wirklich zu jedem Zeitpunkt alle diese Objekte brauchst, sondern auswählen kannst, welche du zu welchem Zeitpunkt brauchst. Für so einen Zweck unterteilt man seinen Bereich (bei dir geht's wohl um ein Spiel, also ist der Bereich zum Beispiel eine Karte) in mehrere Sektoren, sodass man nur die Objekte laden muss, die in umliegenden Sektoren sind.

Dazu legt man üblicherweise neben der Datei mit allen Objekten eine Indexdatei an, die für jeden Sektor angibt, an welcher Adresse der anderen Datei die Objekte gespeichert sind und wie viele Objekte dort gespeichert sind. So kannst du in der Indexdatei sehr schnell nachschlagen, von wo bis wo du die andere Datei auswerten musst.

 

[eMmiE]

Das mit der Sektorisierung mache ich schon.
Meine Idee:
Einteilung der Welt in x und y und "up" oder "down"
"up" oder "down" gibt hierbei an, ob ich die obere Hälfte Benutze oder die untere

Bsp.:
Insgesamt ist meine Welt 1024 Voxel-Dinger hoch
Sie soll in x und y Richtung gegen unendlich (erstmal gegen Integer.MAX_VALUE gehen)
Ich teile meine Koordinaten auf in S(x|y|z) und A(a|b|c) (nur Beispiel)
mit a|b|c spreche ich den jeweiligen Sektor, ich nenns Areal, an.
Am Anfang, wenn noch keine Welt "da" ist, erstelle ich 18 Areale.
Die in der Mitte sind die, in denen ich mich bewege.

Wenn a = 0 und b = 0 und c = true(->"up"), dann spreche ich die obere Hälfte des Areals an, das sich bei (0|0) befindet

Warum 18 Areale?
-> jeweils eines in der Mitte plus alle Umliegenden für oben und unten

Auf die Zahlen komme ich durch rein Vorstellung.
1024 Klötze in der Höhe sollten eigentlich reichen.

Meine nächste Idee ist jetzt, dass ich meine Areale in jeweils 16*16*16 große Untereinheiten aufteile, die ich immer dann im Cache habe, wenn das Areal gebraucht wird (-> im Umfeld vom Mittelareal s.o.) und immer lade, wenn ich sie brauche

Ist es nicht besser, wenn ich in so einem Fall die Welt in "Sticks" aufteile, die einfach 1024 Voxel umfassen (->von oben nach unten) und die dann immer lade?

 

[rme]

Aber warum willst du dann alle Objekte laden? Üblicherweise macht man das so, dass du aus der Indexdatei nun in Zeit O(1) ausliest, welche Voxel du für einen bestimmten Punkt im Spiel benötigst. Dann kannst du die in Zeit O(n) lesen, wobei n die Anzahl der benötigten (!) Voxel ist. Diese speicherst du dir solange zwischen, wie der Spieler sich noch in diesem Gebiet aufhält. Sobald er sich bewegt, leitest du aus dem Richtungsvektor schonmal den nächsten Sektor ab und lädst ihn im Hintergrund. Sobald er in diesen gewechselt ist, kannst du den vorletzten Sektor wegwerfen. Auf diese Weise benötigst du immer nur ein paar Sektoren im Speicher, hast eine nahezu konstante und kurze Ladezeit und musst nicht bei jeder Bewegung durch alle Voxel iterieren, um erstmal die relevanten rauszufinden.

Beispiel für eine Indexdatei:
* Aufteilung in z.B. 128 * 128 Blöcke, sodass jeder Block 8 * 8 Voxel oder was auch immer enthält
* Codierung: an Position [x * 128 + y] ist ein 2-Tupel der Form (offset, Anzahl) codiert
* dadurch hat jeder Eintrag die Größe 8, falls beides int-Werte sind

So kannst du zu einem gegebenen Punkt sofort und in einem Schritt zur korrekten Adresse (nämlich ((x / 8) * 128 + (y / 8)) * 8) der Indexdatei seeken, offset und Anzahl auslesen und mit diesen Informationen die Voxel der tatsächlichen Datei laden. Wenn beide Dateien in den Speicher gemappt sind, hast du eine sehr hohe Geschwindigkeit.

Edit: Meine Antwort hat sich mit deinem Edit überschnitten, aber ich denke, dass es trotzdem klar wird, wie ich das meine bzw. wie du das machen könntest, oder?

 

[eMmiE]

Ich habe das so gemacht, dass meine "Festplatte" aus Ordnern besteht, die immer angeben, wo sich das Aeal befindet (-> z.B. 0,0,0)

Als nächstes will ich einen Cache-Ordner anlegen, in dem ich die benötigten Areale in chunkform zwischenspeichere. Als Chunk lege ich jetzt einfach mal 16*16*16 Voxel fest.

Grundlegendes (angedachtes) Prinzip:
Immer die Chunks laden, die ich für die Darstellung brauche und zwar jeden Frame aufs Neue

Frage: Ist das nicht zu langsam?

 

[rme]

Okay, damit verschiebst du das Indexieren auf das Dateisystem und damit auf das Betriebssystem, was normalerweise eine gute Idee ist 🙂

Ich würde die Chunks laden, sobald absehbar ist, dass der Spieler deren Sektor betritt - und sie dann im Speicher halten, bis der Spieler sich von diesem Sektor weit genug entfernt hat. Wenn du sie jedes Mal auf's neue laden musst, könnte das zu langsam sein. Dabei ist das Laden aus einer memory-mapped-I/O-Datei nicht das Langsamste, sondern das dynamische Erzeugen deiner Voxel-Objekte aus diesen Daten. Deshalb würde ich sie im Speicher halten, bis sie nicht mehr gebraucht werden - zum Beispiel in Form eines Szenengraphs oder eines Quad-Baums - je nachdem, wie deine Szenen aussehen und die Daten strukturiert sind.

 

[eMmiE]

Also:
Jetzt nochmal zur Grundstruktur, wie dus aufbauen würdest...
Eine Klasse, über die man an 128*128*512 Klötze ran kann.
-> Areal
Die Klötze sind in jeweils 16*16*16 Würfeln abgespeichert
-> Chunks im Cache-Ordner
D.h. Areal muss 8*8*32 Dateipfade = 2048 Dateipfade

Ich meine, dass immer die Klötze, die sich in einem riesigen 128*128*128-Würfel um den Spieler rum befinden benötigt werden...

Wie setzt man das jetzt am besten um?
Immer, wenn sich der Spieler bewegt, neu laden?

 

[rme]

Bei jeder Bewegung prüfen, in welche Richtung sie geht und das angrenzende Areal in dieser Richtung schonmal nebenläufig vorladen.