Effondrement de la fonction d'onde: un algorithme inspiré de la mécanique quantique

L'algorithme de réduction de la fonction d'onde génère des bitmaps qui sont localement similaires au bitmap d'entrée.

Le semblant local signifie que

• (C1) Chaque motif de NxN pixels dans la sortie doit apparaître au moins une fois dans l'entrée.
• (Condition faible C2) La distribution des modèles NxN dans l'entrée doit être similaire à la distribution des modèles NxN dans un nombre significativement élevé d'ensembles de sorties. En d'autres termes, la probabilité qu'un certain motif se rencontre dans la sortie doit être proche de la densité de ces motifs dans l'entrée.

Dans les exemples, la valeur standard de N est 3.


L'algorithme WaveFunctionCollapse (WFC) initialise le bitmap de sortie comme un état complètement inobservable dans lequel la valeur de chaque pixel est une superposition des couleurs du bitmap d'entrée (donc si l'image d'entrée est en noir et blanc, les états non observables sont affichés sous différentes nuances de gris). Les coefficients de ces superpositions sont des nombres réels, pas des nombres imaginaires, donc l'algorithme n'utilise pas de mécanique quantique réelle, il s'en est plutôt inspiré. Ensuite, le programme entre dans le cycle d'observation-propagation:

• À chaque étape d'observation, parmi l'espace non observé, la région NxN avec l'entropie de Shannon la plus faible est sélectionnée. L'état de cette région s'effondre ensuite vers un état de certitude conformément aux coefficients et à la distribution des motifs NxN dans les données d'entrée.
• À chaque étape de la diffusion, les nouvelles informations obtenues lors de l'effondrement de l'étape précédente sont diffusées en fonction des résultats.

À chaque étape, l'entropie totale diminue, et à la fin nous obtenons un état complètement observable, l'effondrement de la fonction d'onde se termine.

Il peut arriver que pendant le processus de propagation tous les coefficients d'un pixel particulier deviennent nuls. Cela signifie que l'algorithme est entré en contradiction et ne peut plus être exécuté. La tâche de déterminer si un bitmap donné fournit d'autres bitmaps non triviaux satisfaisant la condition (C1) est NP-difficile, il est donc impossible de créer une solution rapide qui termine toujours l'algorithme. Cependant, dans la pratique, l'algorithme rencontre rarement des contradictions.

L'algorithme d'effondrement de la fonction d'onde est implémenté en C ++ , Python , Kotlin , Rust , Julia , Haxe , JavaScript et adapté pour Unity . Les fichiers exécutables officiels peuvent être téléchargés depuis itch.io ou exécutés dans un navigateur . WFC génère des niveaux dans Bad North , Caves of Qud , plusieurs petits jeux, ainsi que de nombreux prototypes. Sa création a conduit à une nouvelle étude . Pour d'autres travaux , explications , démos interactives , guides , didacticiels et exemples, consultez la section ports, fourches et spin-offs .

Regardez une démonstration de l'algorithme WFC sur YouTube: https://youtu.be/DOQTr2Xmlz0

Algorithme

1. Lisez le bitmap entrant et comptez le nombre de modèles NxN.
   
   1. (facultatif) Complétez les données de motif avec des motifs tournés et réfléchis.
2. Créez un tableau avec les tailles des données de sortie (appelées «wave» dans la source). Chaque élément de ce tableau indique l'état d'une région de taille NxN dans la sortie. L'état de la région NxN est une superposition de motifs NxN de données d'entrée avec des coefficients booléens (c'est-à-dire que l'état d'un pixel dans la sortie est une superposition de couleurs entrantes avec des coefficients réels). Le coefficient False signifie que le motif correspondant est interdit, le coefficient true signifie que le motif correspondant n'est pas encore interdit.
3. Initialisez l'onde dans un état complètement inobservable, c'est-à-dire où tous les coefficients booléens sont vrais.
4. Répétez les étapes suivantes:
   
   1. Observation:
      
      1. Trouvez l'élément d'onde avec une entropie minimale non nulle. S'il n'y a pas de tels éléments (si tous les éléments ont une entropie nulle ou indéfinie), alors terminez le cycle (4) et passez à l'étape (5).
      2. Réduisez cet élément dans un état de certitude conformément à ses coefficients et à la distribution des motifs NxN des données d'entrée.
   2. Diffusion: diffuser les informations obtenues lors de l'étape d'observation précédente.
5. À ce stade, tous les éléments de l'onde ont un état entièrement observable (tous les coefficients, sauf un, sont égaux à zéro) ou sont dans un état de contradiction (tous les coefficients sont égaux à zéro). Dans le premier cas, retournez la sortie. Dans le second cas, sortez sans rien retourner.

Génération de cartes de tuiles

Le cas non trivial le plus simple de l'algorithme est le modèle NxN = 1x2 (plus précisément, NxM). Si nous le simplifions encore plus, en préservant non pas les probabilités des paires de couleurs, mais les probabilités des couleurs elles-mêmes, nous obtiendrons ce qu'on appelle un «modèle de tuile simple». La phase de propagation dans ce modèle est simplement la propagation d'une dépendance de voisinage. Il est pratique d'initialiser un modèle de tuile simple avec une liste de tuiles et leurs données de voisinage (les données de voisinage peuvent être considérées comme un grand nombre de très petits échantillons), plutôt qu'une image bitmap échantillonnée.

GIF | GIFV

Les listes de toutes les paires possibles de tuiles voisines dans des ensembles de tuiles pratiques peuvent être assez longues, donc pour raccourcir l'énumération, j'ai implémenté un système de symétrie pour les tuiles. Dans ce système, chaque tuile doit être affectée à son type de symétrie.


Notez que les tuiles ont la même symétrie que les lettres qui leur sont attribuées (en d'autres termes, les actions du groupe dièdre D4 sont isométriques pour les tuiles et les lettres correspondantes). Grâce à ce système, il suffit de lister les paires de tuiles voisines uniquement à leur symétrie, raccourcit la liste des voisins pour les sets de tuiles avec de nombreuses tuiles symétriques plusieurs fois (même dans les tuiles du terrain d'été, malgré le fait que les images ne sont pas symétriques, le système considère ces tuiles symétriques).









Notez qu'un ensemble illimité de tuiles à partir de nœuds (dans lequel les 5 tuiles sont valides) n'est pas intéressant pour l'algorithme WFC, car vous ne pouvez pas vous retrouver dans une situation où il est impossible de placer une tuile. Nous appelons les ensembles de tuiles avec cette propriété «simple». Sans heuristique complexe, les ensembles de tuiles simples ne créent pas de structures globales intéressantes, car les corrélations dans les ensembles de tuiles simples à distance diminuent rapidement. De nombreuses tuiles simples peuvent être trouvées sur cr31 . Regardez là le jeu de tuiles «Dual» double face. Comment créer des nœuds (sans connexions en T, c'est-à-dire difficiles), tout en étant simple? La réponse est qu'elle ne peut générer qu'un type étroit de nœuds et ne peut pas créer de nœud arbitraire.

Il convient également de noter que les ensembles de tuiles Circuit, Été et Pièces ne sont pas des tuiles Van. Autrement dit, les données de leur voisinage ne peuvent pas être générées à partir de la coloration des bords. Par exemple, dans le jeu de tuiles Circuit (circuit intégré), deux coins ne peuvent pas être adjacents, bien qu'ils puissent être connectés avec une connexion (Connexion), et les pistes diagonales ne peuvent pas changer de direction.

Dimensions supérieures

L'algorithme WFC dans les dimensions supérieures fonctionne exactement de la même manière que dans les deux dimensions, mais les performances deviennent un problème ici. Ces modèles de voxels ont été générés à N = 2 dans le modèle de tuile avec chevauchement en utilisant des blocs 5x5x5 et 5x5x2 et des heuristiques supplémentaires (hauteurs, densités, courbures ...).


Captures d'écran de dimensions supérieures: 1 , 2 , 3 .

Les modèles Voxel générés à l'aide de WFC et d'autres algorithmes seront dans un référentiel séparé.

Synthèse restreinte

L'algorithme WFC prend en charge les restrictions. Par conséquent, il peut facilement être combiné avec d'autres algorithmes génératifs ou création manuelle.

Voici comment le WFC termine automatiquement un niveau initié par une personne:

GIF | GIFV

L'algorithme ConvChain satisfait la version stricte de la condition (C2): la distribution des limites des modèles NxN dans les données de sortie qu'il crée est exactement la même que la distribution des modèles dans les données d'entrée. Cependant, ConvChain ne satisfait pas (C1): souvent, il crée des artefacts perceptibles. Il est logique de démarrer ConvChain pour obtenir une configuration bien échantillonnée, puis WFC pour corriger les artefacts locaux. Ceci est similaire à une stratégie courante en optimisation: nous exécutons d'abord la méthode Monte Carlo pour trouver le point. proche de l'optimum global, puis effectuez une descente de gradient à partir de ce point pour une plus grande précision.

L'algorithme de synthèse de texture de P.F. Harrison est beaucoup plus rapide que le WFC, mais il a des problèmes avec de longues corrélations (par exemple, cet algorithme est difficile à synthétiser des textures de mur de briques avec des briques correctement construites). C'est dans de tels cas que WFC démontre sa supériorité, et l'algorithme de Harrison prend en charge les limitations. Il est logique de générer d'abord le schéma de mur de briques idéal à l'aide de WFC, puis d'exécuter un algorithme de synthèse de texture limité pour ce schéma.

Commentaires

Pourquoi l'heuristique d'entropie minimale est-elle utilisée? J'ai remarqué que lorsque les gens dessinent quelque chose, ils suivent souvent l'heuristique d'entropie minimale eux-mêmes. C'est pourquoi l'algorithme est si intéressant à regarder.

Le modèle de chevauchement correspond à un modèle simple de la même manière que les chaînes de Markov d'ordre supérieur correspondent aux chaînes de Markov de premier ordre.

Il convient de noter que l'entropie d'un nœud ne peut pas augmenter au stade de la propagation, c'est-à-dire les probabilités n'augmentent pas, mais peuvent être remises à zéro. Lorsque l'étape de propagation ne peut plus réduire l'entropie, nous activons l'étape d'observation. Si l'étape d'observation ne peut pas réduire l'entropie, cela signifie que l'algorithme a terminé son travail.

La phase de propagation dans l'algorithme WFC est très similaire à l'algorithme de propagation de croyance en boucle. En fait, j'ai initialement programmé la propagation des croyances (BP), mais je suis ensuite passé à la propagation avec des contraintes avec une distribution stationnaire fixe, car BP est beaucoup plus lent sans parallélisation massive (dans le CPU) et il n'a pas produit de meilleurs résultats pour mes tâches.

Notez que les échantillons «Simple Knot» et «Trick Knot» n'ont pas 2, mais 3 couleurs.

Une dimension peut être le temps. En particulier, le WFC dimensionnel d affiche le comportement de n'importe quel automate cellulaire dimensionnel (d-1).

Les références

Ce projet s'appuie sur les travaux de Paul Merrell sur la synthèse des modèles, en particulier sur le chapitre sur la synthèse discrète des modèles de sa thèse . Paul répartit les limites du voisinage dans ce que nous avons appelé un modèle de tuile simple, avec une heuristique qui cherche à calculer la propagation dans une petite zone en mouvement.

Mon projet a également été fortement influencé par le chapitre sur la synthèse déclarative des textures de la thèse de Paul F. Harrison . Paul définit les données sur le voisinage des tuiles, marquant leurs limites et utilisant la recherche de retour pour remplir la carte des tuiles.

Assemblage

WFC est une application console qui ne dépend que de la bibliothèque standard. Téléchargez .NET Core pour Windows, Linux ou macOS et exécutez

 dotnet run WaveFunctionCollapse.csproj 

Ou vous pouvez utiliser les instructions de création de communauté pour différentes plates-formes dans le problème correspondant . Casey Marshall a créé une demande d'extraction qui simplifie l'utilisation d'un programme en ligne de commande et inclut un package d'instantanés.

Ports, fourches et spin-offs intéressants

• Emil Ernerfeld a créé un port en C ++ .
• Max Eller a créé la bibliothèque Kotlin (JVM) appelée Kollapse . Joseph Roscopf a créé un port ligne par port sur la version optimisée de Kotlin de l'algorithme 2018. Edwin Jacobs a créé une autre bibliothèque Kotlin .
• Kevin Chapelier a créé un port sur JavaScript .
• Oscar Stalberg a programmé un modèle de tuile en trois dimensions, un modèle de tuile en deux dimensions pour les grilles inégales dans une sphère. Voici les magnifiques jeux de tuiles 3D pour eux: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 .
• Joseph Parker a adapté WFC pour Unity et l'a utilisé pour générer des skateparks dans le jeu Proc Skater 2016 , des plateaux fantastiques dans le jeu Swapland 2017 et des niveaux de plateforme dans le jeu Bug with a Gun 2018.
• Martin O'Leary a appliqué un algorithme de type WFC pour générer de la poésie: 1 , 2 , 3 , 4 .
• Nick Nenov a créé un ensemble de carreaux de voxel en trois dimensions basé sur mon ensemble de carreaux Castle. Nick utilise l'option de sortie de texte du modèle de mosaïque pour recréer des modèles 3D dans Cinema 4D.
• Sean Lefler a implémenté un modèle avec un chevauchement sur Rust .
• rid5x crée une version de WFC sur OCaml .
• J'ai publié un modèle de tuile tridimensionnel simple afin que les gens puissent créer leurs propres ensembles de tuiles 3D sans attendre le référentiel complet d'un algorithme tridimensionnel.
• J'ai créé un modèle interactif du modèle qui se chevauchent. L'exécutable de l'interface graphique peut être téléchargé à partir des pages WFC sur itch.io.
• Brian Buckley a assemblé un pipeline de génération de niveaux pour le jeu Caves of Qud , qui utilise le WFC en plusieurs passes: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 .
• Danny Wine a mis en œuvre un modèle de tuile en trois dimensions .
• Arvi Teikari a programmé un algorithme de synthèse de texture heuristique entropique sur Lua. Headchant l'a porté pour travailler avec LÖVE.
• Isaac Curt a créé un port sur le modèle Python avec chevauchement.
• Oscar Stalberg a créé une version interactive du modèle de tuile qui s'exécute dans le navigateur.
• Matt Ricks a implémenté un modèle de tuile en trois dimensions ( 1 , 2 , 3 , 4 ) et a créé un modèle de tuile en trois dimensions dans lequel l'une des dimensions est le temps ( 1 , 2 , 3 , 4 , 5 ).
• Nick Nenov a créé un guide visuel du système de symétrie des carreaux.
• Isaac Curt et Adam M. Smith ont écrit un article de recherche dans lequel ils formulent le WFC comme un problème ASP, utilisent le résolveur de contraintes générales clingo généralisé pour générer des bitmaps, expérimenter avec des contraintes globales, retracer l'historique du WFC et fournir une description détaillée de l'algorithme.
• Sylvain Lefebvre a créé une implémentation C ++ de la synthèse de modèles tridimensionnels, décrit le processus de réflexion de la création d'un échantillon et a montré un exemple dans lequel les restrictions de voisinage garantissent que la sortie est connectée (vous pouvez la contourner).
• J'ai généralisé le WFC tridimensionnel pour qu'il fonctionne avec le groupe de symétrie du cube et crée un jeu de tuiles générant des scènes dans le style d'Escher .
• Il existe de nombreuses façons de visualiser des états d'ondes partiellement observables. Dans le code, les valeurs de couleur des options possibles sont moyennées pour obtenir la couleur finale. Oscar Stalberg montre des états partiellement observables sous forme de rectangles translucides: plus il y a d'options, plus le rectangle est grand. Dans un schéma de voxels, je visualise les états des vagues par vote pixel par pixel.
• Remy Devo a implémenté le modèle de tuile dans PICO-8 et a écrit un article sur la génération de données cohérentes avec une explication de WFC.
• Pour son jeu Bad North, Oscar Stalberg utilise une heuristique qui essaie de sélectionner de telles tuiles afin qu'à chaque étape la zone observée résultante soit passable.
• William Manning a implémenté un modèle qui se chevauchent en C #; Tout d'abord, il a cherché à rendre le code lisible et a complété WPF avec une interface graphique.
• Joseph Parker a écrit un tutoriel WFC pour Procjam 2017.
• Aman Tiwari a formulé la contrainte de connexion comme une tâche ASP pour clingo.
• MatveyK a programmé un modèle tridimensionnel avec chevauchement .
• Silvan Lefebvre , Lee Yu Wei et Connelly Barnes explorent la possibilité de cacher des informations dans les textures. Ils ont créé un outil qui peut coder les messages texte sous forme de vignettes WFC et les décoder à nouveau. Cette technique permet d'utiliser des tuiles WFC comme codes QR.
• Mathieu Fer et Nathaniel Kuran ont considérablement amélioré le temps d'exécution du WFC, pour un modèle qui se chevauchent d'un ordre de grandeur. J'ai intégré leurs améliorations dans le code.
• Vasu Mahesh a porté le modèle de tuile 3D sur TypeScript, a créé un nouveau jeu de tuiles et a visualisé le processus de génération dans WebGL.
• Kim Huanghee a expérimenté le WFC en trois dimensions et créé / adapté de nombreux ensembles de carreaux de voxel: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 .
• Oscar Stalberg a fait une présentation sur la génération de niveaux à Bad North lors de la conférence Everything Procedural Conference 2018.
• J'ai écrit sur la façon de générer (approximativement) des chemins non déformés entre deux points en utilisant WFC et d'autres algorithmes.
• Aiser Curt et Adam M. Smith ont publié une préimpression décrivant le système basé sur WFC, qui apprend à partir d'exemples positifs et négatifs, et en a parlé dans le contexte général des dialogues avec des générateurs d'échantillons.
• Brandan Anthony utilise WFC pour générer des décorations murales dans Rodina .
• Tim Kong a implémenté un modèle se chevauchant sur Haxe .
• Boris le Brave a appliqué la méthode de ciselage au WFC pour générer des structures connectées. Il a publié une bibliothèque prenant en charge les maillages hexagonaux, les restrictions supplémentaires et les retours en arrière.
• Marian Kleineberg a créé pour Procjam 2018 un générateur de ville basé sur le modèle de tuile. Il a écrit un article décrivant ses approches pour définir le quartier, revenir en arrière et les variations en ligne du WFC.
• Sol Bekic a programmé un modèle de tuile basé sur GPU en utilisant PyOpenCL. Au lieu de stocker une file d'attente de nœuds à partir de laquelle la distribution est effectuée, ce modèle effectue simultanément la distribution à partir de chaque nœud de grille.
• Wouter van Oortmerssen a implémenté le modèle de tuile dans une seule fonction C ++ avec une structure pour accélérer l'observation, semblable à une file d'attente prioritaire.
• Robert Hoenig a implémenté un modèle avec chevauchement sur Julia avec l'option de distribuer les restrictions uniquement localement.
• Edwin Jacobs a appliqué le WFC au transfert de style et au tramage .

Remerciements

Quelques exemples sont tirés des jeux Ultima IV et Dungeon Crawl . Cercles de tuiles tirés de Mario Klingemann . L'idée de générer des circuits intégrés a été proposée par Moonasaur , et leur style a été emprunté au jeu Ruckingenur II de Zachtronics. L'exemple de chevauchement Cat est tiré de la vidéo Nyan Cat, l'exemple Qud a été créé par Brian Buckley , les exemples Magic Office + Spirals sont rid5x, les exemples de superpositions Colored City + Link + Link 2 + Mazelike + Red Dot + Smile City sont Arvi Teikari. Le Tileset Summer a été créé par Hermann Hillmann. Les modèles Voxel sont rendus dans MagicaVoxel .