Générateur de labyrinthes

Comment utiliser le générateur de labyrinthes

1. Réglez la Largeur (colonnes) et la Hauteur (lignes), de 4 à 60 cases chacune, puis choisissez un Algorithme. Cliquez sur Nouveau labyrinthe.
2. Vous êtes le point placé dans l’entrée verte, en haut à gauche. Il faut rejoindre la sortie rouge, en bas à droite.
3. Déplacez-vous avec les flèches, ou avec ZQSD sur un clavier AZERTY (WASD en QWERTY). Maintenez Maj avec une flèche pour courir dans le couloir jusqu’au prochain embranchement. Sur téléphone ou tablette, balayez le labyrinthe pour foncer dans une direction, ou touchez les boutons fléchés pour avancer d’une case.
4. Le chrono démarre au premier déplacement et s’arrête à la sortie. Votre tracé reste affiché derrière vous ; revenir sur vos pas l’efface, si bien qu’il montre toujours le chemin en cours.
5. Bloqué ? Afficher la solution dessine le plus court chemin entre votre position et la sortie. Retour au départ vous replace à l’entrée et remet le chrono à zéro.
6. Pour jouer sur papier, cliquez sur Imprimer ou Télécharger en PDF. Cochez d’abord Ajouter une page de solution si vous voulez le corrigé sur une deuxième page.

Partager un labyrinthe grâce à son code

Chaque labyrinthe possède un Code du labyrinthe, par exemple b20x15-k3j9x2 : la lettre de l’algorithme (b, p ou k), la largeur × la hauteur, puis une graine aléatoire. Le même code reconstruit toujours exactement le même labyrinthe, sur n’importe quel appareil : idéal pour défier un ami sur le même parcours. Saisissez ou collez un code puis cliquez sur Charger le code, ou utilisez Copier le lien pour envoyer une adresse qui ouvre directement ce labyrinthe.

Les trois algorithmes de génération

Les trois construisent un labyrinthe parfait : toutes les cases sont accessibles et il existe un seul chemin entre deux cases, sans boucle ni zone fermée. Seule la « texture » change :

• Backtracking récursif (longs couloirs) avance au hasard de case en case en abattant les murs, et revient en arrière quand il tombe sur un cul-de-sac. On obtient de longs couloirs sinueux, peu ramifiés, et une solution souvent longue qui traverse presque toute la grille.
• Prim (nombreux culs-de-sac courts) fait grandir le labyrinthe à partir d’une case choisie au hasard, en ajoutant chaque fois une case de la frontière. Il en résulte beaucoup de petites impasses : l’ensemble paraît touffu, mais le chemin principal se devine plus vite.
• Kruskal (régulier, très ramifié) supprime au hasard des murs entre des cases qui ne sont pas encore reliées (suivies par une structure union-find). Les ramifications sont réparties partout, sans point de départ visible.

La ligne au-dessus du labyrinthe indique la taille, la longueur du plus court chemin et le nombre de culs-de-sac, pour comparer les algorithmes d’un coup d’œil.

Comment la solution est trouvée

La solution est calculée par un parcours en largeur (BFS) : depuis votre case, on explore toutes les voisines à un pas, puis à deux pas, et ainsi de suite jusqu’à la sortie. Chaque pas ayant le même coût, ce parcours trouve toujours le plus court chemin. Si la solution a été affichée pendant la partie, votre temps n’est pas enregistré comme record.

Conseils d’impression

Les versions imprimée et PDF dessinent des murs noirs sur fond blanc, avec le code du labyrinthe dans le titre pour le retrouver plus tard. Une taille d’environ 15 × 15 convient aux jeunes enfants ; à partir de 30 × 30, le casse-tête devient sérieux pour un adulte. Les très grands labyrinthes (50 × 60) ont des couloirs étroits sur une page A4 : imprimez-les en pleine page.