🏰 Générateur de donjon procédural

La génération BSP divise récursivement une zone rectangulaire en deux rectangles plus petits, en alternant coupes horizontales et verticales, jusqu'à ce que chaque région soit assez petite pour contenir une salle. Une salle est ensuite placée dans chaque nœud feuille, et les salles sont reliées par des corridors droits ou en L suivant l'ordre de leur création. Cela produit des donjons avec une structure arborescente naturelle et peu de salles qui se chevauchent, et c'est l'une des techniques les plus utilisées dans les roguelikes car elle garantit des salles non chevauchantes sans aucune vérification de collision.

Le générateur propose de manière répétée une salle de largeur et hauteur aléatoires à une position aléatoire, puis la vérifie par rapport à chaque salle déjà placée à l'aide d'un test de chevauchement de boîtes englobantes alignées sur les axes (avec une marge d'une case). En cas de chevauchement avec une salle existante, la tentative est abandonnée et une nouvelle est essayée, jusqu'à un nombre limité de tentatives. Une fois qu'il existe suffisamment de salles non chevauchantes, elles sont reliées par une chaîne gloutonne du plus proche voisin — à chaque étape, la salle non encore connectée la plus proche est rattachée au réseau grandissant par un corridor en L, dans un esprit similaire à la construction d'un arbre couvrant minimal.

La grotte commence sous la forme d'une grille remplie aléatoirement de murs à un pourcentage choisi (35–60%). Elle est ensuite lissée sur plusieurs passes : à chaque passe, chaque case compte combien de ses 8 voisines sont des murs, et devient elle-même un mur si 5 voisines ou plus sont des murs, sinon elle devient du sol. Répéter cela plusieurs fois érode le bruit isolé et transforme les petits amas de murs en parois de grotte lisses et organiques — le même principe qui sous-tend le Jeu de la vie de Conway, appliqué à la génération de niveaux plutôt qu'à la simulation de cellules vivantes.

La simulation utilise un générateur congruentiel linéaire (LCG) : une formule simple qui transforme de manière répétée un état interne de 32 bits par multiplication et addition avec des constantes fixes, produisant un flux déterministe de nombres pseudo-aléatoires. Comme le générateur est réinitialisé à la même valeur de graine chaque fois que « Générer » est pressé, saisir la même graine avec le même algorithme et les mêmes paramètres produit toujours exactement la même disposition de donjon, ce qui explique pourquoi le champ de graine et le bouton « Nouvelle graine » permettent d'enregistrer ou de reproduire une carte précise.

Une fois un donjon généré, la simulation lance un parcours en largeur depuis une case de sol pour trouver la case atteignable la plus éloignée, puis lance un second BFS depuis cette case pour trouver le vrai diamètre de la région connectée — c'est la technique classique du « double BFS » pour trouver le plus long plus-court-chemin dans un graphe non pondéré. Les deux extrémités deviennent les marqueurs de départ et de sortie, la longueur du chemin entre eux est affichée comme « Plus long chemin », et « Connectivité » indique quel pourcentage de toutes les cases de sol sont atteignables depuis le départ, ce qui signale si la grotte ou le donjon comporte des poches isolées et inaccessibles.