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

L'algorithme Hunt and Kill est en fait une version modifiée du Recursive Backtracker. La modification consiste à rechercher systématiquement (ou "chasser") une nouvelle cellule à partir de laquelle continuer lorsqu'il n'est plus possible d'aller plus loin, par opposition à une véritable recherche récursive, qui reviendra toujours à la cellule précédente sur la pile.

Pour cette raison, 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 en mode "chasse" plus souvent ou selon des règles spécifiques. La version mise en œuvre ici n'entre en mode "chasse" que lorsqu'elle ne peut pas aller plus loin que 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 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 Recursive Backtracker), sauf que lorsqu'il ne peut pas aller plus loin à partir de la position actuelle, il parcourt (ou "chasse") systématiquement le labyrinthe pour trouver une nouvelle cellule à partir de laquelle continuer. L'algorithme se compose de deux phases principales : la marche et la chasse.

Fonctionnement de l'algorithme "Hunt and Kill" pour la génération de labyrinthes

Étape 1 : Commencer par une cellule aléatoire

• Trouver une cellule aléatoire dans la grille et la marquer comme visitée.

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

• Choisir un voisin aléatoire non visité.
• 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éter l'opération jusqu'à ce qu'il n'y ait plus de voisins non visités.

Étape 3 : Phase de chasse (retour en arrière par balayage)

• Balayez 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 l'opération jusqu'à ce que toutes les cellules aient été visitées.