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

L’algorithme Growing Tree est intéressant, car il peut émuler le comportement de plusieurs autres algorithmes, selon la façon dont la prochaine cellule est choisie lors de la génération. L’implémentation sur cette page utilise une approche en largeur, de type 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 l’arbre en croissance

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 prochaine cellule à traiter.

Comment fonctionne l’algorithme de l’arbre en croissance

Étape 1 : Initialisation

• Commencez par une grille de cellules non visitées.
• Choisissez une cellule de départ au hasard et ajoutez-la à une liste.

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

• Bien que la liste de cellules ne soit pas vide : Sélectionnez une cellule de la liste selon une stratégie spécifique (expliquée ci-dessous). Taillez un passage de la cellule sélectionnée vers l’un de ses voisins non visités (choisi au hasard). Ajoute 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, retirez-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 tout le labyrinthe a été sculpté.

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

La caractéristique définissante 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 :

Cellule la plus récente (comportement de type pile) – Retour en arrière récursif :

• Choisissez toujours la cellule la plus récemment ajoutée.
• Produit de longs corridors 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 aléatoire) :

• Choisis une cellule au hasard dans la liste à chaque fois.
• Ça crée un labyrinthe plus uniformément distribué avec des chemins complexes et emmêlés.
• Moins de longs corridors et plus de bifurcations.

Cellule la plus ancienne (comportement en file d’attente) :

• Choisissez toujours la case la plus ancienne de la liste.
• Génère des labyrinthes avec une dispersion plus uniforme, comme un motif de recherche en largeur.
• Des passages courts et broussailleux avec des connexions denses.
• (Voici la version implémentée ici)

Approches hybrides :

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

• 90% les plus récents, 10% aléatoires : Ça ressemble surtout à un labyrinthe récursif de retour en arrière, mais avec des branches occasionnelles qui brisent de longs corridors.
• 50% les plus récents, 50% les plus anciens : Équilibre les longs corridors avec une croissance touffue.

Lectures complémentaires

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

• Générateur de labyrinthes récursifs de type Backtracker
• Générateur de labyrinthe d’algorithme d’Eller
• Chasser et tuer générateur de labyrinthe