Génère un labyrinthe parfait de 16x11 puis trouve le chemin optimal vers la sortie à l’aide de l’algorithme A*. Mémorise le labyrinthe ayant le plus chemin
from kandinsky import * from random import randrange,random import time from ion import * largeur, hauteur = 320, 222 width, height = 32, 22 taille_x = largeur // width taille_y = hauteur // height def trace_case(laby, x, y, couleur_fond=(128,128,128), couleur_murs=(200,200,200)): # tracé du fond de case fill_rect(x*taille_x, y*taille_y, taille_x, taille_y, couleur_fond) fill_rect(int((x+0.9)*taille_x), y*taille_y,int(0.1*taille_x),int(0.1*taille_y),couleur_murs) fill_rect(int((x+0.9)*taille_x), int((y+0.9)*taille_y),int(0.1*taille_x),int(0.1*taille_y),couleur_murs) fill_rect(x*taille_x, int((y+0.9)*taille_y),int(0.1*taille_x),int(0.1*taille_y),couleur_murs) fill_rect(x*taille_x, (y)*taille_y,int(0.1*taille_x),int(0.1*taille_y),couleur_murs) # présence ou non de murs sur les côtés gauche, haut, droite, bas = get_directions(laby, x, y) # tracé des murs if not gauche: fill_rect(x * taille_x, int((y + .1) * taille_y), int(0.1 * taille_x), int(0.8 * taille_y), couleur_murs) if not haut: fill_rect(int((x + 0.1) * taille_x), y * taille_y, int(0.8 * taille_x), int(0.1 * taille_y), couleur_murs) if not droite: fill_rect(int((0.9 + x) * taille_x), int((y + 0.1) * taille_y), int(0.1 * taille_x), int(0.8 * taille_y), couleur_murs) if not bas: fill_rect(int((x + 0.1) * taille_x), int((y + 0.9) * taille_y), int(0.8 * taille_x), int(0.1 * taille_y), couleur_murs) def dessine(laby): for h in range(height): for w in range(width): trace_case(laby, w, h, (128,128,128) ,(200,200,200)) def get_directions(laby, x, y): if x > 0 : gauche = (laby & 2 ** (2 * (width * y + x - 1))) >> (2 * (width * y + x - 1)) else : gauche = 0 if y>0 : haut = (laby & 2 ** (2 * (width * (y - 1) + x) + 1)) >> (2 * (width * (y - 1) + x) + 1) else : haut = 0 droite = (laby & 2 ** (2 * (width * y + x))) >> (2 * (width * y + x)) bas = (laby & 2 ** (2 * (width * y + x) + 1)) >> (2 * (width * y + x) + 1) return gauche, haut, droite, bas def inverse_mur(laby,x,y,direction): mask = laby & 0 if direction == 0: mask += 2 ** (2 * (width * y + x - 1)) elif direction == 1: mask += 2 ** (2 * (width * (y - 1) + x) + 1) elif direction == 2 : mask += 2 ** (2 * (width * y + x)) else : mask += 2 ** (2 * (width * y + x) + 1) return laby ^ mask def perfect(laby): groupes=[[(i%width,i//width)] for i in range(width*height)] while len(groupes) > 1: groupe = randrange(0,len(groupes)) mur_casse = False ordre_cases = sorted(groupes[groupe], key=lambda x: random()) k = 0 while not mur_casse: case = ordre_cases[k] directions = sorted([0, 1, 2, 3], key=lambda x: random()) for i in directions: if (i == 0 and ordre_cases[k][0] > 0 and not (ordre_cases[k][0] - 1, ordre_cases[k][1]) in groupes[groupe] ): to_move = get_group(groupes,(ordre_cases[k][0] - 1, ordre_cases[k][1])) mur_casse = True elif ( i == 1 and ordre_cases[k][1] > 0 and not (ordre_cases[k][0], ordre_cases[k][1] - 1) in groupes[groupe] ): to_move = get_group(groupes,(ordre_cases[k][0], ordre_cases[k][1] - 1)) mur_casse = True elif ( i == 2 and ordre_cases[k][0] < width - 1 and not (ordre_cases[k][0] + 1, ordre_cases[k][1]) in groupes[groupe] ): to_move = get_group(groupes,(ordre_cases[k][0] + 1, ordre_cases[k][1])) mur_casse = True elif ( i == 3 and ordre_cases[k][1] < height - 1 and not (ordre_cases[k][0], ordre_cases[k][1] + 1) in groupes[groupe] ): to_move = get_group(groupes,(ordre_cases[k][0], ordre_cases[k][1] + 1)) mur_casse = True if mur_casse and groupe != to_move: laby = inverse_mur(laby, ordre_cases[k][0], ordre_cases[k][1], i) groupes = merge_groupes(groupes, groupe, to_move) break k += 1 return laby def get_group(groupes, XY): for i in range(len(groupes)): if XY in groupes[i]: return i else : raise ValueError("{} n'est pas dans le groupe".format(XY)) def merge_groupes(groupes,A,B): groupes[A] += groupes[B] del(groupes[B]) return groupes def recherche_trajet(laby, depart = (0, 0), arrivee = (0, 0), dessine = False, temps = 0): distances = [[((w-arrivee[0])**2+(h-arrivee[1])**2)**.5 for w in range(width)] for h in range(height)] visitees = [[-1 for w in range(width)] for h in range(height)] a_traiter = [depart] visitees[depart[1]][depart[0]] = 0 itineraire_trouve=False while len(a_traiter) > 0: x,y=a_traiter[0] case = get_directions(laby,x,y) if dessine : trace_case(laby,x,y,(200,128,128),(200,200,200)) if temps!=0: time.sleep(temps) if a_traiter[0] == arrivee: return visitees del(a_traiter[0]) if x > 0 and case[0]: if visitees[y][x-1] == -1: visitees[y][x-1] = visitees[y][x] + 1 a_traiter.append((x - 1, y)) if y > 0 and case[1]: if visitees[y-1][x] == -1: visitees[y-1][x] = visitees[y][x] + 1 a_traiter.append((x, y - 1)) if x < (width - 1) and case[2]: if visitees[y][x + 1] == -1: visitees[y][x + 1] = visitees[y][x] + 1 a_traiter.append((x + 1, y)) if y < (height - 1) and case[3]: if visitees[y + 1][x] == -1: visitees[y + 1][x] = visitees[y][x] + 1 a_traiter.append((x, y + 1)) a_traiter.sort(key=lambda d:distances[d[1]][d[0]]) raise ValueError("Chemin non trouvé") def chemin(laby,visitees,depart,arrivee,dessine=False,temps=0): itineraire=[arrivee] while itineraire[-1]!=depart: case=itineraire[-1] x,y=case direction=get_directions(laby,x,y) possibles=[] if x>0: if visitees[y][x -1] == visitees[y][x]- 1 and direction[0]: possibles.append((x - 1, y)) if y>0: if visitees[y - 1][x] == visitees[y][x] - 1 and direction[1]: possibles.append((x, y - 1)) if x<width - 1: if visitees[y][x + 1]==visitees[y][x] - 1 and direction[2]: possibles.append((x + 1,y)) if y<height - 1: if visitees[y + 1][x]==visitees[y][x] - 1 and direction[3]: possibles.append((x,y + 1)) itineraire.append(possibles[0]) for i in itineraire: if dessine : trace_case(laby,i[0],i[1],(250,250,128),(200,200,200)) if temps!=0: time.sleep(temps) return itineraire[::-1] def dessine_perso(x,y,taille_perso): fill_rect(x, y, taille_perso, taille_perso, (255,255,0)) def move_perso(laby,x,y,taille_perso): new_x=x-keydown(KEY_LEFT)+keydown(KEY_RIGHT) new_y=y-keydown(KEY_UP)+keydown(KEY_DOWN) directions=get_directions(laby,new_x//taille_x,new_y//taille_y) # tests position a = new_x % taille_x < 0.1 * taille_x b = new_x % taille_x + taille_perso > 0.9 * taille_x c = new_y % taille_y < 0.1 * taille_y d = new_y % taille_y + taille_perso > 0.9 * taille_y if (not(((not c) and (not d))) and (not ((not a) and (not b)))): return x,y if ((not directions[0]) and a) or ((not directions[1]) and c) or ((not directions[2]) and b) or ((not directions[3]) and d): return x,y return new_x,new_y def jeu(laby,position): x,y=position taille_perso=int(0.5*taille_x) while True: trace_case(laby,x//taille_x,y//taille_y) if x//taille_x > 0 : trace_case(laby,x//taille_x - 1,y//taille_y) if y//taille_y > 0: trace_case(laby,x//taille_x,y//taille_y - 1) if x//taille_x - 1 < width : trace_case(laby,x//taille_x + 1,y//taille_y) if y//taille_y - 1 < height : trace_case(laby,x//taille_x,y//taille_y + 1) dessine_perso(x,y,taille_perso) if keydown(KEY_ZERO): visitees = recherche_trajet(a, (x//taille_x,y//taille_y), (width-1,height-1),False,0) itineraire = chemin(a,visitees,(x//taille_x,y//taille_y), (width-1,height-1),True,0) x,y=move_perso(a,x,y,taille_perso) time.sleep(0.01) if x//taille_x==width-1 and y//taille_y==height-1: return True while True : a = 0 fill_rect(0,0,320,222,(128,128,128)) draw_string("Génération du labyrinthe",10,100) draw_string("Patientez !",10,150) a = perfect(a) dessine(a) trace_case(a,width - 1,height - 1,(128,255,128)) jeu(a,(int(taille_x*0.2),int(taille_x*0.2)))