Générateur de labyrinthe de chasse et de meurtre

L'algorithme Hunt and Kill est en réalité une version modifiée du Recursive Backtracker. La modification consiste à parcourir systématiquement (ou « chasser ») une nouvelle cellule à partir de laquelle poursuivre lorsqu'il est impossible d'aller plus loin, contrairement à une véritable recherche récursive qui revient toujours à la cellule précédente dans la pile.

De ce fait, cet algorithme peut être facilement adapté pour générer des labyrinthes d'apparence et de comportement variés, simplement en choisissant d'activer plus fréquemment le mode « recherche » ou selon des règles spécifiques. La version implémentée ici n'active ce mode que lorsqu'elle ne peut plus s'éloigner de la cellule actuelle.

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 chasse et d'élimination

L'algorithme Hunt and Kill est une méthode simple mais efficace pour générer des labyrinthes. Il s'apparente à une recherche en profondeur (comme l'algorithme de retour arrière récursif), à ceci près que, lorsqu'il ne peut plus progresser à partir de sa position actuelle, il parcourt systématiquement le labyrinthe pour trouver une nouvelle cellule. L'algorithme se compose de deux phases principales : la marche et la recherche.

Comment fonctionne l'algorithme de chasse et d'élimination pour la génération de labyrinthes

Étape 1 : Commencez par une cellule aléatoire

• Trouvez une cellule au hasard dans la grille et marquez-la comme visitée.

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

• Choisissez un voisin aléatoire que vous n'avez pas encore visité.
• Déplacez-vous vers cette cellule voisine, marquez-la comme visitée et tracez un chemin entre la cellule précédente et la nouvelle.
• Répétez l'opération jusqu'à ce qu'il ne reste plus aucun voisin non visité.

Étape 3 : Phase de recherche (Retour sur les lieux par balayage)

• Scannez la grille ligne par ligne (ou colonne par colonne).
• Trouvez la première cellule non visitée qui a au moins une voisine visitée.
• Connectez cette cellule à une cellule voisine visitée pour reprendre la phase de marche.
• Répétez l'opération 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 de type Backtracker récursif
• Générateur de labyrinthe avec l'algorithme de Wilson
• Générateur de labyrinthe avec l'algorithme de Kruskal