Geekly articles weekly

Wellenfunktionskollaps: Ein von der Quantenmechanik inspirierter Algorithmus

Bild

Der Wave Function Collapse-Algorithmus generiert Bitmaps, die der Eingabe-Bitmap lokal ähnlich sind.

Lokaler Schein bedeutet das

  • (C1) Jedes Muster von NxN-Pixeln in der Ausgabe sollte mindestens einmal in der Eingabe auftreten.
  • (Schwache Bedingung C2) Die Verteilung der NxN-Muster in der Eingabe sollte der Verteilung der NxN-Muster in einer signifikant großen Anzahl von Ausgabesätzen ähnlich sein. Mit anderen Worten, die Wahrscheinlichkeit, dass sich ein bestimmtes Muster in der Ausgabe trifft, sollte nahe an der Dichte solcher Muster in der Eingabe liegen.





In den Beispielen beträgt der Standardwert von N 3.


Der WaveFunctionCollapse (WFC) -Algorithmus initialisiert die Ausgabebitmap als einen vollständig nicht beobachtbaren Zustand, in dem der Wert jedes Pixels eine Überlagerung der Farben der Eingabebitmap ist (wenn das Eingabebild also Schwarzweiß ist, werden die nicht beobachtbaren Zustände als unterschiedliche Graustufen angezeigt). Die Koeffizienten dieser Überlagerungen sind reelle, keine imaginären Zahlen, daher verwendet der Algorithmus keine reale Quantenmechanik, sondern wurde von ihr inspiriert. Dann geht das Programm in den Beobachtungs-Ausbreitungszyklus:

  • In jedem Beobachtungsstadium wird unter dem nicht beobachteten Raum die NxN-Region mit der niedrigsten Shannon-Entropie ausgewählt. Der Zustand dieses Bereichs kollabiert dann in Übereinstimmung mit den Koeffizienten und der Verteilung der NxN-Muster in den Eingabedaten zu einem Zustand der Sicherheit.
  • In jeder Verteilungsstufe werden neue Informationen, die während des Zusammenbruchs der vorherigen Stufe erhalten wurden, entsprechend der Ausgabe verbreitet.

In jedem Stadium nimmt die Gesamtentropie ab, und am Ende erhalten wir einen vollständig beobachtbaren Zustand, der Zusammenbruch der Wellenfunktion endet.

Es kann vorkommen, dass während des Ausbreitungsprozesses alle Koeffizienten für ein bestimmtes Pixel gleich Null werden. Dies bedeutet, dass der Algorithmus zu einem Widerspruch gekommen ist und nicht weiter ausgeführt werden kann. Die Aufgabe zu bestimmen, ob eine gegebene Bitmap andere nichttriviale Bitmaps liefert, die die Bedingung (C1) erfüllen, ist NP-schwer, so dass es unmöglich ist, eine schnelle Lösung zu erstellen, die den Algorithmus immer vervollständigt. In der Praxis stößt der Algorithmus jedoch überraschend selten auf Widersprüche.

Der Wellenfunktionskollapsalgorithmus ist in C ++ , Python , Kotlin , Rust , Julia , Haxe , JavaScript implementiert und für Unity angepasst. Offizielle ausführbare Dateien können von itch.io heruntergeladen oder in einem Browser ausgeführt werden . WFC generiert Levels in Bad North , Caves of Qud , mehreren kleineren Spielen sowie vielen Prototypen. Seine Schaffung führte zu einer neuen Studie . Weitere verwandte Arbeiten , Erklärungen , interaktive Demos , Anleitungen , Tutorials und Beispiele finden Sie im Abschnitt Ports, Gabeln und Ausgründungen .

Sehen Sie sich eine Demonstration des WFC-Algorithmus auf YouTube an: https://youtu.be/DOQTr2Xmlz0

Algorithmus


  1. Lesen Sie die eingehende Bitmap und zählen Sie die Anzahl der NxN-Muster.
    1. (optional) Ergänzen Sie die Musterdaten mit gedrehten und reflektierten Mustern.
  2. Erstellen Sie ein Array mit den Größen der Ausgabedaten (in der Quelle als „Welle“ bezeichnet). Jedes Element dieses Arrays gibt den Zustand eines Bereichs der Größe NxN in der Ausgabe an. Der Zustand des NxN-Bereichs ist eine Überlagerung von NxN-Mustern von Eingabedaten mit Booleschen Koeffizienten (dh der Zustand eines Pixels in der Ausgabe ist eine Überlagerung eingehender Farben mit reellen Koeffizienten). Der Koeffizient False bedeutet, dass das entsprechende Muster verboten ist, der Koeffizient true bedeutet, dass das entsprechende Muster noch nicht verboten ist.
  3. Initialisieren Sie die Welle in einem völlig unbeobachtbaren Zustand, dh in dem alle Booleschen Koeffizienten wahr sind.
  4. Wiederholen Sie die folgenden Schritte:
    1. Beobachtung:
      1. Finden Sie das Wellenelement mit minimaler Entropie ungleich Null. Wenn es keine solchen Elemente gibt (wenn alle Elemente eine Entropie von Null oder unbestimmt haben), schließen Sie den Zyklus (4) ab und fahren Sie mit Schritt (5) fort.
      2. Reduzieren Sie dieses Element gemäß seinen Koeffizienten und der Verteilung der NxN-Muster der Eingabedaten in einen sicheren Zustand.
    2. Verbreitung: Verbreitung der im vorherigen Beobachtungsschritt erhaltenen Informationen.
  5. Zu diesem Zeitpunkt haben alle Elemente der Welle entweder einen vollständig beobachtbaren Zustand (alle Koeffizienten außer einem sind gleich Null) oder befinden sich in einem widersprüchlichen Zustand (alle Koeffizienten sind gleich Null). Geben Sie im ersten Fall die Ausgabe zurück. Im zweiten Fall beenden Sie das Programm, ohne etwas zurückzugeben.

Kachelkartengenerierung


Der einfachste nicht triviale Fall des Algorithmus ist das Muster NxN = 1x2 (genauer NxM). Wenn wir es noch weiter vereinfachen und dabei nicht die Wahrscheinlichkeiten von Farbpaaren, sondern die Wahrscheinlichkeiten der Farben selbst beibehalten, erhalten wir ein sogenanntes „einfaches Kachelmodell“. Die Ausbreitungsphase in diesem Modell ist einfach die Ausbreitung einer Nachbarschaftsabhängigkeit. Es ist zweckmäßig, ein einfaches Kachelmodell mit einer Liste von Kacheln und ihren Nachbarschaftsdaten (Nachbarschaftsdaten können als eine große Anzahl sehr kleiner Stichproben betrachtet werden) anstelle einer abgetasteten Bitmap zu initialisieren.

GIF | GIFV

Die Listen aller möglichen Paare benachbarter Kacheln in praktischen Kachelsätzen können sehr lang sein. Um die Aufzählung zu verkürzen, habe ich ein Symmetriesystem für Kacheln implementiert. In diesem System muss jeder Kachel ihre Symmetrietyp zugewiesen werden.


Beachten Sie, dass Kacheln dieselbe Symmetrie haben wie die ihnen zugewiesenen Buchstaben (mit anderen Worten, die Aktionen der Diedergruppe D4 sind für die Kacheln und die entsprechenden Buchstaben isometrisch). Dank dieses Systems reicht es aus, die Paare benachbarter Kacheln nur nach ihrer Symmetrie aufzulisten und die Liste der Nachbarn für Kachelsätze mit vielen symmetrischen Kacheln mehrmals zu verkürzen (selbst in den Kacheln des Sommerreliefs betrachtet das System solche Kacheln als symmetrisch, obwohl die Bilder nicht symmetrisch sind).









Beachten Sie, dass ein unbegrenzter Kachelsatz von Knoten (in dem alle 5 Kacheln gültig sind) für den WFC-Algorithmus nicht interessant ist, da Sie nicht in eine Situation geraten können, in der es unmöglich ist, eine Kachel zu platzieren. Wir nennen Kachelsätze mit dieser Eigenschaft "einfach". Ohne komplexe Heuristiken erzeugen einfache Kachelsätze keine interessanten globalen Strukturen, da die Korrelationen in einfachen Kachelsätzen aus der Ferne schnell abnehmen. Viele einfache Kacheln finden Sie auf cr31 . Schauen Sie sich dort das doppelseitige „Dual“ -Kachelset an. Wie kann er Knoten erstellen (ohne T-förmige Verbindungen, das heißt schwierig) und gleichzeitig einfach sein? Die Antwort ist, dass es nur einen schmalen Knotentyp und keinen beliebigen Knoten erzeugen kann.

Es ist auch erwähnenswert, dass Circuit-, Summer- und Rooms-Kachelsätze keine Van-Kacheln sind. Das heißt, die Daten ihrer Nachbarschaft können nicht aus der Färbung der Kanten erzeugt werden. Beispielsweise können im Schaltungskachelsatz (integrierte Schaltung) zwei Ecken nicht benachbart sein, obwohl sie mit einer Verbindung verbunden werden können (Verbindung), und diagonale Spuren können die Richtung nicht ändern.

Höhere Dimensionen


Der WFC-Algorithmus in höheren Dimensionen funktioniert genauso wie in zwei Dimensionen, aber die Leistung wird hier zum Problem. Diese Voxelmodelle wurden bei N = 2 im Kachelmodell mit Überlappung unter Verwendung von 5x5x5- und 5x5x2-Blöcken und zusätzlichen Heuristiken (Höhen, Dichten, Krümmungen ...) erzeugt.


Screenshots höherer Dimensionen: 1 , 2 , 3 .

Mit WFC und anderen Algorithmen generierte Voxel-Modelle befinden sich in einem separaten Repository.

Eingeschränkte Synthese


Der WFC-Algorithmus unterstützt Einschränkungen. Daher kann es leicht mit anderen generativen Algorithmen oder der manuellen Erstellung kombiniert werden.

So schließt der WFC automatisch eine von einer Person initiierte Ebene ab:

GIF | GIFV

Der ConvChain- Algorithmus erfüllt die strenge Version der Bedingung (C2): Die Verteilung der Grenzen der NxN-Muster in den von ihm erstellten Ausgabedaten entspricht genau der Verteilung der Muster in den Eingabedaten. ConvChain erfüllt jedoch nicht (C1): Oft entstehen auffällige Artefakte. Es ist logisch, zuerst ConvChain zu starten, um eine gut abgetastete Konfiguration zu erhalten, und dann WFC, um lokale Artefakte zu korrigieren. Dies ähnelt einer in der Optimierung üblichen Strategie: Zuerst führen wir die Monte-Carlo-Methode aus, um den Punkt zu finden. nahe am globalen Optimum und führen Sie dann einen Gradientenabstieg von diesem Punkt aus durch, um eine höhere Genauigkeit zu erzielen.

Der Textur-Synthesealgorithmus von P. F. Harrison ist viel schneller als WFC, hat jedoch Probleme mit langen Korrelationen (zum Beispiel ist dieser Algorithmus schwierig, Ziegelmauertexturen mit korrekt gebauten Ziegeln zu synthetisieren). In solchen Fällen demonstriert WFC seine Überlegenheit, und Harrisons Algorithmus unterstützt Einschränkungen. Es ist sinnvoll, zuerst das ideale Backsteinmauerschema mit WFC zu generieren und dann einen begrenzten Textur-Synthesealgorithmus für dieses Schema durchzuführen.

Kommentare


Warum wird die Heuristik der minimalen Entropie verwendet? Mir ist aufgefallen, dass Menschen, die etwas zeichnen, oft selbst der Heuristik der minimalen Entropie folgen. Deshalb ist der Algorithmus so interessant anzusehen.

Das überlappende Modell entspricht einem einfachen Modell auf die gleiche Weise, wie Markov-Ketten höherer Ordnung Markov-Ketten erster Ordnung entsprechen.

Es sollte beachtet werden, dass die Entropie eines Knotens in der Ausbreitungsstufe nicht zunehmen kann, d.h. Die Wahrscheinlichkeiten erhöhen sich nicht, können aber auf Null zurückgesetzt werden. Wenn die Ausbreitungsstufe die Entropie nicht weiter reduzieren kann, aktivieren wir die Beobachtungsstufe. Wenn die Beobachtungsstufe die Entropie nicht reduzieren kann, bedeutet dies, dass der Algorithmus die Arbeit beendet hat.

Die Ausbreitungsphase im WFC-Algorithmus ist dem Schleifen-Glaubensausbreitungsalgorithmus sehr ähnlich. Eigentlich habe ich ursprünglich die Glaubensausbreitung (BP) programmiert, dann aber auf die Weitergabe mit Einschränkungen mit einer festen stationären Verteilung umgestellt, da BP ohne massive Parallelisierung (in der CPU) viel langsamer ist und für meine Aufgaben keine wesentlich besseren Ergebnisse liefert.

Beachten Sie, dass die Beispiele „Simple Knot“ und „Trick Knot“ nicht zwei, sondern drei Farben haben.

Eine Dimension kann Zeit sein. Insbesondere zeigt die d-dimensionale WFC das Verhalten eines beliebigen (d-1) -dimensionalen zellularen Automaten.

Referenzen


Dieses Projekt basiert auf der Arbeit von Paul Merrell zur Synthese von Modellen, insbesondere auf dem Kapitel über die diskrete Synthese von Modellen aus seiner Dissertation . Paul verbreitet die Grenzen der Nachbarschaft in einem sogenannten einfachen Kachelmodell mit einer Heuristik, die versucht, die Ausbreitung in einem kleinen Bewegungsbereich zu berechnen.

Mein Projekt wurde auch stark vom Kapitel über die deklarative Synthese von Texturen aus Paul F. Harrisons Dissertation beeinflusst . Paul legt die Daten für die Nachbarschaft von Kacheln fest, markiert deren Grenzen und verwendet die Rückgabesuche, um die Kachelkarte zu füllen.

Montage


WFC ist eine Konsolenanwendung, die nur von der Standardbibliothek abhängt. Laden Sie .NET Core für Windows, Linux oder macOS herunter und führen Sie es aus

 dotnet run WaveFunctionCollapse.csproj

Sie können auch Anweisungen zum Aufbau einer Community für verschiedene Plattformen in der entsprechenden Ausgabe verwenden . Casey Marshall hat eine Pull-Anforderung erstellt , die die Verwendung eines Befehlszeilenprogramms vereinfacht und ein Snap-Paket enthält.

Interessante Häfen, Gabeln und Ausgründungen



Danksagung


Einige Beispiele stammen aus Ultima IV- und Dungeon Crawl- Spielen. Tileset Circles von Mario Klingemann . Die Idee, integrierte Schaltkreise zu erzeugen, wurde von Moonasaur vorgeschlagen, und ihr Stil wurde dem Spiel Ruckingenur II von Zachtronics entnommen. Das Cat-Überlappungsbeispiel stammt aus dem Nyan Cat-Video, das Qud-Beispiel wurde von Brian Buckley erstellt , die Magic Office + Spirals-Beispiele sind rid5x, die Colored City + Link + Link 2 + Mazelike + Red Dot + Smile City-Overlays sind Arvi Teikari. Der Tileset Summer wurde von Hermann Hillmann kreiert. Voxel-Modelle werden in MagicaVoxel gerendert.


Source: https://habr.com/ru/post/de437604/

More articles:


All Articles