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

L'algorithme de l'arbre croissant est intéressant car il peut imiter le comportement de plusieurs autres algorithmes, selon la façon dont la cellule suivante est choisie lors de sa génération. L'implémentation présentée sur cette page utilise une approche de type parcours en largeur avec une file d'attente.

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 de l'arbre de croissance

L'algorithme de l'arbre croissant est une méthode flexible et puissante pour générer des labyrinthes parfaits. Cet algorithme est intéressant car il peut imiter le comportement de plusieurs autres algorithmes de génération de labyrinthes, tels que l'algorithme de Prim, le retour arrière récursif et la division récursive, selon la manière dont on sélectionne la cellule suivante à traiter.

Fonctionnement de l'algorithme de l'arbre de croissance

É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

• Tant que la liste des cellules n'est pas vide : sélectionnez une cellule selon une stratégie spécifique (expliquée ci-dessous). Créez un passage depuis la cellule sélectionnée jusqu'à l'une de ses voisines non visitées (choisie aléatoirement). Ajoutez cette voisine à la liste, car elle fait désormais partie du labyrinthe. Si la cellule sélectionnée n'a pas de voisine non visitée, retirez-la de la liste.

Étape 3 : Terminaison

• L'algorithme s'achève lorsqu'il n'y a plus de cellules dans la liste, ce qui signifie que le labyrinthe entier a été tracé.

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

La caractéristique principale de l'algorithme Growing Tree réside dans le choix de la cellule à traiter ensuite. Ce choix influence considérablement l'apparence du labyrinthe :

Nouvelle cellule (comportement de type pile) – Retour arrière récursif :

• Sélectionnez toujours la cellule ajoutée le plus récemment.
• Produit de longs couloirs sinueux avec de nombreuses impasses (comme un labyrinthe de recherche en profondeur).
• Les labyrinthes ont généralement 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 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 à répartition plus uniforme, comme un modèle de recherche en largeur.
• Passages courts et touffus, aux connexions denses.
• (Il s'agit de la version implémentée ici)

Approches hybrides :

Combinez les stratégies en fonction des caractéristiques variées du labyrinthe. Par exemple :

• 90 % les plus récents, 10 % aléatoires : ressemble principalement à un labyrinthe de type « backtracking » récursif, mais avec des embranchements occasionnels qui interrompent les longs couloirs.
• 50 % de plantes les plus récentes, 50 % des plus anciennes : un équilibre entre les longs couloirs et la végétation dense.

Lectures complémentaires

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

• Générateur de labyrinthe avec l'algorithme de Wilson
• Générateur de labyrinthe de chasse et de meurtre
• Générateur de labyrinthe de type Backtracker récursif