Algorithme "chasse et tue"

Labyrinthes : différents algorithmes

Algorithme “chasse et tue”

Traduit en Français par moi-même. Les originaux sont ici.

L’algorithme “chasse et tue” (Hunt and kill algorithm) : cet algorithme est pratique parce qu’il ne requiert pas d’espace mémoire supplémentaire ni de pile, c’est pourquoi c’est le plus adapté à la création de grands labyrinthes.

De plus, comme il n’y a aucune règle particulière qui doit être systématiquement appliquée, c’est aussi le plus facile à modifier pour essayer d’avoir des motifs originaux. Il est très proche de l’algorithme du retour récursif, mis à part le fait que lorsqu’il n’y aucune cellule “vierge” à côté de la cellule courante, vous passez en mode “chasse” et vous recherchez dans tout le labyrinthe la première cellule qui n’est pas vierge et qui en côtoie une qui l’est.

A ce moment là, vous recommencez à creusez à partir de la cellule non-vierge. La labyrinthe est terminé si, lorsque vous passez en mode “chasse”, il n’y a plus aucune cellule à “chasser”. Cet algorithme a tendance à faire des labyrinthes avec un facteur “rivière” grand, mais pas aussi grand que celui du “retour-récursif”.

Vous pouvez diminuer le facteur “rivière” et entrant plus souvent, et de manière aléatoire, en mode “chasse”. Cet algorithm est long principalement à cause du temps mis à chercher les dernières cellules, mais il n’est tout de même pas aussi long que l’algorithme de Kruskal. On peut même le faire non plus en tant que “creuseur”, mais en tant que poseur de murs, sachant qu’il faut de temps à autre se téléporter afin d’éviter les problèmes qu’a l’algorithme du “retour-récursif” en tant que poseur de murs.