Wave Function Collapse: lokale Constraints und globale Spielbarkeit

Nach expliziten Regeln generieren

Wave Function Collapse eignet sich zum Anordnen von Inhalten, wenn sich lokale Kompatibilität klar formulieren lässt: welche Tile-Kanten aneinanderstossen dürfen oder welche überlappenden Muster nebeneinander bestehen können. Das Verfahren ersetzt nicht die Definition der Level-Ziele. Zuerst visuelle Konsistenz von Anforderungen wie einem erreichbaren Ausgang oder einer garantierten Ressource trennen.

Domänen, Entropie und Propagation

Die ursprüngliche Implementierung verwaltet die möglichen Muster, wählt eine noch unbestimmte Position mit niedriger Entropie, legt dort ein Muster fest und propagiert die daraus folgenden Einschränkungen. Leere Möglichkeitsmengen zeigen Widersprüche an. [1] Erklärungen aus dem Bereich Constraint Solving beschreiben Backtracking als Rückkehr zu einer früheren Entscheidung, um Alternativen auszuprobieren. [2] Nicht jede WFC-Implementierung enthält Backtracking, und gewichtete Entropie ist spezifischer als das blosse Zählen der verbleibenden Optionen.

Durchgerechnetes Beispiel

Als Veranschaulichung dient eine Reihe aus 3 Zellen. Ein RoadEW-Tile hat Strassenanschlüsse nach Osten und Westen, Grass hat keine. Die Regel verlangt, dass Strassenkanten nur an Strassenkanten und leere Kanten nur an leere Kanten grenzen. Die linke Zelle ist auf RoadEW festgelegt, die rechte auf Grass; die mittlere erlaubt anfangs beide Tiles.

Der linke Nachbar erzwingt für die Mitte RoadEW, der rechte Nachbar schliesst genau das aus. Die Domäne der mittleren Zelle wird leer: Die festen Vorgaben widersprechen sich. Ein Neustart mit anderem Zufalls-Seed kann diese konkrete feste Konfiguration nicht reparieren. Stattdessen eine Anforderung lockern, ein kompatibles Übergangs-Tile einführen oder einen Fehlschlag melden.

Nun eine grössere, lokal gültige Karte: Passende Strassenkanten können trotzdem voneinander getrennte Schleifen bilden. Ein erfolgreicher Collapse belegt daher keinen Weg vom Eingang zum Ausgang. Diese Eigenschaft erfordert einen zusätzlichen Constraint, eine vorab reservierte Wegstruktur oder eine separate Konnektivitätsprüfung.

Authoring-Workflow

Einen kleinen Tile-Katalog mit expliziten Ausrichtungen, Kantenbezeichnungen und Gewichten anlegen. Jede Nachbarschaftsregel in beiden relevanten Richtungen prüfen. Randbedingungen unabhängig von den Regeln für das Innere testen; ein Weltrand braucht unter Umständen eine eigene Abschlussregel. Tiles schrittweise hinzufügen, damit sich Widersprüche auf eine überschaubare Änderung zurückführen lassen.

Obergrenzen für Entscheidungen, Propagationsaufwand, Backtracking und Neustarts festlegen. Seed, Katalogversion, feste Constraints und Fehlerposition speichern, damit sich Ergebnisse reproduzieren lassen. Bei Generierung zur Laufzeit festlegen, ob unvollendete Arbeit die Kontrolle abgibt, einen Fallback liefert oder die Anfrage ablehnt.

Grenzen und Validierung

Gewichte steuern die Auswahl, garantieren aber keine exakten Tile-Anteile im Endergebnis. Lokale Konsistenz belegt weder Pacing noch Zugänglichkeit, Begehbarkeit oder Ressourcenbalance. Diese Eigenschaften anhand der tatsächlichen Gameplay-Repräsentation validieren, nicht nur anhand des generierten Bildes.

Generierungszeit, Häufigkeit von Widersprüchen, Anzahl Neustarts und Ablehnungsrate über eine vielfältige Menge von Seeds messen. Diese Werte nur dann als Projektmessungen angeben, wenn sie tatsächlich erhoben wurden. Bei grossen Welten planen, wie benachbarte Regionen sich auf gemeinsame Grenzen einigen; auch einzeln erfolgreich generierte Chunks lassen sich unter Umständen nicht zu einem brauchbaren Ganzen verbinden.

Quellen

[1] WaveFunctionCollapse implementation — Maxim Gumin und Mitwirkende.

[2] Wave Function Collapse explained — Boris the Brave.