Génération procédurale de donjons 3D à plusieurs étages

Récemment, j'ai joué à plusieurs roguelike, j'ai donc décidé d'essayer d'écrire mon propre générateur de donjon procédural. Il existe de nombreuses façons de résoudre ce problème, et j'ai choisi l'algorithme de l'auteur TinyKeep décrit ici . J'ai développé cet algorithme pour qu'il fonctionne en 3D et puisse créer des donjons à plusieurs étages.

Exemple de code publié dans le référentiel Github . Pour la démonstration, j'utilise Unity3D, mais ces concepts, bien sûr, s'appliquent à tout autre moteur.

Deux dimensions

J'ai d'abord besoin d'écrire un algorithme à deux dimensions. En général, il fonctionne de la même manière que l'algorithme TinyKeep, mais présente des différences pour créer des niveaux plus intéressants.

La scène de cet exemple s'appelle Dungeon2D. Le code correspondant se trouve dans le dossier Scripts2D.

Algorithme

Le monde est divisé en une grille rectangulaire. Je suppose qu'une unité suffira pour indiquer le couloir. Dans une partie complète, 1 unité d'Unité peut correspondre, par exemple, à 5 mètres. Pour la grille, j'ai choisi une taille de 30 × 30.

1. Nous organisons les chambres de manière arbitraire, mais afin qu'elles ne se chevauchent pas. L'emplacement n'a pas d'importance, donc dans cet exemple, je leur donne juste un emplacement et une taille aléatoires. De plus, de chaque côté, j'ai ajouté un tampon de 1 unité de large (pour que les pièces ne se touchent pas), mais ce n'est pas nécessaire pour que l'algorithme fonctionne.


Les rectangles rouges sont des pièces

2. Créez un graphique de triangulation Delaunay pour les pièces. J'ai utilisé l'algorithme Bower-Watson pour cela. Il existe de nombreuses implémentations de cet algorithme dans de nombreux langages, j'en ai choisi une qui sera facile à porter en C #.


Triangulation de Delaunay

3. Créez un arbre couvrant minimum (MST) à partir de la triangulation. J'ai utilisé l'algorithme Prim pour cela.


Couloirs MST

4. Nous créons une liste de couloirs, en commençant par chaque bord de l'arbre de l'étape 3. L'arbre contient toutes les pièces, donc le chemin vers chaque pièce est garanti d'exister. Ajoutez au hasard les bords de la triangulation à la liste. Nous allons donc créer plusieurs boucles dans les couloirs. Dans mon code, j'ai utilisé la probabilité d'ajouter chaque bord à 12,5%.


Couloirs après l'ajout de plusieurs arêtes au MST. Notez que des boucles sont apparues.

5. Pour chaque couloir de la liste, utilisez l'algorithme A * pour trouver les chemins depuis le début du couloir jusqu'à la fin. Après avoir trouvé un chemin, il change l'état du monde afin que les futurs couloirs puissent toujours contourner les couloirs existants.

La fonction de coût que j'ai utilisée rend moins coûteux de se déplacer le long d'un couloir coupé dans une itération différente que de créer un nouveau couloir. Cela stimule un algorithme de recherche de chemin pour combiner des couloirs traversant un espace. Se déplacer dans la pièce est possible mais coûteux. Par conséquent, dans la plupart des cas, l'algorithme de recherche de chemin préfère éviter les salles.


Les rectangles bleus sont des couloirs

Voici quelques exemples d'un algorithme qui utilise de vraies ressources graphiques (les ressources et le code pour leur placement ne sont pas dans le référentiel):

Trois dimensions

Après avoir créé un générateur de donjon 2D fonctionnel, j'ai commencé à le transférer en 3D. Tous les algorithmes utilisés ont des versions 3D, donc ça devrait être simple, non?

Algorithme

La grille a maintenant une taille de 30x5x30.

1. Le premier changement a été la génération de pièces en 3D. Ce changement est insignifiant.


Veuillez noter que les chambres peuvent avoir plusieurs étages.

2. On retrouve alors la triangulation 3D de Delaunay de ces pièces, ou plutôt la tétraédrique Delaunay. Après avoir recherché des informations sur les requêtes «triangulation Delaunay 3D» ou «tétraédrique Delaunay», j'ai trouvé de nombreux articles de recherche, mais pas un seul exemple de code.

Le plus proche de ce dont j'avais besoin était l'implémentation de la triangulation CGAL 3D, mais elle posait deux problèmes. Tout d'abord, ce module n'était disponible que sous licence GPL. La seconde - le code était tellement modèle et obscur que je ne pouvais pas comprendre où l'algorithme était implémenté.

Au final, j'ai dû étudier moi-même le principe de l'algorithme de Bower-Watson pour le changer moi-même. Je ne comprends toujours pas vraiment pourquoi les cercles circonscrits sont si importants, mais au moins j'ai pu réécrire l'algorithme avec les sphères décrites en utilisant cette page avec Wolfram MathWorld. Comme il s'agit principalement d'opérations avec des matrices 4x4, j'ai affecté tout le travail complexe au type Matrix4x4 d'Unity3D.

Cette nouvelle version est située dans Scripts3D/Delaunay3D.cs , au cas où quelqu'un aurait besoin d'un code facile à comprendre avec une licence MIT.


C'est difficile à remarquer, mais au lieu d'un triangle à trois sommets, l'algorithme crée maintenant un tétraèdre à 4 sommets. Au moins un de ces pics sera situé à un autre étage, sinon le tétraèdre sera dégénéré. Cela donne à l'étape de recherche de nombreuses possibilités de se déplacer entre les étages.

3 et 4. Les bords de l'étape 2 avec des changements complètement triviaux peuvent être passés à l'algorithme Prim.


Couloirs 3D-MST


Couloirs avec plusieurs nervures ajoutés à nouveau

5. Les difficultés commencent lorsqu'elles sont implémentées dans l'algorithme 3D A *. La version 2D est terriblement simple, c'est une implémentation standard de A *. Pour le transférer en 3D, j'ai besoin d'ajouter la possibilité à l'algorithme de recherche de chemin pour monter et descendre et connecter des pièces à différents étages. J'ai décidé de relier les étages non pas à des escaliers verticaux, mais à des volées d'escaliers.

Voilà le problème. Un escalier est plus compliqué que de simplement monter. Pour se déplacer verticalement, les escaliers doivent se déplacer horizontalement. Autrement dit, elle a une ascension et une envergure . Jetez un œil à l'image ci-dessous. La cellule actuelle est un carré bleu uni. Les voisins possibles sont des cases vides. L'algorithme de recherche de chemin ne peut pas se déplacer vers une cellule directement au-dessus de la cellule actuelle. Au lieu de cela, il devra se déplacer à la fois horizontalement et verticalement.


Vue latérale. Vous pouvez créer des nœuds sur les côtés, mais pas un nœud sur le dessus.

Pour créer un algorithme de recherche de chemin pour un escalier, je devais sélectionner sa forme. Un rapport hauteur / longueur de 1: 1 serait trop raide, j'ai donc choisi un rapport de 1: 2. Pour chaque unité de mesure verticale, l'échelle déplace deux unités horizontales. De plus, pour que le personnage soit placé, il doit y avoir un espace au-dessus de l'escalier, c'est-à-dire que deux cellules au-dessus de l'escalier doivent également être ouvertes. En général, un escalier occupe quatre cellules:


Escalier et espace libre au-dessus

Il devrait également y avoir un couloir en haut et en bas des escaliers. L'algorithme de recherche de chemin ne doit pas pouvoir arriver aux escaliers par le côté ou par la direction opposée. Il sera peu pratique et étrange si l'escalier s'écrase dans le couloir, comme illustré ci-dessous.



Autrement dit, le format de l'escalier devrait ressembler à l'image ci-dessous. L'algorithme de recherche de chemin doit garantir l'existence de couloirs dans deux carrés bleus.


L'escalier commence par un carré bleu uni et monte d'un étage.

L'algorithme de recherche de chemin doit se déplacer du début au point final en une seule étape. Cela signifie qu'il doit être décalé de 3 unités horizontalement et 1 unité vers le haut ou vers le bas. L'algorithme A * est conçu pour passer à chaque étape d'un nœud à l'autre. Pour créer l'escalier, je dois "sauter" quatre cellules de l'escalier.

La difficulté est qu'en quelque sorte j'ai besoin d'obtenir l'algorithme pour contourner les escaliers qu'il crée. Je ne peux pas les ajouter à l' ensemble fermé A *, car alors à travers ces cellules, un autre chemin d'une autre direction ne pourra pas aller. Mais je ne peux pas les laisser non plus, car l'algorithme de recherche de chemin pourra alors se déplacer le long de l'échelle nouvellement créée, créant les situations indésirables illustrées ci-dessus.

La solution était que chaque nœud devrait garder une trace de tous les nœuds précédents sur son chemin. Ensuite, lors de l'examen d'un nœud voisin, il sera rejeté s'il fait référence au chemin du nœud actuel. Le couloir à la fin de l'escalier contiendra toutes les cellules occupées par l'escalier, le nœud au début de l'escalier et tous les nœuds sur son chemin, et ainsi de suite jusqu'au tout début. L'algorithme de recherche de chemin peut créer un autre chemin passant par les escaliers, car le deuxième chemin ne connaîtra pas les escaliers.

Le comportement décrit ci-dessus n'est nécessaire que pour quelques chemins potentiels dans le même appel de fonction de chemin. Pour générer tous les couloirs, il reste encore de nombreux défis à relever pour trouver le chemin. Les itérations suivantes contourneront simplement les escaliers existants comme auparavant.

À ce stade, l'algorithme n'est plus complètement A *. Il y a trop de cas particuliers pour la comptabilité des escaliers. La nécessité de vérifier l'intégralité du chemin précédent à chaque étape est un processus coûteux. Une implémentation naïve a suivi tous les nœuds avant le début, les lisant comme une liste chaînée. Il faudrait ensuite O (N) pour vérifier le chemin de chaque nœud voisin.

J'ai choisi cette implémentation: stocker une table de hachage dans chaque nœud, dont les clés sont les nœuds précédents. Grâce à cela, la vérification du chemin est effectuée dans O (1), cependant, lors de l'ajout d'un nœud au chemin, la table de hachage doit être copiée, et c'est O (N). J'ai choisi cette méthode car j'ai réalisé que l'algorithme lira les chemins plus souvent que de les changer.

Quoi qu'il en soit, la complexité globale sera d'environ O (N ^ 2), bien que je ne sache pas comment l'analyser correctement. Cette modification est le principal «goulot d'étranglement» de l'algorithme de génération de donjon.

Après avoir effectué toutes ces modifications, le résultat était le suivant:


Les rectangles verts sont des escaliers


Les chemins des générateurs peuvent être simples ...


... ou compliqué

Voici à quoi ressemble un donjon 3D avec de vraies ressources graphiques:


Donjon à plusieurs étages


L'algorithme de génération de donjon est capable de créer des comportements émergents intéressants.


Deux escaliers forment un escalier à double largeur


Échelle triple largeur difficile à expliquer


Un chemin descendant sur deux étages peut créer deux escaliers avec une plate-forme au milieu


Lorsque plusieurs chemins passent côte à côte, les couloirs peuvent être assez grands


Deux escaliers descendent à un étage

Conclusion

La partie la plus difficile du projet a été la création des algorithmes nécessaires à la version 3D. Je n'ai pas pu trouver une seule implémentation de la triangulation 3D de Delaunay, donc j'ai dû le faire moi-même. Les exigences de l'algorithme de recherche de chemin étaient très spécifiques, donc je l'ai fait moi-même aussi.

Mais le travail en valait la peine. Les donjons créés par cet algorithme sont intéressants et peuvent devenir la base d'un bon jeu.