Miklix

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

Publié : 16 février 2025 à 19:58:40 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 de conserver en mémoire que la ligne courante (et non le labyrinthe entier), il peut donc ê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é traduite de l'anglais afin de la rendre accessible au plus grand nombre. Malheureusement, la traduction automatique n'est pas encore une technologie parfaite, et des erreurs peuvent donc se produire. 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 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.


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

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

Mikkel Bang Christensen

A propos de l'auteur

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