Miklix

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

Publié : 16 février 2025 à 20 h 40 min 07 s UTC

Générateur de labyrinthe utilisant l’algorithme d’Eller pour créer un labyrinthe parfait. Cet algorithme est intéressant car il ne nécessite que de garder la ligne actuelle (pas tout le labyrinthe) en mémoire, de sorte qu’il peut être utilisé pour créer de très, très grands labyrinthes, même sur des systèmes très limités.

Cette page a été automatiquement traduite de l'anglais afin de la rendre accessible au plus grand nombre. Malheureusement, la traduction automatique n'est pas encore une technologie au point, des erreurs peuvent donc survenir. Si vous préférez, vous pouvez consulter la version originale en anglais ici :

Eller's Algorithm Maze Generator

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.


Générer un nouveau labyrinthe








À 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.

Partager sur BlueskyPartager sur FacebookPartager sur LinkedInPartager sur TumblrPartager sur XPartager sur LinkedInÉpingler sur Pinterest

Mikkel Bang Christensen

À propos de l'auteur

Mikkel Bang Christensen
Mikkel est le créateur et propriétaire de miklix.com. Il a plus de 20 ans d'expérience en tant que programmeur informatique/développeur de logiciels professionnel et est actuellement employé à temps plein pour une grande société informatique européenne. Lorsqu'il ne blogue pas, il consacre son temps libre à une vaste gamme d'intérêts, de passe-temps et d'activités, qui peuvent dans une certaine mesure se refléter dans la variété des sujets abordés sur ce site Web.