Voici un algorithme très simple à mettre en place pour générer facilement un labyrinthe, qui aura la particularité de posséder un et un seul chemin entre deux cases quelconques.

Le principe va être de creuser un chemin dans un labyrinthe initialement uniquement constitué de murs.

Voici les principales étapes de la création de ce labyrinthe :

  • Initialisation du labyrinthe avec des murs partout.
  • Partir d’un point.
  • Creuser un mur dans une direction au hasard, vers une case du labyrinthe non encore visitée.
  • Recommencer l’opération précédente (creuser), à partir de la dernière case creusée, et jusqu’à ce qu’aucune direction ne soit plus possible (impasse au milieu d’autres cases déjà toutes visitées, case contre le bord, etc.)
  • A partir de là, prendre une case qui n’a pas été visitée et qui est à coté d’une case visitée, choisir une direction vers une case qui a déjà été visitée, et creuser vers cette case. C’est cette opération qui assure que toutes les cases seront accessibles.
  • Ensuite reprendre une direction au hasard vers une case non visitée jusqu’à impossibilité.
  • Puis recommencer ces opérations tant qu’il reste encore des cases non visitées.

J’ai fait cette première description de manière volontairement générale pour bien faire comprendre que la méthode dont je parle ensuite n’est qu’un cas particulier particulièrement pauvre, mais efficace et très simple à coder. Cependant, il faut garder en mémoire que la manière de choisir les directions et de choisir les cases non visitées influe particulièrement sur le labyrinthe.

Voici donc un exemple pratique et simple de cette méthode :

  • Partir d’un tableau contenant uniquement des murs.
  • Partir de la case en bas à droite du tableau.
  • La marquer comme étant visitée dans le tableau.
  • Déterminer une direction au hasard.
  • Recommencer tant que l’on ne trouve pas de case attenante non visitée.
  • Si une direction est trouvée, alors creuser en direction de cette case (c’est à dire supprimer l’existence du mur dans le tableau), et marquer cette case visitée. Recommencer les opérations à partir de cette case.
  • Si aucune direction n’est trouvée, alors abandonner ce chemin, et passer à la case de départ suivante dans le tableau (le sens de parcours est de droite à gauche et de bas en haut). Si cette case a été visitée alors on prend la suivante, jusqu’à en trouver une non visitée.
  • On raccorde cette case à une case visitée, le plus simple étant la case directement à droite, ou en bas si la case est complètement à droite du tableau.
  • Recommencer la creusée d’un chemin dans les cases non visitées.
  • Une fois que toutes les cases ont été parcourues de droite à gauche et du bas vers le haut, alors nous sommes sûrs que toutes les cases ont été visitées, et qu’il existe un unique chemin les reliant toutes entre elles.

Pour résumer brièvement les étapes importantes, le tout est de parcourir toutes les cases du tableau, et de relier chaque cellule parcourue au labyrinthe existant, et de chercher à creuser à partir de cette case un chemin dans les cases non visitées.
Il est alors évident que le premier chemin va être en général très long, et que au fur et à mesure, les chemins vont être de plus en plus court, et que vers la fin, les cellules seront toutes visitées bien avant d’être parcourue par la boucle systématique.

Là encore j’ai laissé de coté des détails :

  • Le format du tableau
    En effet, il existe plusieurs modes de représentation possibles, et il faut choisir celui qui sera le plus adapté à ce que vous voulez faire. On en distingue en particulier deux :
    • Murs plats : dans ce mode, les murs n’ont de façon naturelle aucune épaisseur : il s’agit de stocker simplement dans un tableau, sil la case comporte un mur en haut et à gauche. Les cellules situées à la droite et en bas de cette cellule fourniront les renseignement quant aux murs en bas et à droite. C’est une formule très économique : si vous prenez un tableau d’octets : vous réservez donc un bit pour le mur du haut, un bit pour le mur de gauche, et un bit pour savoir si la case est visitée ou non. Il vous reste ainsi 5 bits pour décrire le contenu de la case, voire 6 bits puisque le bit servant à l’attribut visité ne sert que lors de la création du labyrinthe.
    • Murs épais : C’est un mode nettement mois économique en place que le précédent. Il s’agit de considérer que les murs sont des cases pleines. Une case isolées sera donc représentée dans le tableau comme une case vide (0), entourée de 8 murs (les 8 entrées voisines du tableau deux dimensions étant à 1). On peut remarquer tout de suite que si on établit un parallèle avec le mode de stockage précédent, des cases seront toujours pleines (les angles de murs en 2*X,2*Y), d’autres toujours vides (en 2*X+1,2*Y+1), et les autres seront les murs, tantôt vides, tantôt pleins.
  • Le choix des directions
    Le choix des directions vers une cellule non visitée n’est pas simple, il faut à la fois que : le choix soit le plus aléatoire possible, le choix ne tourne pas à vide en cas d’impossibilité. En effet, un choix comme while (choixnonvalide(choix)) { choix=rand(4); }, bouclerais dans les cas où les quatre choix seraient non valides. Il faut pouvoir être capable de déterminer cette éventualité, et la traiter. Une des solutions facile est de choisir une direction au hasard, et tant qu’elle ne convient pas, tourner la direction de 90°. Si on se retrouve avec la même direction que au départ, c’est qu’il n’y a aucune direction qui convient. Cette solution à l’avantage de marier raisonnablement le caractère aléatoire avec la très grande simplicité de codage.

Voila ! Maintenant vous devriez être en mesure de pouvoir générer vos labyrinthes facilement.
A titre d’exemple, voici des codes sources de génération de labyrinthes :

On peut noter que beaucoup d’extensions et de perfectionnement sont possibles. Par exemple, trouver des parcours systématique plus originaux que celui de droite à gauche et de bas en haut. La seule condition est que ces parcours soient connexes et exhaustifs, ou que les différentes parties connexes soient reliées entre elles.

Yann Langlais a réalisé une très intéressante page sur la génération de labyrinthes à l’adresse http://intrasys.fr/maze.fr.html.