Wir beschäftigen uns mit dem Wellenfunktionskollapsalgorithmus

Seit dem Aufkommen von DeBroglie und Tessera wurde ich oft gebeten, zu erklären, wie sie funktionieren. Generieren mag wie Magie aussehen, aber die Regeln dahinter sind eigentlich einfach.

Was ist der WFC-Algorithmus (Wave Function Collapse)? Es wurde von Maxim Gumin entwickelt , um "gekachelte" Bilder basierend auf einer einfachen Konfiguration oder Bildbeispielen zu erstellen. Der Algorithmus kann viel: Schauen Sie sich die Beispiele von Maxim und Twitter #wavefunctioncollapse an und sehen Sie sich dieses Video an . Die Vielfalt ist unglaublich.


Maxim in README hat die Arbeit von WFC kurz erläutert, aber es scheint mir, dass dieses Problem von Grund auf eine detailliertere Offenlegung erfordert. Da sich der Algorithmus auf das Programmieren in Einschränkungen bezieht, widmet sich der größte Teil des Artikels der Erläuterung des Konzepts des Programmierens in Einschränkungen, und am Ende kehren wir zu WFC zurück .

Eingeschränkte Programmierung ist eine Möglichkeit, Computer anzuweisen. Im Gegensatz zur imperativen Programmierung, wenn Sie eine Liste expliziter Funktionen angeben, oder der funktionalen Programmierung, wenn Sie mathematische Funktionen angeben, geben Sie dem Computer hier eine strenge Beschreibung des Problems und verwenden die integrierten Algorithmen, um eine Lösung zu finden.

Hinweis:Dieses Handbuch beschreibt verschiedene Konzepte, nicht Methoden und Code. Wenn Sie mehr an der Implementierung interessiert sind, können Sie meine WFC-OpenSource-Bibliothek ( Github , Dokumentation ) verwenden. Obwohl es besser ist, mit der Implementierung von Maxim zu lernen . Wenn Sie Unity verwenden, können Sie Tessera kaufen . Dies ist mein Tool zum Anwenden von WFC in dieser Engine.

Mini Sudoku

Zur Veranschaulichung nahm ich ein Mini- Sudoku . Dies ist ein Puzzle, das wie ein 4 × 4-Raster mit Zahlen in einigen Zellen aussieht.


Ziel ist es, jede leere Zelle gemäß den Regeln mit einer Zahl von 1 bis 4 zu füllen:

• Jede Zahl von 1 bis 4 muss in jeder Zeile in einer einzigen Kopie vorhanden sein.
• Jede Zahl von 1 bis 4 muss in jeder Spalte in einer einzigen Kopie vorhanden sein.
• Jede Zahl von 1 bis 4 muss in einer einzelnen Kopie in jedem 2 × 2-Eckquadrat vorhanden sein.

Nach diesen Regeln lautet die Lösung wie folgt:


Möglicherweise haben Sie dieses Rätsel leicht gelöst. Wir sind jedoch daran interessiert, wie ein Computer dies tun kann. Das Problem kann in zwei Teile unterteilt werden: eine Beschreibung der Bedingungen für den Computer und anschließend eine Lösung mithilfe des Algorithmus.

Beschreibung der Bedingungen

In der Regel wird hierfür eine Programmiersprache mit Einschränkungen verwendet. Es gibt mehrere solcher Sprachen, und ihre Wirkprinzipien sind ähnlich.

Zuerst definieren wir die Variablen . Hier sind sie nicht die gleichen wie bei der herkömmlichen Programmierung. Im Kontext eines Problemlösers ist eine Variable ein unbekannter Wert, der gelöst werden muss, um ein Problem zu lösen. In unserem Sudoku-Beispiel erstellen wir Variablen für alle leeren Zellen. Zur Vereinfachung können Sie auch Variablen für gefüllte Zellen erstellen.

Dann definieren wir für jede Variable eine Domäne : eine Reihe möglicher Werte. In unserem Sudoku ist die Domäne für jede leere Zelle {1, 2, 3, 4}. Und für eine Zelle, in die 1 bereits eingegeben wurde, ist die Domäne {1}.

Schließlich legen wir die Einschränkungen fest: Regeln, die unsere Variablen binden. In den meisten Programmiersprachen gibt es bereits eine Funktion mit Einschränkungen all_distinct(..), die eindeutige Werte übergeben muss. So können Sudoku-Regeln in 12 Einschränkungen übersetzt werden all_distinct- eine für jede Zeile und Spalte sowie für 2 × 2 Eckquadrate. Wir benötigen nur eine Art von Einschränkung, um dieses Problem zu lösen. Problemlöser zur Erfüllung der Einschränkungen werden jedoch normalerweise mit einer großen Bibliothek verschiedener Arten von Einschränkungen geliefert, um Ihr Problem zu beschreiben.

Hinweis : In der Praxis unterstützen Programmiersprachen Arrays in Einschränkungen, sodass es genauere Möglichkeiten gibt, diese Aufgabe zu formulieren. Es gibt viele Artikel im Internet über das Lösen von Sudoku.

Algorithmen zur Lösung von Problemen mit der Einschränkungszufriedenheit

Es gibt verschiedene Lösungstechniken. Aber ich werde die einfachste von ihnen in Betracht ziehen, um Ihnen das Prinzip ihrer Arbeit zu demonstrieren. Domänen für jede Zelle werden hier angezeigt:


Dies sind alles mögliche Werte in variablen Domänen.

Nehmen Sie nun die erste Einschränkung. Es erfordert, dass alle Werte in der oberen Zeile eindeutig sind. In einer Zelle ist der Wert 4 bereits eingeschrieben, daher kann dieser Wert in anderen Zellen der Reihe nicht sein . Wir entfernen es aus den Domänen dieser Zellen.


Wiederholen Sie diesen Vorgang mit allen 12 Einschränkungen. Dies wird als Weitergabe von Einschränkungen bezeichnet , da Informationen durch Einschränkungen von einer Variablen auf eine andere verteilt werden.


Und schauen Sie, wir haben Variablen, in deren Domänen noch ein Wert übrig ist. Dies sollten die richtigen Lösungen für diese Variablen sein.


Es scheint, dass wir noch mehr von der Verteilung der Beschränkungen profitieren können: Die neuen roten Einheiten zeigen an, dass wir mit einer einzelnen Domäne noch mehr Variablen haben werden, und dies wird auch zur Verteilung beitragen. Wiederholen Sie den Vorgang, bis das Rätsel gelöst ist.

Wir erschweren die Aufgabe

Leider können nicht alle logischen Rätsel so schnell gelöst werden. Hier ist ein großes Sudoku, es funktioniert genauso, außer dass wir jetzt 9 verschiedene Werte, 9 Zeilen, 9 Spalten und 9 3 × 3 Quadrate haben.


Wenn wir versuchen, die oben genannte Technik anzuwenden, bleiben wir stecken:


Jetzt sind alle Einschränkungen gleich, aber es gibt immer noch undefinierte Variablen.

Eine Person wird dies entscheiden, aber ein Computeralgorithmus wird dies nicht können. Die Handbücher für Menschen sagen, dass wir jetzt nach immer komplizierteren logischen Schlussfolgerungen suchen müssen. Dafür benötigen wir jedoch keinen Computeralgorithmus, da dies schwierig ist. Wir benötigen jedoch einen universellen Algorithmus, der mit allen Einschränkungen und nicht nur nach Sudoku-Regeln arbeiten kann.

Daher machen Computer das Dümmste: Sie nehmen an . Zuerst zeichnen wir den aktuellen Status des Puzzles auf. Dann wählen wir eine beliebige Variable aus und setzen sie auf einen der möglichen Werte. Angenommen, wir weisen der zentralen Zelle den Wert 1 zu.

Jetzt können wir die Einschränkungen etwas weiter verbreiten. Folgendes habe ich für die mittlere Spalte erhalten:


Die blauen Werte sind die Schlussfolgerungen, die wir nach der Annahme gezogen haben. Wie Sie sehen können, ist etwas passiert. Wir schreiben noch ein paar Variablen auf, schauen uns aber die mittlere obere Zelle an. Es ist leer: In seiner Domäne gibt es keine möglichen Werte, die die Einschränkungen erfüllen (es kann keine 5 geben, da dieser Wert bereits im selben 3 × 3-Quadrat vorhanden ist und alle anderen Zahlen bereits in dieser Spalte enthalten sind).

Wenn wir eine Variable mit einer leeren Domäne erhalten, bedeutet dies, dass wir ihr keinen Wert zuweisen können. Das heißt, das Rätsel kann nicht gelöst werden. Es stellt sich heraus, dass unsere Annahme falsch war .

Angesichts eines solchen Widerspruchs führen wir den Rückgabesuchprozess durch(Rückverfolgung). Zuerst stellen wir den Zustand wieder her, der vor unserer Annahme war. Dann entfernen wir den Wert, den wir als Annahme verwendet haben, aus der Domäne - es kann nicht mehr die richtige Antwort sein.


Es wurde viel Arbeit geleistet, aber sie sind vorwärts gegangen. Selbst nach dem Ausschluss von 1 aus der zentralen Zelle befinden wir uns jedoch immer noch in einem toten Punkt. Es ist Zeit, immer wieder und immer wieder davon auszugehen.

Hier gibt es nicht viele algorithmische Aktionen. Jedes Mal, wenn wir keine Beschränkungen verteilen können, gehen wir davon aus und fahren fort. Und da Sie mehrmals stecken bleiben können, bevor Sie auf einen Widerspruch stoßen, werden Sie mehrere gespeicherte Zustände und Annahmen ansammeln.

Bei jeder Iteration mit einer Rückgabe reduzieren Sie die Domäne um mindestens eine Variable, sodass der Algorithmus trotz zahlreicher Rollbacks die Arbeit schließlich abschließt.

Dieses Thema ist viel umfangreicher als ich beschreibe. In der Praxis können Optimierungen wie die Auswahl von Annahmen, das Verständnis, wann verteilt werden muss und wann komplexere logische Schlussfolgerungen gezogen werden müssen, einen großen Einfluss auf die Programmausführung haben. Und da Probleme mit Einschränkungen in der Regel exponentiell zunehmen, können Sie morgen oder nach 5000 Jahren eine Antwort erhalten.

Wir kehren zum Zusammenbruch der Wellenfunktion zurück

Der Zusammenbruch der Wellenfunktion ist eine schwierige Aufgabe mit einer Einschränkung: Es gibt Tausende von möglichen Lösungen. Wenn wir zufällig Annahmen treffen , erhalten wir anstelle eines Lösers einen Generator . Gleichzeitig wird es weiterhin alle gegebenen Einschränkungen erfüllen, das heißt, es wird viel leichter zu handhaben sein als die meisten anderen Verfahrensgeneratoren.

Die Aufgabe des WFC-Algorithmus besteht darin, Zellen mit Kacheln zu füllen, damit die Bilder auf den Kacheln miteinander kombiniert werden. Innerhalb der oben verwendeten Terminologie ist jede Kachel ein Wert, jede Zelle ist eine Variable und die Regeln für das Platzieren von Kacheln sind Einschränkungen.

Maxim, der Autor von WFC, stellte fest, dass Sie bei einer angemessenen Auswahl an Kacheln und einer geeigneten Randomisierung selten Backtracking verwenden müssen, sodass dieses Verfahren nicht implementiert werden kann. Somit ist das Wesen von WFC wie folgt:

• Für jede Zelle wird ein boolesches Array erstellt, das die Domäne dieser Variablen darstellt. Domänen enthalten einen Datensatz pro Kachel, und alle werden mit einem Wert initialisiert true. Eine Kachel betritt eine Domäne, wenn ihr Wert gleich ist true.
• Gleichzeitig gibt es Zellen, in denen Domänen mehrere Elemente enthalten:
  
  • Auswahl einer Zufallszelle nach der heuristischen Methode der "geringsten Entropie".
  • Wählen Sie eine zufällige Kachel aus der Zelldomäne aus und entfernen Sie alle anderen Kacheln von dort.
  • Das Aktualisieren der Domänen anderer Zellen basierend auf diesen neuen Informationen ist die Ausbreitung der Zellrestriktion. Dies muss wiederholt erfolgen, da Änderungen in den Zellen weitere Konsequenzen haben können.

Hinweis : Meine Bedingungen unterscheiden sich von den Bedingungen von Maxim. Er nennt das Array von Domänen eine Welle, und die Auswahl einer zufälligen Kachel ist eine Beobachtung. Das heißt, es wird eine Analogie zur Quantenmechanik gezogen. Aber der Vergleich ist oberflächlich, deshalb werden wir ihn ignorieren.

Es gibt viele Ergänzungen zu den oben genannten Prinzipien, die dem Algorithmus Anmut und Leistung verleihen. Aber schauen wir uns zuerst die beschriebenen Schritte an.

Beispiel

Angenommen, wir müssen ein 3 x 3-Raster mit vier Arten von Kacheln füllen:


Die Einschränkungen sind: Die Farben benachbarter Kacheln müssen übereinstimmen.

Wie im Sudoku-Beispiel werde ich den Inhalt von Domänen mit monochromen Bildern veranschaulichen. Wenn nur noch ein Element in der Domäne vorhanden ist, vergrößere ich es und zeige es in Farbe.

Erstens können in jeder Zelle Kacheln jeglicher Art lokalisiert werden:


Führen Sie die Haupt-WFC-Schleife aus. Wählen Sie zufällig eine Zelle aus, z. B. oben links. Wählen Sie nun eine Kachel in der Domäne aus und löschen Sie alle anderen.


Verteilen Sie die Einschränkungen. Die einzige Regel gilt für benachbarte Kacheln, daher müssen zwei Zellen aktualisiert werden:


Können wir andere Kacheln angesichts der schrumpfenden Domänen aktualisieren? Ja! Obwohl wir uns bei der Auswahl der ersten Kachel nicht sicher sind, sehen wir, dass die verbleibenden Optionen nach rechts führen. Das heißt, einige Arten von Kacheln können nicht in die obere rechte Ecke gelegt werden. Gleiches gilt für die untere linke Ecke.


Wir können die Einschränkungen nicht mehr verteilen, daher wiederholen wir den Hauptzyklus: Zellauswahl, Kachelauswahl und Verteilung. Diesmal nehmen wir die obere mittlere Zelle:


Ein weiterer Zyklus: Nehmen Sie die linke mittlere Zelle. Nach der Proliferation von Restriktionen für die zentrale Zelle bleibt ein möglicher Wert übrig.


Im Allgemeinen verstehen Sie die Idee. Sie können den Rest der Zellen selbst ausfüllen.

Wenn Sie mit einem komplexeren interaktiven Beispiel experimentieren möchten , empfehle ich dieses .

Kleinste Entropie

Bei der Auswahl der nächsten auszufüllenden Zelle sind einige Optionen vorzuziehen. Wenn Sie zufällig aus einer beliebigen Stelle im Raster auswählen, kann eine Situation auftreten, in der gleichzeitig verschiedene Bereiche des Rasters gefüllt sind. Dies kann zu Problemen führen: Abhängig von den verfügbaren Kacheln können die gefüllten Bereiche nicht verbunden werden. Es ist daher besser, Zellen auszuwählen, bei denen es in Zukunft weniger wahrscheinlich ist, dass sie zu solchen Problemen führen. Mit anderen Worten, Sie müssen Zellen mit der geringsten Anzahl möglicher Werte in der Domäne (jedoch nicht weniger als zwei Werte) verwenden:

1. Höchstwahrscheinlich befinden sie sich neben den bereits gefüllten Zellen.
2. Wenn wir sie für die Zukunft belassen, können Schwierigkeiten auftreten, da die verfügbaren Werte bereits gering sind.

Der kleinste Domänenansatz funktioniert gut, wenn alle Kacheln gleich wahrscheinlich sind. Wenn Sie jedoch aus einer gewichteten Zufallsverteilung auswählen , müssen Sie etwas anderes berücksichtigen. Maxima empfiehlt "minimale Entropie", dh wählen Sie eine Zelle, die minimiert:

$$

$$entropy = — \sum p_{i}log(p_{i})$$

Dies ist eine Zusammenfassung der Kacheln in der Domäne, in der $$$p_{i}$- Wahrscheinlichkeit für diese Kachel.

Effizientes Rechnen

Obwohl ich nicht auf Details eingehen möchte, gibt es zwei Optimierungen, mit denen ich die Geschwindigkeit so stark erhöhen kann, dass sie nicht ignoriert werden können.

Da sich unsere einzige Regel auf benachbarte Kacheln bezieht, können wir nur die Einschränkungen überprüfen, die zu Ergebnissen führen können, die sich von den vorherigen unterscheiden. Das heißt, wenn eine Zelle aktualisiert wird, fügen wir sie der Warteschlange der Zellen hinzu, die auf eine Entscheidung warten. Dann entfernen wir eine Zelle aus der Warteschlange und überprüfen jedes Mal die benachbarten Zellen. Wenn solche Überprüfungen zur Erneuerung anderer Zellen führen, fallen sie ebenfalls in die Warteschlange. Wenn Sie diesen Vorgang wiederholen, bis die Warteschlange leer ist, stellen Sie sicher, dass alle Einschränkungen überprüft werden. Wir überprüfen sie jedoch erst, wenn sich die Domäne mindestens einer Zelle ändert, die diesen Einschränkungen zugeordnet ist.

Um die Adjazenzbeschränkung zu überprüfen, müssen wir außerdem die Frage beantworten: "Welche Kacheln sind angesichts der Kacheln in der Domäne von Zelle A in der Domäne von Zelle B möglich, wenn die Zellen benachbart sind?"

Manchmal wird diese Frage als "Unterstützung" von Zelle A bezeichnet. Für eine bestimmte Kachel "b" in Domäne B ist es einfach, die Zyklen für Kacheln in Domäne A zu berechnen. Wenn A mindestens eine Kachel hat, die neben "b" platziert werden kann, dann "b" immer noch geeignet, zumindest für das betreffende Fliesenpaar. Wenn es in A keine solche Kachel gibt, können Sie die Kachel "b" nicht aus Domäne B ablegen, und wir können sie verwerfen.

Schleifen machen es einfach, dies in Code zu implementieren, arbeiten jedoch extrem langsam. Und wenn wir Informationen in einer zusätzlichen Datenstruktur speichern, können wir die Frage bei Bedarf schnell beantworten. Die neuen Daten sind ein großes Array mit Einträgen für jede Seite jeder Zelle und jeder Kachel. In unserem Beispiel gibt es 9 Zellen mit jeweils 4 Seiten und 4 Arten von Kacheln. Wir brauchen also 9 * 4 * 4 Datensätze. Wir speichern Unterstützungszähler im Array: Für jede Zelle / Kachel / Seite zählen wir die Anzahl der Kacheln in der benachbarten Zellendomäne, die neben der betreffenden Kachel platziert werden können. Wenn der Zähler auf Null fällt, kann dieses Plättchen nicht gelegt werden, da niemand daneben stehen kann.

Algorithmuserweiterungen

Da WFC auf einem allgemeineren Verständnis von eingeschränkten Problemen basiert, gibt es viele Möglichkeiten, den Algorithmus durch Ändern der verwendeten Einschränkungen zu erweitern.

Eine der offensichtlichen Änderungen ist, dass uns niemand zwingt, quadratische Zellen zu verwenden. WFC eignet sich hervorragend für hexagonale Zellen in drei Dimensionen oder noch ungewöhnlicheren Oberflächen .




Sie können zusätzliche Einschränkungen einführen: Korrigieren Sie bestimmte Kacheln oder erstellen Sie „Module“ aus mehreren Zellen.

Die Einführung zusätzlicher Beschränkungen kann aus praktischer Sicht eine sehr wichtige Rolle spielen. Da WFC nur benachbarte Kacheln begrenzt, werden selten große Strukturen erzeugt, die ein hohes Maß an Homogenität bieten und ungewöhnlich aussehen. Dieser Algorithmus funktioniert am besten bei der Auswahl von Kacheln. Um jedoch mit einigen großen Strukturen zu arbeiten, ist es besser, eine andere Technik zu verwenden oder andere Einschränkungen einzuführen.

In einem anderen Artikel habe ich darüber gesprochen, wie Sie mit WFC die besten Ergebnisse erzielen können.

Überlappende WFC

Eine der interessanten Erweiterungen des Algorithmus ist der "überlappende" WFC. In den obigen Beispielen bezog sich die Hauptbeschränkung auf Paare benachbarter Kacheln. Dies reicht aus, um die Verbindung von Linien sicherzustellen und einfache Strukturen wie Höhlen, Räume usw. zu schaffen. Gleichzeitig gehen jedoch viele Informationen verloren. Wenn wir zum Beispiel brauchen, dass rote Kacheln immer neben blauen liegen, aber nie neben ihnen waren, wird es schwierig sein, dies allein in Bezug auf die Nähe auszudrücken.

Maxim schlug das Konzept der Überlappung von WFC vor: Wir ersetzen die Adjazenzbedingung durch eine neue Einschränkung, die mehrere Kacheln gleichzeitig betrifft. Zum Beispiel, so dass am Ausgang jede Gruppe von 3 × 3-Zellen einer 3 × 3-Gruppe aus einer Gitterprobe entspricht. Die in der Probe vorhandenen Muster werden am Ausgang immer wieder in verschiedenen Variationen wiederholt:


Diese Einschränkung ist viel empfindlicher als "einfache" Adjazenzbeschränkungen. Und da es von einer bestimmten Stichprobe abhängt, eignet es sich sehr gut zur Lösung künstlerischer Aufgaben. Bisher bin ich auf nichts so Interessantes gestoßen. Vielleicht liegt der Grund darin, dass ein solcher Algorithmus schwieriger zu implementieren ist oder langsamer arbeitet oder manchmal die ursprüngliche Probe zu gut reproduziert, was dazu führt, dass eine Art von Natürlichkeit und Natürlichkeit verloren geht.

Was weiter?

Das Lösen von Problemen mit Einschränkungen ist ein großes und sich aktiv entwickelndes Gebiet der Informatik, und ich habe es nur angesprochen. WFC ist - genau wie jeder andere Algorithmus zur prozeduralen Generierung zur Lösung eingeschränkter Probleme - noch neu. Ich empfehle, r / procedureuralgeneration , #wavefunctioncollapse , @exutumno und @osksta zu lesen , um sich ein Bild von den jüngsten Anwendungsfällen zu machen.

Sie können auch meinen Artikel über WFC lesen , mit meiner OpenSource-Bibliothek oder dem Unity-Tool experimentieren . Vergessen Sie nicht meine anderen Artikel zur Verfahrensgenerierung .