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

L’algorithme d’Eller est un algorithme de génération de labyrinthes qui produit efficacement des labyrinthes parfaits (labyrinthes sans boucles et avec un seul chemin entre deux points quelconques) en utilisant une approche ligne par rangée. Il produit des labyrinthes similaires à l’algorithme de Kruskal, mais il le fait en générant seulement une ligne à la fois, sans avoir besoin de stocker tout le 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 se distingue par son approche efficace rangée par rangée pour 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 sur la génération de contenu procédurale et la génération de labyrinthes, mais je n’ai pas réussi à trouver de 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, maintenant et modifiant des ensembles de cellules connectées. Il assure la connectivité tout en évitant les boucles, et prolonge efficacement le labyrinthe vers le bas.

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

Étape 1 : Initialiser la première rangée

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

Étape 2 : Rejoindre horizontalement quelques cellules adjacentes

• Fusionnez aléatoirement les cellules adjacentes en leur attribuant le même identifiant d’ensemble. Cela garantit qu’il y a des passages horizontaux.

Étape 3 : Créer des connexions verticales vers la rangée 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 les connecter à la ligne suivante.

Étape 4 : Passer à la rangée suivante

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

Étape 5 : Répétez les étapes 2 à 4 jusqu’à atteindre la dernière rangée

• Continuez le traitement ligne par rangée.

Étape 6 : Traiter la dernière rangée

• Assurez-vous que toutes les cellules de la dernière rangée appartiennent au même ensemble en fusionnant les ensembles séparés restants.

Lectures complémentaires

Si vous avez apprécié cet article, vous aimerez peut-être aussi ces suggestions :

• Chasser et tuer générateur de labyrinthe
• Générateur de labyrinthes récursifs de type Backtracker
• Générateur de labyrinthe d’algorithme de Kruskal