Labyrinthes : différents algorithmes

Algorithme d’Eller

Traduit en Français par moi-même. Les originaux sont ici.

L’algorithme d’Eller : cet algorithme est spécial : non seulement il est plus rapide que tous les autres, mais lors de la création c’est celui qui requiert le moins de mémoire. Avec lui, il n’est même pas nécessaire d’avoir tout le labyrinthe en mémoire, il suffit juste d’avoir un espace de la taille d’une ligne.

Il crée le labyrinthe une ligne par une ligne, et lorsqu’une ligne a été générée, il n’en a plus besoin, parce qu’il ne s’en servira plus. Chaque cellule dans une ligne fait partie d’un groupe, et les cellules sont dans le même groupe s’il y a un chemin qui les relie entre elles depuis le début de la génération du labyrinthe. Grâce à cette information, il est possible d’éviter de faire des boucles ou des passages fermés indépendants des autres.

Cela ressemble un peu à l’algorithme de Kruskal, à la différence qu’il n’y a qu’une ligne faite à la fois, alors que l’algorithme de Kruskal regarde sur la totalité du labyrinthe. Créer une ligne consiste en deux actions :

1. examiner les cellules adjacentes dans la ligne en cours, et connecter des cellules (= creuser des passages horizontaux) de manière aléatoire ;
2. examiner les cellules entre la ligne courante et la ligne suivante, et connecter des cellules (= creuser des passages verticaux) de manière aléatoire.

Lorsqu’on examine les passages horizontaux :

1. il ne faut pas connecter des cellules qui font partie d’un même groupe (cela créerait des boucles) ;
2. si on décide de connecter deux cellules, il faut fusionner les groupes auxquels elles appartiennent en un seul (vu qu’elles se rejoignent).

Lorsqu’on examine des passages verticaux, il faut obligatoirement connecter des cellules qui sont dans un groupe de taille «1». Si ce n’est pas fait, la cellule ne sera connectée avec aucune autre et on se retrouve avec une cellule isolée. À l’inverse, si on décide de ne pas creuser et qu’elle n’appartient à aucun groupe, il faut créer un groupe auquel elle va appartenir, où elle sera seule.

La création commence avec toutes les cellules qui appartiennent à leur groupe de une cellule. Ensuite, on applique l’algorithme : on examine les cellules à l’horizontal en en connectant entre elles au hasard, puis en vertical etc., et ce jusqu’à la dernière ligne où il faut appliquer une règle spéciale : tant que toutes les cellules de la ligne ne sont pas dans le même groupe, faire une boucle, afin d’empêcher d’avoir des cellules (ou passages au complet) isolés. Il suffit pour cela de connecter toutes les cellules qui se touchent et qui ne sont pas encore dans le même groupe.

Un seul problème survient avec cet algorithme : il n’est pas tiré équitablement au hasard sur les cellules du bord du labyrinthe, et les effets “de bord” (sans jeu de mots) sont visibles. Mis à part cela c’est le plus rapide et celui qui prend le moins de mémoire.