Prozedurale hexagonale Karte mit Wave Function Collapse erstellen

• Ein Projekt, das mithilfe des Wave-Function-Collapse-(WFC)-Algorithmus automatisch eine mittelalterlich anmutende Inselkarte aus rund 4.100 Hexagon-Kacheln erzeugt
• Jede Kachel enthält Geländeinformationen wie Straßen, Flüsse, Küsten, Klippen, Wälder und Dörfer und wird mit Three.js WebGPU und TSL-Shadern in etwa 20 Sekunden generiert
• Um Ausfälle in großen Gittern zu beheben, wird die Karte in 19 hexagonale Untergitter aufgeteilt; mit Backtracking und einem Local-WFC-Reparatursystem wird eine Erfolgsquote von über 86 % erreicht
• Visuell kommen PBR-Materialien, WebGPU-basierte Shader, Wasserreflexionen und Welleneffekte sowie Post-Processing (Beleuchtung, Tiefenschärfe, Grain) zum Einsatz, um mehr räumliche Tiefe zu schaffen
• Mit BatchedMesh-Rendering und gemeinsam genutztem Einzelmaterial werden Tausende Kacheln mit 60fps gerendert und das Potenzial der Verbindung aus prozeduraler Generierung und Echtzeitgrafik gezeigt

---

Überblick über die prozedurale Kartenerzeugung

• Das Projekt ist von der AD&D-Dungeon-Würfelgenerierung inspiriert und erschafft eine Welt, die der Algorithmus selbst zusammenstellt, ohne dass Nutzer sie direkt entwerfen müssen
• Die generierte Karte hat die Form einer mittelalterlichen Insel mit Straßen, Flüssen, Küstenlinien, Klippen, Wäldern und Dörfern und besteht aus rund 4.100 hexagonalen Zellen
• Mit Three.js WebGPU und TSL-Shadern wird die vollständige Karte in etwa 20 Sekunden erstellt

Der Wave-Function-Collapse-(WFC)-Algorithmus

• WFC konstruiert das Gelände auf Basis der Einschränkung, dass die Kanten (edges) benachbarter Kacheln zueinander passen müssen
• Hexagon-Kacheln haben 6 Kanten und damit 50 % mehr Randbedingungen als quadratische Kacheln
• Jede Kachel definiert Kantentypen in 6 Richtungen sowie ein Gewicht; eine Straßenkreuzung in 3 Richtungen hat beispielsweise abwechselnd Straßen- und Graskanten
• Der Algorithmus
  1. initialisiert alle Zellen mit allen möglichen Zuständen
  2. wählt die am stärksten eingeschränkte Zelle und „kollabiert“ sie in einen einzelnen Zustand
  3. entfernt unmögliche Zustände in benachbarten Zellen und propagiert diese Änderungen
  4. wiederholt den Vorgang, bis alle Zellen gelöst sind

Große Gitter und modularer Lösungsansatz

• In kleinen Gittern arbeitet das Verfahren stabil, doch bei mehr als 4.000 Zellen steigt die Ausfallwahrscheinlichkeit stark an
• Zur Lösung wird die Karte in 19 hexagonale Untergitter aufgeteilt, die jeweils unabhängig gelöst werden, während Randkacheln als feste Constraints erhalten bleiben
• Wenn Randbedingungen kollidieren, lässt sich das nicht allein durch Backtracking lösen

Backtracking und Reparatursystem

• Backtracking setzt fehlerhafte Entscheidungen zurück und versucht alternative Kacheln; dies geschieht bis zu 500-mal
• Konflikte zwischen Gittern werden jedoch durch ein separates Reparatursystem behandelt
  • Schritt 1: Unfixing — Konfliktzellen werden wieder in einen variablen Zustand versetzt und umliegende Zellen als neue Constraints gesetzt
  • Schritt 2: Local-WFC — Ein Bereich mit Radius 2 Zellen (19 Zellen) wird neu gelöst, um Grenzkompatibilität sicherzustellen; maximal 5 Versuche
  • Schritt 3: Drop & Hide — Falls das scheitert, wird die betreffende Zelle entfernt und mit einer Gebirgskachel abgedeckt, um das Problem natürlich zu kaschieren
• Mit dieser mehrschichtigen Reparatur wird eine Erfolgsquote von rund 86 % bei der vollständigen Kartenerzeugung erreicht

Dreidimensionale Höhenverarbeitung

• Die Karte besitzt 5 Höhenstufen, wobei Hänge und Klippenkacheln obere und untere Ebenen miteinander verbinden
• Bei fehlerhafter Verbindung können Straßen an Klippen enden oder Flüsse nach oben fließen
• Die Höheninformation wird in Instanzfarben kodiert, sodass Shader Farbpaletten für tiefe und hohe Lagen mischen können

Hexagon-Koordinatensystem

• Wegen der 6 Richtungen ist die Nachbarschaftsberechnung mit einem einfachen 2D-Koordinatensystem bei Hexagonen kompliziert
• Daher wird ein Cube-Koordinatensystem (q, r, s) verwendet, um Nachbarschaftsabfragen zu vereinfachen
• Da sich WFC stärker auf die Graphstruktur des Kanten-Matchings als auf die reale Geometrie konzentriert, dient das Koordinatensystem vor allem dem Rendering und der Platzierung mehrerer Gitter

Platzierung von Bäumen und Gebäuden

• WFC ist stark bei lokalen Mustern, aber ungeeignet für großflächige Verteilungen
• Die Dichte von Bäumen und Gebäuden wird daher über ein Perlin-Rauschfeld bestimmt, um natürliche Cluster von Wäldern und Dörfern zu erzeugen
• Zusätzliche Logik platziert Gebäude an Straßenenden, Häfen und Windmühlen an Küsten sowie Henges auf Hügeln

Umsetzung der Wassereffekte

• Das Meer ist nicht nur eine einfache Fläche, sondern enthält Glitzern und Küstenwellen
• Sparkles werden nicht mit Voronoi-Rauschen, sondern mit einer kleinen scrollenden Textur + Rauschmaske umgesetzt, um die GPU-Last zu senken
• Coast Waves entstehen durch das Weichzeichnen einer Küstenmaske, aus der distanzbasierte sinusförmige Bänder erzeugt werden
• Beim Cove-Problem ist die auf Blur basierende Distanzberechnung ungenau; deshalb prüft die CPU umliegende Zellen und erzeugt eine Bereichsmaske für dünnere Wellen

Kachelerstellung und Ausrichtung

• Als Basismodell wird das KayKit Medieval Hexagon Pack verwendet; fehlende Verbindungskacheln wie schräge Flüsse oder Klippenvarianten wurden jedoch direkt in Blender erstellt
• Alle Kacheln sind auf eine Breite von 2 Einheiten vereinheitlicht; bei UV-Ausrichtungsfehlern werden Nahtlinien sichtbar, weshalb präzises Mapping nötig ist

Visuelle Effekte und Rendering

• Umgesetzt mit Three.js WebGPU + TSL-Shadern, also nodebasierten Shadern statt GLSL
• Post-Processing-Stack
  1. GTAO zur Betonung von Schattenbereichen
  2. Tiefenschärfe (Depth of Field) für einen Miniatureffekt
  3. Vignettierung und Film Grain für eine analoge Textur
• Dynamische Shadow Maps werden in jedem Frame an den Kamerablick angepasst, damit Schatten auch beim Hineinzoomen scharf bleiben

Performance-Optimierung

• Mit BatchedMesh werden Kacheln und Dekorationen jedes Gitters zusammengefasst und mit einem einzigen Draw Call gerendert
• Alle Meshes teilen sich ein einziges Material, um Shader-Zustandswechsel zu minimieren
• Das Ergebnis sind 38 BatchedMeshes, 4.100+ Zellen und Rendering mit 60fps

Wichtige Kennzahlen und Tech-Stack

• 30 Kacheltypen, 19 Gitter, ~4.100 Zellen, 500 Backtracking-Versuche, 5 Local-WFC-Versuche, 20 Sekunden Generierung, 100 % Erfolgsquote (500 Tests)
• Verwendet werden Three.js r183, TSL-Shader, Web Workers, Vite-Build, BatchedMesh und Seeded RNG

Demo und Quellcode

• In der Live-Demo lässt sich die Karte erweitern und vollständig generieren
• Der GitHub-Quellcode ist veröffentlicht; mehr als 50 Parameter erlauben Anpassungen an Beleuchtung, Farben, Wasser und WFC-Einstellungen

Zusammenfassung

• Statt mit Würfeln entsteht hier eine Welt durch einen Algorithmus, in der sich jedes Mal neue Geländeformen sowie Straßen- und Flussverbindungen erkunden lassen
• Ein WebGPU-basiertes Experiment zur Kartenerzeugung, das prozedurale Generierung, Grafikoptimierung und Shader-Technik kombiniert

[GN⁺]

Hacker-News-Kommentare

• Im Artikel heißt es, dass Backtracking einfach auf 500 Schritte begrenzt wurde, aber Constraint Programming ist in Wirklichkeit ein sehr interessantes und komplexes Feld.
  Mit Knuths Algorithm X und Dancing Links ließe sich der im Artikel erwähnte Bereich „Layer 2“ vermutlich mit einer Erfolgsquote von über 86 % lösen.
  Außerdem kann man mit verschiedenen Heuristiken viel schneller suchen als mit einfachem Brute Force. Wer schon einmal einen Sudoku-Solver gebaut hat, weiß gut, wie langsam Brute Force werden kann.

  • Für solche kombinatorischen Optimierungsprobleme auf Basis von Constraints gibt es bereits viele spezialisierte Solver oder High-Level-Modellierungssprachen.
    Zum Beispiel bietet MiniZinc eine High-Level-Modellierungssprache mit Unterstützung für mehrere Solver-Backends.
    Statt den Algorithmus selbst zu schreiben, ist es effizienter, das Problem mit solchen industrietauglichen Solvern zu modellieren und den Solver per zufälliger oder vollständiger Suche eine Lösung finden zu lassen.
    So kann man sich darauf konzentrieren, die Problemdefinition anzupassen, um interessantere Karten zu erzeugen, statt Zeit mit dem Schreiben eines Solvers zu verbringen.

• Auf meinem Laptop (Core i5 der 11. Generation, Iris Xe, aktuelle Chrome-Version) läuft die Demo mit 5 FPS. Offenbar ist die GPU der Flaschenhals.
  Im Artikel stand, dass es auf Mobilgeräten mit 60 FPS läuft, daher hatte ich etwas mehr Effizienz erwartet.
  Die Karte ist wunderschön, aber durch die tilebasierten Constraints von WFC entstehen unnatürliche Ergebnisse. Der Grund ist, dass sich nichtlokale Einflüsse (non-local influence) nur schwer abbilden lassen.
  Für Spiele, in denen man Kachel für Kachel erkundet, ist das in Ordnung, aber für die Generierung ganzer Karten ist es nicht ideal.
  Der noise-basierte Ansatz von Red Blob Games liefert bessere Ergebnisse. Wenn man Flüsse über Feuchtigkeitsverfolgung und Straßen oder Brücken in einem separaten Pass verarbeitet, ist das schneller und robuster.
  Trotzdem ist WFC ein interessantes Programmierproblem, daher hat die Implementierung sicher Spaß gemacht. Insgesamt ein großartiger Artikel und eine beeindruckende Demo.

  • Mich würde interessieren, ob du unter Windows oder Linux läufst oder ob CPU-Rendering verwendet wird.
  • Auf meinem Smartphone funktioniert es gut. Mich würde interessieren, wie die FPS gemessen wurden. Auf der Seite wurde nichts angezeigt; hast du vielleicht in den Chrome Dev Tools nachgesehen?

• Oskar Stålberg hat Wave Function Collapse (WFC) in mehreren Spielen eingesetzt, darunter Townscaper.
  Einen passenden Vortrag gibt es unter SGC21 - Beyond Townscapers.

• Das erinnert mich an Jasper Flicks Unity-Tutorial Hex Terrain.
  Dieses Projekt passt vorbereitete Kacheln anhand von Constraints zusammen, während Jaspers Tutorial Kachelgrenzen dynamisch erzeugt.
  Beide Ansätze sind interessant und machen Spaß zu lesen.

• Ein wirklich tolles Projekt.
  Falls der Autor mitliest: Mich würde interessieren, ob erwogen wurde, den Superpositionszustand einer Kachel (die Menge möglicher Optionen) als Bitfeld darzustellen.
  Als ich früher einmal WFC implementiert habe, brachte die Umstellung auf Bitfelder einen enormen Geschwindigkeitsschub. Es wurde sogar schneller, den ganzen Chunk neu zu berechnen, als Backtracking zu verwenden.

  • Ich habe Ähnliches erlebt. Mein WFC-Bot erzeugt Carcassonne-Karten, und die Verwendung der bitset-Bibliothek hat die Performance deutlich verbessert.
    Er speichert den Zustand in regelmäßigen Abständen auf einem Stack und springt bei einer Sackgasse zum letzten Zustand zurück.
    Wenn ich den Variablennamen tenper sehe, bin ich leicht enttäuscht von meinem früheren Ich.

• Am schwierigsten scheint es zu sein, eine Anordnung zu finden, die die Constraints erfüllt.
  Ich frage mich, ob es als Alternative die Verwendung eines SAT-Solvers gibt. Dann würde man allerdings möglicherweise immer nur „einfache“ Lösungen finden und weniger Zufälligkeit bekommen.
  Manche SAT-Solver können die Anfangswerte von Variablen zufällig setzen, aber das bedeutet noch lange keine zufällige Lösung. Mich würde interessieren, ob das schon einmal jemand ausprobiert hat.

  • SAT-Solver haben zudem eine hohe Rechenkomplexität und sind für Menschen ohne Hintergrund in formalen Methoden (formal methods) schwer zu verstehen.
    WFC dagegen ist ein einfaches Brute-Force-Verfahren, leicht zu implementieren und rechnerisch günstig, solange es nicht zu viele Sackgassen gibt.
    In Spielen reicht statt einer perfekten Lösung oft ein Ergebnis, das „gut genug“ ist, daher kann WFC praktischer sein.

• Ein inspirierendes Projekt. Die Referenzmaterialien sind ebenfalls hervorragend, und der Quellcode ist offen verfügbar.
  Es wäre großartig, hier noch den visuellen Stil von Here Dragons Abound zu kombinieren.

• Der OP weiß das vielleicht schon, aber die Hexagon-Mathematik-Seite von Red Blob Games enthält viele hervorragende Beispiele und Code.

  • Im Artikel wird diese Seite bereits verlinkt.

• Die Erkundung von WFC auf nichtquadratischen (non-square) Grids ist interessant.
  Die Komplexität der Constraint-Propagation dürfte viel höher sein als in den üblichen Beispielen.
  Bei solch komplexen Topologien könnten andere Constraint-Solver wie Constraint Logic Programming bei Ausdrucksstärke und Performance im Vorteil sein.

• Das erinnert mich an Dorfromantik. Steam-Link

  • Das basiert auf dem Brettspiel gleichen Namens. Siehe die BoardGameGeek-Seite.