Générateur de labyrinthes récursifs de type Backtracker

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 rechercherait généralement simplement chaque niveau dans un ordre linéaire. Il a tendance à produire des labyrinthes avec de longs corridors sinueux et une solution très longue et sinueuse.

Un labyrinthe parfait est un labyrinthe dans lequel il existe exactement un chemin reliant n’importe quel point du labyrinthe à n’importe quel autre point. Cela signifie que vous ne pouvez pas finir par tourner en rond, mais vous rencontrerez souvent des culs-de-sac, ce qui vous obligera à faire demi-tour et à revenir en arrière.

Les cartes de labyrinthe générées ici incluent une version par défaut sans aucune position de départ et d'arrivée, vous pouvez donc les décider vous-même : il y aura une solution de n'importe quel point du labyrinthe à n'importe quel autre point. Si vous voulez trouver de l'inspiration, vous pouvez activer une position de départ et d'arrivée suggéré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 (labyrinthes sans boucles et avec un seul chemin entre deux points). Il est simple, efficace et produit des labyrinthes visuellement attrayants avec de longs corridors sinueux.

Malgré son nom, il n’est pas nécessairement nécessaire de l’implémenter à l’aide de la récursivité. Il est souvent implémenté dans une approche itérative en utilisant une file d'attente LIFO (c'est-à-dire une pile). Pour les labyrinthes très grands, l'utilisation de la récursivité est plus susceptible d'entraîner un dépassement de la pile d'appels, selon le langage de programmation et 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 à l'aide d'une approche de recherche en profondeur basée sur la pile. Voici la procédure é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 y a au moins un voisin non visité :
     • Choisissez au hasard l'un des voisins non visités.
     • Retirez le mur entre la cellule actuelle et la cellule voisine choisie.
     • Déplacez-vous vers le voisin choisi et marquez-le comme visité.
     • Pousse la cellule actuelle sur la pile.
   • S'il n'existe aucun voisin non visité :
     • Retournez 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 un générateur de labyrinthe et comme un résolveur 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 une file d'attente LIFO pour générer des labyrinthes sur cette page et une version basée sur la récursivité pour résoudre des labyrinthes, également des labyrinthes générés par d'autres algorithmes (c'est ainsi que les cartes avec les solutions sont faites). Avoir deux versions différentes, c'est juste pour le sport parce que je suis un nerd qui trouve ça intéressant, l'une ou l'autre aurait pu fonctionner pour les deux ;-)