▶ TP Labyrinthe⚓︎

Objectif

L'objectif de ce TP est de trouver et d'afficher le chemin le plus court entre une entrée (en vert sur l'illustration ci-dessous) et une sortie (en rouge) d'un labyrinthe, créé aléatoirement comme on l'a fait ici.

Le principe est de représenter le labyrinthe comme un graphe, puis d'utiliser la recherche d'un chemin entre le départ et l'arrivée à l'aide d'un parcours BFS.

Vous pouvez tout faire from scratch, ou bien utiliser ce fichier qui contient:

les classes Graphe, Cellule et Labyrinthe écrites précédemment;
les constantes et l'affichage utilisées dans l'activité de génération du labyrinthe;
les instructions et la boucle des événements de Pygame.

Travail à réaliser

Dans la partie Fonctions, copier les fonctions recupere_chemin et trouve_chemin écrites dans l'activité précédente.
Adapter la fonction recupere_chemin pour qu'elle renvoie une liste (des sommets du chemin entre la source et la cible), et non une chaîne de caractères.
Compléter la fonction affiche_chemin .
Choisir une adresse pour le départ et l'arrivée dans la partie Constantes.
Le labyrinthe doit maintenant être modélisé par un graphe selon ce principe: chaque cellule (c'est-à-dire un tuple (ligne i, colonne j)) est un sommet du graphe et deux sommets sont reliés par une arête s'il n'y a pas de mur entre les cellules qu'ils représentent. En pratique on parcourt la grille du labyrinthe et pour chaque cellule, s'il n'y a pas de mur nord alors on ajoute une arête avec la cellule/sommet du dessus, s'il n'y pas de mur ouest alors on ajoute une arête avec la cellule/sommet de gauche, etc.

Compléter la partie Graphe, puis affecter à la variable chemin le chemin entre la source et la cible.
Passer les bons arguments à l'appel de la fonction affiche_chemin dans la partie Pygame.
F5

Si vous avez fini...

Modifier le programme pour qu'il affiche cellule par cellule l'avancée dans le labyrinthe du départ vers l'arrivée...