Diablo 1 est le roguelike hack and slash classique de 1996. Ce fut l'une des premières tentatives réussies pour initier les masses au roguelike, qui avait jusque-là des graphismes de niche sous la forme d'art ASCII. Le jeu a engendré plusieurs suites et de nombreuses simulations. Elle est connue pour son atmosphère sombre et sombre, s'épaississant lorsque le joueur descend dans les donjons situés sous la ville de Tristram. Ce fut l'un des premiers jeux avec une génération de cartes procédurales pour moi, et la possibilité de générer de tels niveaux crédibles m'a choqué.

J'ai récemment découvert qu'en raison de la découverte de divers fichiers avec des symboles de débogage, plusieurs fans du jeu ont pris la tâche de faire de l'ingénierie inverse du code source pour le nettoyer et comprendre à quoi ressemblait le code écrit par les développeurs. C'est ainsi qu'a commencé mon excursion d'une semaine dans l'étude de la façon dont le développeur principal David Brevik a créé ces niveaux. Peut-être à cause de cela, la magie du jeu s'est partiellement effondrée pour moi, mais j'ai appris de nombreuses techniques qui seront utiles aux développeurs de jeux similaires, donc dans cet article je les partagerai.

Merci à David Brevik et à l'équipe de Blizard North pour avoir créé un jeu aussi incroyable, ainsi qu'à galaxyhaxz et à l'équipe Devilution pour leur travail incroyable sur la restauration du code source lisible du projet.

Présentation

Diablo est un jeu composé de tuiles isométriques. Le jeu se compose de 4 étapes, chacune ayant 4 niveaux. Étapes du jeu: cathédrale, catacombes, grottes et enfer. Il existe également plusieurs niveaux fixes, par exemple la ville de Tristram, que je ne considérerai pas dans l'article. Diablo a des procédures de génération de niveaux distinctes pour chacune des 4 étapes, je vais donc d'abord parler de leurs fonctionnalités, puis considérer séparément le fonctionnement de chacune des étapes.

Je voulais seulement savoir comment les niveaux étaient générés. Pour en savoir plus sur les quêtes, les monstres, etc. Je recommande de lire le Guide de Jarulf sur Diablo et Hellfire , qui décrit ces aspects en détail.

Caractéristiques Générales

Bien que chaque étage ait son propre générateur de niveau, ils ont tous des caractéristiques communes.

Donjons et tuiles

Chaque niveau du jeu est généré pour remplir une grille de 40 x 40 tuiles. L'axe X correspond au sud-est et l'axe Y correspond au sud-ouest.

Ces tuiles sont utilisées uniquement pour les tâches de génération de niveau. Après avoir créé un niveau, chaque tuile est divisée en 4 "fragments de donjon", qui sont rendus à l'écran.


Cette grille plus détaillée est utilisée pour déterminer les tuiles traversées et permet également une réutilisation plus efficace de la mémoire graphique. Plus tôt, j'ai écrit sur les schémas de division des tuiles .

Cela signifie que la carte Diablo standard se compose de plus d'une centaine de tuiles, dont beaucoup sont des variantes mineures d'autres, pour prendre en compte toutes les façons possibles de les connecter. Nous en reparlerons plus tard.

À ma grande surprise, contrairement aux autres jeux de cette série, les cartes de donjon ne sont pas composées de blocs pré-créés. Presque tout est créé à l'aide d'algorithmes.

Processus en plusieurs étapes

Chaque procédure de génération de donjon est divisée en deux étapes. La pré-génération ne concerne pas du tout le choix des carreaux. Il génère simplement un tableau dans lequel des tuiles praticables, des tuiles dans lesquelles se trouvent des portes et d'autres détails de haut niveau sont marqués. À la deuxième étape, ce vide de donjon est converti en un tableau de tuiles, après quoi la génération est effectuée et des modifications sont apportées en tenant compte de ces tuiles.

Cela devrait être incroyablement pratique pour le concepteur. Vous pouvez expérimenter avec un plan d'étage complètement indépendant du choix des carreaux et du style. Mais dans de nombreux cas, ils sont interconnectés, offrant un sentiment de niveau plus holistique.

Toutes les étapes de la création d'ébauches de donjon commencent par un niveau rempli de «dureté» solide, après quoi les différentes parties du niveau se transforment récursivement en carreaux de sol. Je vais en discuter plus en détail ci-dessous.

Fragments finis

Les fragments finis sont des blocs de niveau pré-créés qui sont simplement insérés dans un niveau généré aléatoirement. Ils sont utilisés pour la plupart des quêtes de jeu. À chaque niveau, il ne peut y avoir qu'un seul fragment fini, dont l'emplacement à chaque étape est sélectionné séparément.


Butcher's Den est l'un des premiers extraits prédéfinis trouvés dans le jeu.

Mini ensembles

Les mini-kits sont une autre façon d'insérer du contenu dans un niveau de contenu pré-créé. Ce sont de petits morceaux, généralement d'environ 3 × 3, insérés au hasard dans le donjon. Il existe un schéma d'appariement de motifs simple, grâce auquel ils n'apparaissent qu'aux bons endroits. Souvent, ils sont codés avec des exigences supplémentaires, par exemple, les mini-ensembles ne peuvent pas être placés à proximité les uns des autres, ils ne peuvent pas se chevaucher avec des fragments prêts à l'emploi, etc. Certains mini-kits recherchent et remplacent toujours, tandis que d'autres le font avec une probabilité fixe.

Les mini kits Diablo sont utilisés à de nombreuses fins différentes. Ils sont utilisés pour placer de grands objets à partir de carreaux, tels que des escaliers, pour corriger des combinaisons de carreaux qui ne se connectent pas bien les uns aux autres et pour ajouter des variations aléatoires aux carreaux.

Salles thématiques

Les chambres à thème sont de petits espaces délimités par un mur et une porte. Habituellement, en eux, de manière aléatoire, certains objets prédéterminés sont localisés. Par exemple, les bibliothèques ont toujours une bibliothèque avec deux bougies de chaque côté, plusieurs serre-livres aléatoires et des monstres. Monster Lairs contient de nombreux monstres et un élément aléatoire, etc.

Aux niveaux de l'étage cathédrale, le générateur crée des pièces adaptées, reconnues par le remplissage et réutilisées. À d'autres étapes, l'algorithme trouve des espaces ouverts dans lesquels des murs et une porte sont dessinés pour créer des pièces.

Chaque type de salle thématique a certaines exigences quant à la taille et au stade auquel elle est générée.

Remplacement des carreaux

Certaines cartes ont une adaptation spéciale des tuiles, mais elles ont toutes une caractéristique commune: certaines tuiles peuvent être remplacées par des variations similaires. Les tuiles les plus standard (par exemple, les sols et les murs plats) ont diverses variations, ce qui réduit la monotonie du niveau. Les remplacements de carreaux ne sont jamais réutilisés côte à côte.

Comparaison des modèles et des «corrections»

Comme mentionné ci-dessus, les mini-ensembles sont utilisés comme mécanisme de recherche et de remplacement qui corrige les défauts du générateur. Mais à la plupart des étapes, il existe des procédures qui détectent et résolvent des problèmes plus spécifiques. Je n'entrerai pas dans les détails, car il n'y en a qu'un tas. Il suffit de dire que Diablo est assez bogué, et plus près de la sortie, il est devenu évident qu'il serait plus facile d'ajouter la reconnaissance de problèmes spécifiques que d'éliminer leurs causes fondamentales.

L'un des «correctifs» les plus courants était le «verrouillage»: il vérifiait s'il était possible de parcourir tout le donjon et recommençait la génération si ce n'était pas le cas.

Quêtes

La plupart des quêtes ont été créées à l'aide de fragments prêts à l'emploi, mais certains ont utilisé leur propre logique. Par exemple, Zhar le fou génère des salles de bibliothèque thématiques, l'entrée de l'eau empoisonnée est générée par mini-numérotation et Anvil of Fury a un code de génération de niveau spécifique. Je n'entrerai pas dans les détails, mais le code est plein de vérifications similaires pour les quêtes.

La cathédrale

La cathédrale est probablement la plus emblématique des scènes de Diablo. Il se caractérise par de longues rangées d'arches gothiques, des pièces exiguës et de nombreux goulots d'étranglement en forme de portes. Voyons comment il a été créé.

Donjon vierge

La première chose que fait l'algorithme est de dessiner le cœur de la carte. Il sélectionne au hasard jusqu'à trois pièces 10 × 10 dans des positions prédéterminées le long de l'axe central X ou Y. Un large couloir reliant les pièces est également tracé le long de l'axe. S'il y a un fragment fini au niveau, alors il est toujours situé au centre de l'une de ces pièces. Ces salles de donjon centrales sont marquées comme inadaptées aux nouveaux murs, de sorte qu'elles restent toujours de grands espaces ouverts.

Toutes les autres pièces sont générées par la technique de bourgeonnement récursif dans une fonction appelée L5roomGen , qui est déclenchée dans chacune de ces pièces, et en sélectionnant un axe.

Fonction L5roomGen

• Elle passe le rectangle de la pièce d'origine, à partir de laquelle vous devez commencer à bourgeonner, ainsi que l'axe préféré.
• Avec une probabilité de 1/4, l'axe préféré change.
• La taille aléatoire de la nouvelle salle est sélectionnée, avec 2, 4 ou 6 tuiles de chaque côté.
• Pour chaque côté de la pièce d'origine le long de l'axe sélectionné (c'est-à-dire SE / NS pour X, SW / NE pour Y):
  
  • Le rectangle de la nouvelle pièce s'aligne avec le centre du bord de la pièce d'origine
  • La vérification est faite qu'avant cela il n'y avait rien de dessiné et nous n'avons pas atteint la fin de la carte. Les murs nécessitent une bordure d'une tuile.
  • Si la vérification réussit, une salle est tirée.
• Pour chaque pièce à L5roomGen , L5roomGen est appelée récursivement, qui passe la nouvelle pièce et l'axe opposé à celui utilisé précédemment.

En fin de compte, cette procédure commence par plusieurs pièces découpées à l'intérieur des carreaux "solides", puis colle à plusieurs reprises de nouveaux rectangles pour découper de nouvelles zones praticables. A ce stade, toutes les «pièces» sont ouvertes d'un côté, car chaque nouvelle pièce est située directement à côté de la précédente, sans laissez-passer pour la pose des murs.

Le générateur calcule ensuite le nombre de tuiles traversées générées. S'il est inférieur au seuil minimum, qui augmente avec chaque niveau, le donjon est détruit et la tentative de génération est exécutée à nouveau.

Donjon

Jusqu'à présent, l'algorithme n'a que les tuiles "solides" et de genre. Nous devons les remplacer par de vrais carreaux de mur. Pour cela, Diablo utilise l'algorithme des carrés de marche, que j'ai décrit dans un article précédent .

Cependant, le jeu utilise sa variation inhabituelle. L'ensemble de tuiles de la cathédrale contient des murs, mais ils sont toujours situés sur le bord éloigné de la tuile. Par conséquent, il y a une tuile avec un mur sur le bord nord-est, mais il n'y a pas de tuile avec un mur sur le bord sud-est. Pour créer des murs sur d'autres côtés, vous devez trouver une tuile «solide» qui a un mur supplémentaire qui s'étend vers l'extérieur à partir de la bordure de la tuile. Cela semble étrange, mais en fait, il est très pratique pour trier les murs par profondeur.


Pour y faire face, Diablo saute certains murs pendant la phase des cubes de marche:


Des murs supplémentaires sont ajoutés ultérieurement, au stade des «correctifs». Je pense que cette procédure simple affecte le plus le "style" de la cathédrale. Étant donné que les murs opposés sont attachés à des carreaux solides, dans le cas de deux pièces séparées par un carreau mural, le mur opposé ne sera tout simplement pas créé. Cela signifie que les séparateurs entre les pièces sont «plus minces» que ce que vous pouvez généralement obtenir dans la résolution à laquelle les carrés de marche sont exécutés.

Après avoir placé les murs principaux, le générateur ajoute quatre colonnes indépendantes à chacune des pièces centrales et une colonnade d'arches pour le couloir central. Cela vous permet de donner à la cathédrale un sens du design plus réfléchi que les autres niveaux, et aide également les joueurs à naviguer.

Le générateur ajoute ensuite au hasard des murs de séparation. Les murs de séparation vont toujours directement le long de l'axe d'un mur à l'autre. Ils partent des coins, de sorte que les zones sont magnifiquement divisées en pièces. Dans 25% des cas, un mur est une série d'arcs, dans 25% des cas, c'est une série d'arcs avec une grille bloquant l'entrée, et dans tous les autres cas, c'est un mur plein. Dans le cas de grilles et de murs solides, quelque part le long du mur de séparation, une porte ou une arche est ajoutée au hasard pour rendre l'espace praticable.

La procédure de remplissage détecte les pièces à thème potentielles.

Des escaliers sont placés pour se connecter à d'autres niveaux. S'il est impossible de les placer, la tentative de génération du donjon recommence.

Quant à l'agencement des mini-sets, "fix" et remplacements, je ne les examinerai pas en détail. Surtout, j'adore le mini-kit PANCREAS1, qui a 1% de chances de placer un tas de chair ensanglantée sur le carrelage. À la fin, 5 à 10 objets lampes sont placés dessus pour décorer le donjon.

Catacombes

Contrairement à la cathédrale, qui semble être un bâtiment conçu, les catacombes se sentent beaucoup plus spontanées. Ils se caractérisent par des pièces carrées reliées entre elles par de nombreux couloirs sinueux. Dans de nombreux endroits, au lieu de portes, de grandes ouvertures sont situées. augmentant la probabilité que le joueur soit entouré de nombreux ennemis.

L'algorithme de génération le plus complexe du jeu a été utilisé pour générer des catacombes. Je soupçonne que le manque de temps a contraint les développeurs à appliquer des solutions plus simples dans les étapes suivantes.

Donjon vierge

La procédure pour créer un vide de donjon pour les catacombes est assez unique. À toutes les autres étapes, il existe une seule valeur booléenne indiquant la présence ou l'absence de sexe (plus un ensemble de bits pour des détails supplémentaires). Les catacombes stockent le donjon vierge sous la forme d'une carte ASCII, presque comme un roguelike classique. Et cela n'est pas particulièrement surprenant étant donné l' admission de David Brevik selon laquelle il s'est inspiré de Diablo d'Angband .

Le générateur de pièce principale est à nouveau un algorithme récursif, mais cette fois une partition récursive. La fonction CreateRoom appelée pour toute la zone du donjon de 40 × 40 moins 1 tuile de bordure.

Fonction CreateRoom

• La fonction CreateRoom passe un rectangle indiquant la zone à l'intérieur de laquelle vous souhaitez générer des pièces. Des détails sont également transmis à la fonction concernant la pièce d'origine (initialement nulle)
• Si la zone est trop étroite, la fonction est quittée.
• Une taille aléatoire est sélectionnée pour la pièce de 4 à 9 tuiles de chaque côté, en tenant compte de la taille maximale de la zone dans laquelle vous souhaitez placer la pièce.
• Dans la zone, une position aléatoire est sélectionnée pour placer la pièce.
• La pièce est rendue sur une carte ASCII. Sur la figure, le symbole '.' les carreaux de sol sont indiqués, le symbole '#' est le mur d'enceinte et les lettres 'A' , 'B' , 'C' et 'E' sont les quatre coins.
• Si une pièce a une pièce source:
  
  • Une tuile aléatoire est sélectionnée aux bords les plus proches des pièces originales et nouvelles.
  • Ces informations sont enregistrées dans la liste des couloirs, qui sera utilisée ultérieurement.
• Les parties restantes de la zone, à l'exception de la pièce actuelle, sont découpées, créant quatre rectangles.
• La taille de chaque rectangle est réduite de deux tuiles pour créer un espace entre les pièces, puis la fonction CreateRoom est appelée récursivement, la région pour laquelle ce rectangle est utilisé et la pièce créée comme source.

S'il y a un fragment fini sur la carte, il sera toujours dans la première pièce créée par CreateRoom, et ses dimensions sont faites de sorte que ce fragment y soit placé.

Après avoir appelé CreateRoom obtenons un tableau ASCII similaire à celui montré ci-dessous (merci nomdenom pour l'avoir extrait du code):

 A##B #..# A####B #..# #....# #..# #....# C##E #....# C####EA#####B #.....# #.....# A########B #.....# #........# #.....# #........# C#####E #........# A#B #........# #.# #........# #.# #........# #.# #........# #.# #........# #.# C########E #.# #.# A#BC#E #.# A####B #.# #....# #.# #....# #.# #....# #.# C####E #.# #.# A#####BC#E #.....# A###B #.....# #...# #.....# C###E #.....# C#####E 

Dans ce cas, la pièce «racine», créée à l'origine, était la plus basse.

Les informations sur le couloir précédemment collectées sont ensuite appliquées. Une ligne est tracée entre chaque paire de points enregistrée. Lorsqu'il traverse un mur, 'D' écrit et lorsqu'il traverse une tuile pleine, ',' . Les couloirs ont une largeur aléatoire: 1, 2 ou 3. Les tuiles d'angle sont utilisées pour faciliter la navigation.

Si les portes sont adjacentes à une autre porte, elles sont ignorées et les couloirs peuvent se chevaucher, ce qui vous permet de masquer la simplicité du générateur.

Après avoir enregistré tous les couloirs, la carte ASCII est effacée. Les tuiles d'angle deviennent des tuiles murales, et les tuiles ' ' côté de ',' deviennent également des murs. Enfin, les caractères ',' sont remplacés par les caractères '.' . Nous obtenons donc le plan du donjon illustré ci-dessous.

 #### #..# ###### #..# #....# #..# #....# #D## #....# #.# #D#### ##D#### #..# #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# #........# ### #.##D#### #........# #.### #.##...# #........###.D.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# ###D#######..#.# #.##...# #.......#..#.# #.###D## ###.....#..### #.# #.# #######D##.# #.# #.# #....#.# #.# #.# #....D.# #.# #.# #....###### #.# #.# ##D####....## #.# #.# #...........# #.# #.# ####....###D####.# ### ######.....##.# #####.D.....##.# #...D.#.....D..# #####.#.....#### ######### 

Comme vous pouvez le voir, cette procédure peut laisser beaucoup d'espace vide sur la carte. Par conséquent, la prochaine étape du générateur consiste à «combler les vides». Il recherche toutes les sections de murs adjacentes auxquelles des rectangles de sol supplémentaires peuvent être collés. Les rectangles peuvent avoir au moins 5 × 5 et pas plus de 12 × 14.

Le remplissage du vide se poursuit jusqu'à ce qu'un minimum de 700 tuiles soit obtenu, ou que la limite de nouvelle tentative soit atteinte. Si le générateur n'a pas atteint 700 tuiles, la génération du donjon commence à zéro.

Cela nous donne le vide du donjon illustré ci-dessous.

  ########## #........# ########### #........# #.........# #........# #.........# #........# #.........# #### #........# #.........# #..# #######..###.........# #..# #..............# #..# #..............# #D## #..............# #.# #D####.........# ##D#### #..# ########### #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# ########........# ### #.##D#### #...............# #.### #.##...# #...............###.D.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #......###D#######..#.# #.##...# #......# #.......#..#.# #.###D## #......# ###.....#..### #.# #.# #......#########D##.# #.# #.# #.........# #....#.# #.# #.# #.........# #....D.# #.# #.# #.........# #....###### #.# #.# #.........# ##D####....## #.# #.# #.........# #...........# #.# #.# #.........# ####....###D####.# ### #.........# ######.....##.# #.........# #####.D.....##.# #.........# #...D.#.....D..# ########### #####.#.....#### ######### 

Donjon

Encore une fois, les catacombes sont différentes de la formule de niveau standard. Au lieu de l'algorithme des carrés de marche (qui attribue des tuiles sur la base de 2 × 2 carrés du vide de donjon), il utilise sa propre procédure de correspondance de motifs, qui examine chacun des rectangles 3 × 3 du vide de donjon et sélectionne la tuile correspondante pour le donjon. Les motifs déterminent ce que doit être chaque tuile de donjon: un mur, un sol, une porte, une tuile pleine ou une combinaison de ceux-ci. Je ne comprends pas très bien pourquoi.

Le reste de la fonction vous semblera familier de Cathedral. Des escaliers de haut en bas sont placés sur la carte, le donjon est vérifié pour la possibilité de passage complet, et diverses corrections sont également effectuées. Comme décrit dans la section Caractéristiques générales, des pièces sont insérées, suivies de nombreux mini-ensembles et remplacements de tuiles.

Je pense que les mini-sets affectent en quelque sorte les portes, mais ils sont assez ennuyeux à lire sans outils, donc je ne me suis pas plongé dans ce sujet.

Grottes

Les niveaux des grottes sont remplis de vastes espaces ouverts et de rivières de lave. Les murs de cette zone sont rugueux et ondulés. Les seuls éléments rectangulaires ici sont des échafaudages en bois, apparemment apparus plus tard que les grottes elles-mêmes.

Cette étape est l'une des plus belles du jeu grâce à la lave animée. On sent qu'il est très différent des niveaux précédents constitués de pièces. Par conséquent, j'ai été très surpris que la majeure partie de la génération soit modélisée selon les principes de la scène de la cathédrale, et les cartes aient un aspect plus «grotte» en utilisant des astuces délicates.

Donjon vierge

La création d'un niveau de grotte commence par une pièce aléatoire 2 × 2 située quelque part près du centre de la carte. Le générateur appelle ensuite la procédure DRLG_L3CreateBlock pour chaque bord de ce bloc.

Lorsque vous dessinez des rectangles à ce niveau, le remplissage normal n'est pas utilisé. Les intérieurs sont toujours solides, mais chaque carreau sur la bordure a 50% de chances de devenir un sol, sinon il reste solide.

Procédure DRLG_L3CreateBlock

• Cette fonction obtient le bord du rectangle, c'est-à-dire point de départ, direction et longueur.
• La taille du bloc nouvellement créé est sélectionnée dans la plage de 3-4 pour chaque côté.
• Le nouveau bloc est placé de manière aléatoire par rapport au bord d'entrée.
• S'il n'y a pas assez d'espace pour dessiner un bloc, la sortie est effectuée.
• Le bloc est dessiné.
• Avec une probabilité de 1/4, la sortie est exécutée.
• DRLG_L3CreateBlock est appelé DRLG_L3CreateBlock pour trois arêtes, en plus de celle d'où nous venons.

Bien que cette procédure soit similaire à L5roomGen , l'utilisation d'une taille de bloc beaucoup plus petite et le dessin de bordures grossières lui donnent un aspect beaucoup plus organique. De plus, il ne comprend pas de bordure de 1 tuile pour les murs, par conséquent, contrairement aux générateurs précédents, il peut créer des boucles.

Après avoir créé une ébauche de la forme du donjon, le générateur applique les procédures d'érosion:

• Tout d'abord, il trouve des zones de tuiles 2 × 2 avec des tuiles solides diagonalement opposées. Il est souvent difficile de travailler avec de telles formations lors de l'exécution de carrés de marche, donc l'une des tuiles solides est remplacée au hasard par le sexe.
• Tous les carreaux simples solides entourés de 8 carreaux de sol sont remplacés par un carreau de sol.
• Toutes les sections de murs longues et droites sont rendues rugueuses au hasard en remplaçant 50% des murs par des carreaux de sol.
• Les diagonales des tuiles continues sont éliminées à plusieurs reprises.

Toutes ces procédures ajoutent plus de carreaux de sol, de sorte que la carte devient plus ouverte.

S'il contient moins de 600 tuiles de sol, la carte est régénérée.

Donjon

Les blancs de donjon sont convertis en tuiles à l'aide de carrés de marche. Contrairement à la cathédrale et aux catacombes, le jeu de tuiles est beaucoup plus pratique ici et contient presque toutes les combinaisons nécessaires pour les carrés de marche. Il n'y a pas de carreaux pour les murs diagonalement opposés, mais ils ont été éliminés lors de la phase de fabrication, ils n'apparaissent donc jamais.

Ensuite, comme d'habitude, il existe de nombreux mini-sets. Le code a plusieurs mini-ensembles qui définissent une section séparée des murs et la remplacent par des stalagmites et des planchers, ce qui augmente l'ouverture des espaces.

Des lacs de lave sont ajoutés. L'algorithme recherche une section de mur adjacente à l'aide du remplissage . S'il parvient à trouver une section de murs / carreaux solides de moins de 40 carreaux complètement entourée de carreaux de sol, alors ils sont remplacés par de la lave. Si le lac de lave est introuvable, la génération du donjon recommence.


Un mur 3 × 3 se transforme en un lac de lave

Ensuite, plusieurs rivières de lave sont ajoutées. Le générateur fait plusieurs tentatives pour dessiner une rivière commençant au lac de lave et se terminant au mur. Les exigences suivantes sont imposées à la rivière: elle ne doit pas se traverser, la rivière a une longueur de 7 à 100 tuiles et il doit y avoir un endroit approprié pour le pont. La tuile pont garantit que la carte entière reste praticable. S'il y a de l'espace sur la carte, jusqu'à quatre rivières peuvent être ajoutées.

Ensuite, des chambres à thème sont placées. À ce stade, les murs des salles thématiques sont des clôtures en bois, à travers lesquelles vous ne pouvez pas passer, mais vous pouvez regarder. Les clôtures en bois sont également utilisées dans les deux procédures suivantes. Le premier met une clôture sur toutes les sections restantes des murs, ayant des sections droites assez longues. Le second dessine une ligne de clôtures sur la carte, d'un mur à l'autre, puis insère la porte. Contrairement à la procédure de génération d'une cathédrale, il ne cherche pas de coins pour commencer à créer ces murs.

L'enfer

L'enfer est la dernière étape de Diablo. Dans ce document, l'accent est déjà mis sur les monstres, et la conception des niveaux passe par la route. Cette scène a le plus petit ensemble de tuiles de tous, et la plupart est utilisée pour les escaliers et pentagrammes énormes. Les niveaux infernaux se composent généralement de plusieurs pièces carrées et ont une disposition symétrique.

Donjon vierge

La génération de l'enfer commence avec une pièce aléatoire de 5-6 tuiles de chaque côté (plus si elle a un fragment prêt à l'emploi pour la quête), puis le même bourgeonnement récursif est appliqué comme dans la cathédrale. Cependant, la génération est limitée à 20 × 20.

Un couloir vertical et horizontal est ajouté, tendu jusqu'au bord de la zone 20 × 20.

Ensuite, le vide du donjon est mis en miroir horizontalement et verticalement pour obtenir la pleine taille.

Donjon

Les blancs de donjon sont à nouveau convertis en tuiles à l'aide de carrés de marche. Ensuite, comme pour la création de la cathédrale, des murs sont ajoutés, comme dans les catacombes et les grottes.

Conclusion

J'ai vraiment apprécié lire ce code. Bien qu'il y ait évidemment des bogues, les noms sont attribués au hasard et certaines parties ne peuvent pas être recréées dans du code source de haute qualité, il est clairement visible que ce code a passé un test sérieux au combat et il est plein d'idées intelligentes.

Voici les leçons les plus importantes pour moi:

• Le diable est dans les détails: les composants individuels ne sont pas incroyablement complexes, mais lorsqu'ils sont combinés, ils donnent quelque chose de merveilleux. Je peux imaginer comment les développeurs se sont penchés sur l'amélioration de la qualité jusqu'à ce que les niveaux passent de simplement bons à incroyables. Le nombre de tuiles et la complexité combinatoire des ensembles de tuiles est également très élevé - il est impossible de le mettre en œuvre sans tenir compte de la façon dont les éléments sont connectés.
• La recherche et le remplacement de la correspondance de motifs est un outil très puissant avec lequel vous pouvez implémenter de nombreux effets différents. Il corrige les bugs de génération, ajoute de la variabilité, insère du contenu pré-créé, gère l'érosion et bien plus encore.
• La division de la génération de donjon dans la carte de passabilité (préparation du donjon) et la génération de tuiles est également une technique très pratique, à la fois en termes de conception et de débogage.
• Si vous souhaitez donner à différentes zones un style différent, une excellente solution consiste à créer un algorithme distinct. , .
• , .