Labyrinthes Sidewinder

Labyrinthes : différents algorithmes

Labyrinthe Sidewinder

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Labyrinthe Sidewinder

Cet algorithme simple est très similaire à l’algorithme de l’arbre binaire, et seulement légèrement plus compliqué. Le labyrinthe est généré ligne par ligne : Pour chaque cellule, décidez au hasard de creuser un passage vers la droite. Si un passage n’est pas creusé, alors considérez le passage horizontal qui vient d’être complété, formé par la cellule actuelle et toutes les cellules à gauche qui ont creusé des passages menant jusqu’à elle. Choisissez au hasard une cellule le long de ce passage, et creusez un passage vers le haut à partir de celle-ci (qui doit être la cellule actuelle si la cellule adjacente n’a pas creusé). Alors qu’un labyrinthe en arbre binaire monte toujours depuis la cellule la plus à gauche d’un passage horizontal, un labyrinthe Sidewinder monte depuis une cellule aléatoire. Alors qu’un arbre binaire a les bords supérieur et gauche du labyrinthe formant un long passage, un labyrinthe Sidewinder n’a que le bord supérieur formant un long passage. Comme l’arbre binaire, un labyrinthe Sidewinder peut être résolu de manière déterministe sans erreur de bas en haut, car à chaque ligne, il y aura toujours exactement un passage menant vers le haut. Une solution à un labyrinthe Sidewinder ne reviendra jamais sur elle-même ou ne visitera jamais une ligne plus d’une fois, bien qu’elle « serpente de côté en côté ». Le seul type de cellule qui ne peut pas exister dans un labyrinthe Sidewinder est une impasse avec le passage orienté vers le bas, car cela contredirait le fait que chaque passage montant mène au début. Un labyrinthe Sidewinder a tendance à avoir une solution élitiste, où le bon chemin est très direct, mais il y a beaucoup de longs faux chemins descendant du haut à côté de lui.