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

L’algorithme de retour en arrière récursif est en réalité une recherche en profondeur à usage général. Lorsqu’elle est utilisée pour la génération de labyrinthes, elle est légèrement modifiée pour choisir le chemin au hasard, alors que si elle est utilisée pour la recherche réelle, on cherche généralement chaque niveau dans un ordre linéaire. Elle a tendance à créer 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 retour en arrière récursif est une méthode de recherche en profondeur pour générer des labyrinthes parfaits (des labyrinthes sans boucles et avec un seul chemin entre deux points quelconques). Elle 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 d’avoir été implémenté par récursion. Elle est souvent mise en œuvre selon une approche itérative à l’aide d’une file LIFO (c’est-à-dire une pile). Pour les très grands labyrinthes, l’utilisation de la récursion est plus susceptible de provoquer un débordement de pile d’appels, selon le langage de programmation et la mémoire disponible. Une file LIFO peut être plus facilement adaptée pour gérer de grandes quantités de données, même en gardant la file sur disque ou dans une base de données si la mémoire disponible est insuffisante.

Comment ça fonctionne

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 case de départ et marquez-la comme visitée.
2. Bien qu’il y ait des cellules non visitées : Regardez les cellules voisines qui n’ont pas encore été visitées. Si au moins un voisin non visité existe : Choisissez au hasard un des voisins non visités. Enlève le mur entre la cellule actuelle et le voisin choisi. Déménagez vers le voisin choisi et marquez-le comme visité. Poussez la cellule actuelle sur la pile. Si aucun voisin non visité n’existe : Revenir en arrière en faisant apparaître 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 labyrinthes et comme solveur de labyrinthes. Si tu le fais jouer sur un labyrinthe déjà généré et que tu t’arrêtes juste quand tu atteins le point final, la pile contiendra la solution du labyrinthe.

J’ai en fait deux versions de cet algorithme en cours sur ce site : une file d’attente LIFO pour générer des labyrinthes sur cette page et une autre basée sur la récursion pour résoudre des labyrinthes, ainsi que des labyrinthes générés par d’autres algorithmes (c’est comme ça que les cartes avec les solutions sont créées). Avoir deux versions différentes, c’est juste pour le sport parce que je suis un nerd qui trouve ça intéressant, les deux auraient pu fonctionner pour les deux;-)

Lectures complémentaires

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

• Générateur de labyrinthe d’algorithme d’arbre de croissance
• Chasser et tuer générateur de labyrinthe
• Générateur de labyrinthe d’algorithme de Wilson