Labyrinthe - Terminale

Prérequis

• structures de contrôle ;
• boucles ;
• tableaux à deux dimensions ;
• fonctions ;
• modules ;
• programmation orientée objet ;
• cours : files, graphes.

Présentation

Le but de ce projet est de trouver un chemin pour sortir d’un labyrinthe. L’entrée est dans le coin supérieur gauche et la sortie dans le coin inférieur droit. Nous utiliserons le labyrinthe ci-dessous. Les murs sont les cases noires.

Une classe GrapheProjet4 permettant de manipuler le labyrinthe vous est fournie. Le labtrinthe est généré à partir d’un tableau de chaines de caractères. Les # représentent les murs et les . les chemins.

Plusieurs méthodes sont fournies (voir les détails dans le code fourni) :

• creeListeAdjacence: génère les listes d’adjcence de chaque nœud du labyrinthe. chaque nœude est référencé dans un dictionnaire par ses coordonnées (x, y). Le coin supérieur gauche correspond à (0, 0)

• trace: méthode principale qui gère tous les affichages.

• traceLabirynthe: trace le labyrinthe.

• traceChemin: trace un chemin dans le labyrinthe.

• trouveChemin: détermine un chemin pour aller de l’entrée à la sortie.

Cahier des charges

L’objectif principal est de trouver un chemin en utilisant l’algorithme de recherche de chemin vu précédement. Il y a ensuite des améliorations à effectuer pour les plus rapides d’entre vous.

1. trouver un chemin ;
2. trouver un chemin plus rapidement en mémorisant les échecs pour ne pas chercher à nouveau un chemin déjà exploré (c’est ce qu’on appelle la mémoïsation , un genre de programmation dynamique) ;
3. trouver un chemin encore plus rapidement en explorant en priorité le nœud adjacent le plus proche de la sorie (version simplifié de A*) ;
4. générer aléatoirement un labyrinthe avec au moins un chemin valide et le retrouver avec l’algorithme précédent ;
5. trouver le chemin le plus court.

Tableau du barème

Voilà le barème complet sur 10 pour ce projet.

Classe GrapheProjet4

# Auteurs :
# Logan Monier
# Thomas Beline
# Alexandre Loubet

import copy
import time
import pyxel

class GrapheProjet4:
    """
    Recherche d'un chemin dans un labyrinthe.
    """
    def __init__(self, labyrinthe):
        self.hauteur = len(labyrinthe)
        self.largeur = len(labyrinthe[0])
        # On crée un dictionnaire vide
        self.listeAdjacence = {}
        # On génère la liste d'adjacence à partir du labyrinthe
        self.creeListeAdjacence(labyrinthe)

        self.trace(labyrinthe)

    def creeListeAdjacence(self, labyrinthe):
        """
        Fabrique la liste d'adjcence du graphe représentant le labyrinthe.
        """
        for y in range(self.hauteur):
            for x in range(self.largeur):
                self.listeAdjacence[(x, y)] = list()
                if labyrinthe[y][x] == ".":
                    if x-1 > -1:
                        if labyrinthe[y][x-1] == ".":
                            self.listeAdjacence[(x, y)].append((x-1, y))
                    if x+1 < self.largeur:
                        if labyrinthe[y][x+1] == ".":
                            self.listeAdjacence[(x, y)].append((x+1, y))
                    if y-1 > -1:
                        if labyrinthe[y-1][x] == ".":
                            self.listeAdjacence[(x, y)].append((x, y-1))
                    if y+1 < self.hauteur:
                        if labyrinthe[y+1][x] == ".":
                            self.listeAdjacence[(x, y)].append((x, y+1))


    def trace(self, labyrinthe):
        """
        Méthode principale qui gère tous les affichages.
        """
        pyxel.init(self.largeur, self.hauteur)

        # On dessine le labyrinthe
        self.traceLabirynthe(labyrinthe)

        # On recherche un chemin
        chemin = self.trouveChemin()

        # On trace le chemin
        self.traceChemin(chemin)

        pyxel.show()

    def traceLabirynthe(self,labyrinthe):
        """
        Trace le labyrinthe.

        Les cases noires représentent les murs.
        """
        for y in range(self.hauteur):
            for x in range(self.largeur):
                if labyrinthe[y][x] == "#":
                    color = 0
                elif labyrinthe[y][x] == ".":
                    color = 7
                pyxel.pset(x, y, color)
        #modifie la fenêtre
        pyxel.flip()



    def traceChemin(self, chemin):
        """
        Trace le chemin dans le labyrinthe.

        chemin : liste de tuples contenant les coordonnées (x, y) des cases constituant le chemin
        """
        for sommet in chemin:
            pyxel.pset(sommet[0], sommet[1], 8)

        pyxel.flip()

    def effaceChemin(self, chemin):
        """
        Efface le chemin en appliquant des carrés blancs

        chemin : liste de tuples contenant les coordonnées (x, y) des cases constituant le chemin
        """

        for sommet in chemin:
            pyxel.pset(sommet[0], sommet[1], 7)

    def apercuChemin(self, chemin):
        """
        Trace le chemin actuel et l'efface aussitôt

        chemin : liste de tuples contenant les coordonnées (x, y) des cases constituant le chemin
        """
        self.traceChemin(chemin)
        time.sleep(0.02)
        self.effaceChemin(chemin)

    def trouveChemin(self):
        """
        Retourne un chemin entre le coin supérieur gauche et le coin inférieur droit ne passant que par les cases blanches.
        """
        chemin = self.trouveRecursif((0,0), (self.largeur - 1, self.hauteur - 1), [])
        return chemin

    def trouveRecursif(self, start, end, chaine):
        """
        Partie récursive de l'algorithme de recherche de chemin
        """

		# À compléter pour retourner un chemin qui ne passe pas à travers les murs
        return [(0,0), (self.largeur - 1, self.hauteur - 1)]


lab_1 = ["..#.###...",
         "#.#...#.#.",
         "....#...#.",
         ".#####.###",
         ".#...#...#",
         "...#.#.###",
         "####.#....",
         "#....##.##",
         "..####...#",
         "#......#.."]

lab_2 = ["..#.###...",
         "#.#...#.#.",
         "....#...#.",
         ".#####.###",
         ".#...#...#",
         "...#.#.###",
         "####.#....",
         "#....##.##",
         "..####...#",
         "#....#.#.."]


lab_3 = [".#....#......#....#...#.....#.",
         ".#.##.#.####.#.##.#.#.#.###.#.",
         "....#.#....#....#...#.#.#.#...",
         "###.#.##.#.#.##.#######...#.##",
         "....#....#......#....#..#.....",
         ".#######.#.###.##.##.#.######.",
         ".....#.......#....#..#........",
         "#.##.#.#####.######.##.#.#.###",
         "..#..#.#.....#......#..#.#..#.",
         ".##.##.#.#####.###.##.##.##...",
         "..###..#.........#.#..#...##.#",
         "#.#...##.#.#####.....####.#...",
         "#...###..#...#.#.###....#.###.",
         "#.###...####.#.#...##.#...#...",
         "..#...####...#.#........#.#.##",
         ".##.###....#.#.###.#.##.#.....",
         ".#....#.##.#.......#..#.#.##.#",
         ".#.##.#..#.####.#.###...#..#..",
         "...#..##.#.#....#.#.#.####.##.",
         "####.....#...####...#....#.#.."]

graphe = GrapheProjet4(lab_1)