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.