Générateur de labyrinthe d’algorithme d’Eller

L’algorithme d’Eller est un algorithme de génération de labyrinthe qui produit efficacement des labyrinthes parfaits (labyrinthes sans boucles et un seul chemin entre deux points quelconques) en utilisant une approche ligne par ligne. Il produit des labyrinthes similaires à l’algorithme de Kruskal, mais il le fait en générant une seule ligne à la fois, sans avoir besoin de stocker l’ensemble du labyrinthe en mémoire. Cela le rend utile pour générer de très grands labyrinthes sur des systèmes très limités et pour la génération de contenu procédural.

Un labyrinthe parfait est un labyrinthe dans lequel il existe exactement un chemin reliant n’importe quel point du labyrinthe à n’importe quel autre point. Cela signifie que vous ne pouvez pas finir par tourner en rond, mais vous rencontrerez souvent des culs-de-sac, ce qui vous obligera à faire demi-tour et à revenir en arrière.

Les cartes de labyrinthe générées ici incluent une version par défaut sans aucune position de départ et d'arrivée, vous pouvez donc les décider vous-même : il y aura une solution de n'importe quel point du labyrinthe à n'importe quel autre point. Si vous voulez trouver de l'inspiration, vous pouvez activer une position de départ et d'arrivée suggérée - et même voir la solution entre les deux.

À propos de l’algorithme d’Eller

L’algorithme d’Eller a été introduit par David Eller.

L’algorithme est remarquable pour son approche efficace ligne par rangée de la génération de labyrinthes, ce qui le rend idéal pour les labyrinthes infinis ou les labyrinthes générés en temps réel. Il est couramment cité dans la littérature procédurale de génération de contenu et de génération de labyrinthe, mais je n’ai pas été en mesure de trouver des sources primaires détaillant sa publication originale.

Comment fonctionne l’algorithme d’Eller pour la génération de labyrinthes

L’algorithme d’Eller traite une ligne à la fois, en maintenant et en modifiant des ensembles de cellules connectées. Il assure la connectivité tout en évitant les boucles, et il étend efficacement le labyrinthe vers le bas.

Il peut théoriquement être utilisé pour générer des labyrinthes infinis, mais afin de s’assurer que le labyrinthe généré est réellement résoluble, il est nécessaire de passer à la logique « dernière ligne » à un moment donné pour terminer le labyrinthe.

Étape 1 : Initialiser la première ligne

• Attribuez à chaque cellule de la ligne un ID d’ensemble unique.

Étape 2 : joindre certaines cellules adjacentes horizontalement

• Fusionnez de manière aléatoire les cellules adjacentes en les définissant sur le même ID d’ensemble. Cela garantit qu’il y a des passages horizontaux.

Étape 3 : Créer des connexions verticales à la ligne suivante

• Pour chaque ensemble qui apparaît dans la ligne, au moins une cellule doit se connecter vers le bas (pour assurer la connectivité).
• Choisissez au hasard une ou plusieurs cellules de chaque ensemble pour vous connecter à la ligne suivante.

Étape 4 : Passer à la ligne suivante

• Reportez les connexions verticales en attribuant le même ID d’ensemble aux cellules correspondantes ci-dessous.
• Affectez de nouveaux IDs d’ensemble à toutes les cellules non attribuées.

Étape 5 : Répétez les étapes 2 à 4 jusqu’à ce que la dernière ligne soit atteinte

• Poursuivre le traitement ligne par ligne.

Étape 6 : Traiter la dernière ligne

• Assurez-vous que toutes les cellules de la dernière ligne appartiennent au même ensemble en fusionnant tous les ensembles distincts restants.