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.