C12.6 : TD Labyrinthe
Présentation
Généralités
Ce TD propose différentes activités autour de la notion de labyrinthe :
- - affichage d'un labyrinthe avec la librairie pygame ;
- - déplacement d'un pion dans un labyrinthe par l'utilisateur ;
- - recherche des solutions au labyrinthe par l'ordinateur.
Implémentation du labyrinthe
Il existe plusieurs façons d'implémenter un labyrinthe.
La méthode la plus immédiate est probablement la liste de liste :
[[1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 1],
[0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1]]Cependant, nous choisissons, dans ce TD, d'implémenter les labyrinthes sous la forme de graphes non orientés :
A faire :
En vous basant sur la classe de l'activité "C12.2 : Parcours d'un graphe", écrire une classe pour les graphes non orientés.
Affichage d'un labyrinthe
Afin de visualiser le labyrinthe, on utilisera la librairie Pygame.
Lien sur ostralo.net : Initiation à l'utilisation de la librairie pygame
A faire :
Écrire le code du programme qui permet d'obtenir un affichage visuel du labyrinthe.
Résolution d'un labyrinthe par l'utilisateur
A faire :
Écrire le code du programme qui permet à l'utilisateur de déplacer un pion (par exemple un rond rouge) dans le labyrinthe, sans traverser les murs.
Compléter le code de façon à ce que le programme indique que le pion arrive sur la case de sortie du labyrinthe.
Résolutions d'un labyrinthe par l'ordinateur
Résolution "au hasard"
Écrire le code du programme qui permet à l'ordinateur de déplacer un pion dans le labyrinthe au hasard, sans traverser les murs.
Compléter le code de façon à ce que le programme indique que le pion arrive sur la case de sortie du labyrinthe.
On fera en sorte que les déplacements du pions soient visibles par l'utilisateur.
Résolution avec un parcours un profondeur d'abord
En reprenant et en adaptant la fonction def parcours_rec_profondeur(g, sommet, liste_sommets_visites) de C12.2, écrire le code du programme qui permet à l'ordinateur de déplacer un pion dans le labyrinthe jusqu'à ce qu'il trouve la sortie.
On fera en sorte que les déplacements du pions soient visibles par l'utilisateur.
Le meilleur chemin pour sortir du labyrinthe
En vous appuyant sur l'exercice n° 3, écrire le code du programme qui permet à l'ordinateur de trouver une des solutions les plus courtes pour sortir du labyrinthe.
Pour aller plus loin
Ecrire le code du programme qui permet à l'utilisateur de construire lui-même un labyrinthe.
Cette partie du programme doit aboutir à un graphe.