Dans cet article, je décrirai l'algorithme de génération procédurale des niveaux d'un donjon bidimensionnel avec une structure prédéterminée. Dans la première partie, une description générale sera présentée, et dans la seconde, la mise en œuvre de l'algorithme.
Présentation
L'algorithme a été écrit dans le cadre
d'un travail de licence et est basé sur un article de
Ma et al (2014) . Le but du travail était d'accélérer l'algorithme et de le compléter avec de nouvelles fonctions. Je suis assez content du résultat, car nous avons rendu l'algorithme assez rapide pour l'utiliser lors de l'exécution du jeu. Après avoir terminé le travail du baccalauréat, nous avons décidé de le transformer en
article et de l'envoyer à la conférence Game-ON 2018.
Algorithme
Pour créer un niveau de jeu, l'algorithme reçoit en entrée un ensemble de blocs de construction polygonaux et un graphe de connectivité de niveau (topologie de niveau). Les nœuds du graphique indiquent les pièces et les bords déterminent les connexions entre elles. Le but de l'algorithme est d'attribuer à chaque nœud du graphique la forme et l'emplacement de la pièce de sorte qu'aucune forme de pièce ne se recoupe et que chaque paire de pièces voisines puisse être reliée par des portes.
a)
b)
(c)
(d)
Les figures (c) et (d) montrent les diagrammes générés à partir du graphique d'entrée (a) et des blocs de construction (b).
À l'aide du graphique de connectivité, un concepteur de jeu peut facilement contrôler le flux du gameplay. Avez-vous besoin d'un chemin commun vers la salle du boss avec plusieurs chemins latéraux en option? Commencez simplement par le graphique du chemin, puis spécifiez quelques nœuds dans lesquels le joueur peut choisir: soit suivre le chemin principal, soit explorer le chemin latéral, avec des trésors et / ou des monstres possibles qui l'attendent. Avez-vous besoin de couper le chemin? Sélectionnez simplement les deux nœuds dans le graphique et ajoutez une courte route les reliant. Les possibilités de ce schéma sont infinies.
Exemples de graphiques d'entrée. Le chemin principal est indiqué en rouge, les chemins auxiliaires sont bleus, le chemin court est orange.L'algorithme permet non seulement aux concepteurs de jeux de gérer la structure de haut niveau des cartes générées, mais offre également la possibilité de contrôler l'apparence des pièces individuelles et la façon de les connecter les unes aux autres.
Différentes formes pour différentes pièces
J'ai mentionné la salle des boss à la fin du niveau. Nous ne voulons pas que la pièce du patron ressemble à une autre pièce ordinaire, non? L'algorithme vous permet de définir des formulaires pour chaque pièce. Par exemple, nous pouvons créer une salle au début du niveau et une salle de boss, qui devrait avoir leurs propres ensembles de formes de pièce et un ensemble commun pour toutes les autres pièces.
Deux circuits générés à partir du graphique d'entrée, dans lesquels une forme spéciale de pièces est associée à la pièce numéro 8.
Positions de porte explicitement indiquées
Imaginez que vous ayez un script de réunion de boss de haute qualité et que nous ayons besoin que le joueur entre dans la salle du boss depuis une tuile spécifique. Ou nous pouvons avoir un modèle de pièce dans lequel certaines tuiles sont réservées aux murs et autres obstacles. L'algorithme permet aux concepteurs de définir explicitement les positions de porte possibles pour les formes de pièces individuelles.
Mais parfois, l'objectif peut être le contraire. Nous pouvons créer des modèles de pièce de telle manière que les portes puissent être presque n'importe où. Pour cette raison, nous imposons moins de restrictions à l'algorithme; par conséquent, il s'exécute souvent plus rapidement, et les circuits générés peuvent sembler moins monotones et plus organiques. Pour de telles situations, il est possible d'indiquer simplement la longueur des portes et à quelle distance elles doivent être des coins. La distance par rapport aux coins est une sorte de compromis entre la disposition manuelle de toutes les portes et la présence de portes n'importe où.
a)
b)
La figure (a) illustre les différents types de placement des portes - une pièce carrée a 8 positions de porte clairement définies, et une pièce rectangulaire utilise la longueur et la distance des coins. La figure (b) montre un diagramme généré simple avec les formes des pièces de la figure (a).
Couloirs entre les chambres
Lorsque nous parlons de niveaux de donjon, nous imaginons souvent des pièces reliées par des couloirs étroits. Je voudrais supposer que les connexions sur le graphique d'entrée indiquent les couloirs, mais elles ne le sont pas. Ils garantissent simplement que tous les nœuds voisins seront directement connectés par des portes. Si nous voulons que les pièces soient connectées par des couloirs, nous devons insérer un nouveau nœud entre toutes les paires de pièces voisines et prétendre qu'il s'agit de pièces de couloir (avec certaines formes de pièces et des positions de porte données).
a)
b)
Une illustration de la façon dont nous pouvons modifier le graphique d'entrée pour ajouter des couloirs entre les pièces. La figure (a) montre le graphique d'entrée avant d'ajouter les pièces du couloir. La figure (b) montre le graphique d'entrée créé à partir de (a) en ajoutant de nouvelles pièces entre toutes les pièces adjacentes du graphique d'origine.
Malheureusement, cela complique grandement la tâche de l'algorithme, car souvent le nombre de nœuds double. Par conséquent, j'ai implémenté une version de l'algorithme qui prend en compte les couloirs, ce qui permet de réduire la diminution des performances lors de l'aménagement des salles de couloir. À l'heure actuelle, l'algorithme prend en charge soit des couloirs entre toutes les pièces, soit l'absence totale de couloirs, mais à l'avenir, je prévois de le rendre plus flexible.
Des exemples
Plusieurs schémas générés à partir de différents ensembles de blocs de construction et avec des couloirs activés.Plusieurs schémas générés à partir de différents ensembles de blocs de construction avec des couloirs activés et désactivés.Dans la deuxième partie de l'article, je parlerai du fonctionnement interne de l'algorithme.
Je travaille également sur un plugin Unity pour la génération de donjons procéduraux, qui inclura cet algorithme. Je le fais car malgré la possibilité d'utiliser cet algorithme directement dans Unity (il est écrit en C #), la commodité de travailler avec lui est loin d'être idéale. Il faut beaucoup de temps pour créer des modèles de salle sans interface graphique, et beaucoup de code est nécessaire pour convertir la sortie de l'algorithme en la représentation utilisée dans le jeu.
Comme je ne suis pas moi-même développeur de jeux, mon objectif est de rendre le plugin suffisamment bon pour que d'autres personnes puissent l'utiliser. Si tout se passe bien, j'essaierai de publier des mises à jour lorsque j'aurai quelque chose d'intéressant à dire. J'ai déjà pas mal d'idées sur le générateur lui-même et sur le test de ses capacités.
Captures d'écran du plugin Unity (le projet est en cours de développement)Partie 2. Mise en œuvre de l'algorithme
Dans cette partie, je parlerai des idées de base énoncées dans la base de l'algorithme décrit dans la première partie de l'article. Au départ, je voulais décrire les concepts de base ainsi que les principales améliorations nécessaires pour que l'algorithme soit suffisamment rapide. Cependant, il s'est avéré que même les concepts de base sont plus que suffisants pour ce poste. Par conséquent, j'ai décidé de révéler les améliorations de performances dans un futur article.
La motivation
Avant de passer à la mise en œuvre, je veux montrer le résultat de ce que nous allons faire. La vidéo ci-dessous montre 30 circuits différents générés à partir d'un graphique d'entrée et d'un ensemble de blocs de construction. L'algorithme s'arrête toujours pendant 500 ms après avoir généré le circuit, puis essaie de générer le suivant.
Comment ça marche
Le but de l'algorithme est d'attribuer la forme et la position de la pièce à chaque nœud du graphique de sorte qu'aucune pièce ne se croise et que les pièces voisines soient reliées par des portes.
Une façon d'y parvenir est d'essayer toutes les combinaisons possibles de formes de pièce et de leurs positions. Cependant, comme vous pouvez le deviner, cela sera très inefficace et nous ne serons probablement pas en mesure de générer des circuits, même sur la base de graphiques d'entrée très simples.
Au lieu de rechercher toutes les combinaisons possibles, l'algorithme calcule comment connecter correctement toutes les pièces individuelles (les soi-disant espaces de configuration) et utilise ces informations pour diriger la recherche. Malheureusement, même avec ces informations, il est encore assez difficile de trouver le bon schéma. Par conséquent, pour une étude efficace de l'espace de recherche, nous utilisons une technique d'optimisation probabiliste (dans ce cas, la simulation de recuit). Et pour accélérer davantage l'optimisation, nous divisons la tâche d'entrée en sous-tâches plus petites et plus faciles à résoudre. Cela se fait en divisant le graphique en parties plus petites (appelées chaînes) avec la création ultérieure de schémas pour chacun d'eux dans l'ordre.
Espaces de configuration
Pour une paire de polygones dans lesquels l'un est fixé en place et l'autre peut se déplacer librement, l'espace de configuration est l'ensemble des positions d'un polygone libre auquel deux polygones ne se croisent pas et peuvent être reliés par des portes. Lorsque vous travaillez avec des polygones, chaque espace de configuration peut être représenté comme un ensemble de lignes éventuellement vide et calculé par de simples outils géométriques.
a)
b)
Configurations spatiales. La figure (a) montre l'espace de configuration (lignes rouges) d'un rectangle libre par rapport à un polygone fixe en forme de L. Il détermine tous les emplacements du centre du carré où les deux blocs ne se croisent pas et ne se touchent pas. La figure (b) montre l'intersection (points jaunes) des espaces de configuration d'un carré mobile par rapport à deux rectangles fixes.
L'algorithme suivant est utilisé pour calculer l'espace de configuration d'un bloc fixe et d'un bloc libre. Nous sélectionnons un point de référence sur le bloc mobile et considérons tous les emplacements dans
, de sorte que lors du déplacement du polygone de sorte que son point de référence se trouve à cet emplacement, les blocs mobile et fixe se touchent, mais ne se coupent pas. L'ensemble de tous ces points forme l'espace de configuration de deux blocs (figure (a) ci-dessus). Afin d'obtenir l'espace des configurations du bloc mobile par rapport à deux ou plusieurs blocs fixes, l'intersection des espaces de configuration individuels est calculée (figure (b) ci-dessus).
L'algorithme utilise les espaces de configuration de deux manières. Tout d'abord, au lieu d'essayer les positions aléatoires de pièces individuelles, nous utilisons des espaces de configuration pour rechercher des positions menant au plus grand nombre possible de pièces adjacentes reliées par les portes. Pour ce faire, nous devons obtenir l'intersection maximale non vide des espaces de configuration des voisins. Deuxièmement, nous utilisons des espaces de configuration pour vérifier si toutes les paires de pièces voisines peuvent être connectées avec des portes. Cela se fait en vérifiant si la position de la pièce est à l'intérieur de l'espace de configuration de tous ses voisins.
Étant donné que les formes des pièces ne changent pas pendant l'exécution du jeu, nous pouvons pré-calculer les espaces de configuration de toutes les paires de formes de pièces avant le démarrage de l'algorithme. Grâce à cela, l'ensemble de l'algorithme est considérablement accéléré.
Schéma incrémental
Lors de la résolution d'un problème complexe, l'une des approches possibles consiste à le diviser en sous-tâches plus petites et plus simples, et à les résoudre déjà. C'est exactement ce que nous ferons avec la tâche de placer des pièces individuelles. Au lieu d'organiser toutes les pièces à la fois, nous divisons le graphique d'entrée en sous-graphiques plus petits et essayons d'en créer des diagrammes un par un. Les auteurs de l'algorithme original appellent ces sous-graphes des «chaînes» en raison du principe même de ces graphes, dans lequel chaque nœud n'a pas plus de deux voisins, et il est donc assez simple de créer leur schéma.
Le circuit de sortie final est toujours un composant connecté, il est donc inutile de connecter les composants individuels au circuit, puis d'essayer de les combiner, car le processus de combinaison peut être assez compliqué. Par conséquent, après avoir placé la chaîne, la prochaine chaîne connectée sera toujours celle qui est connectée aux sommets déjà alignés dans le circuit.
Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null; }
Pseudo-code montrant une approche incrémentale pour trouver le bon schéma.Le pseudo-code présenté ci-dessus illustre l'implémentation d'un schéma incrémentiel. À chaque itération de l'algorithme (lignes 6-18), nous prenons d'abord le dernier circuit de la pile (ligne 7) et calculons la chaîne à ajouter ensuite (ligne 8). Cela peut être fait en stockant simplement le numéro du dernier circuit ajouté à chaque circuit partiel. À l'étape suivante, nous ajoutons la chaîne suivante au circuit (ligne 9), générant plusieurs circuits détaillés et les enregistrons. Si la phase d'expansion échoue, mais aucun nouveau schéma partiel n'est ajouté à la pile, et l'algorithme doit continuer avec le dernier schéma partiel enregistré. Nous appelons cette situation une recherche de retour car l'algorithme ne peut pas étendre le schéma partiel actuel et doit revenir en arrière et continuer avec un autre schéma enregistré. Cela est généralement nécessaire lorsqu'il n'y a pas assez d'espace pour connecter des circuits supplémentaires aux sommets déjà composés dans le circuit. De plus, une recherche de retour est la raison pour laquelle nous essayons toujours de générer plusieurs schémas avancés (ligne 9). Sinon, nous n'aurions rien sur quoi revenir. Le processus se termine lorsque nous générons un circuit complet ou que la pile est vide.
(a) Graphique d'entrée
(b) Diagramme partiel
(c) Diagramme partiel
d) Aperçu complet
e) Plan complet
Schéma incrémental. Les figures (b) et (c) montrent deux schémas partiels après la planification du premier circuit. La figure (d) montre le circuit complet après expansion (b) par un deuxième circuit. La figure (e) montre le circuit complet après expansion (c) par un deuxième circuit.
Pour diviser le graphique en parties, vous devez trouver une incorporation à plat du graphique d'entrée, c'est-à-dire un dessin sur le plan dans lequel les arêtes se coupent uniquement aux extrémités. Cette pièce jointe est ensuite utilisée pour obtenir toutes les faces du graphique. L'idée principale de la décomposition est qu'il est plus difficile de créer un circuit à partir de cycles, car leurs nœuds ont plus de restrictions. Par conséquent, nous essayons d'organiser les cycles au début de la décomposition, afin qu'ils soient traités le plus tôt possible et de réduire la probabilité d'un besoin de revenir en arrière dans les étapes suivantes. La première chaîne de décomposition est formée par la plus petite face de l'attachement, et les faces suivantes sont ensuite ajoutées dans l'ordre de recherche en largeur. Si d'autres faces peuvent être sélectionnées, la plus petite d'entre elles est utilisée. Lorsqu'il n'y a plus de faces, les composants non cycliques restants sont ajoutés. La figure 4 montre un exemple de décomposition dans une chaîne, qui a été obtenue conformément à ces étapes.
a)
b)
Décomposition en chaînes. La figure (b) montre un exemple de disposition de la figure (a) sur un circuit. Chaque couleur représente une chaîne distincte. Les nombres indiquent l'ordre dans lequel les chaînes sont créées.
(c) Bonne conception partielle
d) Aperçu complet
(a) Graphique d'entrée
(b) Mauvais graphique partiel
Recherche avec retour. La figure (b) montre un exemple d'un mauvais circuit partiel, car il n'y a pas assez d'espace pour connecter les nœuds 0 et 9. Pour générer le circuit complet (d), un retour à un autre circuit partiel (c) est nécessaire.
Recuit simulé
L'algorithme de simulation de recuit est une technique d'optimisation probabiliste dont le but est d'étudier l'espace des circuits possibles. Il a été choisi par les auteurs de l'article original parce qu'il s'est avéré utile dans des situations similaires dans le passé. Lors de la mise en œuvre de l'algorithme, j'ai décidé d'utiliser la même méthode, car je voulais commencer par ce qui a déjà prouvé son efficacité pour résoudre ce problème. Cependant, je pense qu'elle peut être remplacée par une autre méthode et ma bibliothèque est écrite de telle manière que le processus de remplacement de la méthode est assez simple.
L'algorithme de simulation de recuit évalue de manière itérative de petits changements dans la configuration ou le circuit actuel. Cela signifie que nous créons une nouvelle configuration en sélectionnant au hasard un nœud et en modifiant sa position ou sa forme. Si la nouvelle configuration améliore la fonction énergétique, elle est toujours acceptée. Sinon, il y a peu de chances d'accepter la configuration de toute façon. La probabilité de prendre de mauvaises décisions diminue avec le temps. La fonction d'énergie est conçue de manière à imposer de grosses amendes aux nœuds qui se croisent et aux nœuds adjacents qui ne se touchent pas.
A est la zone d'intersection totale entre toutes les paires de blocs du diagramme. D est la somme des carrés des distances entre les centres des paires de blocs dans le graphe d'entrée qui sont voisins mais ne se touchent pas. Valeur
affecte la probabilité que le recuit simulé soit autorisé à passer à la pire configuration; ce paramètre est calculé à partir de la surface moyenne des blocs de construction.
Après avoir sélectionné un nœud à modifier, nous modifions sa forme ou sa position. Comment choisissons-nous un nouveau poste? Vous pouvez le choisir au hasard, mais cela dégradera souvent la fonction d'énergie et l'algorithme convergera très lentement. Pouvons-nous choisir une position plus susceptible d'augmenter la fonction énergétique? Vous voyez à quoi je mène? Nous utilisons des espaces de configuration pour sélectionner une position qui satisfait les limites du plus grand nombre de pièces voisines.
Ensuite, pour modifier la forme, sélectionnez simplement l'une des formes de pièce disponibles. Bien que l'algorithme n'essaie pas de décider quelle forme est la plus susceptible de nous conduire au schéma correct. Cependant, il serait intéressant d'essayer cette fonctionnalité et de voir si elle accélère l'algorithme.
List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if () { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if () { currentLayout = newLayout; } else if () { currentLayout = newLayout; } } } return generatedLayouts; }
Il s'agit du pseudo-code de la méthode responsable de la création d'un circuit séparé en simulant un recuit.
Pour accélérer l'ensemble du processus, nous allons essayer de trouver la configuration initiale basse énergie. Pour ce faire, nous organiserons les nœuds de la chaîne actuelle pour une recherche en premier, en commençant par ceux qui sont adjacents aux nœuds déjà inclus dans le schéma. Ensuite, les nœuds ordonnés sont placés un à la fois et pour eux, la position avec l'énergie la plus faible est sélectionnée dans l'espace de configuration. Ici, nous ne faisons aucun retour en arrière - c'est un processus simple et gourmand.
Vidéo bonus
La vidéo ci-dessous montre les diagrammes générés à partir du même graphique d'entrée que dans la première vidéo. Cependant, cette fois, une approche incrémentale est montrée. Vous remarquerez peut-être que l'algorithme ajoute des chaînes de nœuds un par un. On voit également qu'il existe parfois deux circuits partiels consécutifs avec le même nombre de nœuds. Cela se produit lorsque l'algorithme revient. Si la première tentative d'ajouter un autre circuit au premier circuit partiel échoue, alors l'algorithme essaie un autre circuit partiel.
Documents téléchargeables
L'implémentation de l'algorithme sur .NET se trouve dans
mon github . Le référentiel contient la DLL .NET et l'application graphique WinForms, contrôlées par les fichiers de configuration YAML.