Générateur de labyrinthe d’algorithme d’arbre de croissance

L’algorithme de l’arbre en croissance est intéressant, car il peut émuler le comportement de plusieurs autres algorithmes, selon la façon dont la cellule suivante est choisie pendant la génération. L’implémentation sur cette page utilise une approche axée sur l’étendue, semblable à une file d’attente.

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.

À propos de l’algorithme de croissance des arbres

L’algorithme Growing Tree est une méthode flexible et puissante pour générer des labyrinthes parfaits. L’algorithme est intéressant parce qu’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, selon la façon dont vous sélectionnez la cellule suivante à traiter.

Comment fonctionne l’algorithme de croissance des arbres

Étape 1 : Initialisation

• Commencez par 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 du labyrinthe

• Bien que la liste des cellules ne soit pas vide :
  • Sélectionnez une cellule dans la liste en fonction d’une stratégie spécifique (expliquée ci-dessous).
  • Sculptez un passage de la cellule sélectionnée à l’un de ses voisins non visités (choisi au hasard).
  • Ajoutez le voisin à la liste puisqu’il fait maintenant partie du labyrinthe.
  • Si la cellule sélectionnée n’a pas de voisins non visités, supprimez-la de la liste.

Étape 3 : Cessation d’emploi

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

Stratégies de sélection cellulaire (flexibilité de l’algorithme)

La caractéristique déterminante de l’algorithme Growing Tree est la façon dont vous choisissez la cellule à traiter ensuite. Ce choix affecte considérablement l’apparence du labyrinthe :

Nouvelle cellule (comportement de type pile) – Backtracker récursif :

• Sélectionnez toujours la cellule ajoutée la plus récemment.
• Produit de longs couloirs 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 une cellule au hasard dans la liste à chaque fois.
• Crée un labyrinthe plus uniformément réparti avec des chemins complexes et enchevêtrés.
• Moins de longs couloirs et plus de branchements.

Cellule la plus ancienne (comportement semblable à une 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 axé sur la largeur.
• Des passages courts et buissonnants avec des connexions denses.
• (C’est la version mise en œuvre ici)

Approches hybrides :

Combinez des stratégies pour des caractéristiques variées du labyrinthe. Par exemple:

• 90% les plus récents, 10% aléatoires : Ressemble principalement à un labyrinthe de backtracker récursif, mais avec des branches occasionnelles qui brisent de longs couloirs.
• 50% les plus récents, 50% les plus anciens : Équilibre les longs couloirs avec une croissance buissonnante.