Générateur de labyrinthe d'algorithme d'arbre en croissance

L'algorithme Growing Tree est intéressant, car il peut émuler le comportement de plusieurs autres algorithmes, en fonction de la manière dont la cellule suivante est choisie lors de la génération. L'implémentation sur cette page utilise une approche de type file d'attente, axée sur la largeur.

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.

À propos de l'algorithme Growing Tree

L'algorithme Growing Tree est une méthode flexible et puissante pour générer des labyrinthes parfaits. L'algorithme est intéressant car il peut émuler le comportement de plusieurs autres algorithmes de génération de labyrinthes, tels que l'algorithme de Prim, le retour en arrière récursif et la division récursive, en fonction de la manière dont vous sélectionnez la cellule suivante à traiter.

Comment fonctionne l'algorithme Growing Tree

Étape 1 : Initialisation

• Commencez avec une grille de cellules non visitées.
• Choisissez une cellule de départ aléatoire et ajoutez-la à une liste.

Étape 2 : Boucle de génération de labyrinthe

• Tant que la liste des cellules n’est pas vide :
  • Sélectionnez une cellule dans la liste en fonction d’une stratégie spécifique (expliquée ci-dessous).
  • Creusez un passage depuis la cellule sélectionnée vers l'une de ses voisines non visitées (choisies au hasard).
  • Ajoutez le voisin à la liste puisqu'il fait désormais partie du labyrinthe.
  • Si la cellule sélectionnée n'a pas de voisins non visités, supprimez-la de la liste.

Étape 3 : Résiliation

• L'algorithme se termine lorsqu'il n'y a plus de cellules dans la liste, ce qui signifie que le labyrinthe entier a été creusé.

Stratégies de sélection des cellules (flexibilité de l'algorithme)

La caractéristique déterminante de l'algorithme Growing Tree est la manière dont vous choisissez la cellule à traiter ensuite. Ce choix affecte considérablement l'apparence du labyrinthe :

Cellule la plus récente (comportement de type pile) – Backtracker récursif :

• Sélectionnez toujours la cellule la plus récemment ajoutée.
• Produit des couloirs longs et sinueux avec de nombreuses impasses (comme un labyrinthe de recherche en profondeur).
• Les labyrinthes ont tendance à avoir de longs passages et sont faciles à résoudre.

Cellule aléatoire (algorithme de Prim randomisé) :

• Choisissez à chaque fois une cellule aléatoire dans la liste.
• Crée un labyrinthe plus uniformément réparti avec des chemins complexes et emmêlés.
• Moins de longs couloirs et plus de ramifications.

Cellule la plus ancienne (comportement de type file d'attente) :

• Choisissez toujours la cellule la plus ancienne de la liste.
• Génère des labyrinthes avec une répartition plus uniforme, comme un modèle de recherche en largeur d'abord.
• Des passages courts et touffus avec des liaisons denses.
• (Il s'agit de la version implémentée ici)

Approches hybrides :

Combinez des stratégies pour différentes caractéristiques du labyrinthe. Par exemple :

• 90 % plus récent, 10 % aléatoire : ressemble principalement à un labyrinthe de type backtracker récursif, mais avec des branches occasionnelles qui interrompent de longs couloirs.
• 50 % plus récent, 50 % plus ancien : équilibre les longs couloirs avec une croissance touffue.