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 (des labyrinthes sans boucle et un seul chemin entre deux points) 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'intégralité 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 seul chemin entre n'importe quel point du labyrinthe et n'importe quel autre point. Cela signifie que vous ne pouvez pas tourner en rond, mais que vous rencontrerez souvent des impasses qui vous obligeront à faire demi-tour.

Les cartes de labyrinthe générées ici comprennent une version par défaut sans position de départ et d'arrivée, afin que vous puissiez décider vous-même de ces positions : il y aura une solution de n'importe quel point du labyrinthe à n'importe quel autre point. Si vous souhaitez vous inspirer, vous pouvez activer une suggestion de position de départ et d'arrivé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 ligne 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 fréquemment cité dans la littérature sur la génération de contenu procédural et la génération de labyrinthes, mais je n'ai pas pu 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, en conservant et en modifiant des ensembles de cellules connectées. Il assure la connectivité tout en évitant les boucles et étend efficacement le labyrinthe vers le bas.

Il peut théoriquement être utilisé pour générer des labyrinthes infinis, cependant afin de garantir que le labyrinthe généré soit 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 ligne

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

Étape 2 : joindre certaines cellules adjacentes horizontalement

• Fusionnez de manière aléatoire les cellules adjacentes en leur attribuant le même identifiant d'ensemble. Cela garantit la présence de 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 ligne suivante

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

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

• Continuer le traitement ligne par ligne.

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

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