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.
Abonnieren
Posts (Atom)