Ein kleiner Interims-Post, um mal ein Lebenszeichen zu geben.
Nein, das Projekt ist nicht tot. Im Gegenteil. Ich habe angefangen, die verschiedenen Fäden in einem z.Z. noch nicht funktionierenden Server zu integrieren. Leider fehlt mir im Moment etwas der nötige private Spielraum, die Entwicklung mit höherer Priorität voranzutreiben. Ich habe mir aber vorgenommen, zu versuchen täglich mindestens eine Stunde aufzuwenden.
Die zugehörigen Aktivitäten kann man unter https://bitbucket.org/s_l_teichmann/mygomine verfolgen. "MyGoMine" ist im Übrigen der aktuelle Arbeitstitel der in der Entstehung begriffenen Software.
Aktuelle Arbeitsfront ist die über mehrere Kerne skalierende Integration von Datenquellen für das modifizierte Geländemodell aus dem Backend, aus gecachten unmodifizierten Regionen, aus dem Geländegenerator und der Simulation. Es ist eine sehr spannende und nicht triviale Aufgabe, dies race-frei zu realisieren und dabei die Code-Komplexität im Auge zu behalten. Die finale Lösung kann ich aktuell noch nicht bieten. Ich experimentiere noch mit verschiedenen Ansätzen, aber eine gute und intelligente Lösung zeichnet sich ab, die aus einem kaskadierenden Mischalgorithmus bestehen wird ... wenn nur nicht die Feinheiten des konkurrierenden Zugriffs wären. ;-)
Details hierzu, wenn ich etwas konzeptionell völlig durchdachtes und funktionierendes habe. Hier des kurzfristigen Effektes wegen etwas zu kurz Geschmortes zu präsentieren, führt erfahrungsgemäß zu extrem schwierig debug- und wartbarem Code. Stay tuned.
Dienstag, 27. November 2012
Sonntag, 4. November 2012
Raumfüllend - Von Z-Kurven und LevelDB
Beim letzten Mal haben wir uns über die Ausdehung unserer geplanten Minecraft-Welt unterhalten. Heute soll es tatsächlich um die Speicherung der zugehörigen Daten gehen.
Unsere Welt besteht aus Voxeln, die ihrerseits in PUs (Persistence Units) zusammengefasst werden. Diese Chunks sollen - wie der Name schon andeutet - persistiert werden.
Das angestrebte Datenmodell soll einfach sein. Als Schlüssel soll der Identifikator der PU dienen und die Daten werden als Blob repräsentiert.
Eine einzelne PU kann man auf vielfältige Arten speichern. Für unseren Fall (Nur ein Block-Typ, keine weiteren Attribute) habe ich mich für eine Lauflängencodierung entlang der Hauptachsen entschieden, da die PUs z.Z. im Inneren doch recht fortlaufend strukturiert sind. Aus den 262.144 (64x64x64) Byte werden für PUs, die von unserem SimpleyNoise-Generator erzeugt werden, im Schnitt ungefähr 10.000 Byte.
Andere Kompressionsmethoden wie deflate brächten hier mehr Einsparung. Die Wahl fiel auf RLE, weil es einfach zu erzeugen und ggf. auch einfach im zukünftigen Javascript-Client zu entpacken ist. Das letzte Wort ist an dieser Stelle aber noch nicht gesprochen. Hier müssen erst Erfahrungswerte mit der Gesamtbalance des Systems gewonnen werden. Die spätere Einführung weiterer Block-Typen oder gar Beleuchtung-Attribute könnte die Karten hier komplett neu mischen.
Die Konstruktion der PU-Identifikatoren ist hier schon fester gesetzt. Wie im vergangenen Artikel bereits erwähnt, ist es nötig, diese so zu wählen, dass man effizient auch in größeren Beständen schnell die zugehörigen Daten findet. Zum einen ist das Laden einzelner PUs relavant, zum anderen aber auch die räumliche Abfrage nach PUs innerhalb eines gegebenen Suchkubus. Ein PUs ist im Raum durch seine Lage in X, Y und Z beschrieben und kann somit als dreidimensionaler Punkt verstanden werden.
Derart räumliche Zugriffe werden häufig mit zusätzlichen Indices realisiert, seien es speziell räumliche wie R-Trees, Octress, k-D-Trees, etc oder skalare über die Komponenten des Punktes. Allen diesen ist gemein, dass sie eine sekundäre Datenstruktur darstellen, die mit dem Primärdatenbestand in Sync gehalten werden muss. Auch wenn dies aktuelle Datenbankmanagement-Systeme unter der Haube tun, bedeutet es in dynamischen Situationen (die wir haben) immer einen gewissen zusätzlich Änderungsaufwand.
In unserem einfachen Fall von Punkten kann man durch ein bitweises Interleaving der X,Y und Z-Komponenten eine raumfüllende Z-Kurve definieren,
die aus den 3D-Punkten skalare Werte macht. Diese skalaren Werte können dann direkt als Schlüssel in einer einfache Key/Value-Datenbank benutzt werden.
Als Key/Value-Datenbank wird im weiteren die LevelDB benutzt, die die Vorteile einer guten Performance und einer einfachen API aufweist, die gut auf unseren Anwendundsfall passt. Wir wollen beim Ermitteln der PUs eines Raumsektors nicht jeden einzelnen Punkt einzeln abfragen. Stattdessen wäre eine einmaliges von/bis-Abfrage sinnvoll. Die LevelDB erlaubt es, einen Iterator auf einen zu definierenden Key zu setzen und dann mit dessen Hilfe die fortlaufenden Key/Value-Paare abzurufen.
Die Z-Ordnung ermöglicht uns, einen skalaren Von/Bis-Bereich aufzuspannen. Iteriert man über diesen, läuft man ggf. aus dem eigentlichen Suchbereich heraus, da die skalare Projektion einen dreidimensionalen Schlauch aufspannt, dessen Teilmenge der Suchbereich zwar ist, aber zusätzlich noch irrelevante Bereiche enthält. Zu Details hierzu sei auf die einstweilige Literatur verwiesen.
Die LevelDB erlaubt es, während des Iterierens den Iterator auf eine neue Position zu setzen. Diese neue Position kann mittels eines von H. Tropf und H. Herzog 1981 beschriebenen Verfahren (BIGMIN) im Programmcode effizient errechnet werden.
Folgende Programme testen diesen Ansatz:
Um die Belastbarkeit auch für größere Welten zu testen, habe ich eine 1024x3x1024 Welt erzeugt. Dies entspricht einer Kantenlänge in X- und Z-Richtung von ungefähr 65km und in Y-Richtung von bis zu 192m.
Die LevelDB nahm nachher einen Platz von ungefähr 5,9GiB ein.
Die Erzeugung dauert auf einem halbwegs modernen Intel Core i7-System mit 2,8Ghz ungefähr 4h:20m. Ein Profiling ergab, dass über 95% der Zeit in der Simplex-Noise-Funktion (to be optimized later) verbracht wurden, knapp 3% im RL-Encoder und 1% im Job-Erzeugungs-Code. LevelDB-Aktivität ist nicht relevant gewesen.
Die Abfragen mittels terrainfetch.go laufen in Sekundenbruchteilen und scheinen fürs erste schnell genug zu sein. Auch hier wird man im weiteren ggf. nachjustieren müssen. Die Auswirkungen der LevelDB-eigenen Kompression via Snappy sind sicher besser auf das eigene PU-Kompressionsverfahren abzustimmen. Ein reales Spiel wird zudem noch weitere Schichten besitzen, um nur modifizierte PUs zu im Backend speichern und mittels Caching auf aktuelle aber unmodifizierte PUs zugreifen.
Als Resultat lässt sich festhalten, dass die Kombination von Z-Order und LevelDB möglich ist und in den einfachen Test auch hinreichend gut skaliert.
Wir verlassen jetzt die Ebene der Backend-Experimente und wenden uns in den folgenden Beiträgen der Spiellogik, der Physik und dem Streaming zwischen Server und Client zu.
Unsere Welt besteht aus Voxeln, die ihrerseits in PUs (Persistence Units) zusammengefasst werden. Diese Chunks sollen - wie der Name schon andeutet - persistiert werden.
Das angestrebte Datenmodell soll einfach sein. Als Schlüssel soll der Identifikator der PU dienen und die Daten werden als Blob repräsentiert.
Eine einzelne PU kann man auf vielfältige Arten speichern. Für unseren Fall (Nur ein Block-Typ, keine weiteren Attribute) habe ich mich für eine Lauflängencodierung entlang der Hauptachsen entschieden, da die PUs z.Z. im Inneren doch recht fortlaufend strukturiert sind. Aus den 262.144 (64x64x64) Byte werden für PUs, die von unserem SimpleyNoise-Generator erzeugt werden, im Schnitt ungefähr 10.000 Byte.
Andere Kompressionsmethoden wie deflate brächten hier mehr Einsparung. Die Wahl fiel auf RLE, weil es einfach zu erzeugen und ggf. auch einfach im zukünftigen Javascript-Client zu entpacken ist. Das letzte Wort ist an dieser Stelle aber noch nicht gesprochen. Hier müssen erst Erfahrungswerte mit der Gesamtbalance des Systems gewonnen werden. Die spätere Einführung weiterer Block-Typen oder gar Beleuchtung-Attribute könnte die Karten hier komplett neu mischen.
Die Konstruktion der PU-Identifikatoren ist hier schon fester gesetzt. Wie im vergangenen Artikel bereits erwähnt, ist es nötig, diese so zu wählen, dass man effizient auch in größeren Beständen schnell die zugehörigen Daten findet. Zum einen ist das Laden einzelner PUs relavant, zum anderen aber auch die räumliche Abfrage nach PUs innerhalb eines gegebenen Suchkubus. Ein PUs ist im Raum durch seine Lage in X, Y und Z beschrieben und kann somit als dreidimensionaler Punkt verstanden werden.
Derart räumliche Zugriffe werden häufig mit zusätzlichen Indices realisiert, seien es speziell räumliche wie R-Trees, Octress, k-D-Trees, etc oder skalare über die Komponenten des Punktes. Allen diesen ist gemein, dass sie eine sekundäre Datenstruktur darstellen, die mit dem Primärdatenbestand in Sync gehalten werden muss. Auch wenn dies aktuelle Datenbankmanagement-Systeme unter der Haube tun, bedeutet es in dynamischen Situationen (die wir haben) immer einen gewissen zusätzlich Änderungsaufwand.
In unserem einfachen Fall von Punkten kann man durch ein bitweises Interleaving der X,Y und Z-Komponenten eine raumfüllende Z-Kurve definieren,
die aus den 3D-Punkten skalare Werte macht. Diese skalaren Werte können dann direkt als Schlüssel in einer einfache Key/Value-Datenbank benutzt werden.
Als Key/Value-Datenbank wird im weiteren die LevelDB benutzt, die die Vorteile einer guten Performance und einer einfachen API aufweist, die gut auf unseren Anwendundsfall passt. Wir wollen beim Ermitteln der PUs eines Raumsektors nicht jeden einzelnen Punkt einzeln abfragen. Stattdessen wäre eine einmaliges von/bis-Abfrage sinnvoll. Die LevelDB erlaubt es, einen Iterator auf einen zu definierenden Key zu setzen und dann mit dessen Hilfe die fortlaufenden Key/Value-Paare abzurufen.
Die Z-Ordnung ermöglicht uns, einen skalaren Von/Bis-Bereich aufzuspannen. Iteriert man über diesen, läuft man ggf. aus dem eigentlichen Suchbereich heraus, da die skalare Projektion einen dreidimensionalen Schlauch aufspannt, dessen Teilmenge der Suchbereich zwar ist, aber zusätzlich noch irrelevante Bereiche enthält. Zu Details hierzu sei auf die einstweilige Literatur verwiesen.
Die LevelDB erlaubt es, während des Iterierens den Iterator auf eine neue Position zu setzen. Diese neue Position kann mittels eines von H. Tropf und H. Herzog 1981 beschriebenen Verfahren (BIGMIN) im Programmcode effizient errechnet werden.
Folgende Programme testen diesen Ansatz:
- multidimrangesearch.py Ist ein einfaches Python-Programm, das die Ergebnis von Tropf und Herzog nachvollzieht.
- bigmintest.go ist eine Go-Implementation des BIGMIN-Algorithmus nach Tropf und Herzog. Es wird die Korrektheit mit einem Ergebnisvergleich mit einer naiven Implementation überprüft.
- terrainstore.go speichert mittels Simplex-Noise erzeugte Landschaften in Form von RLE-kodieren PUs in Z-Ordung in eine LevelDB
- terrainfetch,go erlaubt es, räumliche Abfragewürfel gegen die erzeugte LevelDB zu starten. Die Ergebnisse werden als 8-Bit-Raw-Dateien pro PU ins Dateisystem geschrieben. Die Korrektheit der Queries kann dann z.B. mit Paraview geschehen.
Um die Belastbarkeit auch für größere Welten zu testen, habe ich eine 1024x3x1024 Welt erzeugt. Dies entspricht einer Kantenlänge in X- und Z-Richtung von ungefähr 65km und in Y-Richtung von bis zu 192m.
Die LevelDB nahm nachher einen Platz von ungefähr 5,9GiB ein.
Die Erzeugung dauert auf einem halbwegs modernen Intel Core i7-System mit 2,8Ghz ungefähr 4h:20m. Ein Profiling ergab, dass über 95% der Zeit in der Simplex-Noise-Funktion (to be optimized later) verbracht wurden, knapp 3% im RL-Encoder und 1% im Job-Erzeugungs-Code. LevelDB-Aktivität ist nicht relevant gewesen.
Die Abfragen mittels terrainfetch.go laufen in Sekundenbruchteilen und scheinen fürs erste schnell genug zu sein. Auch hier wird man im weiteren ggf. nachjustieren müssen. Die Auswirkungen der LevelDB-eigenen Kompression via Snappy sind sicher besser auf das eigene PU-Kompressionsverfahren abzustimmen. Ein reales Spiel wird zudem noch weitere Schichten besitzen, um nur modifizierte PUs zu im Backend speichern und mittels Caching auf aktuelle aber unmodifizierte PUs zugreifen.
Als Resultat lässt sich festhalten, dass die Kombination von Z-Order und LevelDB möglich ist und in den einfachen Test auch hinreichend gut skaliert.
Wir verlassen jetzt die Ebene der Backend-Experimente und wenden uns in den folgenden Beiträgen der Spiellogik, der Physik und dem Streaming zwischen Server und Client zu.
Sonntag, 28. Oktober 2012
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:
Für die Kantenlänge der Gesamtwelt von 220 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 (220)3 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, 220]3. 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.
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 220 PU nebeneinander eingelegt werden. Dies entspricht also einer simulierten Länge von ~67.108 Kilometern (vgl. Erdumfang ~40.000km).
Für die Kantenlänge der Gesamtwelt von 220 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 (220)3 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, 220]3. 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.
Montag, 22. Oktober 2012
Von grünen Hügeln
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.
Sonntag, 21. Oktober 2012
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:
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.
Abonnieren
Posts (Atom)