Der Wave Function Collape Algorithmus (kurz WFC) wurde 2016 auf GitHub von Maxim Gumin veröffentlicht. Der Algorithmus wurde analog zum gleichnamigen Ereignis in der Quantenmechanik entwickelt und dient zur Lösung von Constraint Satisfaction Problemen. In der ursprünglichen Implementierung von Gumin diente er zur Generierung von Bildern mit Vorgabe eines Tilesets, welche alle möglichen Anordnungen der Kacheln beinhaltet. Der WFC Algorithmus hat nach seiner Veröffentlichung durch seine menschenähnliche Ergebnisse schnell großen Einfluss auf die Indie Entwicklerszene gewonnen und wird seitdem verstärkt im Feld der Procedural Content Generation (PCG) eingesetzt und weiterentwickelt. Er wurde zum beispiel in spielen wie Proc Skater 2016 und Caves of Quad verwendet.
Im folgenden Kapitel wird der Ablauf des WFC Algorithmus in der ursprünglichen Fassung von Maxim Gumin beschrieben nach Karth und Smith [1]. Der Algortihmus benötigt zum Start ein Sample Image, welches alle möglichen Kachelanordnungen besitzt. Hierbei ist das Sample Image periodisch gekachelt und die Ränder umschließen sich. Des weiteren muss angegeben werden, welche Dimensionen das Ergebnis haben soll. Am Ende solle jede Zelle des Ergebnisses mit einer Kachel besetzt sein, sodass nur Anordnungen wie im Sample Image vorkommen.
function Run():
PatternsFromSample()
BuildPropagator()
Loop until finished:
Observe()
Propagate()
OutputObservations()
Der WFC Algorithmus extrahiert zuerst aus einem Sample Image legitime Patterns der Kacheln, die anschließend in der Funktion Build Propagator in eine Index Struktur mit aus dem Sample Image hergeleiteten erlaubten Verknüpfungen geladen werden, welcher später die Kacheln richtig befüllen soll.
Der Mainloop besteht nun aus zwei Schritten. Zuerst wird im Observe-Schritt eine noch nicht gefüllte Zelle betrachtet und ihr zufällig eine für diese Zelle zulässige Kachel zugeordnet. Anschließend werden im Propagate-Schritt die zulässigen Kacheln der Nachbarnzellen aktualisiert.
function Observe():
FindLowestEntropy()
If there is a contradiction, throw an error and quit
If all cells are at entropy 0, processing is complete:
Return CollapsedObservations()
//Else
Choose a pattern by a random sample, weighted by the
pattern frequency in the source data
Set the boolean array in this cell to false, except for the chosen pattern
In der Observe Funktion wird zuerst die Zelle mit der geringsten Entropy nach Gumins Entropy Heuristik großer Null bestimmt. Wenn eine Zelle mit keinem Pattern befüllt werden kann, ist das ein Widerspruch und der Algorithmus terminiert und muss gegebenenfalls erneut gestartet werden. Deshalb ist wichtig frühzeitig Zellen zu besetzen, welche, wenige Werte haben, um sehr unwahrscheinliche Zellanordnungen zu vermeiden. Wenn alle Zellen eine Entropy von 0 haben, wird der Mainloop beendet und das Bild ist voll ausgefüllt.
Nun wird für die ausgewählte Zelle zufällig ein passendes Pattern gewählt und gesetzt. Und alle anderen Pattern für diese Zelle als nicht mehr möglich gekennzeichnet.
function Propagate():
Loop until no more cells are left to be updated:
For each neighboring cell:
For each pattern that is still potentially valid:
Compare this location in the pattern with the cell's values
If this point in the pattern no longer matches:
Set the array in the wave to false for this pattern
Flag this cell as needing to be updated in the next iteration
Nachdem eine Zelle gesetzt wurde, wird die neu gewonnene Information mit den benachbarten Zellen verglichen. Wenn ein Pattern im Nachbarn nicht mehr angewandt werden kann, wird das Pattern als nicht mehr möglich für die Zelle gekennzeichnet und, wenn dadurch ein Wert nicht mehr möglich wird, wir diese Zelle markiert, dass sie ein Update benötigt. Anschließend werden die nächsten Nachbarn durchsucht und so die Domains der Zellen Wellenförmig ausgebreitet.
Entropy entspricht, wie bei der physikalischen Wellenfunktion, der Wahrscheinlichkeitsverteilung der möglichen Pattern. Die Entropy berechnet sich aus der Summe der Wahrscheinlichkeiten, dass ein Pattern und somit eine Kachel in die Zelle gesetzt wird.
Wobei die Summe der Wahrscheinlichkeiten von allen Pattern ist, in denen Kachel i in die Zelle gesetzt wird.
Eine Zelle mit geringer Entropy ist eine Zelle mit einer geringen Anzahl an Pattern. Eine Zelle mit nur einem möglichen Pattern hat eine Entropy von Null.
Ein großer Nachteil der Implementierung von Maxim Gumin ist, dass sobald eine Zelle nicht mehr gefüllt werden kann, der Algorithmus terminiert und von vorne gestartet werden muss. Dies dann relevant, wenn es durch kleine Tilesets oder zusätzliche Constraints nur wenige mögliche Konfigurationen der Kacheln gibt. Das Backtracking wird so implementiert, dass der Suchbaum gespeichert wird und bei Contradictions zur letzten gültigen Iteration zurückgesprungen wird, um alternative Lösungen zu evaluieren.[2]
Für spielespezifische Anwendungen zum Beispiel 3D Raster kann es sinnvoll sein den Algorithmus auf Graphen zu erweitern. Da es bei Graphen nicht möglich ist auf eine Richtungen zu schließen, ist es nötig die Eingabestrukturen anzupassen. So muss für jede Kachel angegeben werden, welche Nachbarn ausgewählt werden können.
Durch die erhöhte Anzahl an Verbindungen zwischen einzelnen Zellen/Knoten und die daraus folgenden Constraints ist es wahrscheinlicher, dass es zu einer Contradiction kommen kann. Um dies zu verhindern ist es meist notwendig Beácktracking zu implementieren.
Durch die Erweiterung auf Graphen kann der Algorithmus für alle Constraint Satisfaction Problems verwendet werden, wie zum Beispiel Sudoku oder das 4-Coloring Problem angewendet werden. [2]
Ein weiteres Problem des WFC Algorithmus ist es, dass mit ihm nur locale Restraints betrachtet werden können. Am Beispiel einer Karte die mit Wasser, Erde und Bergen generiert werden soll, kann dies dann problematisch werden, wenn eine Mindest- oder Maximalanzahl eines Elemente generiert werden soll.
Der Lösungsansatz dafür ist es, im Vorfeld die Elemente mit einem anderen Algorithmus zu setzen und anschließend im WFC Algorithmus diese als fest zu betrachten. [3]
Der WFC Algorithmus ist ein viel verwendeter und ständig weiterentwickelt und angepasster, aber noch recht neuer Algorithmus. Es wurde schnell gezeigt, dass dieser viel Potential für Indie Entwickler bietet aber auch in anderen Gebieten Anwendung finden kann. Es gibt derzeit nur wenige Studien, die die Qualität der generierten Ergebnisse bewerten. Nur die Popularität des Algorithmus zeigen, dass die einfache Implementierung und die schnellen Ergebnisse für viele Entwickler ein grund ist, sich für WFC zu entscheiden.
Zu zeigen bleibt allerdings noch ausführlicher, ob der mit dem WFC generierte Content wirklich kaum vom menschengenierten Content unterschieden werden kann. Zudem scheint die Wahl auf die Gumin Heuristik recht willkürlich.
Es muss ermittelt werden, wie effizient und sinnvoll diese Wahl ist.
[1] I. Karth und A. M. Smith, „WaveFunctionCollapse is constraint solving in the wild“, in Proceedings of the 12th International Conference on the Foundations of Digital Games, in FDG ’17. New York, NY, USA: Association for Computing Machinery, Aug. 2017, S. 1–10. doi: 10.1145/3102071.3110566.
[2] D. Cheng, H. Han, und G. Fei, „Automatic Generation of Game Levels Based on Controllable Wave Function Collapse Algorithm“, in Entertainment Computing – ICEC 2020, N. J. Nunes, L. Ma, M. Wang, N. Correia, und Z. Pan, Hrsg., Cham: Springer International Publishing, 2020, S. 37–50. doi: 10.1007/978-3-030-65736-9_3.
[3] H. Kim, S. Lee, H. Lee, T. Hahn, und S. Kang, „Automatic Generation of Game Content using a Graph-based Wave Function Collapse Algorithm“, in 2019 IEEE Conference on Games (CoG), Aug. 2019, S. 1–4. doi: 10.1109/CIG.2019.8848019.