Concernant les labyrinthes, il n’est nulle part précisé le principe de pondération des liens. Alors je le fais !

La pondération, c’est « donner un poids ». Dans la plupart des algorithmes que j’ai donné on peut tout à fait donner un « poids » à chaque lien. Et en fonction de son poids, le lien aura plus ou moins de chances d’être tiré.
Exemple : une cellule a 4 sorties possibles : N, E, S, O. Chaque sortie a un poids.

• Premier exemple : N = 1, E=1, S = 1, O = 1. Les chances sont toutes identiques. La pondération n’est pas utile dans ce cas, mais c’est juste pour avoir une idée.
• Deuxième exemple : N = 40, E=10, S = 40, O = 10. La somme totale de la pondération est 100. On aura 80 chances sur 100 de tirer N ou S, et à peine 20 chances sur 100 de tirer E ou O.

Voilà sur le principe.
En pratique, voilà comment j’ai implémenté cela : j’ai, au départ, un tableau de poids. Par exemple :
poids[0] = 1, poids[1]=40 et poids[2]=10
Tous mes liens n’ont pas un poids, mais un indice vers le tableau des poids.
Reprenons les exemples :

• Premier exemple : ma cellule aura les liens ainsi : N = 0, E=0, S = 0, O = 0 ;
• Deuxième exemple : ma cellule aura les liens ainsi : N = 1, E=2, S = 1, O = 2.

Au moment de « tirer au hasard » un lien parmi ceux présents de la cellule : je fais la somme de tous les poids.
Reprenons les exemples :

• Premier exemple : somme = 4 ;
• Deuxième exemple : somme = 100.

Ensuite, je tire un chiffre entre 1 et la somme et je cherche à quelle direction cela correspond.
En pratique, il m’est ainsi possible de créer des labyrinthes avec des « orientations » dans certaines zones, et d’autres orientations dans d’autres zones.
Si cette idée vous a été utile, servez-vous en !

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.

Labyrinthes : différents algorithmes

L’algorithme de Prim

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

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

L’algorithme de Prim

Il faut une place mémoire équivalente à la taille du labyrinthe.

États possibles des cellules :

1. « Dedans » : la cellule est une partie du labyrinthe et on a déjà creusé dedans au moins une fois
2. « Frontière » : la cellule n’est pas une partie du labyrinthe et on n’a pas encore creusé dedans, mais est à côté d’une cellule de type « Dedans »
3. « Vierge » : la cellule n’est ni « Dedans » ni « Frontière »

Étapes de l’algorithme :

1. Choisir une cellule « Vierge » au hasard
2. La marquer comme « Dedans »
3. Marquer tous ses voisins en tant que « Frontière »
4. Répéter jusqu’à ce qu’il n’y ait plus de cellules « Frontière »

Caractéristiques du labyrinthe généré :

• Facteur « rivière » très bas
• Nombreux petits culs-de-sac
• Solution rapide à trouver en général

Performance :

Lorsqu’il est correctement implémenté, c’est l’algorithme le plus rapide, en seconde position après celui d’Eller.

Labyrinthes : différents algorithmes

Algorithme de Wilson

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

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

L’algorithme de Wilson

C’est une version améliorée de l’algorithme d’Aldous-Broder, en ce sens que les labyrinthes générées sont exactement du même type, avec des labyrinthes crées selon une probabilité égale, mis à part que l’algorithme de Wilson est beaucoup plus rapide. Il requiert un espace mémoire pouvant aller jusqu’à la taille du labyrinthe.

Étapes de l’algorithme :

1. Commencez en choisissant une cellule au hasard dans le labyrinthe.
2. Creusez au hasard dans le labyrinthe tant que vous ne rencontrez pas de cellule déjà creusée.
3. Si vous rencontrez une cellule déjà creusée :
   • Revenez à la cellule précédemment creusée
   • Essayez avec la cellule sur laquelle vous êtes revenu de creuser à nouveau dans le sens essayé pour la dernière fois
4. Répétez jusqu’à ce que toutes les cellules aient été ajoutées au labyrinthe.

Avantages de cette méthode :

• Cette approche réduit les boucles le long du tracé
• Résulte en un seul et long passage ajouté au labyrinthe

Performance et caractéristiques :

• Mêmes défis de performance que l’algorithme d’Aldous-Broder :
  • Le premier chemin tiré au hasard peut mettre beaucoup de temps à trouver la cellule de départ
  • Une fois quelques chemins tirés, le reste du labyrinthe est très rapidement complété
• En moyenne :
  • Cinq fois plus rapide que l’algorithme d’Aldous-Broder
  • Deux fois plus rapide que les algorithmes expliqués précédemment

Optimisation :

Il peut être accéléré par deux lorsqu’il est programmé en tant qu’ajouteur de murs, car :

• Les murs sur les côtés sont dès le début considérés comme une partie du labyrinthe
• Les premiers murs ajoutés sont connectés beaucoup plus rapidement

Labyrinthes : différents algorithmes

Algorithme de Kruskal

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

L’algorithme de Kruskal

Cet algorithme est intéressant parce qu’il ne « grandit » pas en créant le labyrinthe selon le principe d’un arbre, mais en enlevant des segments de murs au hasard dans tout le labyrinthe, et malgré ce, le labyrinthe est de type Parfait au final. ll requiert un espace mémoire proportionnel à la taille du labyrinthe.

Prérequis :

Il faut juste avoir la capacité d’énumérer toutes les séparations du labyrinthe et d’en tirer au hasard (habituellement, cela implique de créer une liste de tous les murs et la mélanger).

Étapes de l’algorithme :

1. Donnez à chaque cellule un numéro unique (Id)
2. Faite une boucle sur toutes les séparations du labyrinthe aléatoirement
3. Pour chaque séparation :
   • Si les cellules de chaque côté de ce mur ont un Id différent :
     • Supprimez ce mur
     • Gardez un des deux Ids
     • Appliquez cet Id des deux côtés partout où vous retrouvez l’un des deux Ids dans le labyrinthe
   • Si les cellules de chaque côté de la séparation ont déjà le même Id :
     • La séparation doit être transformée en mur (car il existe déjà un chemin de tracé pour les relier)

Caractéristiques :

• Cet algorithme donne des labyrinthes avec un facteur « rivière » bas, mais pas aussi bas que l’algorithme de Prim.
• L’opération de « fusion » des Ids peut être lente si elle est mal pensée.

Optimisation :

Il faut imaginer le labyrinthe en terme d’arbre et, lors de la fusion des « Ids », ne faire que déplacer les cellules dans les bonnes branches, afin de faire une fusion pratiquement instantanée. Bien programmé, cet algorithme est moyennement rapide.

Labyrinthes : différents algorithmes

Algorithme de l’arbre qui grandit

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

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

L’algorithme de l’arbre qui grandit (Growing tree algorithm)

C’est un algorithme générique, capable de créer des labyrinthes composés de motifs différents. Il requiert un espace pouvant aller jusqu’à la taille totale du labyrinthe.

Étapes de l’algorithme :

1. Commencez par prendre une cellule et ajoutez la dans une liste
2. Creusez dans une cellule liée à cette dernière et qui n’a jamais été creusée
3. Ajoutez la cellule destination dans la liste
4. Choisissez une cellule au hasard dans la liste et creusez (créez un passage) vers une cellule vierge (= qui n’a jamais été creusée)
5. Avec la cellule courante, s’il ne reste plus de liaison possible avec une cellule « vierge », retirez la de la liste
6. Le labyrinthe est terminé lorsque la liste est vide

Variations et résultats :

• Si vous reprenez systématiquement la dernière cellule avec laquelle vous avez creusé, cet algorithme revient à celui du retour-récursif
• Si vous tirez toujours une cellule au hasard, le comportement se rapprochera de l’algorithme de Prim
• Si vous reprenez systématiquement la dernière cellule ajoutée à la liste, vous allez créer un labyrinthe avec le facteur « rivière » le plus bas possible, encore plus bas que l’algorithme de Prim
• Si vous recommencez de temps à autre sur la cellule la plus récente, et vous en prenez occasionnellement une au hasard, le labyrinthe aura :
  • Un facteur « rivière » haut
  • Une solution souvent courte et directe
• Si vous tirez au hasard parmi les dernières cellules ajoutées, le labyrinthe aura :
  • Un facteur « rivière » bas
  • Une solution longue et sinueuse

Labyrinthes : différents algorithmes

Algorithme Retour-récursif

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

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Retour-récursif

(« Recursive backtracker ») : cette méthode nécessite une pile qui doit pouvoir aller jusqu’à la taille totale du nombre de cellules. Lorsque vous creusez, soyez le plus gourmand possible, et creusez toujours dans une cellule sur laquelle vous n’avez jamais été, dans la mesure où elle touche celle qui est en cours.

Chaque fois que vous creusez :

1. Placez la cellule courante en haut de la pile ;
2. Creusez ;
3. Si, dans la cellule courante, vous ne pouvez plus creuser (donc il n’y a aucune cellule pas encore faite collée à la cellule courante), retirez la dernière cellule de la liste et considérez la comme la cellule courante.

Le labyrinthe est terminé lorsque votre pile est vide. Cet algorithme crée des labyrinthes avec le facteur « rivière » le plus grand possible, avec moins de cul-de-sac, et une grande distance entre eux, et la solution pour aller de l’un à l’autre est en générale longue et tortueuse. Cet algorithme est assez rapide, même si il l’est moins que l’algorithme de Prim.

Labyrinthes : différents algorithmes

Autres algorithmes à traduire

J’ai traduit tous les autres, il me reste ceux-ci à finir. L’intégralité des algorithmes se trouve ici.

Binary tree Mazes : This is basically the simplest and fastest algorithm possible, however Mazes produced by it have a very biased texture. For each cell carve a passage either leading up or leading left, but not both. In the wall added version, for each vertex add a wall segment leading down or right, but not both. Each cell is independent of every other cell, where you don’t have to refer to the state of any other cells when creating it. Hence this is a true memoryless Maze generation algorithm, with no limit to the size of Maze you can create. This is basically a computer science binary tree, if you consider the upper left corner the root, where each node or cell has one unique parent which is the cell above or to the left of it. Binary tree Mazes are different than standard perfect Mazes, since about half the cell types can never exist in them. For example there will never be a crossroads, and all dead ends have passages pointing up or left, and never down or right. The Maze tends to have passages leading diagonally from upper left to lower right, where the Maze is much easier to navigate from lower right to upper left. You will always be able to travel up or left, but never both, so you can always deterministically travel diagonally up and to the left without hitting any barriers. Traveling down and to the right is when you’ll encounter choices and dead ends. Note if you flip a binary tree Maze upside down and treat passages as walls and vice versa, the result is basically another binary tree.

Sidewinder Mazes : This simple algorithm is very similar to the binary tree algorithm, and only slightly more complicated. The Maze is generated one row at a time: for each cell randomly decide whether to carve a passage leading right. If a passage is not carved, then consider the horizontal passage just completed, formed by the current cell and any cells to the left that carved passages leading to it. Randomly pick one cell along this passage, and carve a passage leading up from it (which must be the current cell if the adjacent cell didn’t carve). While a binary tree Maze always goes up from the leftmost cell of a horizontal passage, a sidewinder Maze goes up from a random cell. While binary tree has the top and left edges of the Maze one long passage, a sidewinder Maze has just the top edge one long passage. Like binary tree, a sidewinder Maze can be solved deterministically without error from bottom to top, because at each row, there will always be exactly one passage leading up. A solution to a sidewinder Maze will never double back on itself or visit a row more than once, although it will « wind from side to side ». The only cell type that can’t exist in a sidewinder Maze is a dead end with the passage facing down, because that would contradict the fact that every passage going up leads back to the start. A sidewinder Maze tends to have an elitist solution, where the right path is very direct, but there are many long false paths leading down from the top next to it.