Algorithme de la Division récursive

Labyrinthes : différents algorithmes

Algorithme de la Division récursive

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 !

Algorithme de la Division récursive

Cet algorithme est un peu similaire au retour-récursif, puisqu’ils sont tous deux basés sur une pile, sauf que celui-ci se concentre sur les murs plutôt que sur les passages. Commencez par créer un mur horizontal ou vertical aléatoire traversant la zone disponible dans une rangée ou une colonne aléatoire, avec une ouverture placée au hasard le long de celui-ci. Ensuite, répétez le processus de manière récursive sur les deux sous-zones générées par le mur de division. Pour de meilleurs résultats, privilégiez le choix horizontal ou vertical en fonction des proportions de la zone, par exemple une zone deux fois plus large que haute devrait être divisée plus souvent par un mur vertical. C’est l’algorithme le plus rapide sans biais directionnel, et peut même rivaliser avec les labyrinthes en arbre binaire car il peut terminer plusieurs cellules à la fois, bien qu’il ait le défaut évident de longs murs traversant l’intérieur. Cet algorithme est une forme de labyrinthes fractals imbriqués, sauf qu’au lieu de toujours créer des labyrinthes de taille de cellule fixe avec des labyrinthes de même taille dans chaque cellule, il divise la zone donnée de manière aléatoire en un labyrinthe de taille aléatoire 1×2 ou 2×1. La division récursive ne fonctionne pas comme un creuseur de passages, car cela aboutirait à un chemin de solution évident qui suit soit le bord extérieur, soit traverse directement l’intérieur.