Chasser et tuer générateur de labyrinthe

L’algorithme Hunt and Kill est en réalité une version modifiée du Recursive Backtracker. La modification consiste à balayer systématiquement (ou « chasser ») une nouvelle cellule à partir de laquelle elle ne peut pas aller plus loin, contrairement à une véritable recherche récursive, qui reviendra toujours à la cellule précédente de la pile.

Grâce à cela, cet algorithme peut facilement être adapté pour générer des labyrinthes avec un aspect et une sensation différents, simplement en choisissant d’entrer plus souvent en mode « chasse » ou selon des règles spécifiques. La version implémentée ici n’entre en mode « chasse » que lorsqu’elle ne peut pas s’éloigner de la cellule actuelle.

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 chasse et de mise à mort

L’algorithme Hunt and Kill est une méthode simple mais efficace pour générer des labyrinthes. C’est quelque peu similaire à une recherche en profondeur (c’est-à-dire l’algorithme Recursive Backtracker), sauf que lorsqu’il ne peut pas s’éloigner de la position actuelle, il scanne systématiquement (ou « chasse ») le labyrinthe pour trouver une nouvelle cellule à partir de laquelle continuer. L’algorithme se compose de deux phases principales : la marche et la chasse.

Comment fonctionne l’algorithme de chasse et de tuerie pour la génération de labyrinthes

Étape 1 : Commencez à une cellule aléatoire

• Trouve une cellule aléatoire dans la grille et marque-la comme visitée.

Étape 2 : Phase de marche (marche aléatoire)

• Choisissez un voisin non visité au hasard.
• Déplacez-vous vers ce voisin, marquez-le comme visité, et tracez un chemin entre la cellule précédente et la nouvelle.
• Répétez jusqu’à ce qu’il ne reste plus aucun voisin non visité.

Étape 3 : Phase de chasse (revenir en arrière via scanning)

• Scannez la grille ligne par ligne (ou colonne par colonne).
• Trouvez la première cellule non visitée qui a au moins un voisin visité.
• Connectez cette cellule à un voisin visité pour reprendre la phase de marche.
• Répétez jusqu’à ce que toutes les cellules aient été visitées.

Lectures complémentaires

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

• Générateur de labyrinthe d’algorithme de Kruskal
• Générateur de labyrinthe d’algorithme de Wilson
• Générateur de labyrinthe d’algorithme d’arbre de croissance