Un labyrinthe sera représenté en machine par une liste de listes Python. Dans la liste lab, pour chaque couple de coordonnées (i, j), lab[i][j] sera un objet de type Cellule possédant trois attributs :
un booléen est indiquant si le mur à l'est de cette cellule est présent ou non (True par défaut),
un booléen sud indiquant si le mur au sud de cette cellule est présent ou non (True par défaut),
un entier zone donnant la zone à laquelle appartient cette cellule. Deux cellules sont dans la même zone s'il existe un chemin menant de l'une à l'autre dans le labyrinthe.
Remarque
Les cellules n'ont que deux murs et pas quatre afin d'éviter les doublons (le mur au sud d'une cellule pourrait correspondre au mur au nord de la cellule du dessous...).
Lors du dessin du labyrinthe, les murs au nord de la première ligne et à l'ouest de la première colonne seront dessinés par défaut.
La fonction base_labyrinthe permet de créer un labyrinthe dont tous les murs sont pleins. Elle prend en argument deux entiers strictement positifs, la hauteur hauteur et la largeur largeur du labyrinthe.
Initialement, chaque cellule du labyrinthe est fermée sur elle-même : toutes les cellules sont donc initialement dans des zones différentes.
On peut accéder aux différentes cellules en procédant ainsi :
🐍 Console Python
>>> # Création de la base d'un labyrinthe de hauteur 4 et largeur 10>>> lab=base_labyrinthe(4,10)>>> # Le mur à l'est de la cellule en haut à gauche est présent>>> lab[0][0].estTrue>>> # La cellule de la 3ème ligne, 8ème colonne est dans la zone 26>>> lab[2][7].zone26
La fonction dessin_console renvoie la chaîne de caractères représentant le labyrinthe passé en argument :
Une variante de l'algorithme de Kruskal permet de construire des labyrinthes dans lesquels toutes les cellules appartiennent à la même zone et ne comportant pas de « boucles ».
On débute avec un labyrinthe dans lequel tous les murs sont présents. Au fil du traitement, on retire des murs de façon à fusionner des zones distinctes.
Les étapes de l'algorithme sont les suivantes :
créer un labyrinthe dans lequel tous les murs sont présents ;
créer la liste de tous les murs ;
mélanger cette liste ;
récupérer (et supprimer) le dernier mur de la liste jusqu'à ce qu'elle soit vide :
si ce mur sépare deux cellules de la même zone, ne rien faire,
s'il sépare deux cellules de zones différentes :
supprimer ce mur,
fusionner les zones correspondantes.
La dernière étape est importante : il faut non seulement faire en sorte que les deux cellules séparées par le mur soient dans la même zone mais aussi toutes les cellules communicantes. Ainsi, si l'on supprime un mur entre une zone de 5 cellules et une autre de 3 cellules, on obtiendra une nouvelle zone de 8 cellules.
La figure ci-dessous illustre la fusion de plusieurs zones (la construction du labyrinthe n'est pas terminée à la fin de l'animation).
La fonction murs_aleatoires prend en argument les dimensions du labyrinthe (hauteur et largeur) et renvoie la liste mélangée de ses murs sous la forme d'une liste de triplets (i, j, orientation). Le triplet (2, 7, "est") désignera par exemple le mur à l'est de la cellule de coordonnées (2, 7).
Cette fonction renvoie l'ensemble des murs « intérieurs » du labyrinthe : les murs à l'est des cellules de la dernière colonne et ceux au sud de la dernière ligne ne figurent pas dans la liste.
Pour faciliter la correction du code l'aspect « aléatoire » est limité et la fonction murs_aleatoires renvoie toujours le même mélange pour des dimensions données.
Remarque
Toutes les classes et fonctions citées plus haut :
Cellule,
base_labyrinthe,
dessin_console,
murs_aleatoires
sont déjà chargées en mémoire. Il est inutile de les retaper.
Compléter la fonction labyrinthe prenant en argument deux entiers strictement positifs hauteur et largeur et renvoyant le labyrinthe obtenu grâce à l'algorithme de Kruskal.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)