""" Petit module qui illustre la recherche d'une chemin dans une grille selon l'algorithme A* """ from browser import document from browser import html from browser import timer SIZE = 10 # taille de la grille SLEEP = 400 # ms DECALAGE_X = {'gauche': -1, 'haut': 0, 'droite': 1, 'bas': 0} DECALAGE_Y = {'gauche': 0, 'haut': -1, 'droite': 0, 'bas': 1} idtimer = 1 to_draw = [] # liste des cases a dessiner pour l'animation nb_to_draw = 0 # nombre de cases a dessiner pour l'animation nb_extremite = 0 extremite_x = [-1, -1] extremite_y = [-1, -1] astar = None grille = [[0] * SIZE for i in range(SIZE)] class Case: """ Classe qui represente une case d'une grille avec comme attributs: - sa position en x et en y - son cout (par rapport a sa distance au point de depart) - sa case parente par rapport au cout permettant de remonter le chemin. """ def __init__(self, posx=None, posy=None, cout=None, parent=None): self.x = posx self.y = posy self.cout = cout self.parent = parent def dist(self, case): """ retourne la distance euclidienne (au carre) a une autre case. """ return ((self.x - case.x) * (self.x - case.x) + (self.y - case.y) * (self.y - case.y)) def __eq__(self, case): """ Definit ce qu'est l'egalite entre deux cases. """ return (self.x == case.x) and (self.y == case.y) def cmp(self, case): """ Definit une fonction de comparaison entre deux cases (selon le cout).""" return min(self.cout, case.cout) class Astar: """ Une implantation de l'algorithme de recherche de chemin A* L'algorithme A* repose sur deux listes: - un liste ouverte des possibilites non explorees - une liste fermee des possibilites déjà explorees et sur une estimation du cout du chemin et du deplacement. """ def __init__(self, taille=10): self.liste_ouverte = [] self.liste_fermee = [] self.size = taille def _explore_noeud(self, noeud, grille, direction, fin): """ Explore si une case a partir d'une case de depart et d'une direction est a considerer. """ global nb_to_draw new_case = Case(noeud.x + DECALAGE_X[direction], noeud.y + DECALAGE_Y[direction]) if (0 <= new_case.x < self.size) and (0 <= new_case.y < self.size): if __debug__: print(direction) print('{} {} {}'.format(new_case.x, new_case.y, grille[new_case.y][new_case.x])) if grille[new_case.y][new_case.x] >= 0: # Case libre if __debug__: print('case libre') if new_case not in self.liste_ouverte: # Pas dans la liste ouverte if new_case in self.liste_fermee: if __debug__: print('') # il est present # on fait rien else: new_case.cout = new_case.dist(fin) new_case.parent = noeud self.liste_ouverte.append(new_case) if grille[new_case.y][new_case.x] != 1: # grille_cases_html[new_case.y][ # new_case.x].bgcolor = 'darkgray' nb_to_draw += 1 to_draw.append((new_case.x, new_case.y, 'darkgray')) else: # le noeud existe deja meme_case = self.liste_ouverte[ self.liste_ouverte.index(new_case)] if meme_case.cout > new_case.dist(fin): meme_case.cout = new_case.dist(fin) meme_case.parent = noeud def cherche_chemin(self, grille, debut, fin): """ L'algorithme de recherche du chemin par A*. """ global idtimer if __debug__: print(grille) idtimer = timer.set_interval(_dessine_case, SLEEP) fini = False debut.cout = debut.dist(fin) self.liste_ouverte.append(debut) while self.liste_ouverte and not fini: # parmi les possibilites on choisi celle de plus faible cout noeud = min(self.liste_ouverte, key=lambda x: x.cout) self.liste_ouverte.remove(noeud) self._explore_noeud(noeud, grille, 'gauche', fin) self._explore_noeud(noeud, grille, 'haut', fin) self._explore_noeud(noeud, grille, 'droite', fin) self._explore_noeud(noeud, grille, 'bas', fin) self.liste_fermee.append(noeud) fini = (noeud.cout == 0) # time.sleep(0.4) if __debug__: if self.liste_ouverte is False: print('Pas de chemine trouve') else: print('chemin trouve') def affiche_chemin(self, grille): """ Affiche graphiquement le chemin trouve. """ global nb_to_draw case = self.liste_fermee.pop() # on part du point d'arrivé while case is not None: i = case.x j = case.y if grille[j][i] != 1: to_draw.append((i, j, 'blue')) nb_to_draw += 1 # grille_cases_html[j][i].bgcolor = 'blue' # time.sleep(0.4) case = case.parent # on remonte le chemin def _dessine_case(): """ Fonction qui colori une case de la grille. Cette fonction est appelee a interval regulier pour l'animation de la recherche et du chemin. """ global nb_to_draw if nb_to_draw == 0 and calcul_fini: timer.clear_interval(idtimer) else: case = to_draw.pop(0) if case is not None: i, j, couleur = case grille_cases_html[j][i].bgcolor = couleur nb_to_draw -= 1 def _draw_wall(event): """ Fonction qui dessine à l'ecran une case representant un mur. """ i = int(event.target.x) j = int(event.target.y) if grille[j][i] == -1: grille[j][i] = 0 event.target.bgcolor = 'lightgray' else: grille[int(event.target.y)][int(event.target.x)] = -1 event.target.bgcolor = 'red' event.stopPropagation() if __debug__: print('click ', event.x, event.y, event.target.x, event.target.y) def _draw_start_end(event): """ Fonction qui dessine les points de depart et d'arrive et qu'une fois que ces deux points ont ete places, commence la recherche du chemin avec son affichage. """ global astar global nb_extremite global extremite_x global extremite_y global calcul_fini if __debug__: print('click ', event.x, event.y, event.target.x, event.target.y) if nb_extremite == 2: # le point de depart et d'arrive ont ete definis et le chemin # deja ete affiche. On reinitialise pour placer de nouveaux points # de depart et d'arrive. # par la suite des events pour un double click, # la case est devenue un mur, il faut l'enlever i = int(event.target.x) j = int(event.target.y) grille[j][i] = 0 i = extremite_x[0] j = extremite_y[0] grille[j][i] = 0 k = extremite_x[1] l = extremite_y[1] grille[l][k] = 0 nb_extremite = 0 # les cases non vides for i in range(0, 10): for j in range(0, 10): if grille[j][i] == -1: grille_cases_html[j][i].bgcolor = 'red' if grille[j][i] == 1: grille_cases_html[j][i].bgcolor = 'green' if grille[j][i] == 0: grille_cases_html[j][i].bgcolor = 'lightgray' del astar astar = Astar() else: # on définit un point de départ ou d'arrivé et si les deux sont définis # on affiche le chemin i = int(event.target.x) j = int(event.target.y) grille[j][i] = 1 extremite_x[nb_extremite] = i extremite_y[nb_extremite] = j nb_extremite += 1 event.target.bgcolor = 'green' if nb_extremite == 2: a = extremite_x[0] b = extremite_y[0] k = extremite_x[1] l = extremite_y[1] depart = Case(a, b) fin = Case(k, l) if __debug__: print(grille) calcul_fini = False astar.cherche_chemin(grille, depart, fin) astar.affiche_chemin(grille) calcul_fini = True event.stopPropagation() # programme principal if __debug__: print(grille) # on cree un tableau table = html.TABLE(align='center', border=1, width=312, height=312, rules='all') grille_lignes_html = {i: html.TR() for i in range(SIZE)} grille_cases_html = [[html.TD(bgcolor='lightgray', x=i, y=j) for i in range(SIZE)] for j in range(SIZE)] for i in range(SIZE): grille_lignes_html[i] <= grille_cases_html[i] table <= grille_lignes_html[i] # association d'une fonction au click dans une case for ligne in grille_cases_html: for case in ligne: case.bind('click', _draw_wall) case.bind('dblclick', _draw_start_end) document['mon_test_2'] <= table astar = Astar(taille=SIZE)