Comprendre (pour tous) la génération aléatoire de labyrinthes

C’était le sujet du topo du jour, dont reste un vague tableau :

cm 2019-02-08 explications génération aléatoire labyrinthe_1

Et on se souvient que pour (pas comme ci-dessus) largeur=9 et hauteur=7, alors largeur//2=4 et hauteur//2=3 et il y a donc 4 \times 3 = 12 cases «intersections de lignes oranges » à vider pour estimer que le labyrinthe est creusé.

111111111
111111111
111111111
111111111
111111111
111111111
111111111

Étape 1 :

On creuse un chemin initial de longueur 6 (par exemple) :

  • en partant d’une case aléatoire parmi les 12 à grignoter, ici ligne 3 (la quatrième) et colonne 7 (la huitième)
  • et en testant les directions « valables » :
    • déplacement horizontal ou vertical de deux cases,
    • rester dans la grille,
    • pas de zéro !
  • et en grignotant donc deux cases, ici :
    • d’abord vers le haut,
    • puis vers la gauche,
    • puis vers le bas,
    • puis vers la gauche,
    • puis vers le bas.

111111111
111110001
111110101
111000101
111011111
111011111
111111111

Étape 2 : tant que « nombre de cases à grignoter > 0 »

  • En partant d’une case aléatoire parmi les cases restant à grignoter
  • et en testant les directions « valables » et en grignotant donc deux cases, ici, je continue à grignoter jusqu’à ce que je tombe sur une case du chemin obtenu après l’étape précédente, avec la condition
while carte[y][x]>0 or not ancienne[y][x]==0:

c’est-à-dire « tant que la case est à grignoter ou qu’elle n’était pas grignotée dans la carte copie après l’étape précédente ».

debut chemin en 5 5
111111111
111110001
111110101
111000101
111010111
111010111
111111111

debut chemin en 1 3
111111111
111110001
111110101
101000101
101010111
100010111
111111111

debut chemin en 1 1
111111111
100000001
111110101
101000101
101010111
100010111
111111111

debut chemin en 7 5
111111111
100000001
111110101
101000101
101010111
100010001
111111111

Bonnes vacances !

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.