Spiele - Labyrinth zeichnen mit Excel

Générer un labyrinthe

Les méthodes pour trouver le chemain à travers un labyrinthe sont décrites partout. Dans cet article je vous décris la génération d'un labyrinthe.

Algorithme de Wilson

L'algorithme de Wilson génère un labyrinthe par une séquence de marches aléatoires en éliminant les boucles. A partir d'une cellule choisie fortuitement, une première marche aléatoire est générée avec une longueur finale égale à la somme de largueur et hauteur de la plage. Cette première marche est considérée comme le labyrinthe initial.

Une nouvelle cellule, non encore appartenant au labyrinthe est choisie fortuitement, une nouvelle marche aléatoire est lancée et poursuivie jusqu'à ce qu'elle

1. rencontre sa propre trace. Dans ce cas c'est une boucle, qui est éliminée. La marche est reprise à partir de la cellule rencontrée
2. atteint une cellule du labyrinthe. Dans ce cas, la trace y est ajoutée

De nouvelles marches sont commencées pour autant qu'il reste des cellules non encore couvertes.

Video démo

La vidéo illustre la génération d'un labyrinthe au moyen du module VBA développé à cet effet.