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.