Nous traitons de l'algorithme d'effondrement de la fonction d'onde

Depuis l'avènement de DeBroglie et Tessera, on m'a demandé à plusieurs reprises d'expliquer leur fonctionnement. La génération peut sembler magique, mais les règles qui la sous-tendent sont en fait simples.

Qu'est-ce que l'algorithme WFC (Wave Function Collapse)? Il a été développé par Maxim Gumin pour créer des images «en mosaïque» basées sur une configuration simple ou des échantillons d'images. L'algorithme peut faire beaucoup: regardez les exemples fournis par Maxim et Twitter #wavefunctioncollapse , regardez cette vidéo . La variété est incroyable.


Maxim dans README a brièvement expliqué le travail de WFC, mais il me semble que ce problème nécessite une divulgation plus détaillée, à partir des bases. Puisque l'algorithme est lié à la programmation dans les contraintes , la plupart de l'article est consacré à expliquer le concept de programmation dans les contraintes, et à la fin nous reviendrons sur WFC .

La programmation restreinte est un moyen d'instruire les ordinateurs. Contrairement à la programmation impérative, lorsque vous spécifiez une liste de fonctions explicites, ou la programmation fonctionnelle, lorsque vous spécifiez des fonctions mathématiques, vous fournissez ici à l'ordinateur une description stricte du problème, et il utilise les algorithmes intégrés pour trouver une solution.

Remarque:Ce guide décrit divers concepts, pas les méthodes et le code. Si vous êtes plus intéressé par l'implémentation, vous pouvez utiliser ma bibliothèque open source WFC ( github , documentation ). Bien qu'il soit préférable de commencer l'étude avec la mise en œuvre de Maxim . Si vous utilisez Unity, vous pouvez acheter Tessera , c'est mon outil pour appliquer WFC dans ce moteur.

Mini sudoku

À titre d'illustration, j'ai pris un mini Sudoku . C'est un puzzle qui ressemble à une grille 4 × 4 avec des nombres dans certaines cellules.


L'objectif est de remplir chaque cellule vide d'un nombre de 1 à 4 conformément aux règles:

• Chaque numéro de 1 à 4 doit être présent sur chaque ligne en un seul exemplaire.
• Chaque numéro de 1 à 4 doit être présent dans chaque colonne en un seul exemplaire.
• Chaque numéro de 1 à 4 doit être présent dans chaque carré d'angle 2 × 2 en un seul exemplaire.

Selon ces règles, la solution sera la suivante:


Vous avez peut-être facilement résolu ce puzzle. Mais nous voulons savoir comment un ordinateur peut le faire. Le problème peut être divisé en deux parties: une description des conditions de l'ordinateur, puis une solution utilisant l'algorithme.

Description des conditions

Habituellement, un langage de programmation avec restrictions est utilisé pour cela. Il existe plusieurs de ces langages et leurs principes d'action sont similaires.

Nous définissons d'abord les variables . Ici, ils ne sont pas les mêmes que dans la programmation conventionnelle. Dans le contexte d'une solution de problème, une variable est une valeur inconnue qui doit être résolue pour résoudre un problème. Dans notre exemple de Sudoku, nous allons créer des variables pour toutes les cellules vides. Pour plus de commodité, vous pouvez également créer des variables pour les cellules remplies.

Ensuite, pour chaque variable, nous définissons un domaine : un ensemble de valeurs possibles. Dans notre sudoku, pour chaque cellule vide, le domaine sera {1, 2, 3, 4}. Et pour une cellule dans laquelle 1 est déjà entré, le domaine sera {1}.

Enfin, nous fixons les contraintes: règles liant nos variables. Dans la plupart des langages de programmation, il existe déjà une fonction avec des restrictions all_distinct(..)qui doit transmettre des valeurs uniques. Ainsi, les règles de Sudoku peuvent être traduites en 12 contraintes all_distinct- une pour chaque ligne et colonne, ainsi que pour les coins 2 × 2. Nous n'avons besoin que d'un seul type de contrainte pour résoudre ce problème, cependant, les résolveurs de problèmes pour répondre aux contraintes sont généralement fournis avec une grande bibliothèque de différents types de contraintes pour décrire votre problème.

Remarque : dans la pratique, les langages de programmation prennent en charge les tableaux dans les contraintes, il existe donc des moyens plus précis de formuler cette tâche. Il existe de nombreux articles sur le net sur la résolution de sudoku.

Algorithmes pour résoudre les problèmes de satisfaction des contraintes

Il existe plusieurs techniques de solution différentes. Mais je considérerai les plus simples d'entre eux pour vous démontrer le principe de leur travail. Les domaines pour chaque cellule sont affichés ici:


Ce sont toutes des valeurs possibles dans des domaines variables.

Prenez maintenant la première limitation. Cela nécessite que toutes les valeurs de la ligne supérieure soient uniques. Dans une cellule, la valeur 4 est déjà inscrite, par conséquent, dans d'autres cellules de la série, cette valeur ne peut pas l'être . Nous le supprimons des domaines de ces cellules.


Répétez ce processus avec les 12 restrictions. C'est ce qu'on appelle la propagation de restrictions , car les informations sont distribuées d'une variable à l'autre par le biais de restrictions.


Et regardez, nous avons des variables, dans les domaines dont il reste une valeur. Ces solutions devraient être les bonnes pour ces variables.


Il semble que nous puissions tirer encore plus d'avantages de la distribution des restrictions: les nouvelles unités rouges indiquent que nous aurons encore plus de variables avec un seul domaine, ce qui contribuera également à la distribution. Répétez la procédure jusqu'à ce que le puzzle soit résolu.

Nous compliquons la tâche

Malheureusement, tous les puzzles logiques ne peuvent pas être résolus aussi rapidement. Voici un grand sudoku, il fonctionne de la même manière, sauf que maintenant nous avons 9 valeurs différentes, 9 lignes, 9 colonnes et 9 carrés 3 × 3.


Si nous essayons d'appliquer la technique ci-dessus, nous resterons bloqués:


Maintenant, toutes les restrictions sont communes, mais il reste des variables non définies.

Une personne décidera de cela, mais un algorithme informatique ne pourra pas le faire. Les manuels destinés aux gens disent que nous devons maintenant chercher des conclusions logiques de plus en plus compliquées. Mais nous n'avons pas besoin d'un algorithme informatique pour ce faire, car c'est difficile, mais nous avons besoin d'un algorithme universel qui peut fonctionner avec n'importe quel ensemble de restrictions, et pas seulement selon les règles du sudoku.

Par conséquent, les ordinateurs font la chose la plus stupide: ils supposent . Tout d'abord, nous enregistrons l'état actuel du puzzle. Ensuite, nous sélectionnons une variable arbitraire et la définissons sur l'une des valeurs possibles. Disons que nous attribuons la valeur 1 à la cellule centrale.

Maintenant, nous pouvons étendre un peu plus les restrictions. Voici ce que j'ai obtenu pour la colonne centrale:


Les valeurs bleues sont les conclusions que nous avons tirées après l'hypothèse. Comme vous pouvez le voir, quelque chose s'est produit. Nous avons ajouté quelques variables supplémentaires, mais jetons un œil à la cellule supérieure du milieu. Il est vide: dans son domaine il n'y a pas de valeurs possibles satisfaisant aux restrictions (il ne peut pas y en avoir 5, car cette valeur existe déjà dans le même carré 3 × 3, et tous les autres nombres sont déjà dans cette colonne).

Si nous obtenons une variable avec un domaine vide, cela signifie que nous ne pouvons lui attribuer aucune valeur. Autrement dit, le puzzle ne peut pas être résolu. Il s'avère que notre hypothèse était erronée .

Face à une telle contradiction, nous effectuons le processus de recherche de retour(retour en arrière). Tout d'abord, nous restaurons l'état qui était avant notre hypothèse. Ensuite, nous supprimons du domaine la valeur que nous avons utilisée comme hypothèse - ce ne peut plus être la bonne réponse.


Beaucoup de travail a été fait, mais ils ont progressé. Cependant, même après exclusion de 1 de la cellule centrale, nous sommes toujours au point mort. Il est temps de faire une hypothèse encore et encore et encore.

Il n'y a pas beaucoup d'actions algorithmiques ici. Chaque fois que nous ne pouvons pas distribuer de restrictions, nous faisons une hypothèse et continuons. Et puisque vous pouvez rester bloqué plusieurs fois avant de rencontrer une contradiction, vous accumulerez alors plusieurs états et hypothèses enregistrés.

À chaque itération avec un retour, vous réduisez le domaine d'au moins une variable, de sorte que, malgré de nombreux retours en arrière, l'algorithme finira par terminer le travail.

Ce sujet est beaucoup plus étendu que je ne le décris. En pratique, les optimisations telles que le choix des hypothèses, la compréhension du moment de la distribution et du moment de tirer des conclusions logiques plus complexes peuvent avoir un impact énorme sur l'exécution du programme. Et comme les problèmes de contraintes augmentent généralement de façon exponentielle, vous pouvez obtenir une réponse demain ou après 5000 ans.

Nous revenons à l'effondrement de la fonction d'onde

L'effondrement de la fonction d'onde est une tâche délicate avec une limitation: il existe des milliers de solutions possibles. Si nous faisons des hypothèses au hasard, alors au lieu d'un solveur, nous obtenons un générateur . Dans le même temps, il respectera toujours toutes les restrictions données, c'est-à-dire qu'il sera beaucoup plus facile à gérer que la plupart des autres générateurs de procédures.

La tâche de l'algorithme WFC est de remplir les cellules avec des tuiles afin que les images sur les tuiles soient combinées les unes avec les autres. Dans la terminologie utilisée ci-dessus, chaque mosaïque est une valeur, chaque cellule est une variable et les règles de placement des mosaïques sont des contraintes.

Maxim, l'auteur de WFC, a constaté qu'avec un choix raisonnable de tuiles et une randomisation appropriée, vous devez rarement utiliser le retour arrière, donc cette procédure ne peut pas être mise en œuvre. Ainsi, l'essence du WFC est la suivante:

• Un tableau booléen est créé pour chaque cellule, qui représente le domaine de cette variable. Les domaines contiennent un enregistrement par tuile et tous sont initialisés avec une valeur true. Une tuile entre dans un domaine si sa valeur est égale true.
• Dans le même temps, il existe des cellules dans lesquelles les domaines contiennent plusieurs éléments:
  
  • Sélection d'une cellule aléatoire en utilisant la méthode heuristique de "moindre entropie".
  • Sélectionnez une tuile aléatoire dans le domaine cellulaire et supprimez toutes les autres tuiles de là.
  • La mise à jour des domaines d'autres cellules sur la base de ces nouvelles informations est la propagation de la restriction cellulaire. Cela doit être fait à plusieurs reprises, car les changements dans les cellules peuvent avoir d'autres conséquences.

Remarque : mes conditions sont différentes de celles de Maxim. Il appelle le tableau des domaines une onde, et le choix d'une tuile aléatoire est une observation. Autrement dit, une analogie est établie avec la mécanique quantique. Mais la comparaison est superficielle, nous allons donc l'ignorer.

Il existe de nombreux ajouts aux principes ci-dessus qui ajoutent de la grâce et des performances à l'algorithme. Mais regardons d'abord les étapes décrites.

Exemple

Disons que nous devons remplir une grille 3 x 3 avec quatre types de tuiles:


Les limitations sont les suivantes: les couleurs des tuiles adjacentes doivent correspondre.

Comme dans l'exemple de Sudoku, je vais illustrer le contenu des domaines avec des images monochromes. Lorsqu'il ne reste plus qu'un élément dans le domaine, je vais l'augmenter en taille et l'afficher en couleur.

Tout d'abord, dans chaque cellule, des carreaux de toute nature peuvent être localisés:


Exécutez la boucle WFC principale. Sélectionnez au hasard une cellule, par exemple, en haut à gauche. Sélectionnez maintenant une vignette dans le domaine et supprimez toutes les autres.


Distribuez les restrictions. La seule règle s'applique aux tuiles adjacentes, nous devons donc mettre à jour deux cellules:


Pouvons-nous mettre à jour d'autres tuiles compte tenu des domaines en diminution? Oui! Bien que nous ne soyons pas sûrs du choix de la première tuile, nous voyons que les options restantes mènent à droite. Autrement dit, certains types de tuiles ne peuvent pas être placés dans le coin supérieur droit. Même chose avec le coin en bas à gauche.


Nous ne pouvons plus distribuer les restrictions, nous répétons donc le cycle principal: sélection des cellules, sélection et distribution des tuiles. Cette fois, nous prenons la cellule centrale supérieure:


Un autre cycle: prenez la cellule centrale gauche. Après la prolifération des restrictions pour la cellule centrale, une valeur possible demeure.


En général, vous comprenez l'idée. Vous pouvez remplir vous-même le reste des cellules.

Si vous voulez expérimenter avec un exemple interactif plus complexe , je recommande celui-ci .

Entropie la plus petite

Lors du choix de la cellule suivante à remplir, certaines options seront préférables. Si vous choisissez au hasard n'importe où dans la grille, une situation peut se produire lorsque vous aurez en même temps différentes zones de la grille remplies. Cela peut entraîner des problèmes: selon les tuiles disponibles, les zones remplies ne peuvent pas être jointes. Il est donc préférable de choisir des cellules qui sont moins susceptibles de conduire à de tels problèmes à l'avenir. En d'autres termes, vous devez prendre des cellules avec le moins de valeurs possibles dans le domaine (mais pas moins de deux valeurs):

1. Très probablement, ils seront à côté des cellules déjà remplies.
2. Si nous les laissons pour l'avenir, des difficultés peuvent survenir, car les valeurs disponibles sont déjà peu nombreuses.

L'approche du plus petit domaine fonctionne bien si toutes les tuiles sont également probables. Mais si vous choisissez parmi une distribution aléatoire pondérée , vous devez alors envisager autre chose. Maxima recommande une «entropie minimale», c'est-à-dire choisir une cellule qui minimise:

$$

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

Ceci est une somme de tuiles dans le domaine où $$$p_{i}$- probabilité pour cette tuile.

Informatique efficace

Bien que je ne veuille pas entrer dans les détails, cependant, il y a deux optimisations qui me permettent d'augmenter tellement la vitesse qu'elles ne peuvent pas être ignorées.

Puisque notre seule règle est liée aux tuiles adjacentes, nous ne pouvons vérifier que les restrictions qui peuvent donner des résultats différents des précédents. Autrement dit, lors de la mise à jour d'une cellule, nous l'ajoutons à la file d'attente des cellules en attente d'une décision. Ensuite, nous supprimons une cellule de la file d'attente, en vérifiant à chaque fois ses cellules adjacentes. Si de tels contrôles conduisent au renouvellement d'autres cellules, ils tombent également dans la file d'attente. En répétant cette procédure jusqu'à ce que la file d'attente soit vide, nous nous assurons de vérifier toutes les restrictions. Mais nous ne les vérifions pas tant que le domaine d'au moins une cellule associée à ces restrictions ne change pas.

De plus, pour vérifier la contrainte d'adjacence, nous devons répondre à la question: «Étant donné les tuiles dans le domaine de la cellule A, quelles tuiles sont possibles dans le domaine de la cellule B si les cellules sont adjacentes?»

Parfois, cette question est appelée le "support" de la cellule A. Pour une tuile "b" donnée dans le domaine B, il est facile de calculer les cycles pour les tuiles du domaine A. Si A a au moins une tuile qui peut être placée à côté de "b", alors "b" convient toujours, au moins pour la paire de tuiles en question. Si dans A il n'y a pas une telle tuile, alors vous ne pouvez pas mettre la tuile «b» du domaine B, et nous pouvons la jeter.

Les boucles facilitent l'implémentation de cela dans le code, mais fonctionneront extrêmement lentement. Et si nous stockons des informations dans une structure de données supplémentaire, nous pouvons répondre rapidement à la question si nécessaire. Les nouvelles données sont un grand tableau avec des entrées pour chaque côté de chaque cellule et chaque tuile. Dans notre exemple, il y a 9 cellules, chacune avec 4 côtés et 4 types de tuiles. Nous avons donc besoin de 9 * 4 * 4 enregistrements. Nous enregistrerons les compteurs de support dans le tableau: pour chaque cellule / tuile / côté, nous comptons le nombre de tuiles dans le domaine de cellule adjacent qui peuvent être placées à côté de la tuile en question. Si le compteur tombe à zéro, cette tuile ne peut pas être mise, car personne ne peut être adjacent à elle.

Extensions d'algorithme

Le WFC étant basé sur une compréhension plus générale des problèmes contraints, il existe de nombreuses façons d'étendre l'algorithme en modifiant les contraintes utilisées.

L'un des changements évidents est que personne ne nous oblige à utiliser des cellules carrées. Le WFC fonctionne très bien sur les cellules hexagonales, en trois dimensions ou sur des surfaces encore plus inhabituelles .




Vous pouvez introduire des restrictions supplémentaires: corriger certaines tuiles ou créer des «modules» à partir de plusieurs cellules.

L'introduction de restrictions supplémentaires peut jouer un rôle très important d'un point de vue pratique. Étant donné que le WFC ne limite que les carreaux adjacents, il génère rarement de grandes structures qui offrent un haut niveau d'homogénéité et un aspect inhabituel. Cet algorithme fonctionne mieux lors du choix des tuiles, mais pour travailler avec certaines grandes structures, il est préférable d'utiliser une technique différente ou d'introduire d'autres restrictions.

Dans un autre article, j'ai expliqué comment obtenir les meilleurs résultats du WFC.

Chevauchement WFC

L'une des extensions intéressantes de l'algorithme est le WFC «à chevauchement». Dans les exemples ci-dessus, la principale limitation était liée aux paires de tuiles adjacentes. Cela suffit pour assurer la connexion des lignes et créer des structures simples comme des grottes, des salles, etc. Mais en même temps, beaucoup d'informations sont perdues. Si nous avons besoin, par exemple, que les carreaux rouges soient toujours situés à côté du bleu, mais qu'ils n'y aient jamais été adjacents, alors cela sera difficile à exprimer en termes de contiguïté uniquement.

Maxim a proposé le concept de chevauchement des WFC: nous remplaçons la contrainte d'adjacence par une nouvelle contrainte qui affecte plusieurs tuiles à la fois. Par exemple, de sorte qu'en sortie chaque groupe de 3 × 3 cellules correspond à un groupe 3 × 3 d'un échantillon de grille. Les motifs présents dans l'échantillon seront répétés encore et encore dans différentes variations à la sortie:


Cette restriction est beaucoup plus sensible que les restrictions de contiguïté «simples». Et comme cela dépend d'un échantillon donné, il est très approprié pour résoudre certains types de tâches artistiques. Jusqu'à présent, je n'ai rien trouvé d'aussi intéressant. La raison en est peut-être qu'un tel algorithme est plus difficile à mettre en œuvre, ou qu'il fonctionne plus lentement, ou qu'il reproduit parfois trop bien l'échantillon d'origine, ce qui entraîne une perte de naturalité et de naturalité.

Et après?

La résolution de problèmes avec des restrictions est un domaine de l'informatique vaste et en développement actif, et je ne l'ai abordé que. WFC - comme tout autre algorithme de génération procédurale pour résoudre des problèmes contraints - est encore nouveau. Je recommande de lire r / proceduralgeneration , #wavefunctioncollapse , @exutumno et @osksta pour avoir une idée des cas d'utilisation récents.

Vous pouvez également lire mon article sur WFC , expérimenter avec ma bibliothèque opensource ou l'outil Unity . N'oubliez pas mes autres articles sur la génération procédurale .