Wave Function Collapse: PCG mit Constraints

Constraint-basierte Verfahren zur "Procedural Content Generation" (PCG) erfreuen sich spätestens seit dem Aufkommen der Methode "Wave Function Collapse" (WFC) großer Beliebtheit bei den Computerspiel-Programmierern. In diesem Video wird die dahinter stehende Methode anhand von Beispielen erläutert. Dabei wird vor allem auf den Algorithmus "Arc Consistency 3" (AC-3) eingegangen; die grundlegenden Ideen des weiter optimierten Algorithmus AC-4 finden ebenfalls Erwähnung.
0:00 Einleitung
2:54 Constraint-Based Synthesis
5:14 Maps generieren mit WFC
7:41 Beispiel-orientierte Synthese mit WFC
14:42 Model Synthesis
17:35 Definitionen
21:25 das Constraint Satisfaction Problem...
22:30 ...ist NP-schwer
26:03 Suchraum einschränken
27:53 Arc Consistency
32:07 Beispiel für Arc Consistency
38:24 Algorithmus ConstraintSatisfaction
40:09 Minimum Entropy
40:46 Algorithmus AC-3
45:15 Laufzeit AC-3
48:17 Algorithmus AC-4
50:58 Laufzeit ConstraintSatisfaction
52:20 Beispiel für Konflikte
55:09 Lösungsansätze bei Konflikten