🌟 🌥️ 🙎 Conseils d'utilisation de l'algorithme de réduction de la fonction d'onde ♓️ ⛽️ 😁

Récemment, j'ai beaucoup expérimenté la génération basée sur des contraintes procédurales. En particulier, avec l'algorithme Wave Function Collapse (WFC, wave function collapse). J'ai même écrit ma propre bibliothèque open source et mon actif d'unité .

WFC est un algorithme très flexible, en particulier avec les améliorations que j'ai développées. Mais en même temps, j'ai trouvé difficile de créer des niveaux pratiques applicables aux jeux informatiques avec son aide . La principale difficulté est que le WFC n'a pas de structure globale. Tout ce qu'il fait, c'est que la génération de sortie ressemble localement à l'entrée, par exemple, en examinant les petits rectangles individuels de la sortie.

Dans cet article, je vais vous dire ce que j'ai appris et ce qui pourra élever les générateurs basés sur des restrictions à un nouveau niveau.

Les bases

Il est difficile d'utiliser WFC si vous ne savez pas comment cela fonctionne. Il s'agit d'un algorithme de génération procédurale basé sur des contraintes qui a fait l'objet de beaucoup d'attention récemment. En fait, cela n'a pratiquement rien à voir avec le concept de physique quantique en l'honneur duquel elle a été nommée.

WFC est facile à configurer - vous donnez simplement à l'algorithme un exemple de carte, après quoi il génère de nouvelles cartes qui ressemblent à la carte d'origine en raison de l'utilisation répétée de ses petits fragments.

Il a deux types - avec un arrangement voisin ou avec une superposition d'éléments. Cela peut se faire en 2D ou 3D, et même sur des grilles d' hexagones ou inégalesgrilles. La plupart de mes conseils s'appliquent quelle que soit la façon dont vous utilisez l'algorithme.

Je vous suggère de jouer avec cette démo pour avoir une idée sur l'algorithme, et de lire cette introduction [ traduction sur Habré] si vous êtes intéressé par les détails techniques.

Conception de tuiles

L'algorithme WFC est basé sur des tuiles. En ce sens, sa qualité dépend des tuiles que vous lui transférez pour le travail. Je ne suis pas un artiste, donc je peux peu aider à dessiner de beaux ensembles de tuiles (bien que vous puissiez voir ici ), mais un bon ensemble de tuiles nécessite également des connaissances techniques.

Cubes de marche

Marching cubes est un algorithme qui sélectionne les tuiles à définir selon que chaque sommet de la tuile est plein ou vide. Voici la liste des tuiles utilisées pour la 2D.

Si vous construisez des tuiles de sorte que les coins noir et blanc correspondent toujours, alors les lignes rouges se connecteront toujours correctement.

Ici, nous n'avons pas besoin de comprendre l'ensemble de l'algorithme, mais il convient de noter que l'idée de concevoir des tuiles en tenant compte uniquement de leur comportement dans les coins est une technique très puissante. Il est utilisé dans bon nombre des meilleurs ensembles de tuiles, car il garantit que les tuiles se connectent toujours bien.

Cette technique est particulièrement puissante pour WFC. C'est arrivé, car si vous manquez quelques tuiles, WFC, cela n'aura pas d'importance. Il contournera ce problème et ne créera jamais de configurations nécessitant des tuiles manquantes. C'est très pratique pour la 3D, car il existe des dizaines de tuiles potentielles, et certaines d'entre elles ne sont nécessaires que dans des situations très difficiles. Voir la section «Fondation» ci-dessous, dans laquelle j'utilise encore plus largement cette astuce.

Connaître d' autres motifs de carreaux peut également être utile , mais Marching Cubes est le meilleur.

Les chambres

Parfois, il est plus facile de travailler avec de simples ensembles de tuiles. Cette combinaison de 4 tuiles (une tuile est vide) génère facilement des pièces carrées.

La taille des pièces peut facilement être modifiée en modifiant le poids de chaque carreau. Après avoir ajouté les carreaux de porte et de couloir, vous pouvez créer la diversité caractéristique des plans d'étage des personnes.

Fondation

Lorsque vous travaillez avec WFC, il est intéressant d'expérimenter avec des ensembles de tuiles. Si vous mettez simplement une tuile, WFC cherche à tirer le meilleur parti de l'espace restant. Parfois, cela conduit à des résultats radicalement différents, comme on peut le voir sur l'image de Maxim Gumin:

Nous pouvons utiliser ce comportement pour stimuler WFC à générer de nombreuses structures reconnaissables.

Voici un exemple de château (inspiré de @greentecq ):

Dans ce document, j'ai utilisé le jeu de tuiles suivant:

Ces tuiles ont une propriété importante - toutes les tuiles à la base ont une largeur non inférieure à celle du haut. Cela signifie qu'il n'est pas possible de construire ces tuiles d'une manière non prise en charge. Le WFC répond immédiatement à cela et crée des bâtiments avec une bonne fondation.

Fractal Split Approximation

En étudiant le sujet de la stimulation de certains comportements en choisissant le jeu de tuiles approprié, j'ai constaté que si le jeu de tuiles se compose de routes droites et de branches, mais sans coins, alors vous pouvez obtenir une bonne approximation du fractionnement récursif (sans la partie «récursive»). C'est assez bon pour les niveaux de grille.

Grandes tuiles

Vous pouvez ajouter WFC pour prendre en charge des tuiles qui sont plusieurs fois plus grandes qu'une tuile ordinaire. Par exemple, cela est pris en charge dans mon module complémentaire Tessera .

Les grandes tuiles peuvent être utilisées de différentes manières. Puisqu'ils s'étendent au-delà des limites de la grille, vous pouvez les utiliser pour ajouter des courbes plus lisses et plus larges que ce qui est généralement possible lors de l'accrochage à la grille. Ils sont également parfaits pour les éléments d'un grand nombre de tuiles, ou simplement pour masquer que la génération est basée sur des tuiles.

Voici un exemple à apprendre d' Oscar Stalberg du jeu Bad North . Oscar montre comment il a utilisé de grandes tuiles pour ajouter des côtes incurvées en douceur, de grandes maisons et la variabilité des falaises.

Limites

À la base, WFC est un algorithme basé sur des contraintes. Cela signifie qu'il cherche à générer des niveaux qui correspondent à un ensemble spécifique de critères. En WFC pur, il n'y a qu'un seul critère - que les niveaux ressemblent localement à un échantillon d'entrée. Ci-dessous, je parlerai des améliorations WFC pour ajouter de nouveaux types de restrictions.

Tuiles fixes

Il est très facile de corriger des tuiles individuelles avant de générer un niveau dans WFC. Plus tard, ils s'intègrent parfaitement au niveau généré.

Avant la génération

Après la génération

Cette technique peut être utilisée de différentes manières. Voici quelques idées:

- , WFC .
,
/ WFC

Chemins de limitation (contrainte de chemin) - c'est ma propre contribution au WFC. Il s'agit d'une technique extrêmement puissante, mais un article complet nécessitera très probablement un article séparé.

Cette restriction analyse globalement toutes les sorties générées et indique de force qu'un chemin doit passer entre les tuiles marquées. Ou en d'autres termes, il indique à un sous-ensemble de tuiles de former un seul composant du graphique . En raison de sa nature globale, il complète le comportement WFC habituel, qui ne prend en compte que les tuiles locales.

J'ai découvert que l'ajout de cette restriction affecte fortement l'apparence du niveau généré. Sans cela, WFC génère souvent plusieurs pièces ou zones divisées qui semblent irréalistes et non créées par des humains.

. .

Une autre situation où la limitation de chemin est appropriée est ... le tracé de chemins. Par défaut, la restriction de chemin d'accès garantit uniquement qu'il existe un itinéraire entre les tuiles. Cela ne garantit pas que le chemin sera aussi simple que possible. Par conséquent, dans le cas des rivières et des routes, il dessine souvent des joints en forme de T dans des endroits facultatifs. L'astuce consiste soit à retirer simplement toutes les tuiles des joints en T, soit à leur donner un poids très faible, afin qu'elles ne soient sélectionnées qu'en cas d'absolue nécessité.

J'adore utiliser des tuiles fixes pour fixer les points de terminaison d'un chemin. Pour cette raison, la restriction de chemin est requise pour insérer des tuiles qui connectent le reste du chemin.

Les chemins générés en fixant les quatre coins comme points de terminaison des chemins

Si vous voulez expérimenter avec des chemins, alors j'ai une petite démo javascript qui est présentée ici .

La diversité

Tuiles alternatives

Il est très facile d'ajouter des options de tuile à l'algorithme WFC. Ajoutez simplement les tuiles à la liste des tuiles possibles, en lui donnant les mêmes connexions que la tuile qu'elle remplace. Ou cela peut être fait au stade du post-traitement, comme c'est généralement le cas dans d'autres styles de génération procédurale.

Deux carreaux muraux, l'un d'eux avec une fenêtre. Ils sont complètement interchangeables et ajoutent simplement de la variabilité à la conception.

Variabilité des tuiles par niveau

Si vous mettez beaucoup d'efforts pour créer une conception de jeu de tuiles, vous remarquerez que le caractère aléatoire de WFC commence à lui nuire. Il utilise l'ensemble de tuiles, c'est-à-dire que vous pouvez obtenir un niveau avec de la lave mélangée, de la neige et du désert. Cela semble souvent complètement illogique.

Vous pouvez restaurer l'intégrité d'une manière simple: décidez à l'avance à quel biome le niveau appartiendra, puis désactivez toutes les tuiles qui ne conviennent pas à ce biome.

Bad North (encore) en est un excellent exemple. À certains niveaux, les rochers sont complètement interdits, à d'autres il y a beaucoup de végétation, dans les troisièmes ruines et des cimetières sont ajoutés. Cela donne à chaque niveau un style unique sans avoir besoin d'un changement significatif dans le style de génération.

Seulement environ 10% des îles ont des éléments de grottes, visibles dans le coin supérieur droit.

Variabilité des tuiles dans la carte

Le mélange de tuiles peut aller encore plus loin.

Si vous utilisez WFC pour générer une grande carte, elle commence à sembler très uniforme. C'est une autre conséquence du fait que l'algorithme est un solveur de contraintes locales .

La meilleure solution à ce problème que j'ai vue dans le jeu Caves of Qud . Dans l'histoire des développeurs sur la génération ( 1 , 2 ), ils disent qu'ils divisent la carte en différentes zones, puis démarrent WFC avec des paramètres distincts pour les sous-ensembles de la carte. Cela signifie que sur la carte, il peut y avoir une zone de ruines et une zone d'une ville dans laquelle des modèles et des tuiles complètement différents sont utilisés.

Exemple de mathématiques pour les développeurs de jeux: génération de cartes basées sur des tuiles à l'aide de l'effondrement de la fonction d'onde dans «Caves of Qud»

Conclusion

L'algorithme WFC, comme toutes les techniques de génération basées sur des contraintes, a pour principe de faire attention à vos envies . Il est facile de personnaliser et d'obtenir de beaux résultats, mais il peut être très difficile de mettre en œuvre les détails spécifiques nécessaires à votre jeu.

J'espère que les techniques présentées par moi vous aideront à apprivoiser ce monstre, mais au final, il est préférable de créer un game design basé sur les forces de la génération procédurale, et de ne pas essayer de le forcer à en créer trop pour vous.

Je vous recommande de jouer à Bad North et Caves of Qud . Les deux jeux sont d'excellents exemples d'utilisation de WFC dans des conditions réelles, et les développeurs ont bien pensé à l'utilisation optimale de l'algorithme dans leurs jeux.

Conseils d'utilisation de l'algorithme de réduction de la fonction d'onde