Binding of Isaac et son remake Binding Of Isaac: Rebirth font partie de mes jeux préférés. Ils appartiennent au genre de tir à double bâton roguelite et sont très similaires à Enter the Gungeon .
Les donjons générés par ces jeux sont particulièrement connus. J'ai vu d'innombrables tutoriels sur Internet sur la façon de créer une génération de style Isaac, mais je me suis demandé comment cela avait été implémenté dans l'original. À ma grande surprise, la plupart des tutoriels décrivent le processus de manière incorrecte. Dans cet article, je vais parler du fonctionnement de la génération et en montrer un exemple dans une démo Javascript.
Bien que j'ai dû décompiler et actualiser mes connaissances poussiéreuses de Flash (j'ai une fois écrit mon propre décompilateur Actionscript), j'ai également eu beaucoup de chance: le développeur IsaacFlorian Himsl et l'un des principaux développeurs de Rebirth, Simon Parser , ont répondu avec plaisir à mes questions. En fait, Florian a même récemment enregistré une vidéo décrivant l'algorithme. Sur sa chaîne, vous pouvez également découvrir les détails du développement de son nouveau jeu Squid Invaders.
Compte tenu de la présence de son histoire, mon article peut être considéré comme redondant, mais si vous voulez des détails sanglants, continuez à lire.
Algorithme de base
Les développeurs d'Isaac se sont fortement inspirés des jeux 2D de la série Zelda et ont généré des cartes similaires à leurs donjons.
Il s'agit d'un ensemble de pièces carrées reliées entre elles par des bords. Certaines chambres sont spéciales - il y a toujours un magasin
, une salle au trésor 
et un patron à chaque étage 
; en outre, plusieurs autres salles spéciales sont sélectionnées au hasard. À l'exception de la salle secrète 
, il n'y a pas de boucles dans le donjon.
Le jeu lui-même consiste en un passage linéaire de tels niveaux, généralement il y en a deux par "chapitre". En cours de passage, les cartes deviennent un peu plus grandes et le contenu des pièces change, mais l'algorithme de création de leur structure reste en fait le même à chaque fois.
La première version d'Isaac a été développée en moins de 3 mois, donc Himslu a dû utiliser son temps de manière incroyablement efficace. La conception fondamentale du jeu est élégante et simple. Tout d'abord, un plan d'étage (niveau) est généré. Ensuite, certaines chambres sont sélectionnées comme spéciales. Ensuite, l'intérieur de chaque pièce est sélectionné dans la piscine correspondante.
Plan d'étage
Isaac est généré sur une grille 9x8. Pour plus de commodité, les cellules sont désignées par des nombres - les uns indiquent la position X, les dizaines - la position Y. Cela signifie que vous pouvez vous déplacer vers le haut, le bas, la gauche et la droite, en ajoutant simplement +10, -10, +1 et -1. Les cellules avec une position X de 0 ne sont pas utilisées (toujours vides), ce qui signifie que la plupart du code n'a pas à se soucier des limites de la carte. Autrement dit, la cellule en haut à gauche sur la carte est 01 et la cellule en bas à droite est 79.
Le plan d'étage détermine uniquement les cellules qui contiendront des pièces - le contenu de la pièce est sélectionné plus tard.
Tout d'abord, la formule
random(2) + 5 + level * 2.6détermine le nombre de chambres. Ceux. les niveaux commencent à 7 ou 8 salles et augmentent de 2 ou 3 salles à chaque fois.
Le jeu place alors la salle de départ (cellule 35) dans la file d'attente. Ensuite, elle contourne cycliquement la file d'attente. Pour chaque cellule de la file d'attente, il parcourt les 4 directions principales et effectue les opérations suivantes:
- Détermine la cellule adjacente en ajoutant + 10 / -10 / + 1 / -1 à la cellule actuelle.
- Si la cellule adjacente est déjà occupée, le jeu ne fait rien.
- Si la cellule voisine elle-même a plus d'un voisin rempli, le jeu ne fait rien.
- S'il y a déjà assez de pièces sur le niveau, le jeu ne fait rien.
- Le jeu ne fait rien avec une probabilité de 50%.
- Sinon, le jeu marque la cellule adjacente comme contenant la pièce et l'ajoute à la file d'attente.
Si une cellule n'ajoute pas de pièce à l'une des cellules adjacentes, il s'agit d'une impasse et elle peut être ajoutée à la liste des pièces de destination pour une utilisation ultérieure.
Dans le cas où les cartes nécessitent plus de 16 salles, la salle de départ est à nouveau mise en file d'attente pour stimuler la croissance.
Puisque l'algorithme décrit ci-dessus commence par une seule pièce et se développe plusieurs fois vers l'extérieur, il s'agit en fait d'une première exploration en profondeur. La restriction ne permettant pas d'ajouter une pièce s'il y a déjà deux voisins divise les pièces en couloirs séparés qui ne se rejoignent jamais en boucles.
La cohérence du plan d'étage est ensuite vérifiée. Il doit contenir le nombre de pièces requis et la salle du boss ne doit pas être située à côté de la salle de départ. Sinon, la génération recommence.
Chambres spéciales
Les salles de boss sont placées en lisant le dernier élément de la liste des salles de fin. En raison du fait que la génération est effectuée comme une croissance vers l'extérieur, ce sera toujours l'une des salles situées à la distance la plus éloignée de la salle de départ.
Ensuite, la position de la salle secrète est indiquée. Ces pièces sont ajoutées au plan d'étage; ils sont l'une des rares exceptions à la règle qui interdit de placer des pièces à côté de plusieurs pièces existantes. En fait, l'algorithme, au contraire, préfère les placer ainsi. Le générateur recherche au hasard une cellule vide à côté d'au moins trois pièces et non à proximité d'une des pièces d'extrémité. S'il ne le trouve pas après 300 tentatives, cela affaiblit légèrement le critère de recherche et après 600 tentatives, il l'affaiblit encore plus. Cette procédure garantit que la pièce secrète est toujours placée au niveau, mais généralement elles sont coincées près des intersections, ce qui signifie qu'il y a toujours de nombreuses pièces à proximité.
Presque toutes les autres salles spéciales sont situées dans des salles d'extrémité aléatoires. Certaines chambres sont garanties, d'autres ont une petite chance ou critère. Par exemple, les salles de sacrifice apparaissent une des sept fois; si le joueur a une santé complète, ils se produisent environ une fois sur trois.
Chambres régulières
Les pièces adjacentes ont toujours une porte (ou un mur cassable) exactement au centre, et chaque pièce est conçue pour être accessible depuis les quatre directions. Par conséquent, aucune considération particulière n'est requise lors du choix des chambres - toute combinaison fera l'affaire.
Les chambres sont sélectionnées au hasard dans la piscine. Les informations sur les pièces contiennent à la fois des structures (fosses, feu, pierres, etc.) et des monstres. Les deux sont sujets à des variations aléatoires, telles que l'apparition de monstres champions et de cheminées rouges.
Pour les chambres standard, il existe trois piscines: facile, moyenne et dure. La première étape du chapitre choisit des salles simples et moyennes, et la seconde des salles moyennes et difficiles. Le premier chapitre (Sous-sol) contient 174 pièces ordinaires dans des piscines. Les «chapitres alternatifs» comme Cellar, qui remplace aléatoirement Basement, ont un ensemble de pièces légèrement différent.
Malédiction du labyrinthe
L'une des fonctionnalités supplémentaires les plus intéressantes du code est les cartes à double taille. Ils sont créés au hasard et uniquement pour certains modes de défi. En plus du doublement évident du nombre de salles spéciales et de deux salles de boss adjacentes, elles comportent également de nombreux petits détails:
- 80% de chambres normales en plus (max 45)
- Seules les 6 salles les plus éloignées sont utilisées pour des salles spéciales
- Les niveaux sélectionnent des chambres parmi des piscines de chambres simples, moyennes et complexes.
- Des pièces normales supplémentaires sont ajoutées aléatoirement au plan d'étage avec une logique de placement similaire aux pièces secrètes.
Démo
J'ai créé un exemple simplifié de générateur en Javascript pour que vous puissiez l'expérimenter. Le code complet peut être trouvé ici , et un exemple fonctionnel peut être trouvé dans l' article original .
Renaissance
Binding of Isaac: Rebirth est un remake du Binding of Isaac original créé par Nicalis , qui à l'époque était célèbre pour ses ports VVVVV et Cave Story . Le jeu a été porté en C ++ et tous les sons et graphismes ont été refaits. Au fil des ans, le jeu a reçu de nombreux DLC, ajoutant de nouveaux objets et ennemis à la liste déjà impressionnante de l'original.
Alors que Rebirth a un tas d'innovations intéressantes, la principale contribution à la génération de niveau a été l'ajout de pièces plus grandes et irrégulières.
Avec un ensemble complet de DLC (au moment d'écrire ces lignes, il s'agit d'Afterbirth +), le jeu dispose de 11 grandes salles: 2 × 2, 2 × 1, couloirs en forme de L et étroits dans différentes options de rotation.
Pièce typique en forme de L, trois fois plus grande qu'une pièce ordinaire. Il a été implémenté par Simon Parser grâce à une modification minutieuse du code source Himsla.
Au lieu de parcourir toutes les directions, l'algorithme contourne toutes les sorties de la pièce. Dans une pièce 2x2, il peut y en avoir jusqu'à huit.
Lorsqu'il s'agit d'insérer une pièce, il essaie au hasard d'insérer une grande pièce à la place. Les contrôles de voisinage sont toujours appliqués, mais uniquement à la première cellule à côté de la porte; cependant, l'algorithme vérifie s'il y a suffisamment d'espace pour le reste de la pièce. Cela signifie que les grandes pièces peuvent créer des boucles de niveau. Habituellement, deux grandes pièces sont générées l'une à côté de l'autre et sont complétées par une paire de portes les reliant.
S'il n'y a pas assez d'espace pour la salle, l'algorithme essaie d'insérer un autre candidat. Si de grandes pièces sont insérées avec succès, il y a 95% de chances qu'elles soient supprimées de la piscine.
Encore plus de code est nécessaire pour gérer les grandes salles de boss. N'oubliez pas que les salles de boss sont toujours situées aussi loin que possible de la salle de départ. Si une pièce plus grande est souhaitée, le générateur remplace la pièce individuelle prévue. Étant donné que les salles de boss sont toujours des impasses, lors du remplacement, l'algorithme vérifie si elles sont adjacentes à certaines pièces supplémentaires. Parfois, le remplacement est encore impossible, donc tous les points d'extrémité sont vérifiés à la distance maximale de la pièce de départ, et s'ils ne correspondent pas, alors l'algorithme abandonne.
Pour les pièces secrètes, les pièces adjacentes sur le plan d'étage sont prises en compte pour le placement, et les pièces sont sélectionnées uniquement lorsque l'algorithme détermine que les portes ne sont pas nécessaires.
À Isaac, les gouffres sont généralement impossibles à franchir
Production
Le générateur de niveau Isaac n'est pas le plus complexe que j'ai vu, mais malgré une si petite quantité de code, il fonctionne incroyablement bien. C'est probablement pourquoi ils essaient de le recréer si souvent. Sa simplicité permet des changements et des extensions, comme on peut le voir dans l'exemple de Rebirth. Un résultat incroyable.
Vous pouvez également remarquer que ce jeu continue la tendance de générer des plans d'étage séparément des détails de la pièce. Dans mes articles sur Diablo 1 [ traduction en Habré] et Enter the Gungeon [ traduction en Habré], j'ai expliqué pourquoi cette approche peut être très puissante.
Lors de la décompilation du code, je n'ai pas trouvé de détails particulièrement intéressants. La chose la plus intéressante que je puisse dire est que l'emplacement de la salle au trésor est stocké dans une variable nommée "boner" - probablement l'abréviation de Bonus Room. Il y a aussi des subtilités dans le code concernant les effets secondaires mineurs de divers éléments, mais je vais laisser ce sujet aux analyseurs .
Ensuite, vous pouvez regarder la série de vidéos de Himsla sur les éléments internes du jeu, ou même jouer à Isaac et voir tous les niveaux en direct. J'ai entendu dire que le nouveau DLC Repentance sortait cette année. Je recommande également de jouer à d'autres jeux du designer en chef Edmund McMillen (en particulier Super Meat Boy).