Von der Vermessung der Welt

Im Laufe der Arbeitswoche sind auch aufgrund von Krankheit ein paar Dinge liegen geblieben, so dass ein kleiner Blog-Stau entstanden ist. Vermutlich habe ich einfach noch nicht die richtige Balance gefunden, hier Dinge voranzubringen. Ggf. muss ich in Zukunft die einzelnen Punkte in kleinere Posts zerlegen.

Weiter im Text.

Ich hatte mich dafür entschieden, die Welt mithilfe von Simplex Noise zu erzeugen. Ein wichtiger Punkte muss diesbezüglich noch erwähnt werden.

Auch wenn es sich hierbei um einen Zufallsprozess handelt, ist dieser im Kern doch von einen Pseudo-Zufallsgenerator abhängig. Dieser ist so gewählt, dass er bei einem gesetzten Seed ein reproduzierbares Ergebnis liefert. Mit anderen Worten: wer den Seed (eine 64-Integer-Zahl) kennt, kann diese Welt immer wieder erzeugen. Auch wenn in realistischeren Szenarien mehrere Zufallsprozesse überlagert werden (z.B. die Verteilung verschiedener Ressourcen auf der virtuellen Karte), ist dieser Determinismus eine sehr praktische Eigenschaft. Zusammen mit der Eigenschaft, dass die Funktion auf dem komplette R³ definiert ist, kann man beliebige Raumausschnitte on-the-fly erzeugen. Es ist insbesondere nicht nötig, einmal erzeugte Abschnitte zu persistieren. Zumindest nicht solange, bis Änderungen seitens der Spieler oder des Systems dies nötig machen.

Da unter Umständen auch die Erzeugung mittels ein oder mehrerer Zufallsfunktionen Zeit kostet, ist es ggf. sinnvoll, hier ein zweischichtiges Weltmodell einzuführen, das neben dem Generator und dem echten Persistenz-Lauer ein Caching von häufig genutzten, aber unmodifizierten Raumausschnitten vorsieht. Ein explizites Caching der modizierten Ausschnitte sollte nicht angestrebt werden, da im Allgemeinen echte Persistenz-Layer (sprich Datenbank-Management-Systeme) ihrerseits schon ein transparentes Caching durchführen.

Bevor wir uns den technischen Details widmen, hier ein paar Design-Entscheidungen bzgl. der Struktur unserer kleinen Welt:

• Die Welt besteht aus Würfeln (Voxel) der virtuellen Kantenlänge von einem Meter.
• Diese werden zu Einheiten von 64 x 64 x 64 zu einer identifizierbaren Persistenzeinheit zusammen gefasst, im folgenden auch als PU (persistence unit) abgekürzt
• In jeder der drei Raumrichtungen können 2²⁰ PU nebeneinander eingelegt werden. Dies entspricht also einer simulierten Länge von ~67.108 Kilometern (vgl. Erdumfang ~40.000km).

Warum diese Vorgaben? Zum einen sind sie bis zu einem gewissen Grad willkürlich; in anderen Minecraft-Alikes sind die PUs z.B. 64x64x128 groß. Zum anderen wurden sie aber auch mit Hinblick auf die Generierung und die Persistenz gewählt. So haben sich 64x64x64 in den Vortests als gut handhabbare Größe im Umgang mit Simplex Noise herausgestellt.

Für die Kantenlänge der Gesamtwelt von 2²⁰ muss man etwas ins Detail gehen. Ginge man naiv her und würde die Welt als dreidimensionales Raster dieser Größe modellieren, hätte man ein Speicherproblem. Nimmt man mal konservativ an, dass sich jeder Voxel in einer PU mit zwei Bit kodieren ließe, bedeutete dies einen Speicherbedarf pro PU von 64KB. Multipliziert man diese mit (2²⁰)³ ergibt sich eine ziemlich große Zahl (Die zugehörigen gigantomanischen Zahlenspiele werden dem Leser überlassen). Man wird also eine kompaktere Darstellung wählen müssen. Hier kommt uns zu gute, dass unter normalen Umständen die Welt aus unmodifizierten, von daher auch nicht zu persistierenden PUs besteht.

Speichert man nur die veränderten PUs ab, so müssen sie sich im Persistenz-Layer mit räumlichen Abfragen, der Art "Gib mir alle PUs im Umkreis von einem halben Kilometer um den Spieler herum." wieder finden lassen. Hierzu speichert man pro PU die zugehörige Raumkoordinate als Tupel aus dem [0, 2²⁰]³. Diese Tupel werden intern als verschränkte 64bit Ganzzahlwerte mit 20bit (64/3 überlaufstabil abgerundet) pro Achse dargestellt. Zur genaueren Darstellung kommen wir im nächsten Eintrag.

Von grünen Hügeln

Heute setzen wir unsere kleine Reihe mit der 3D-Variante von Simplex Noise fort. Mit ihr ist es möglich, *Trommelwirbel* dreidimensionale Landschaften zu erzeugen.

Für die Erzeugung der Beispiele benutzte ich ein kleines Kommandozeilen-Tool namens tilegen3d, das seinerseits auf die Noise3D-Funktion aus meiner simplexnoise-Go-Bibliothek zurückgreift, die ich schon in der letzten Ausgabe vorgestellt habe. Zur Visualisierung der Ergebnisse wurde die Freie Software ParaView verwendet.

Simplex Noise ist für mehr als zwei Dimensionen definiert, insbesondere auch für drei. In diesen Fall wird eine gegebene Raumkoordinate des R³ auf ein en skalaren Wert aus dem Intervall -1 bis 1 abgebildet. Stellt man diese Werte dann jeweils durch Grauwerte da, sieht das für einen Raumbereich exemplarisch wie in nebenstehender Abbildung aus.
Man kann zwar nicht in den Würfel hineinschauen, aber die Strukturen an der Oberfläche setzen sich im Inneren fort.

Wie hilft uns das jetzt bei der Erstellungen von Landschaften? Wie erwähnt, entsprechende die einzelnen Grauwerte einer Zahl zwischen -1 (schwarz) und 1 (weiß). Man kann jetzt einen Schwellwert festlegen, unter dessen Betrag ein Raumpunkt nicht mehr in die Darstellung übernommen wird und quasi ein Loch in der Struktur hinterlässt. Der Einfachheit halber habe ich den Bereich [-1, 1] mittels Addition von 1 und teilen durch 2 auf das Intervall [0, 1] abgebildet und in obigem Beispiel einen Schwellwert von 0,3 angenommen, unterhalb dessen alle zugehörigen Raumpunkte ignoriert werden. Das führt zum links stehenden Ergebnis. Und - oh Wunder - es sind Höhlen und Tunnel in unserem virtuellen Berg entstanden. Das rechte Bild zeigt einem kleineren Raumausschnitt, der den Effekt etwas deutlicher hervorhebt.

Da wir nun in der Lage sind, dass Innere eines Berges zu generieren, stellt sich die Frage, wie es mit der Oberfläche aussieht. Hier zeigt es sich als Vorteil, dass wir den Wertebereich in den Bereich von Null bis Eins verschoben haben. Befinden wir uns nun übertage, kann man von vereinfacht annehmen, dass statisch betrachtet "oben" (im Sinne am oberen Ende der Raumauschnittes) die Wahrscheinlichkeit auf Erde, Fels etc. zu treffen unter normalen Umständen gleich Null ist. "Unten" auf dem Boden ist sie indes Eins. Dazwischen wird in einem Gradienten  der Wahrscheinlichkeitswert langsam zwischen diesen beiden Extremen variieren.

Betrachtet man jetzt das punktuelle Ergebnis der Simplex Noise-Funktion auch als Wahrscheinlichkeit, kann man diese mit dem Erde/Luft-Gradienten mutiplizieren und erhält wieder eine Zahl zwischen Null und Eins, die man anschließend gegen den Schwellwert halten kann.

Das tilegen3d-Tool erlaubt die Angabe es beliebigen Luft-Start- und eines Boden-Endwertes. Dazwischen wird ein linearer Gradient aufgespannt. Dies erlaubt es, die Steigung so anzupassen, um bei Bedarf unterschiedlich hohe Hügel zu erzeugen.
Ein typisches Ergebnis sieht wie nebenstehend aus.


Dies soll es fürs erste in Punkto Generierung von Landschaften gewesen sein. Wir kommen ggf. später noch mal auf das Thema zurück, denn für ein echtes Minecraft-Szenario fehlen doch einige wichtige Aspekte wie zum Beispiel das Verteilen von mehren Materialien wie Sand, Kies, Fels, Erde, etc. Des weiteren führt diese einfache Anwendung von Simplex Noise partiell zu nicht realistischen Landschaftsformen wie kleinen, in der Luft schwebenden Felsbrocken. Die Wahrscheinlichkeit ist auf dem Gradienten halt nicht ganz Null ;-) Aber diese Feinjustierungen heben wir uns für später auf.

Im folgenden geht der Fokus weg von der Küchenmathematik hin zur Informatik. Ich plane, mich mit den Datenstrukturen auseinander zu setzen, die benötigt werden, um auch große Welten effizient verwalten zu können.

Bleiben Sie dran.

Die Welt besteht aus Rauschen

Bevor wir uns mit den verschiedenen technischen Ebenen des Minecraft/WebGL/Websocket/Golang-Clones (Projektname gesucht) beschäftigen, brauchen wir
etwas Datensubstanz für eine begehbare Welt. Doch woher nehmen wenn nicht stehlen?

Mit Welt meine ich im Moment erst einmal ein einfaches 3D-Geländemodel und
auch hier nichts wirklich ausgefeiltes. Etwas ausgefeilt schon, denn es soll
eine solide Basis für weitere Entwicklungsiterationen darstellen.

In Minecraft besteht die Welt aus vielen, aufeinander gestapelten Blöcken mit der virtuellen Kantenlänge von einem Meter. Man bezeichnet die einzelnen Blöcke aus als Voxel (Volume Pixel). Ich fände hier die Bezeichnung Boxel passender, denn mit Voxel verbinde ich eher glattere Darstellungsformen (Marching Cube lässt grüßen). Jeder einzelne Block hat neben seiner Lage im Raum auch noch weitere Eigenschaft, wie z.B. welches Material er repräsentieren soll (Sand, Stein, Dreck, etc.).

Wir müssen also eine Welt aus 3D-Raum-Pixeln erzeugen. Für den allerersten
Anlauf wird es einen einzelnen Blocktyp geben, so dass wir uns völlig
auf die geometrischen Eigenschaften konzentrieren und die weiteren Einschaften vernachlässigen können.

Zur Erzeugung solcher Welten gibt es die verschiedensten Ansätze. Ich habe mich für das gute alte Würfeln entschieden, sprich Erzeugung der Welt mit einen Zufallsprozess. Auch in der Kategorie sind eine Reihe von Algorithmen bekannt: Fraktale Ansätze wie Diamond-Square bis hin zu simulierten Erosionsprozessen, die versuchen, Geologie & Co. nachzuahmen.

Eine beliebter Vertreterin, die unter anderem auch in Minecraft verwendet wird, ist die oskarpremierte Perlin-Noise Rauschfunktion von Ken Perlin, ein Zufallsprozess, der auf das Würfeln und Interpolieren von Gradienten setzt. Da salopp gesprochen der Zufall in differenzierbare erste und zweite Ableitungen versenkt ist, führt er zu gut paketierbaren 2D, 3D, 4D, ...-Funktionen. Dazu mehr in einem späteren Post.

Perlin hat nach der Perlin-Noise-Funktion eine weitere Rauschfunktion, die sogenannte Simplex-Noise veröffentlicht, die bessere mathematische Eigenschaften (Isotropie) und eine geringere Berechnungskomplexität besitzt, was vor allem in höher dimensionalen Anwendung ein wichtiges Kriterium ist. Da die meisten Anwendungen in der Computergrafik eher zwei bzw. dreidmiensional sind, hat sich das Verfahren noch nicht flächendeckend durchgesetzt. Viele betrachten Perlin-Noise für diesen Zweck als gut genug.

Auch hier genug der Vorrede. Ich habe mich entschlossen, Simplex Noise einzusetzen.

Um mit der Technik warm zu werden, habe ich als erstes die in Java geschriebene 2D, 3D, 4D-Variante von Stefan Gustavson und Peter Eastman nach Go portiert und der Philosophie der Autoren folgendend als Public Domain auf bitbucket veröffentlicht.

Das obige Bild wurde im übrigen mit dem Programm tilegen (Auruf: ./tilegen --size=256 --step=.0312) erzeugt, das die neue Go-Library benutzt.

Im nächsten geplanten Blo(ck|g)-Eintrag wird es um weitere Detail zu Simplex Noise und deren konkreter Anwendung zur Erzeugung unserer Klötzchenwelt gehen.

Ein Blog ...

Ein Blog ... nach all den Jahren.

Warum? Zu sagen und zu erzählen habe ich eigentlich eine Menge, aber von Haus habe ich kein allzu großes Bedürfnis mich öffentlich darstellen zu wollen.
Dennoch denke ich, es wäre mal einen Versuch wert, z.B. von meinem privaten Schaffen zu berichten.

Fangen wir mal mit etwas leichtem an. Ggf. wird daraus ein kleines privates Projekt über den Winter, ggf. versandet es aus Zeitgründen, Willensstärke oder mangelnder Disziplin:

Bau eines Mini-Minecraft-Alike auf Basis von WebGL, WebSockets und einem in Go(-lang) geschriebenen Servers.

Mit den genannten Technologien kenne ich mich theoretisch aus, leider hat man mit fortschreitendem Alter auch nicht mehr immer die Muße, sich auch praktisch mit den Dingen intensiver zu beschäftigen. Zudem lässt der Altagsjob in der IT-Branche des öfteren auch mal gerne vergessen, dass man Software eigentlich auch zum Spass und der Ästhetik wegen entwickeln kann.

Der Spass brachte mich auf die Idee. In meiner Firma grassiert z.Z. eine Art Minecraft-Fieber auf Basis der Freien Software Clones Minetest (BTW: Ein empfehlenswertes Spiel).

Da ich initial ein paar technischen Problem mit dem Client der Software hatte, habe ich mir die Quelltexte von Minetest zu Gemüte geführt und mich überkam das bekannte Gefühl, der Fahrradschuppen könnte eine andere Farbe vertragen.

Ja, Minecraft-Alike gibt es wie Sand-Blöcke am Meer, aber halt nicht mein Minecraft-Klon. Und da mir der Sinn mal wieder nach einem Privatprojekt steht, für dessen Umsetzung man mehr als ein Wochenende benötigt, ich mich ohnehin mal intensiver mit WebGL und WebSockets beschäftigen wollte und ich mal einen Server in Go schreiben wollte, der nicht nur triviale Dinge tut, habe ich mich spontan dazu entschieden, mich an Minecraft zu versuchen ... scheitern nicht ausgeschlossen.

Ein 3D-Sandbox-Spiel ist technisch gesehen eine echte Herausforderung auf mehreren Ebenen:

• Serverseitig ist potentiel mit großen und vor allem dynamischen Datenmenge zu hantieren.
• Auf Ebene des Netzwerkprotokolls ist ein effizienter Zugriff auf Teile dieser Daten abzuwickeln.
• Auf der Client-Seite ist ebenfalls einige Cleverness anzuwenden, damit der Eindruck einer großen, lebendigen und frei modifizierbaren Welt entsteht.

So viel der Vorrede. In meinem nächsten Beitrag werde ich mich mit meinen ersten Gehversuchen bezüglich der Erschaffung der simulierten Welt beschäftigen. Stay tuned.