Labyrinthe

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.

Tâche	Barème
Trouver un chemin	4 points
Trouver un chemin plus rapidement	1 points
Trouver un chemin encore plus rapidement	1 points
Générer des labyrinthes	1 point
Trouver le chemin le plus court	1 point bonus
Code propre	1 points
Code optimisé	1 point
Commentaires	1 points
Totals	10

Classe GrapheProjet4

# Auteurs :
# Logan Monier
# Thomas Beline

import copy
import time
import pygame
from pygame.locals import *

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.
        """
        pygame.init()
        # Taille d'un carré de base
        self.tailleCarre = 50
        # On crée une fenêtre à la taille du labyrinthe
        self.fenetre = pygame.display.set_mode((self.tailleCarre*self.largeur, self.tailleCarre*self.hauteur))
        # On dessine le labyrinthe
        self.traceLabirynthe(labyrinthe)

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

        # On trace le chemin
        self.traceChemin(chemin)

        # On attend l'appui sur le bouton fermer de la fenêtre
        continuer = 1
        while continuer:
            for event in pygame.event.get():
                # Si appui sur le bouton fermer
                if event.type == QUIT:
                    continuer = 0

        pygame.quit()

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

        Les cases noires représentent les murs.
        """
        carre = pygame.Surface((self.tailleCarre,self.tailleCarre), pygame.SRCALPHA)
        for y in range(self.hauteur):
            for x in range(self.largeur):
                if labyrinthe[y][x] == "#":
                    color = (0, 0, 0, 255)
                elif labyrinthe[y][x] == ".":
                    color = (255, 255, 255, 255)
                carre.fill(color)
                self.fenetre.blit(carre, (x*self.tailleCarre, y*self.tailleCarre))
        #modifie la fenêtre
        pygame.display.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
        """
        color = (255, 0, 0, 255)
        for i in range(len(chemin)-1):
            pygame.draw.line(self.fenetre, color, (chemin[i][0]*self.tailleCarre+int(self.tailleCarre/2), chemin[i][1]*self.tailleCarre+int(self.tailleCarre/2)), (chemin[i+1][0]*self.tailleCarre+int(self.tailleCarre/2), chemin[i+1][1]*self.tailleCarre+int(self.tailleCarre/2)), 5)

        pygame.display.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
        """
        carre = pygame.Surface((self.tailleCarre,self.tailleCarre), pygame.SRCALPHA)
        color = (255, 255, 255, 255)
        carre.fill(color)
        for coord in chemin:
            self.fenetre.blit(carre, (coord[0]*self.tailleCarre, coord[1]*self.tailleCarre))
        pygame.display.flip()

    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)