Datenstruktur für Arrays mit großen Datenmengen

Ich programmiere an einem Voxel Game, vergleichbar mit Minecraft. Die Landschaft von Voxel Games besteht aus Millionen von Blöcken (Nodes)

Die Blöcke werden beim Start definiert, zB welche Texturen ein Block hat, ob der Block fest ist (Stein) oder nicht (Luft) usw.

Ein Kartengenerator erzeugt mittels Algorithmen im Prinzip ein riesiges Array aus diesen Blöcken. Damit die Blöcke handelbar sind unterteilt man die Karte in sogenannte Chunks. Bei Minecraft besteht ein Chunk aus 16x256x16 Blöcken. Bewegt sich ein Spieler durch die Welt werden um ihn herum die nötigen Chunks geladen.

Zu den Daten eines Blocks kommen noch weitere Informationen wie eine Lightmap, mögliche Rotation eines Blocks und weitere Daten dazu.

Da der Zugriff schnell erfolgen soll und die gespeicherten Datenmengen im RAM halbwegs im Rahmen bleiben sollen, grüble ich darüber nach, wie ich das am effizientesten machen kann.

Meine erste Eingebung ist es, für die Blöcke eine statische Klasse anzulegen und nicht für jeden Block ein Objekt zu erzeugen. In den Chunk Arrays wird lediglich eine ID auf die Definition eines Blocks angelegt.

So ein Spiel kann jedoch eine Menge verschiedene Nodes enthalten, so dass 16 Bit für die ID nicht reichen. Weit über 90% einer Map besteht jedoch aus einer sehr kleinen Anzahl verschiedener Blöcke wie Stein, Erde, Wasser und Luft.

Daher habe ich überlegt, für die Chunks ein Jagged Array zu verwenden und die ID ähnlich wie UTF-8 zu speichern. Die häufigsten Nodes werden in den ersten 7 Bit gespeichert, dass achte Bit gibt an ob Schluss ist oder ob ein weiteres Byte folgt usw. Das würde die Datenmenge erheblich reduzieren auf im Idealfall 64kByte statt 256kByte pro Chunk.

Ich weiß leider zu wenig über Jagged Arrays um sagen zu können, ob der Ansatz sinnvoll ist. Ich weiß, dass Jagged Array ein Array von Arrays sind. Ich nehme mal an, die eigentlichen Daten werden im Speicher abgelegt und es werden nur Referenzen gespeichert. Leider habe ich über die genaue Implementierung noch nichts gefunden.

Ist das ein sinnvoller Ansatz oder gibt in C# eine bessere Lösung?

EDIT: Mir ist gerade eingefallen, dass ich Bit 7 gar nicht benötige. Ich kann das ja über die Länge des Arrays bestimmen. Ich speichere einfach ein, zwei oder vier Byte ab und caste das beim Auslesen einfach in ein uint

Mir ist gerade der Haken an der Methode aufgefallen. Ich muss ja für jeden Block einen Referenz speichern, die selbst vermutlich 64 Bit groß ist. Also fällt das flach

Nein, musst du nicht. Kannst du machen ist aber überflüssig und steht im Gegensatz zu deiner hohen Performance/geringer Speicherplatz Anforderung.

Wenn ein Chunk fix aus 16x16x256 (Breite x Länge x Höhe) Blöcken besteht, dann reicht es aus, wenn diese Blöcke sich an bestimmten Positionen in einem Array befinden. Darüber kann man ganz einfach die Position im Chunk-Block-Array ermitteln (index = z * 256 + y * 16 + x)

Beim Speichern des Chunks wird dieser in einem Rutsch mit den Blöcken (in der Reihenfolge) gespeichert und schon braucht man auch dort diese ID nicht.

@Sir Rufo: ich glaube, du hast mich missverstanden, oder ich verstehe nicht, was du meinst.

Ich hole noch mal etwas weiter aus. Jeder Block muss erst einmal definiert werden, wie er aussieht und welche Eigenschaften er hat. Jede Definition hat eine eigene ID. Mal ein paar Beispiele: Luft = 1, Wasser = 2, Erde = 3, Stein = 4 usw

Der Mapgenerator erzeugt jetzt die Karte und speichert an jede Koordinate eine ID. Ein Chunk kann jetzt z.B. nur aus einsen, vieren usw bestehen oder eben eine beliebige Kombination daraus.

Damit ich genug unterschiedliche Blöcke darstellen kann reichen 16 Bit nicht aus, also bräuchte ich für jede ID 4 Byte, aber die meisten der Bytes sind ungenutzt bzw unnötig, weil eben der größte Teil der Blöcke wie Luft und Wasser nur ein Byte bräuchten.

Ein Kompromiss wäre, ein normales Array mit ushort zu verwenden und das MSB zeigt an, ob aus einer weiteren Tabelle noch irgendwelche Daten geholt werden müssen.

Jedenfalls denke ich, ein Jagged Array scheidet aus.

Die Chunk Größe steht noch nicht 100% fest, aber wenn sie einmal fest steht bleibt sie unverändert. Wie ich in dem Array die einzelnen Blöcke adressieren kann ist mir bekannt.

Ich habe auch schon mal probiert ob es einen Unterschied macht, ob ich ein dreidimensionales Array verwende oder ob ich ein eindimensionales Array verwende und so adressiere, wie du vorgeschlagen hast. Ich konnte keinen Unterschied feststellen. Gibt es einen Grund, ein eindimensionales Array zu verwenden?

Meine erste Eingebung ist es, für die Blöcke eine statische Klasse anzulegen und nicht für jeden Block ein Objekt zu erzeugen.

Das klingt alles sehr abwegig.

Ich weiß leider zu wenig über Jagged Arrays um sagen zu können, ob der Ansatz sinnvoll ist. Ich weiß, dass Jagged Array ein Array von Arrays sind. Ich nehme mal an, die eigentlichen Daten werden im Speicher abgelegt und es werden nur Referenzen gespeichert. Leider habe ich über die genaue Implementierung noch nichts gefunden.

Hier handelt es sich um absolute Grundlagen, die du an den üblichen Stellen nachlesen kannst, z.B. Jagged Arrays (C# Programming Guide) sowie Value Types and Reference Types.

Bitte beachte [Hinweis] Wie poste ich richtig?, Punkt 1.1, 1.2, 4, 5 und so ziemlich alle anderen Punkte!

Da der Zugriff schnell erfolgen soll und die gespeicherten Datenmengen im RAM halbwegs im Rahmen bleiben sollen, grüble ich darüber nach, wie ich das am effizientesten machen kann. Du könntest dich mal mit dem Muster Fliegengewicht / flyweight pattern beschäftigen.

Hier handelt es sich um absolute Grundlagen, die du an den üblichen Stellen nachlesen kannst, z.B.
> sowie
> .

Wenn du meinen zweiten Post gelesen hättest wäre dir mein ursprünglicher Irrtum bereits aufgefallen. Leider steht auch in deinen Links nicht drin, wie ein Jagged Array aufgebaut ist. Da steht zB nur

This example builds an array whose elements are themselves arrays

Dass es sich bei dem ersten Array um Referenzen auf die Elemente handelt muss man sich denken. Ich habe noch nirgendwo explizit gelesen, dass es so ist. Egal wo ich gelesen habe, überall steht nur "Array of Arrays"

Das klingt alles sehr abwegig.

Erklärst du mir auch, warum? Wo ist mein Denkfehler?

Du könntest dich mal mit dem Muster Fliegengewicht / flyweight pattern beschäftigen.

Habe ich getan.

In einem kurzen Satz

A flyweight is an object that minimizes memory use by sharing as much data as possible with other similar objects

Das heißt, es ist immer noch ein Objekt, dass instanziert werden muss und eine Referenz braucht, die bei einem 64 Bit System normalerweise 8 Byte groß ist.

Es ist also egal, wie kompakt das Objekt ist, ich brauche für jedes Objekt mindestens 8 Byte. Sehe ich das richtig?

Mal kurz rechnen: Ein Chunk hat 16x256x16 Blöcke. Für einen einzelnen Spieler und einer geringen Sichtweite von 100 Blöcken brauche ich im Speicher 196 Chunks. Macht fast 13 Millionen Blöcke und bei 8 Byte pro Referenz fast 100MB RAM und ich habe dabei noch nicht ein Bit an Daten

Und meine Berechnung ist noch sehr zurückhaltend. Wenn ich die Sichtweite auf 200 Blöcke schraube bin ich bei über 300MB... nur für einen Spieler und immer noch nur für Referenzen, noch nicht mal für das Objekt selbst.

Angenommen ich verwende die vollen 32 Byte Bit für die ID und speichere sie direkt in einem normalen Array anstatt Objekte zu verwenden, dann belegt ein Chunk Array 256kByte und bei einer Sichtweite von 200 Blöcken macht das 150MByte.

Habe ich irgendwo einen Denk- oder Rechenfehler?

...dann speichere die Welt doch nicht in einem dreidimensionalen Würfel sondern in einer geeigneten Baumstruktur die neben- bzw. übereinanderliegende Blöcke mit denselben Eigenschaften als ein Objekt zusammenfasst.

Du meinst einen Octree? Wäre eine Möglichkeit, kann aber auch nach hinten los gehen. Selbst gleiche Blöcke können unterschiedliche Eigenschaften haben. Der Octree kann also schnell ziemlich ausfransen. Octrees haben Vorteile, wenn es viele große zusammenhängende Bereiche gibt. Wenn es aber viel Kleinkram gibt bis runter zu einzelnen Blöcken kann der Verwaltungsaufwand schnell explodieren. Bei einem Array hat man immer konstante und kalkulierbare Bearbeitungszeiten.

Es gibt jede Menge verschiedener Daten und bei einigen bin ich der Ansicht, dass sie besser in einem eigenen Array oder anderen Datentyp aufgehoben sind statt in einem Objekt. zB kann jeder Block einen eigenen Timer haben. Es ist denke ich einfacher, die Timer in einer eigenen Datenstruktur zu verwalten, über die man einfach drüber laufen kann, und wirklich nur die Blöcke da drin speichert, die auch wirklich einen aktiven Timer haben statt alle Blöcke durchsuchen zu müssen, ob da gerade ein aktiver Timer ist.

Aber ich werde Octrees mal im Hinterkopf behalten. Die können trotzdem noch nützlich werden.

Ich bin grundsätzlich nicht gegen OOP. Im Gegenteil, ich finde es gut. Aber ich sehe hier wirklich arge Probleme. Ich mag vielleicht nicht der beste C# Programmierer sein, aber ich kenne mich mit Voxel Games ziemlich gut aus und weiß, was da auf mich zu kommt.

wie ein Jagged Array aufgebaut ist.

Zumindest hierbei könnte das Openbook weiterhelfen (Punkt 2.5.7 -
Verzweigte Arrays): Openbook - Arrays

Ich habe dir gerade gezeigt, dass auch ihr nicht alles wisst und ihr euch irren könnt.

Und in Büchern steht auch nicht immer alles.

Vielleicht habe ich die Beiträge hier ja falsch verstanden. Ich erläutere mal, was ich verstanden habe.

Ich soll eine Klasse für die Blöcke erstellen. Dann soll ich für jeden Block, der aktuell im Speicher benötigt wird, eine Objektinstanz erzeugen. Egal ob flyweight pattern oder Octree, es läuft auf Objektinstanzen für Blöcke hinaus.

Hab ich das so weit richtig verstanden?

Und für jede Instanz brauche ich neben den Objektdaten noch eine Referenz, die ich speichern muss und die ist bei 64 Bit Systemen 8 Byte groß.

Ist das richtig oder falsch? How big is an object reference in .NET?