Générateur de labyrinthe de type Backtracker récursif

L'algorithme de retour arrière récursif est en réalité une recherche en profondeur d'abord à usage général. Lorsqu'il est utilisé pour la génération de labyrinthes, il est légèrement modifié pour choisir le chemin aléatoirement, tandis que pour la recherche proprement dite, on parcourt généralement chaque niveau de manière linéaire. Il tend à produire des labyrinthes avec de longs couloirs sinueux et une solution très longue et tortueuse.

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.

L'algorithme de retour arrière récursif est une méthode de recherche en profondeur permettant de générer des labyrinthes parfaits (labyrinthes sans boucles et avec un seul chemin entre deux points quelconques). Simple et efficace, il produit des labyrinthes visuellement attrayants, aux longs couloirs sinueux.

Malgré son nom, cette méthode n'est pas nécessairement implémentée par récursivité. Elle est souvent mise en œuvre de manière itérative à l'aide d'une file LIFO (c'est-à-dire une pile). Pour les labyrinthes de très grande taille, l'utilisation de la récursivité risque davantage d'entraîner un dépassement de capacité de la pile d'appels, en fonction du langage de programmation et de la mémoire disponible. Une file LIFO s'adapte plus facilement au traitement de grands volumes de données, et peut même être stockée sur disque ou dans une base de données si la mémoire disponible est insuffisante.

Comment ça marche

L'algorithme utilise une approche de recherche en profondeur basée sur une pile. Voici le détail des étapes :

1. Choisissez une cellule de départ et marquez-la comme visitée.
2. Tant qu'il reste des cellules non visitées : examinez les cellules voisines non visitées. S'il existe au moins une cellule voisine non visitée : choisissez-en une au hasard. Supprimez le mur entre la cellule actuelle et la cellule voisine choisie. Déplacez-vous vers cette cellule et marquez-la comme visitée. Empilez la cellule actuelle. S'il n'existe aucune cellule voisine non visitée : retirez la dernière cellule de la pile.
3. Poursuivez ce processus jusqu'à ce que la pile soit vide.

Ce qui est intéressant avec cet algorithme, c'est qu'il fonctionne à la fois comme générateur et comme résolveur de labyrinthes. Si vous l'exécutez sur un labyrinthe déjà généré et que vous vous arrêtez une fois le point d'arrivée atteint, la pile contiendra la solution du labyrinthe.

J'utilise en fait deux versions de cet algorithme sur ce site : une version basée sur une file LIFO pour générer les labyrinthes de cette page et une version récursive pour résoudre les labyrinthes, y compris ceux générés par d'autres algorithmes (c'est ainsi que sont créées les cartes avec les solutions). Avoir deux versions différentes, c'est juste pour le plaisir, parce que je suis un peu geek et que je trouve ça intéressant ; l'une ou l'autre aurait pu fonctionner pour les deux usages ;-)

Lectures complémentaires

Si vous avez apprécié cet article, vous aimerez peut-être aussi ces suggestions :

• Générateur de labyrinthe avec l'algorithme de Wilson
• Générateur de labyrinthe de chasse et de meurtre
• Générateur de labyrinthe d'algorithme d'arbre en croissance