Die Spielwelt

Eine Blockwelt wie in Minecraft besteht aus Millionen von Blöcken. Dieses Kapitel zeigt, wie eine solche Welt gespeichert wird und mit welchen drei Ideen das Spiel vermeidet, fast alles davon zeichnen zu müssen.

Wie die Welt gespeichert ist

Die Welt ist ein Raster aus gleich großen Würfeln. An jeder Stelle des Rasters sitzt genau ein Block. Für jede Stelle wird nur eine kleine Zahl gespeichert, die sagt, welche Art von Block dort ist. Auch Luft ist eine Blockart.

LUFT, ERDE, STEIN = 0, 1, 2

Wie speichert man ein dreidimensionales Raster? Schritt für Schritt, mit Listen:

• Eine Reihe von Blöcken ist eine Liste: [STEIN, STEIN, ERDE, LUFT]
• Eine Schicht ist eine Liste von Reihen, also eine Tabelle.
• Die Welt ist eine Liste von Schichten: eine Liste von Listen von Listen.

Um einen Block zu finden, braucht man drei Nummern, eine für jede Ebene der Verschachtelung. Das sind genau die Koordinaten x, y und z aus Kapitel 1:

art = welt[x][y][z]          # welche Blockart ist an der Stelle (x | y | z)?
welt[3][2][5] = LUFT         # den Block an der Stelle (3 | 2 | 5) abbauen

Wichtig für alles Weitere: Der Computer muss einen Block nicht suchen. Aus x, y und z ergibt sich direkt die Stelle in der Liste. Der Zugriff dauert immer gleich lang, egal wie groß die Welt ist. Man sagt: Er kostet konstante Zeit, O(1).

Warum man nicht einfach alles zeichnen kann

Die Welt ist in Abschnitte geteilt, damit immer nur die Umgebung der Spielfigur geladen sein muss. Ein Abschnitt ist 16 Blöcke breit, 16 Blöcke tief und 256 Blöcke hoch.

Sichtweite 12 heißt: 12 Abschnitte in jede Richtung, mit dem eigenen also 25 nebeneinander. Fast eine halbe Milliarde Dreiecke in jedem Bild ist auch für eine heutige Grafikkarte zu viel. Zum Glück sind die allermeisten davon gar nicht zu sehen.

Idee 1: Verdeckte Flächen gar nicht erst erzeugen

Ein Block tief im Boden ist auf allen sechs Seiten von anderen Blöcken umgeben. Keine seiner Seiten ist jemals zu sehen. Allgemein gilt: Eine Blockseite ist nur sichtbar, wenn der Nachbar auf dieser Seite Luft ist.

Ob das so ist, lässt sich nachschlagen. Der Nachbar rechts von (x | y | z) ist (x + 1 | y | z), der Nachbar darüber ist (x | y + 1 | z), und so weiter. Jeder Block hat sechs Nachbarn.

Wähle verschiedene Blöcke: einen an der Oberfläche, einen im Inneren, einen am Hang. Die Liste zeigt für jede der sechs Seiten, was der Nachbar ist und ob die Seite gezeichnet werden muss.

Als Programm: Gehe alle Blöcke durch. Für jeden, der nicht Luft ist, prüfe die sechs Nachbarn. Jede Seite mit einem Luft-Nachbarn kommt auf die Liste der Flächen, die gezeichnet werden.

NACHBARN = [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]

def sichtbare_flaechen(welt):
    flaechen = []
    for x in range(16):
        for y in range(256):
            for z in range(16):
                if welt[x][y][z] == LUFT:
                    continue                                  # Luft hat keine Seiten
                for dx, dy, dz in NACHBARN:
                    if blockart(x + dx, y + dy, z + dz) == LUFT:
                        flaechen.append((x, y, z, dx, dy, dz))    # diese Seite ist sichtbar
    return flaechen

Die Funktion blockart schlägt in der Welt nach. Liegt die Stelle außerhalb des Abschnitts, fragt sie den Nachbarabschnitt.

Wie viel das bringt, zeigt der Schnitt durch eine Welt. Hervorgehoben sind die Seiten, die gezeichnet werden müssen. Klicke auf Felder, um zu graben oder zu bauen.

Aufwand: einmal rechnen, Ergebnis aufheben

Die Funktion besucht jeden der 65 536 Blöcke eines Abschnitts einmal und schlägt jeweils sechsmal nach. Das sind rund 400 000 Zugriffe, der Aufwand wächst linear mit der Zahl der Blöcke. Das in jedem der 60 Bilder pro Sekunde für 625 Abschnitte zu tun, wäre viel zu teuer.

Es ist auch nicht nötig. Solange niemand in einem Abschnitt einen Block setzt oder abbaut, ändert sich die Liste seiner sichtbaren Flächen nicht. Das Spiel berechnet sie deshalb einmal, wenn der Abschnitt geladen wird, und hebt sie auf. In jedem Bild wird nur die fertige Liste gezeichnet. Erst wenn sich im Abschnitt ein Block ändert, wird dieser eine Abschnitt neu berechnet.

Das ist dieselbe Idee wie bei Quake in Kapitel 6: Rechenzeit sparen, indem man Ergebnisse speichert.

Idee 2: Nur zeichnen, was im Blickfeld liegt

Die Kamera sieht immer nur einen Ausschnitt der Welt, etwa einen Winkel von 90°. Alles hinter und neben der Spielfigur kann nicht im Bild erscheinen. Das Spiel prüft das nicht für jeden Block einzeln, sondern für ganze Abschnitte: Liegt ein Abschnitt vollständig außerhalb des Blickfelds, wird er komplett übersprungen. Ein einziger Test erspart Zehntausende Flächen. Das ist wieder das Prinzip der Hüllkörper aus Kapitel 3: erst grob prüfen, dann erst genau hinsehen.

Idee 3: Fernes vereinfachen

Nach der Projektion ist ein Block umso kleiner, je weiter er entfernt ist: Größe · f ÷ z. Ab einer gewissen Entfernung ist ein Block kleiner als ein Pixel. Dort jeden Block einzeln zu zeichnen, ist verschwendete Arbeit. Man sieht den Unterschied nicht.

Deshalb gibt es von jedem Abschnitt mehrere Detailstufen (englisch: Level of Detail). In der gröberen Stufe werden 2 · 2 · 2 Blöcke zu einem doppelt so großen Block zusammengefasst, in der nächsten 4 · 4 · 4. Nah an der Spielfigur wird die feine Stufe gezeichnet, weiter weg die groben.

Von Stufe zu Stufe bleibt nur etwa ein Viertel der Flächen übrig. Aus der Nähe sieht man den Unterschied deutlich. Aus großer Entfernung, wenn der ganze Hügel nur noch wenige Pixel groß ist, nicht mehr.

Beide Ideen zusammen

Die Karte zeigt die 625 geladenen Abschnitte von oben. In der Mitte steht die Spielfigur. Schalte die beiden Ideen ein und aus und drehe die Blickrichtung.

Der ganze Weg auf einen Blick

1. Die Welt ist eine verschachtelte Liste von Blockarten, Figuren sind Ecken- und Indexlisten (Kapitel 2).
2. Für jeden Abschnitt wird einmal die Liste der sichtbaren Flächen berechnet und aufgehoben.
3. In jedem Bild: Eingaben lesen, Objekte bewegen, Kollisionen prüfen (Kapitel 3).
4. Abschnitte außerhalb des Blickfelds überspringen, ferne in grober Stufe verwenden.
5. Eckpunkte projizieren, Dreiecke rasterisieren, Textur und Tiefenpuffer anwenden (Kapitel 4).
6. Helligkeit berechnen, Schatten ergänzen (Kapitel 5).

All das geschieht 60-mal pro Sekunde, in jeweils 16,7 Millisekunden.