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 (sans boucles et avec un seul chemin entre deux points quelconques) en parcourant les lignes une à une. Il produit des labyrinthes similaires à l'algorithme de Kruskal, mais en générant une seule ligne à la fois, sans avoir besoin de stocker le labyrinthe entier en mémoire. Cela le rend utile pour générer de très grands labyrinthes sur des systèmes aux ressources limitées et pour la génération procédurale de contenu.

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.

Cet algorithme se distingue par son approche efficace de génération de labyrinthes ligne par ligne, ce qui le rend idéal pour les labyrinthes infinis ou générés en temps réel. Il est fréquemment cité dans la littérature sur la génération procédurale de contenu et la génération de labyrinthes, mais je n'ai pas trouvé 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 les 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, mais afin de garantir que le labyrinthe généré soit effectivement 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 horizontalement des cellules adjacentes

• Fusionnez aléatoirement 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 avec la ligne suivante

• Pour chaque ensemble qui apparaît dans la ligne, au moins une cellule doit être connectée 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

• Prolongez les connexions verticales en attribuant le même identifiant d'ensemble aux cellules correspondantes ci-dessous.
• Attribuez de nouveaux identifiants d'ensemble aux cellules non attribuées.

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

• 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 les ensembles distincts restants.

Lectures complémentaires

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

• Générateur de labyrinthe de type Backtracker récursif
• Générateur de labyrinthe d'algorithme d'arbre en croissance
• Générateur de labyrinthe de chasse et de meurtre