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

L'algorithme de rétro-suivi récursif est en réalité une recherche en profondeur à 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 au hasard, alors que s'il est utilisé à des fins de recherche réelle, on recherche généralement simplement chaque niveau dans un ordre linéaire. Il a tendance à produire des labyrinthes avec de longs couloirs sinueux et une solution très longue et sinueuse.

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 rétro-suivi récursif est une méthode de recherche en profondeur permettant de générer des labyrinthes parfaits (des labyrinthes sans boucle et avec un seul chemin entre deux points). Il est simple, efficace et produit des labyrinthes visuellement attrayants avec de longs couloirs sinueux.

Malgré son nom, il n'est pas nécessaire de l'implémenter en utilisant la récursivité. Il est souvent implémenté selon une approche itérative en utilisant une file d'attente LIFO (c'est-à-dire une pile). Pour les labyrinthes de très grande taille, l'utilisation de la récursivité est plus susceptible d'entraîner un débordement de la pile d'appels, en fonction du langage de programmation et de la mémoire disponible. Une file d'attente LIFO peut être plus facilement adaptée à la gestion de grandes quantités de données, même en conservant la file d'attente sur le disque ou dans une base de données si la mémoire disponible est insuffisante.

Comment ça marche

L'algorithme fonctionne selon une approche de recherche en profondeur basée sur la pile. Voici la répartition étape par étape :

1. Choisissez une cellule de départ et marquez-la comme visitée.
2. Tant qu'il y a des cellules non visitées :
   • Regardez les cellules voisines qui n’ont pas encore été visitées.
   • S'il existe au moins un voisin non visité :
     • Choisissez au hasard l’un des voisins non visités.
     • Supprimez le mur entre la cellule actuelle et la cellule voisine choisie.
     • Déplacez-vous vers le voisin choisi et marquez-le comme visité.
     • Poussez la cellule actuelle sur la pile.
   • S'il n'existe aucun voisin non visité :
     • Revenez en arrière en supprimant la dernière cellule de la pile.
3. Continuez ce processus jusqu’à ce que la pile soit vide.

Un fait intéressant à propos de cet algorithme est qu'il fonctionne à la fois comme générateur de labyrinthe et comme solutionneur de labyrinthe. Si vous l'exécutez sur un labyrinthe déjà généré et que vous vous arrêtez lorsque vous atteignez le point final décidé, la pile contiendra la solution du labyrinthe.

En fait, j'ai deux versions de cet algorithme en jeu sur ce site : une version basée sur la file LIFO pour générer des labyrinthes sur cette page et une version basée sur la récursivité pour résoudre des labyrinthes, ainsi que des labyrinthes générés par d'autres algorithmes (c'est ainsi que les cartes avec les solutions sont créées). Avoir deux versions différentes est juste pour le sport car je suis un nerd qui trouve cela intéressant, l'une ou l'autre aurait pu fonctionner pour les deux ;-)