Level aus einem Seed: zufällig erzeugt und trotzdem für alle gleich
Hundert Level von Hand bauen will niemand, und rein zufällige Level sind für alle Beteiligten wertlos. Wie ein Seed aus einem Zufallsgenerator einen festen Katalog macht – und woran Determinismus in der Praxis scheitert.
Bei DataBurst stand irgendwann die Frage im Raum, wie die Level eigentlich entstehen sollen. Ein Bubble Shooter lebt davon, dass es viele davon gibt – hundert sind kein ungewöhnlicher Umfang, und von Hand gebaut ist das eine Woche Arbeit, bei der man spätestens ab Level 30 anfängt, sich selbst zu wiederholen.
Der naheliegende Ausweg ist, die Level erzeugen zu lassen. Nur hat der in seiner einfachsten Form ein Problem, das größer ist als das, welches er löst: Wenn Level 23 bei jedem Start anders aussieht, ist „Level 23“ kein Name mehr, sondern nur noch eine Zahl.
- Zwei Spieler können ihre Ergebnisse nicht vergleichen.
- Eine Bestenliste je Level ergibt keinen Sinn mehr.
- Ein Fehlerbericht „in Level 73 hängt ein Knoten in der Wand“ ist nicht nachstellbar.
- Und der Schwierigkeitsverlauf, der das eigentliche Kunstwerk an so einem Spiel ist, lässt sich nicht gestalten, wenn man nicht weiß, was man da verteilt.
Die Lösung ist alt und besteht aus einem einzigen Wert: dem Seed.
Zufall im Rechner ist keiner
Was ein Programm als Zufallszahl liefert, ist in aller Regel keine. Ein Pseudozufallsgenerator – PRNG – hält einen internen Zustand und rechnet daraus mit einer festen Formel die nächste Zahl aus, die dann gleichzeitig der neue Zustand ist. Das Ergebnis sieht zufällig aus, besteht statistische Tests und ist trotzdem vollständig vorherbestimmt. Es gibt keine Unbekannte in der Rechnung.
Die einzige Unbekannte ist der Anfangszustand. Und genau der ist der Seed.
Daraus folgt alles Weitere: Gleicher Seed, gleiche Zahlenfolge. Jedes Mal, auf jedem Gerät, in jeder Sitzung. Ein Generator ist damit nicht entweder zufällig oder deterministisch – er ist immer deterministisch, und die Frage ist nur, ob man den Seed in der Hand behält oder ihn aus der Uhrzeit nimmt und wegwirft.
In Godot sieht man diesen Unterschied an zwei Zeilen. Die globalen Funktionen randi() und randf() arbeiten auf einem gemeinsamen Generator, den das Projekt beim Start einmal aus einer nicht vorhersehbaren Quelle setzt. Der ist für Partikel, Varianz in Soundeffekten und Flackern genau richtig – und für Level völlig unbrauchbar, weil ihn jede andere Stelle im Projekt mitbenutzt.
Für alles, was reproduzierbar sein soll, nimmt man einen eigenen:
var rng := RandomNumberGenerator.new()
rng.seed = 12345
print(rng.randi_range(1, 100)) # immer dieselbe Zahl
Das ist der ganze Mechanismus. Der Rest dieses Artikels handelt davon, was man damit anstellt und wie leicht man ihn wieder kaputt macht.
Die Levelnummer ist der Seed
Der Schritt vom einzelnen Seed zum Levelkatalog ist kürzer, als man denkt: Man braucht eine Funktion, die aus der Levelnummer einen Seed macht.
Naheliegend wäre rng.seed = level. Das funktioniert, ist aber aus zwei Gründen keine gute Idee. Erstens liegen die Seeds benachbarter Level dann direkt nebeneinander, und manche Generatoren brauchen eine Weile, bis sich das aus den ersten Zahlen herausgemischt hat – Level 1, 2 und 3 ähneln sich dann sichtbar. Zweitens fehlt die Möglichkeit, den Generator jemals zu ändern, ohne dass alle bestehenden Level sich mit ändern.
Beides löst eine Zeile:
const GENERATOR_VERSION := 1
func level_seed(level: int) -> int:
return hash("databurst-v%d-level-%d" % [GENERATOR_VERSION, level])
Der Hash streut benachbarte Levelnummern auseinander. Und die Version im String macht aus einer Änderung am Generator eine bewusste Handlung: Solange GENERATOR_VERSION auf 1 steht, bleiben alle Level, wie sie sind. Wer den Generator umbaut und die Version mit hochzählt, wirft den gesamten Katalog weg – das soll weh tun, und vor allem soll es nicht aus Versehen passieren.
Damit ist Level 23 keine Zahl mehr, sondern eine Zusage: dieselbe Anordnung, auf jedem Gerät, in jeder Installation, auch in fünf Jahren noch.
Was deterministisch sein soll – und was nicht
Bevor man den Generator schreibt, lohnt sich eine Frage, die leicht übersprungen wird: Was genau soll denn gleich sein?
Bei DataBurst ist die Antwort nicht „alles“. Das Spielfeld – welcher Knoten wo sitzt, in welcher Farbe, welche Sonderknoten dabei sind – muss für alle gleich sein, sonst ist die Bestenliste wertlos. Die Reihenfolge der nachrückenden Knoten dagegen nicht unbedingt: Wäre auch sie fest, hätte jedes Level genau eine optimale Abfolge, die man sich einmal merkt und danach abspult. Das ist dann kein Puzzle mehr, sondern eine Gedächtnisübung.
Die Konsequenz daraus ist eine Regel, die sich durch das ganze Thema zieht: Ein eigener Generator je Belang. Nicht einer für alles.
var layout_rng := RandomNumberGenerator.new() # fest am Level
var queue_rng := RandomNumberGenerator.new() # frei je Partie
func start_level(level: int) -> void:
layout_rng.seed = level_seed(level)
queue_rng.randomize()
build_board(layout_rng)
Das ist nicht nur eine inhaltliche Entscheidung, sondern auch eine technische Absicherung – und damit beim wichtigsten Punkt angekommen.
Warum Determinismus kaputtgeht
Dass gleicher Seed gleiche Zahlen liefert, stimmt immer. Dass gleicher Seed gleiches Level liefert, stimmt nur, solange der Generator jedes Mal dieselben Fragen in derselben Reihenfolge stellt. Und das ist deutlich zerbrechlicher, als es klingt.
Die Reihenfolge der Aufrufe
Ein PRNG ist ein Band, von dem man Zahlen abrollt. Wer irgendwo in der Mitte eine Zahl mehr zieht, verschiebt alles, was danach kommt. Eine Zeile wie
if debug_mode:
rng.randi() # „nur“ ein Probewurf
verändert jedes Level ab dieser Stelle. Dasselbe passiert, wenn eine neue Funktion den gemeinsamen Generator mitbenutzt, wenn eine Bedingung umgestellt wird oder wenn jemand eine Abfrage optimiert und sie dadurch manchmal überspringt.
Deshalb der getrennte Generator je Belang: Wenn die nachrückenden Knoten aus queue_rng kommen, kann an ihrer Logik beliebig geschraubt werden, ohne dass das Spielfeld sich ändert. Zwei Generatoren sind kein Luxus, sie sind die Brandmauer.
Mengen ohne feste Reihenfolge
Der zweite Klassiker ist unauffälliger. Wer über ein Dictionary läuft, über das Ergebnis einer Suche oder über get_children() eines Knotens, der zur Laufzeit gefüllt wurde, bekommt eine Reihenfolge, die nicht garantiert ist. Ist der Seed gleich und die Reihenfolge nicht, ist das Ergebnis trotzdem verschieden.
Die Regel dagegen ist langweilig und wirksam: Alles sortieren, worüber der Generator läuft.
var colors := available_colors.keys()
colors.sort() # ohne das hängt das Level von der Einfügereihenfolge ab
var pick: String = colors[rng.randi() % colors.size()]
Fließkomma über Plattformgrenzen
Der dritte Punkt betrifft nur, wer Positionen ausrechnet statt Felder abzuzählen. Fließkommaoperationen können sich zwischen Plattformen, Compilern und Optimierungsstufen im letzten Bit unterscheiden – und ein letztes Bit reicht, wenn danach gerundet oder verglichen wird.
Für die Struktur eines Levels nimmt man deshalb möglichst Ganzzahlen: nicht „an welcher Position in Pixeln“, sondern „in welcher Zelle“. Was daraus an Koordinaten wird, darf gern Fließkomma sein – es wird ja nur dargestellt und nicht weiterverwendet.
Der Generator selbst
Und schließlich: Ein Seed ist nur zusammen mit dem Algorithmus eindeutig. Wechselt die Engine in einer neuen Hauptversion ihren PRNG, liefert derselbe Seed andere Zahlen. Godots RandomNumberGenerator ist in dieser Hinsicht stabil, aber darauf verlassen sollte man sich nicht blind – wer einen Katalog hat, der über Jahre gleich bleiben soll, schreibt den Generator entweder selbst (ein PCG oder xorshift sind ein paar Zeilen) oder prüft beim Versionssprung einmal nach. Dafür reicht ein Test, der für drei feste Seeds die erwarteten Zahlen erwartet.
Nicht jeder Seed ist ein gutes Level
Ein reproduzierbares Level ist noch kein spielbares. Ein Generator produziert zuverlässig auch Anordnungen, die in zwei Zügen durch sind, die gar nicht lösbar sind oder die alle Sonderknoten in eine Ecke legen.
Der übliche Umgang damit heißt Erzeugen und Verwerfen: Man baut das Level, prüft es gegen ein paar Bedingungen und fängt bei Nichtgefallen von vorn an – mit einem Seed, der sich aus dem ersten ableitet.
func generate(level: int) -> Board:
var base := level_seed(level)
for attempt in 64:
var rng := RandomNumberGenerator.new()
rng.seed = base + attempt
var board := build_board(rng)
if is_acceptable(board, level):
return board
# Kommt das vor, stimmen die Bedingungen nicht – nicht stillschweigend weiterlaufen.
push_error("Kein brauchbares Level %d nach 64 Versuchen" % level)
return build_board(_fallback_rng(base))
Der Punkt daran: Dieser Ablauf bleibt deterministisch. Welcher Versuch angenommen wird, hängt nur vom Seed und von is_acceptable() ab – beides ist auf jedem Gerät gleich. Das Verwerfen kostet Rechenzeit, aber die fällt einmal beim Laden an, und ein paar Dutzend Durchläufe sind in Millisekunden erledigt.
In is_acceptable() steckt dann die eigentliche Arbeit, und dort gehört auch der Schwierigkeitsverlauf hin: Ein Level mit niedriger Nummer darf weniger Farben haben und mehr Luft, ein spätes mehr von beidem. Der Generator würfelt, die Bedingungen formen.
Der eigentliche Gewinn: Es ist testbar
Der Grund, warum sich dieser Aufwand lohnt, zeigt sich nicht im Spiel, sondern daneben.
Ein Fehlerbericht lautet nicht mehr „manchmal geht ein Level nicht“, sondern „Level 73“ – und Level 73 ist auf dem Entwicklungsrechner dasselbe Level. Was reproduzierbar ist, ist behebbar.
Und weil die Erzeugung eine reine Funktion von der Levelnummer auf ein Spielfeld ist, lässt sich der gesamte Katalog in einem Test durchrechnen:
func test_all_levels() -> void:
for level in range(1, 201):
var board := generate(level)
assert(board.is_solvable())
assert(board.color_count() <= max_colors_for(level))
assert(board.node_count() >= 12)
Zweihundert Level, in ein paar Sekunden geprüft, bei jedem Build. Von Hand gebaute Level bekommt man so nicht kontrolliert – da bleibt nur, sie selbst zu spielen.
Und der freie Seed?
Wenn der Katalog erst einmal steht, kostet eine Zugabe fast nichts: Man zeigt den Seed an und lässt ihn eingeben. Aus demselben Mechanismus wird ein geteiltes Rätsel – „nimm mal 8F3C21, das ist gemein“ – und eine tägliche Aufgabe ist dann nur noch ein Seed aus dem Datum:
func daily_seed() -> int:
var today := Time.get_date_dict_from_system(true) # UTC, nicht lokal
return hash("daily-%04d-%02d-%02d" % [today.year, today.month, today.day])
Das true ist dabei nicht egal: Mit lokaler Zeit bekommt jede Zeitzone eine andere Aufgabe, und eine gemeinsame Bestenliste für den Tag fällt in sich zusammen.
Zusammengefasst
- Ein PRNG ist immer deterministisch. Die Frage ist nur, ob man den Seed behält.
- Die Levelnummer über einen Hash in den Seed geben, mit einer Generatorversion im Hash-String.
- Je Belang ein eigener Generator – das ist die Brandmauer gegen verschobene Zahlenfolgen.
- Reihenfolge der Aufrufe und Reihenfolge von Mengen sind die zwei üblichen Bruchstellen. Sortieren hilft.
- Nicht jeder Seed ist ein gutes Level: erzeugen, prüfen, mit
base + attemptverwerfen. - Der Lohn ist nicht der gesparte Aufwand, sondern dass sich hundert Level automatisch prüfen lassen.
Am Ende steht ein Satz, der die ganze Sache trägt: Das Level liegt nicht in einer Datei, es liegt in seiner Nummer.