Cette semaine, j'ai commencé à travailler sur un nouveau sujet: la génération des donjons et des grottes. J'ai utilisé le partitionnement d'espace pour générer des pièces, des algorithmes de génération de labyrinthe pour générer des couloirs et des automates cellulaires pour donner aux grottes un aspect plus naturel.

Fractionnement de l'espace

Il existe de nombreuses façons de générer des salles de donjon ( placement aléatoire , génération basée sur un agent , en utilisant un comportement de pilotage de séparation ou un moteur physique , etc.). Mais ma méthode préférée est de diviser l'espace, car il est facilement contrôlé et étendu.

Il existe également de nombreuses façons de diviser l'espace: division en grilles, partition binaire de l'espace, division de l'espace par un arbre de quadrants, diagrammes de Voronoï, etc. J'ai décidé d'utiliser une partition d'espace binaire, car elle est bien adaptée pour générer des pièces rectangulaires. Cette méthode a gagné en popularité grâce à un article sur RogueBasin.

La seule complexité de cet algorithme est le choix de la position de séparation. Si nous n'imposons pas de restriction sur la position de séparation, nous obtiendrons d'étranges partitions d'espace:


Il existe plusieurs façons d'éviter ce comportement. L'un d'eux est de limiter la position de séparation à deux rapports d'aspect, par exemple, dans la plage de 30% à 70% ou de 40% à 60%. Une autre façon consiste à utiliser une distribution normale ou binomiale au lieu d'une distribution uniforme, augmentant ainsi la probabilité de séparation au centre du côté et non sur les bords. Ces méthodes résolvent le problème, mais il est difficile de comprendre comment exactement les paramètres affectent le résultat final.

Par conséquent, j'ai utilisé une autre méthode, dont l'avantage est qu'elle a un paramètre et est facile à comprendre: le rapport maximum autorisé entre la longueur et la largeur des cellules. Lors de l'échantillonnage d'une nouvelle division, je calcule d'abord les valeurs minimale et maximale qu'elle peut avoir afin que le rapport pour deux nouvelles cellules soit inférieur à la limite, puis j'effectue un échantillonnage uniforme entre ces deux limites. Voici le résultat lors de la variation du rapport maximum autorisé:


De bons résultats sont obtenus avec un rapport maximum de 2,0 à 3,0:

Génération de pièce

L'étape suivante est la génération dans chaque cellule de la pièce. Il n'y a pas de problème particulier ici, je fixe juste des limites pour que les pièces ne soient pas trop petites et ne soient pas trop près des parois des cellules.

Voici les résultats:

Sélection de côtes

Dans les générateurs de donjon de division binaire, l'arbre binaire utilisé dans l'étape de division est généralement réutilisé pour générer des couloirs. Je ne l'ai pas fait, car une telle approche me semble limitative.

Au lieu de cela, au stade de la division de l'espace, je construis la structure d'une liste d'arêtes doublement connectées , ce qui nous permet de savoir quelles cellules sont situées les unes à côté des autres. De cette façon, j'obtiens les graphiques suivants:


Cette approche présente trois avantages. Premièrement: si à l'avenir je veux changer la façon de diviser l'espace, le reste du générateur restera valide, car il ne reçoit qu'une structure de données semi-frontale à l'entrée. Deuxièmement: maintenant pour sélectionner les bords qui deviendront des couloirs, je peux utiliser n'importe quel algorithme pour générer des labyrinthes . Troisièmement: si je veux ajouter des boucles au donjon, je peux facilement l'implémenter.

Pour l'instant, j'utilise simplement l'algorithme Kruskal et la distance des blocs de la ville pour sélectionner les bords. Voici les résultats:

Génération de couloir

L'étape suivante consiste à générer des couloirs à partir des bords sélectionnés. C'est probablement la partie la plus délicate du générateur, car je dois faire attention à ce qu'aucun couloir ne croise un autre.

Voici les résultats:

Génération de grottes

Les résultats précédents étaient appropriés pour créer des donjons, des cryptes et d'autres structures artificielles, mais je voulais donner aux grottes et aux mines un aspect plus naturel. La manière classique de générer des grottes est d'utiliser un automate cellulaire, comme décrit dans cet article RogueBasin. Le gros problème avec les automates cellulaires est que leurs résultats ne sont pas complètement contrôlés.

Quoi qu'il en soit, j'ai décidé d'utiliser des automates cellulaires pour créer une apparence naturelle, mais de leur imposer des restrictions pour obtenir un résultat contrôlé. Au lieu de seulement deux états: morts et vivants, j'en utilise quatre: absolument morts, morts, vivants, définitivement vivants. Les états «parfaitement précis» ne peuvent pas changer dans le processus, ils sont utilisés pour limiter les résultats.

Les pièces et les couloirs générés lors des étapes précédentes sont remplis de cellules «exactement vivantes». Autrement dit, nous avons encore des salles de soutien et nous garantissons qu'ils seront connectés les uns aux autres. Les bords non sélectionnés sont remplis de cellules «exactement mortes» afin qu'aucun nouveau chemin n'apparaisse entre les pièces. Enfin, autour des pièces et des couloirs, nous rendons au hasard certaines cellules vivantes. Voici la configuration initiale:


Ensuite, nous démarrons l'automate cellulaire:



Voici quelques exemples de résultats supplémentaires:


Plus tard, j'ajouterai un remplissage pour supprimer les parties inaccessibles.

Il s'agit de la première étape d'un long voyage pour créer un générateur de donjon intéressant. Je suis content des résultats. Je suis particulièrement fier de la méthode des automates cellulaires contraints de créer des grottes contrôlées et naturelles. J'aime aussi le fait que chaque étape de génération soit distincte des autres et puisse être modifiée individuellement.

Supprimer les cellules isolées

Ensuite, j'ai implémenté un remplissage pour supprimer les cellules inaccessibles:

Couloirs multiples entre les pièces

En expérimentant les paramètres du générateur, j'ai trouvé que si vous ajoutez un peu de bruit entre les pièces communicantes, vous obtenez des résultats intéressants.

Voici la différence de résultats avant d'appliquer du bruit aux pièces communicantes et immédiatement après, le paramètre change d'une seule unité:



Si vous agrandissez les pièces, le résultat sera encore plus intéressant:


C'est formidable que nous ayons un accident et de belles structures surgissent, mais en même temps, la structure du graphique et les désignations des salles sont préservées, ce qui sera utile:

Génération de tuiles pour les grottes

J'ai passé la plupart de mon temps à générer des tuiles. Ce n'est pas très difficile, mais pour une implémentation correcte il faut un peu d'astuces.

Voici des exemples de résultats:


La grande chose est que vous pouvez très facilement passer d'une grotte de pierre à du sable ou de la glace:


Les prochaines étapes de génération du donjon seront l'ajout de décors et de monstres.