Voxel game Chunk Größe

[burli]

Hi, ich bin neu im Forum und noch relativ neu in Unity. Ich bringe allerdings ein wenig Erfahrung mit was Minecraft-ähnliche Spiele angeht.

 

Ich weiß bereits, dass man die Welt in Chunks unterteilt und das man für jeden Chunk ein Mesh erzeugen sollte. Ich weiß auch, dass man bessere Performance erhält, wenn die Zahl der Meshes nicht zu groß ist. Was ich aber noch nicht verstanden habe: warum wird immer so ein 16x16x256 Chunk erzeugt? Warum kein Würfel mit zB 32x32x32?

 

Ich weiß, dass die "infinite world" von Minecraft nur 256 Blöcke hoch ist. Mein Spiel soll aber in allen 3 Dimensionen "infinite" sein

 

Meine Frage ist: hat diese komische Chunk Form nur was mit der begrenzten Welt von Minecraft zu tun oder hat das irgendwelche technischen Gründe in der Engine oder der Grafikkarte?

 

Ich vermute, es hat nur was mit der Höhe der Minecraft Welt zu tun und der Tatsache, dass 16x16x256 = 65536 ergibt. Ein 32x32x32 Cube wäre nur halb so groß, man hätte also unter Umständen doppelt so viele Meshes (aber nicht zwangsläufig).

 

Da fehlt mir noch der tiefere Einblick in Unity

[Zer0Cool]

Das einzige was ich dazu sagen kann, eine Grenze in Unity gibt es für 1 Mesh und die liegt bei 65,534 Vertices. Aber wenn du die Welt eh in kleine Meshes zerhackst spielt das keine Rolle. Performancelastig sind auch nur die Meshes, die die Kamera gerade sieht und die Objekte wo viele Skripte dranhängen oder viele Objekte wo 1 Skript dranhängt.

[Tiwaz]

Moin, ich wollte eigentlich schon vor ein paar Stunden antworten aber musste schnell weg ^^

 

Also die Maße der Chunks ist, da bin ich mir ziemlich sicher, eine Minecraft Eigenheit und hat keinen tieferen Sinn im Hinblick auf spezielle Grafikkartenauslastung oder sowas.

Ich glaube, dass sich der Notch damit einfach das Generieren der Welten ein bisschen vereinfachen wollte.

So muss er nicht prüfen, ob man unterirdische Teile der Welt sieht oder nicht und die Chunks skippen oder ähnliches. Wenn der komplette Pile runter bis zum Bedrock in 1 Chunk steckt spendiert er hald ein paar tausend Triangles, die unnötig gerendert werden müssen, benötigt aber quasi keine Checks und auch immer gleich viele Chunks um eine bestimmte Fläche darstellen zu können.

 

Da ich generell zu Octrees als Datenstruktur für die Voxel rate, sind nicht-kubische Chunks ohnehin nicht gerade die erste Wahl.. Man könnte auf k-d-trees ausweichen, aber ich glaube das ist auch eher suboptimal.

 

Möchtest du eigentlich eine Boxel Engine (aka Minecraft Blockystyle) oder einen Voxel Generator für realistische Terrains?

 

Um auf die Größe der Chunks zurückzukommen, würde ich zu 16³ oder 32³ Voxel großen Chunks raten.

Kleinere Chunks erzeugen massiven Overhead wenn du wie Zer0Cool sagt z.B. ein Script anhängst das beispielsweise checken soll, ob der Chunk entladen werden soll oder vllt die LOD Stufe ändert.

Bei größeren Chunks dauert das Generieren der einzelnen Chunks natürlich sehr viel länger was dazu führen kann, dass Spieler das Nachladen der Chunks bemerken, weil es plötzlich zu ruckeln beginnt.

[burli]

Ok, dachte mir schon, dass die Chunk Größe Minecraft spezifisch ist. Trotzdem versuchen viele, dass nach zu machen.

 

Es soll ein Minecraft-like Spiel werden, also Blöcke. Die Chunks werden aber nicht in Unity generiert. Dafür will ich einen externen Server verwenden. Der Server soll die Chunks generieren, in einer Datenbank speichern und auf Anfrage an die Clients verschicken. In Unity generiere ich aus den Blockdaten lediglich ein Mesh.

 

Ob ich allerdings einen Octree verwende weiß ich noch nicht. Ich tendiere im Moment eher zu einem eindimensionalen Array pro Chunk. Kostet zwar mehr Speicher, ist aber schneller im Zugriff, da man sich nicht durch den Baum hangeln muss. Zumindest auf der Serverseite ist das notwendig, um mit einer xyz loop die Landschaft erzeugen zu können. Da wäre ein Octree meiner Meinung nach eine ganz schöne Bremse.

 

Ach ja Tiwaz, zu deiner Signatur: 1+1=10 ;-)

[Sleepy]

Wenn du mal bei Minecraft darauf achtest dann fällt dir sicherlich auf das du im inventar fast alles in den größen 4,8,16,32,64 usw gespeichert werden. Dies hat technische Gründe und hängt mit bits und bytes zusammen und wie sie gespeichert werde.

 

Ein Chunk hat zb 256 Glötze diese zahlen werden dir in Minecraft öfter begegnen und dienen der optimalen Speicherauslastung.

 

Weitere Informtionen findest du auch zum Thema "Power of Two"

 

https://en.wikipedia.org/wiki/Power_of_two

 

Bei Voxel ist auch ein wichtiger Bestandteil das an einem Punkt einfach nicht mehr weiter berechnet werden muss und somit keine Rechentasks mehr anfallen.

Die Generierung der Generierung eines Chunks kann in Echtzeit und ingame erfolgen somit können Levelteile auch erst generiert werden wenn sich der spieler nähert. Speichern kannst du dann beispielswiese ganze Chunks ist der Spieler weit von einem bestimmtten Chunk entfernt so muss der gesamte Chunk nicht mehr angezeigt werden.

[burli]

Der C64 war mein erster Computer und ich habe schon damals Bits und Bytes persönlich begrüßt. Ich weiß, dass 1+1=10 ist ;-)

 

Und ein Chunk kann zwar in Echtzeit erzeugt werden, aber ich muss ihn speichern können, sonst gehen alle Änderungen verloren.

 

Wie im ersten Beitrag schon geschrieben kenne ich mich mit Minecraft ähnlichen Spielen etwas aus und habe schon einige Sachen dafür programmiert. Ich habe mich nur darüber gewundert, warum nicht nur Minecraft so ein komisches Chunk Format verwendet sondern warum das Format bei den Unity "Klonen", die ich im englischen Forum gefunden habe, übernommen wurde. Hätte ja sein können, dass es irgend einen Vorteil bringt, wenn man das so macht. Ich hab halt keinen gesehen. Ich kenne mich zwar mit Bits und Bytes aus, aber nicht mit Grafikkarten und deren Eigenheiten

[Sleepy]

Ja wie gesagt das liegt daran das man dann zb ein Chunk mit 256 Bit bzw 32 Byte speichern kann. Somit sind 256 Bit voll gelegt und der Speicher ist best möglich ausgenutzt. wenn dein Chunk zb nur 4 * 4 Blöcke groß wäre dann bräuchtest du trotzdem ein Bit. nur das dieses Bit nicht voll wäre.

[burli]

Ja wie gesagt das liegt daran das man dann zb ein Chunk mit 256 Bit bzw 32 Byte speichern kann

 

Ich glaube, wir reden von zwei verschiedenen Sachen. Einen Chunk, so wie ich ihn verstehe, kann man nicht in 32 Byte speichern. Ein Chunk besteht bei einer Größe von 16x16x256 Blöcken aus mindestens 64kByte, wenn man für jeden Block ein Byte rechnet. Dann kann man in einem Spiel wie Minecraft aber nur 256 verschiedene Blöcke darstellen. Man braucht ja für jeden Block (Air, Dirt, Stone, Water, Grass, Wood, Leaves...) eine eindeutige Zuordnung

 

Ich denke, ich werde für jeden Block 2 Byte verwenden und den Chunk 32x32x32 Blöcke groß machen. Dann komme ich auf 64kByte pro Chunk und kann 65536 verschiedene Blöcke speichern

[Tiwaz]

Ich frage mich wie man auf diese Zahlen kommt?

Wieso kannst du nur eine bestimmte Anzahl an Blöcken speichern/darstellen? Und meinst du jetzt persistent auf der Festplatte oder im RAM?

Prinzipiell musst du auf der Festplatte ja lediglich die Operationen speichern, um die Änderungen festhalten zu können bzw. die Änderungen im Densityfield.

Speichertechnisch würde ich das übrigens auch nicht besonders optimieren wollen, höchstens darauf die Zugriffs- und Speicherzeiten möglichst gering zu halten. Wen jucken heutzutage noch ein paar Megabyte mehr oder weniger für ein Savegame?

Ich sehe da zumindest kein gutes Aufwand-Nutzen-Verhältnis.

Sprichst du von der RAM Belegung gibt es andere Optimierungsverfahren, die deutlich mehr bewirken als die Chunkgröße, da denke ich ist man mit dem Managed Code von C# ganz gut bedient, um nicht übermäßig viel Speicher wegen unausgelasteten Datenblöcken zu verschwenden.

 

Dass man in "einem Spiel wie Minecraft aber nur 256 verschiedene Blöcke darstellen kann" halte ich auch für ein Gerücht.

Um ein Material zu definieren könntest du auch eine bestimmte Bitfolge einer double-Variable benutzen. Dann könntest du 2^64 verschiedene Materialien definieren.

Und wie Minecraft zeigt musst du eigentlich auch nicht unbedingt kubische Blöcke nehmen. Sofern du keine Octrees benutzen möchtest würde theoretisch nicht mal etwas dagegen sprechen überhaupt Chunks zu benutzen die power-of-two sind.

Beim Octree ist das hald wichtig, da du sonst irgendwann nicht mehr restlos teilen kannst, was dann ein bisschen doof ist, aber selbst das wäre eigentlich kein allzugroßes Problem, macht allerdings die Implementierung an gewissen Stellen ein bisschen ätzend.

 

Ich würde da beim Optimieren der Laufzeitperformance mein Hauptaugenmerk viel mehr auf Culling, vernünftiges Multithreading, Greedy Meshing und das Reduzieren von unnötigen erzeugten Vertices/Triangles legen.

Wenn der Speicher auf dem Server wirklich das Problem ist, solltest du mal über Kompressionsverfahren nachdenken und dir überlegen welche Daten wirklich relevant sind (also es wert sind sie abzuspeichern). Das bringt wahrscheinlich deutlich mehr.

 

Ich hab im Übrigen Octrees auch deutlich unterschätzt.

Man hört immer, dass Octrees angeblich so langsam sind und in der Theorie stimmt das auch. Aber in der Realität sind Octrees deutlich schneller und sparen immens Speicher, weil man insgesamt weniger berechnen muss, da man anhand der Datenstruktur relativ leichtes Spiel hat zu entscheiden, ob es Sinn macht den Subtree noch weiter zu generieren/berechnen oder ob man aufhört. Das geht mit Arrays nicht so einfach.

Habe relativ lange gebraucht um von Arrays auf Octrees umzusteigen aber durch Octrees war ich genau so schnell wie mit den Arrays und konnte etwa 3/4 des benötigten Speichers weghauen. Mit ein paar Tweaks hab ich dann die Laufzeit auf Kosten des Speicherbedarfs verkürzt, somit konnte ich schneller generieren und musste immerhin nur noch 1/3 des RAMs benutzen.

Natürlich spricht am Ende auch nix dagegen ein Array zu benutzen, da die beiden Datenstrukturen ohne weitere Probleme ineinander überführbar sind, also sind sie wohl so gesehen relativ gleichwertig. Ich würde aber trotzdem mal beide Strukturen benutzen und Vergleiche ziehen und die bessere Variante benutzen, weil warum unnötig Ressourcen verschwenden? ^^

[burli]

Minecraft speichert die Welt als Byte (auf der Festplatte). Deshalb gib es im Default Spiel maximal 256 Blöcke. Für jede Position kann man aber glaube ich (optional) Metadaten speichern. Das wird dann von Mods benutzt, um mehr Blöcke darzustellen.

 

Würde man für jede Koordinate ein Double speichern würden Maps riesige Mengen an Daten ergeben. Problem wäre nicht der Speicherplatz auf der Platte sondern Transferraten von und zur Platte, über das Netzwerk usw. Man könnte die Datenmenge reduzieren indem man zB simples Run Length Encoding verwendet. Aber 64 Bit wären trotzdem noch zu viel.

 

Mich würden diese Octrees interessieren. Der Aufbau ist mir klar, aber wie kann man sie erstellen? Und wie kann man feststellen, welcher Typ Block an einer bestimmten xyz Koordinate ist?

[Mark]

Zu Octree vs Array, man kann in einem eindimensionalem Array auch gut ein Octree abbilden, Stichwort Z Kurven

 

Für den Speicherverbrauch gibts ja wie schon erwähnt auch eine Menge Techniken, simple RLE oder komplexere Techniken. Ganz simpel hats aber auch Tiwaz schon gesagt, nur speichern was sich nicht generieren lässt:

 

Wenn ich die Welt sowieso aus einem Seed generiere muss ich diese Welt nicht unbedingt auf der Festplatte speichern, nur das was der Benutzer verändert hat (den ganzen Chunk oder nur die Aktion) muss ich speichern.

 

Btw hatten wir zu dem Thema schon einige andere Themen, nur der Vollständigkeit halber:

http://forum.unity-community.de/topic/10975-octree-erstellen-und-befullen-optimierungen/

http://forum.unity-community.de/topic/10363-octree-vs-3d-array-voxel/

http://forum.unity-community.de/topic/7437-ein-versuch-voxel-terrain-prozedurale-mesh-erstellung/

[burli]

Ich muss mich korrigieren. In der neuesten Map Version lassen sich 4096 Blöcke darstellen. Anscheinend wurden die 4 freien Bit der Metadaten dazu genommen.

 

Zu Octree vs Array, man kann in einem eindimensionalem Array auch gut ein Octree abbilden, Stichwort Z Kurven

 

Für den Speicherverbrauch gibts ja wie schon erwähnt auch eine Menge Techniken, simple RLE oder komplexere Techniken. Ganz simpel hats aber auch Tiwaz schon gesagt, nur speichern was sich nicht generieren lässt:

 

Wenn ich die Welt sowieso aus einem Seed generiere muss ich diese Welt nicht unbedingt auf der Festplatte speichern, nur das was der Benutzer verändert hat (den ganzen Chunk oder nur die Aktion) muss ich speichern.

 

Btw hatten wir zu dem Thema schon einige andere Themen, nur der Vollständigkeit halber:

http://forum.unity-c...-optimierungen/

http://forum.unity-c...3d-array-voxel/

http://forum.unity-c...esh-erstellung/

 

Danke für die Links. Werde ich mir anschauen. Aber die Daten sollen schon alle nur einmal generiert und dann gespeichert werden. Komplexere Mapgens können schon eine Weile brauchen und belegen auch ordentlich CPU Kapazität.

 

Und ich werde die Octrees auch noch genauer beobachten. Da wo nur wenige unterschiedliche Blöcke gespeichert werden müssen mag es von Vorteil sein, aber in komplexeren Maps könnte der Vorteil schnell dahin sein

[burli]

So, hab mir mal Gedanken gemacht, wie ich anfange. Ich werde mir erst mal keine Gedanken um die grafische Darstellung machen.

 

Ich konzentriere mich erst mal voll auf die Kartengenerierung und nutze Minetest mit einem Lua Wrapper zur Visualisierung. Die Kartengenerierung läuft völlig unabhängig in eigenen Threads. Hab mir da schon einige Gedanken gemacht.

 

Ich werde eine Art Chunk Manager schreiben, der sich um die Generierung, Speicherung und die Verteilung an die Clients kümmert. Zur Datenspeicherung verwende ich vielleicht MongoDB. Jeder Chunk ist ein Dokument.

 

 

[Sleepy]

Die Zahlen sollten nur Beispiele sein wie groß nachher Daten sind kann ich natürlich nicht sagen.

 

Es gibt wohl unterschiedliche Wege wie man Voxel speichern und darstellen kann Octrees sind dabei auch nur ein rädchen eines evenutell komplexen algorithmuses.

 

Ich denke mal das es durchaus Sinnmacht für Voxel den Marching Cubes Algoritmus zu verwenden wobei Isoflächen (Keine Faces) aus Marching Cube Klassen generiert werden können. Durch das Hidden Surface Removal kann dann auch direkt geprüft werden welche Voxel für den Spieler sichtbar und welche unsichtbar sind. Auch das Zbuffer Verfahren kann geprüft werden ob zb ein Cluster durch andere Voxel verdeckt werden diese müssen dann nicht gezeichnet werden.

 

Das tolle an Voxel ist doch das es viele kleine Objekte sind die nur gezeichnet werden müssen wenn sie tatsächlich sichtbar sind.

[Tiwaz]

Es gibt wohl unterschiedliche Wege wie man Voxel speichern und darstellen kann Octrees sind dabei auch nur ein rädchen eines evenutell komplexen algorithmuses.

Hm naja Octrees sind ja erst mal nur Datenstrukturen und haben noch nichts mit irgendeinem Algorithmus zu tun.

 

Ich denke mal das es durchaus Sinnmacht für Voxel den Marching Cubes Algoritmus zu verwenden wobei Isoflächen (Keine Faces) aus Marching Cube Klassen generiert werden können.

Hä?

Burli möchte doch ein Boxel Game machen, dafür ist Marching Cubes denkbar ungeeignet.

Und was meinst du mit "Isoflächen können aus Marching Cube Klassen generiert werden"?

Isosurfaces werden doch üblicherweise durch Dichtefunktionen (Noises) definiert, der Marching Cubes Algo ist aber ein Extraktionsverfahren eben dieser Isosurfaces, der sie mithilfe von Faces visualisiert. Verstehe die Aussage gerade nicht.

[burli]

Ich werde mich erst mal auf den Server konzentrieren, ohne irgendwelche Optimierungen. Einfach stumpf ein Array erstellen und in Unity Blöcke darstellen.

[burli]

Ich werde eine Art Chunk Manager schreiben, der sich um die Generierung, Speicherung und die Verteilung an die Clients kümmert. Zur Datenspeicherung verwende ich vielleicht MongoDB. Jeder Chunk ist ein Dokument.

 

Werde wohl erst mal auf eine dedizierte Datenbank verzichten. Ich denke, es ist einfacher und vielleicht sogar schneller, wenn ich die Daten selbst speichere. Ich erstelle für jeden Chunk ein Verzeichnis mit dem Koordinaten Hash als Verzeichnisname und darin eine Datei für Heightmap, eine für den Chunk usw. Da werden die Objekte dann einfach serialisiert gespeichert