Algorithme de placement de tuiles basé sur des contraintes

Cet article décrit l'algorithme utilisé dans Generate Worlds , un outil qui permet aux utilisateurs de créer et d'explorer des mondes procéduraux en construisant de petits ensembles de tuiles voxel. Je donnerai une brève description de l'algorithme, et dans les articles suivants, je parlerai de ses avantages en termes de vitesse et de flexibilité par rapport à d'autres méthodes. Pour en savoir plus sur ce qu'est la génération procédurale basée sur les contraintes et sur son intérêt, je recommande de lire mon article précédent .

Si vous souhaitez tester vos forces dans la création de mondes procéduraux à l'aide de ce système, vous pouvez acheter Générer des mondes. Si le prix est trop élevé pour vous, alors continuez à lire: cet article vous donnera des informations sur la façon de mettre en œuvre indépendamment l'algorithme Generate Worlds.

Ensembles de tuiles

Dans Generate Worlds, chaque monde est assemblé à partir d'un ensemble de tuiles ( jeu de tuiles ). En substance, les carreaux ne sont que de petits modèles de voxels. Commençons par un exemple. L'image ci-dessous est composée de 9 tuiles. Comme vous pouvez le voir, chaque tuile est constituée de voxels qui apparaissent sous forme de cubes colorés.


Si vous organisez ces modèles de voxels de manière logique, vous pouvez créer une belle scène pastorale, comme dans l'animation ci-dessous. Par «logique», je veux dire que les carreaux s'emboîtent si leurs couleurs le long du bord du joint correspondent.


La tâche de l'algorithme Generate Worlds est de terminer rapidement et automatiquement un tel assemblage. Avant de se lancer dans l'algorithme, regardons l'énoncé du problème.

Nous connectons les carreaux entre eux

Jetez un œil au jeu de tuiles contenant 4 tuiles:


Ces tuiles sont similaires aux tuiles tridimensionnelles illustrées ci-dessus.

L'algorithme Generate Worlds crée des combinaisons de tuiles valides en utilisant une règle simple: si deux tuiles se touchent, toutes les couleurs le long du bord de la touche doivent correspondre . Cette règle formalise l'approche utilisée par un designer vivant pour créer un monde 3D à partir de carreaux de voxel.

Dans une combinaison autorisée des 4 tuiles présentées ci-dessus, les cellules claires le long des limites ne devraient toucher que les cellules claires, et une cellule sombre ne devrait toucher que les cellules sombres. Par exemple:


Exemples de connexions correctes et incorrectes.

L'exemple de droite est inacceptable, car le long du bord du pavé tactile, le carré clair touche le carré sombre. Deux combinaisons valides générées pour cet ensemble de tuiles sont présentées ci-dessous:


Dans le cas général, la création de combinaisons de tuiles valides n'est pas une tâche triviale. Par exemple, considérons la stratégie simple «gourmande» suivante: nous commençons avec une grille vide. À chaque itération, nous plaçons la tuile à un moment donné, en choisissant une tuile qui est acceptable en tenant compte des tuiles déjà placées. Le schéma ci-dessous montre les problèmes d'une telle stratégie.


Si nous plaçons des tuiles sans prévoir comment le placement affectera les choix futurs, alors l'algorithme «gourmand» s'arrête rapidement; dans le schéma ci-dessus, aucune tuile valide ne peut être placée dans le carré rouge. Et c'est le principal problème: les tuiles publiées précédemment peuvent réduire le nombre d'options actuelles à zéro. Nous avons besoin d'un moyen de se protéger contre la pose de carreaux, ce qui peut nous conduire dans une impasse. L'algorithme implémenté dans Generate Worlds commence par considérer toutes les tuiles comme possibles à placer à tous les points de la grille. Si nous plaçons une tuile dans la grille, il est évident que certaines des options futures deviennent inaccessibles. Une fois que l'algorithme a éliminé ces options, nous pouvons réexaminer les options restantes et éliminer les autres tuiles qui sont maintenant incompatibles avec le plus petit nombre de tuiles possibles restantes aux points voisins.

Prenons l'exemple suivant. L'algorithme commence par une grille 3x3, au centre de laquelle se trouve une seule tuile. L'emplacement de cette tuile implique que 9 tuiles possibles aux points de grille voisins ne sont pas autorisées, il les jette donc et ne les considère plus. Après avoir supprimé ces tuiles, il peut supprimer les tuiles qui sont incompatibles avec toutes les tuiles considérées comme candidates au placement aux points de grille voisins. Les carrés rouges dans le diagramme marquent les points où les tuiles sont supprimées, car elles sont incompatibles avec tous les voisins qui sont toujours à l'étude. Si l'algorithme continue ce processus jusqu'à ce qu'il y ait des tuiles qui peuvent être supprimées, il reviendra à l'état affiché dans le coin inférieur gauche du circuit. Comme vous pouvez le voir, de nombreuses tuiles ont été exclues de l'examen. Si la stratégie de placement des tuiles consistait uniquement à choisir des tuiles dans ces groupes restants, alors la probabilité de se retrouver dans une impasse serait beaucoup plus faible que dans l'approche «gourmande» décrite ci-dessus.


Le problème avec cette approche est que chaque fois qu'une tuile est placée, elle nécessite un processus itératif coûteux. Mais notez que chaque fois que je place une tuile avec un T inversé, ces 19 tuiles que j'ai retirées dans l'exemple ci-dessus peuvent être retirées de la considération autour de ce placement. J'appelle la collection de tuiles, qui restent des options valides autour de la tuile hébergée, un voisinage valide de cette tuile.

Placement rapide des carreaux grâce à la mise en cache des informations

Le principe le plus important de l'algorithme Generate Worlds est que les informations collectées sur les voisins de tuiles possibles peuvent être réutilisées chaque fois que cette tuile est placée. Par exemple, dans le cas d'un T inversé pour les huit carrés environnants de la grille, nous pouvons retirer 19 tuiles de la considération immédiatement après avoir placé cette tuile en regardant la version mise en cache du voisinage acceptable pour cette tuile.

Par exemple, dans l'exemple ci-dessous, l'algorithme remplit la grille 5x5 de tuiles en utilisant un voisinage autorisé mis en cache de 4 tuiles. Après avoir placé la première tuile, il retire de la considération 19 tuiles qui étaient impossibles dans l'exemple ci-dessus. Après avoir placé chaque tuile, toutes les options qui sont absentes dans le voisinage acceptable de la tuile placée sont supprimées de la considération.


En continuant ainsi, nous pouvons remplir la grille entière avec seulement des mises à jour locales rapides de l'ensemble de tuiles, qui sont toujours des options valables pour chacun des points.

Les quartiers autorisés peuvent être de la taille dont vous avez besoin, vous pouvez donc supprimer les tuiles incompatibles distantes à chaque fois que vous placez une tuile. Bien que la génération d'un voisinage acceptable soit plutôt lente, elle ne doit être effectuée qu'une seule fois, après quoi chacun dépend linéairement de la taille du voisinage pour accueillir chaque tuile.

Extension du système en 3D

L'algorithme Generate Worlds s'étend naturellement aux mondes ayant une troisième dimension. Au lieu que les tuiles 2D correspondent en couleur avec 4 tuiles voisines le long des faces communes, nous avons maintenant des tuiles 3D qui devraient correspondre en couleur avec leurs voisins le long de 6 faces. Considérez les tuiles 3D suivantes:


L'assemblage de ces tuiles en 3D est le suivant:


Dans ce cas, les voisinages admissibles ne sont pas des grilles bidimensionnelles, mais tridimensionnelles, et l'algorithme les génère dans un cas 2D similaire.

Galerie des résultats

Vous trouverez ci-dessous les mondes générés par les implémentations de cet algorithme ainsi que de brèves descriptions.


Capture d'écran de Generate Worlds montrant la salle avec sortie. Les rebords du plafond coïncident avec les bordures des carreaux.


Une capture d'écran d'un autre outil que je crée qui utilise également l'algorithme Generate Worlds; différents types de chambres et de couloirs sont présentés.


Un monde semblable au précédent, mais maintenant dans une belle vue isométrique


Le monde, dont la création m'a inspiré du neuvième cercle de l'enfer de Dante: des pécheurs figés dans la glace. Rendu dans MagicaVoxel.


Le monde, dont la création m'a inspiré par le deuxième tour de l'enfer de Dante: le paysage, irrigué par une pluie brûlante, qui traverse le pont. Rendu dans MagicaVoxel.


Un monde de plates-formes herbeuses avec des cascades et des rivières. Rendu dans MagicaVoxel.


Paysage d'une ville médiévale avec des bâtiments et des murs. Rendu dans MagicaVoxel.