Projet labyrinthe
- Objectifs:
Trouver la sortie d'un labyrinthe. Le programme construira un labyrinthe dans lequel un cercle rouge se déplace pour en sortir.
Dans la partie A, la boule devra se déplacer avec les touches de directions. C'est l'utilisateur qui guide vers la sortie.
Dans la partie B, un algorithme déterminera le chemin vers la sortie
Il y a deux parties dans le code :
Partie1: l'interface homme machine (ce que voit l’utilisateur) qui est codée avec un canevas dans une fenêtre ( voir la programmation d’un canevas dans Ressources-1 et 2: )
Partie2: le code de contrôle en python, on modélise un labyrinthe par un tableau à deux dimensions à n lignes et m colonnes avec n et m des entiers
Les lignes seront numérotées de 0 à n-1 et les colonnes de 0 à m-1.
La case en haut à gauche est repérée par (0,0) et la case en bas à droite par ( n-1, m-1).
Dans ce tableau :
- 0 représentera une case vide, hors case de départ et arrivée,
- 1 représentera un mur,
- 2 représentera le départ du labyrinthe,
- 3 représentera l'arrivée du labyrinthe.
Ainsi, en Python, le labyrinthe ci-dessous est représentée par le tableau de tableaux lab1:
- Travail demandé
- Proposer une répartition du travail entre les deux membres du groupe
- Proposer un calendrier prévisionnel afin de réaliser le projet dans le temps imparti,
- Réaliser les productions logicielles conformément aux demandes ci-dessous:
Partie A
Dans cette partie, le cercle se déplace dans le labyrinthe avec les touches de clavier
- Coder l'IHM
- Coder le code du déplacement d'un cercle rouge avec les touches de clavier
- Établir une documentation du programme.
Partie B
Dans cette partie, le cercle trouve la sortie automatiquement.
Il faut disposer de fonctions qui permettent au programme de trouver la sortie
- La fonction départ:
La fonction depart(lab) prend en paramètre un labyrinthe et renvoie un tuple qui correspond aux coordonnées de l'entrée du labyrinthe ( la case de valeur 2) , pour lab1 ci-dessus la fonction doit renvoyer (5,0)
- La fonction voisines:
On dit que deux cases d'un labyrinthe sont voisines si elles ont un côté commun. La fonction voisines(i, j, lab) prend en arguments deux entiers i et j représentant les coordonnées d’une case et un tableau lab qui représente un labyrinthe. Cette fonction renvoie la liste des coordonnées des cases voisines de la case de coordonnées ( i, j ) vers lesquelles on peut aller . L'ordre des éléments de cette liste n'importe pas.
Ainsi, l'appel voisines(1, 1, [ [1, 1, 1], [4, 0, 0], [1, 0, 1]] ) renvoie la liste [(2, 1), (1, 2)].
- La fonction solution
Pour déterminer la solution d'un labyrinthe, on parcourt les cases vides de proche en proche. Lors d’un tel parcours, afin d’éviter de tourner en rond, on choisit de marquer les cases visitées. Pour cela, le code remplace la valeur d'une case visitée dans le tableau représentant le labyrinthe par la valeur 4. La fonction solution(lab) prend en paramètre un labyrinthe représenté par la variable lab, elle doit renvoyer une liste de tuples qui correspond au chemin à emprunter pour partir de 2 et arriver en 3. Pour montrer la solution, il suffit de faire de chaque tuple la position du cercle rouge et de mettre à jour le dessin.
On vous donne le début de ce code:
def solution(lab):
""" renvoie la solution du labyrinthe."""
chemin = [depart(lab)] #ajout des coordonnées de la case départ à la liste chemin
case = chemin[0] # case est un tuple = premier élément de la liste chemin
i = case[0] # i = premiere coordonnée du tuple (ligne)
j = case[1] # j = deuxième coordonnée du tuple (colonne)
while lab[i][j] != 3: #Tant que l'arrivée n'a pas été atteinte...
lab[i][j] = 4 # on marque la case visitée avec la valeur 4
cases_voisines = voisines(i, j, lab) # on détermine la liste des cases voisines de la position i,j
- Coder la fonction depart
- Coder la fonction voisines
- Coder la fonction solution
- Coder la mise à jour de l'affichage
- Établir la documentation du programme.
Créé avec HelpNDoc Personal Edition: Éditeur de documentation CHM facile