Chasser et tuer générateur de labyrinthe

L’algorithme Hunt and Kill est vraiment une version modifiée du Backtracker récursif. La modification consiste à scanner systématiquement (ou « chasser ») pour qu’une nouvelle cellule continue à partir du moment où elle ne peut pas aller plus loin, par opposition à une véritable recherche récursive, qui reviendra toujours à la cellule précédente de la pile.

Pour cette raison, cet algorithme peut facilement être adapté pour générer des labyrinthes avec une apparence différente, simplement en choisissant d’entrer en mode « chasse » plus souvent ou selon des règles spécifiques. La version implémentée ici n’entre en mode « chasse » que lorsqu’elle ne peut pas aller plus loin 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 Hunt and Kill

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

Comment fonctionne l’algorithme hunt and kill pour la génération de labyrinthes

Étape 1 : Commencez à une cellule aléatoire

• Trouvez une cellule aléatoire dans la grille et marquez-la comme visitée.

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

• Choisissez un voisin nonvisé aléatoire.
• Déplacez-vous vers ce voisin, marquez-le comme visité et découpez un chemin entre la cellule précédente et la nouvelle cellule.
• Répétez jusqu’à ce qu’il n’y ait plus de voisins nonvisés.

Étape 3 : Phase de chasse (retour en arrière via la numérisation)

• Analysez 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.