Labyrinthes en arbre binaire

Labyrinthes : différents algorithmes

Labyrinthes en arbre binaire

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 !

Labyrinthes en arbre binaire

C’est fondamentalement l’algorithme le plus simple et le plus rapide possible, cependant les labyrinthes qu’il produit ont une texture très biaisée. Pour chaque cellule, creusez un passage soit vers le haut, soit vers la gauche, mais pas les deux. Dans la version avec ajout de murs, pour chaque sommet ajoutez un segment de mur menant vers le bas ou vers la droite, mais pas les deux. Chaque cellule est indépendante de toutes les autres cellules, où vous n’avez pas besoin de vous référer à l’état des autres cellules lors de sa création. Par conséquent, c’est un véritable algorithme de génération de labyrinthe sans mémoire, sans limite de taille du labyrinthe que vous pouvez créer.
C’est fondamentalement un arbre binaire au sens informatique, si vous considérez le coin supérieur gauche comme la racine, où chaque nœud ou cellule a un parent unique qui est la cellule au-dessus ou à gauche de celle-ci. Les labyrinthes en arbre binaire sont différents des labyrinthes parfaits standards, puisqu’environ la moitié des types de cellules ne peuvent jamais exister en eux. Par exemple, il n’y aura jamais de carrefour, et toutes les impasses ont des passages pointant vers le haut ou vers la gauche, et jamais vers le bas ou vers la droite.
Le labyrinthe a tendance à avoir des passages menant en diagonale du coin supérieur gauche au coin inférieur droit, ce qui rend le labyrinthe beaucoup plus facile à naviguer du coin inférieur droit vers le coin supérieur gauche. Vous pourrez toujours voyager vers le haut ou vers la gauche, mais jamais les deux, donc vous pouvez toujours voyager de manière déterministe en diagonale vers le haut et vers la gauche sans rencontrer d’obstacles. C’est en voyageant vers le bas et vers la droite que vous rencontrerez des choix et des impasses. Notez que si vous retournez un labyrinthe en arbre binaire à l’envers et traitez les passages comme des murs et vice versa, le résultat est fondamentalement un autre arbre binaire.