Qu'est-ce que la génération procédurale?

La génération procédurale comprend de nombreux algorithmes génératifs, dont le principe est de créer des données non pas manuellement, mais de façon algorithmique: au lieu de fabriquer manuellement ce que nous voulons créer (cartes, musique, terrain ...), un algorithme est écrit qui peut créer avec succès divers exemples sans effectuer le même processus plusieurs fois. Cette approche est particulièrement utile dans les jeux vidéo où une carte ou un niveau entier peut être généré de manière aléatoire (par exemple, des cartes dans Minecraft, Terraria ou Factorio, ou des schémas de niveaux dans la plupart des roguelike).

L'algorithme d'effondrement de la fonction d'onde et sa portée

Dans cet article, nous examinons l'algorithme d'effondrement de la fonction d'onde (WaveFunctionCollapse, WFC) proposé par Maxim Gumin (son Twitter a une collection de contenu incroyable créé en utilisant cet algorithme par d'autres développeurs!) Pour la génération procédurale d'images ou de terrain en créant des images qui sont localement similaires à celles entrantes image dans une grille d'une taille donnée.

L'algorithme est basé sur l'idée de création pas à pas d'une image finie avec suivi des tuiles «correspondant» à une image déjà partiellement construite. Pour étudier la description détaillée de l'algorithme, nous vous recommandons de vous référer au référentiel WFC d'origine sur Github et à la quatrième section de l'article " WaveFunctionCollapse est la résolution des contraintes dans la nature ".


Exemples d'images de départ générées de manière procédurale

En plus de créer des images similaires, un autre domaine d'application de l'algorithme WFC est la génération de cartes de tuiles. La génération de cartes de tuiles sera le sujet principal de l'article, car il est plus facile à utiliser pour expliquer clairement nos idées. Au lieu d'une image d'exemple, vous ne pouvez stocker que des tuiles et des paires de tuiles qui peuvent être connectées les unes aux autres à tour de rôle. Dans ce cas, l'algorithme peut être utilisé pour créer des images similaires à celle illustrée ci-dessous.


Exemples de tuiles générées au hasard

Le défi et notre solution

Nous avons pris la tâche de générer une carte tuile basée sur le jeu de plateau Carcassonne («Carcassonne»), dans laquelle le champ est généré par les joueurs «manuellement» (voir animation ci-dessous) à partir des tuiles qui doivent être combinées entre elles.


Étonnamment, conceptuellement, cela est très similaire à l'algorithme WFC pour créer des cartes de tuiles arbitraires en ajoutant de nouvelles pièces à une solution incomplète. Et comme WaveFunctionCollapse peut être utilisé comme générateur de cartes de tuiles, il peut également générer des champs "Carcassonne"!

Cependant, dans le jeu lui-même, il y a trop de tuiles différentes, et coder tous leurs ratios est une tâche trop volumineuse pour un hackathon de 24 heures. Par conséquent, nous avons décidé de jouer une version très simplifiée de "Carcassonne" sans châteaux et rivières, uniquement avec des routes, de l'herbe et des monastères. Nous avons donc obtenu 6 tuiles possibles avec leurs rotations et leur symétrie. Mais même dans de telles conditions, le résultat est magnifique et ressemble à un vrai match à Carcassonne!


Visualisation du remplissage de l'algorithme de champ de Carcassonne


Exemple de règles introduites dans l'algorithme

L'image ci-dessus contient un exemple de règles d'entrée ajoutées à l'algorithme. Cependant, nous devons encore contrôler certains aspects de l'apparence du champ. L'algorithme devrait-il créer des «rues» à partir de routes remplies de monastères et similaires à une ville, ou le champ devrait-il être constitué d'herbe avec des villages dispersés autour d'elle? Dans l'algorithme d'origine, il n'y a aucun moyen de contrôler de telles conditions (comme les autres), mais pour la possibilité de contrôle, il est possible d'apporter une amélioration simple.

Distribution de probabilité a priori bayésienne

Comme mentionné ci-dessus, à chaque étape, l'algorithme ajoute une nouvelle tuile au champ afin qu'elle corresponde aux tuiles déjà placées, mais nous n'avons pas dit ce qui se passerait si plusieurs tuiles différentes pouvaient être placées à l'emplacement sélectionné (nous n'avons pas non plus expliqué comment choisissez généralement cet endroit, mais dans l'article, nous ne le considérerons pas!). Dans l'algorithme d'origine, n'importe quelle tuile appropriée est sélectionnée de manière uniforme et aléatoire. Cependant, dans notre décision, nous pouvons préférer des tuiles spécifiques, par exemple, de l'herbe, afin qu'elles se produisent plus souvent sur le terrain. Cela peut être réalisé en créant une distribution inégale de «probabilité préalable» de tuiles, dans laquelle l'herbe a plus de chances d'être utilisée que la route, si les deux types de tuiles peuvent être utilisés. Cela rappelle les techniques bayésiennes. Dans le cas simplifié du choix entre deux options, l'herbe et les routes, on peut ajouter de l'herbe avec une probabilité p> 0,5, et non pas avec l'habituel 0,5, obtenu avec une probabilité uniforme. Cette tâche peut être facilement généralisée en attribuant une valeur de priorité à chaque tuile et en utilisant cette valeur pour définir la probabilité comme une valeur divisée par la somme des valeurs de toutes les tuiles possibles. La figure ci-dessous montre deux solutions appropriées avec des valeurs de coefficient très différentes, ce qui permet de comprendre la sensibilité de l'algorithme.


Différentes solutions pour différentes distributions de probabilité initiales a priori

Autre exemple: probabilités conditionnelles et regroupement

Vous pouvez développer cette idée, et pour illustrer cela, nous allons générer, au lieu des champs de Carcassonne, des cartes bidimensionnelles du minerai Minecraft. Différents types de minerais dans Minecraft se trouvent généralement dans de grandes formations, donc en plus de définir les probabilités de chaque minerai, nous dépendrons des probabilités en fonction des voisins déjà placés sur la carte. Même s'il n'y a rien «d'interdit» dans la disposition du fer à côté du charbon, à côté du charbon déjà placé, un autre charbon est prioritaire.

Bien que cela ne soit pas pris en compte dans l'image ci-dessous, dans le jeu, la probabilité dépend également de la hauteur des tuiles, donc la position dans l'image peut également affecter les conditions de distribution des probabilités de tuile.


Exemple de carte de tuiles de minerai Minecraft créé par WFC

Conclusion

La génération procédurale est un outil puissant qui vaut la peine d'être en stock. En particulier, le WFC est activement utilisé dans la génération mondiale, et il convient de considérer la possibilité que la distribution de nouvelles tuiles soit inégale et puisse être influencée par d'autres facteurs, par exemple, les voisins déjà placés sur la carte, les nouvelles tuiles et la position dans l'image. Nous avons créé une application très simple, mais les possibilités de développement sont presque infinies!