###################################### # GESTION DES LABYRINTHES ###################################### def dessinerTableau(tab): """ permet de dessiner le labyrinthe passe en parametre - les cases avec un 1 sont des murs => '#' - les cases avec un 0 sont des espaces vides => ' ' """ for j in range(0,len(tab[0])): for i in range(0,len(tab)): # mur if tab[i][j]==-1: print('#', end=' ') # vide elif tab[i][j]==0 : print(' ', end=' ') # altitude else : print(tab[i][j], end=' ') print() ################### def transpose(laby): """ permet d'inverser lignes et colonnes d'un labyrinthe (utile pour la creation simple) """ # nouveau laby laby2=[] for i in range(0,len(laby[0])): ligne=[] for j in range(0,len(laby)): ligne+=[0] laby2+=[ligne] # transposition for i in range(0,len(laby[0])): for j in range(0,len(laby)): laby2[i][j]=laby[j][i] return laby2 ################### def getLabyrintheAltitude(): """ Construit et retourne un labyrinthe par defaut a parcourir (de taille 7x7) * mur = -1 * autre case = altitude cout = difference altitude """ # labyrinthe vide laby = [] laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]] laby +=[[-1, 0, 0, 0, 0, 0, 0,-1]] laby +=[[-1, 0,-1, 0,-1, 1,-1,-1]] laby +=[[-1, 2, 2, 0,-1, 2, 0,-1]] laby +=[[-1,-1,-1, 2,-1, 3,-1,-1]] laby +=[[-1, 0, 0, 0, 0, 0, 0,-1]] laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]] # nouveau laby xDep = 6 yDep = 5 return transpose(laby), xDep, yDep ###################################### # AVEC LISTE OUVERTE ###################################### def calculLabyDijkstra(laby,x,y): """ effectue le calcul des distances en utilisant une liste ouverte - strategie consiste à propager case par case - développer la case la plus proche """ # for sorting from operator import itemgetter; # faire un nouveau tableau avec 10000 max = 1000 tab=[] for i in range(len(laby)): t=[] for j in range(len(laby[0])) : t+=[max] tab+=[t] tab[x][y]=0 # voisins connexite 4 voisins=[[0,1],[0,-1],[1,0],[-1,0]] # ouverte : cases à parcourir (x,y,valeur) ouverte = [(x,y,0)] tab[x][y]=0 # tant que non fini fini = False # tant qu'il reste des elements while len(ouverte)>0 : # get element # WARNING : pop(0) si on veut le fonctionnement d'une file # sinon pop() prend en fin de liste # sort by value (i,j,val) = ouverte.pop(0) # pour chaque voisin for v in voisins: # coordonnes du voisin voisinX = i + v[0] voisinY = j + v[1] # si case est pas un mur => la traiter if laby[voisinX][voisinY] != -1 : # TODO Dijkstra -- difference altitude altitude = abs(laby[voisinX][voisinY]-laby[i][j]) # calcule nouvelle distance nouvelleD = tab[i][j] + altitude + 1 # si meilleur met a jour if nouvelleD < tab[voisinX][voisinY] : # si existe deja if tab[voisinX][voisinY] != max : # supprime ancien element de la liste ouverte.remove((voisinX,voisinY,tab[voisinX][voisinY])) # met a jour tab[voisinX][voisinY] = nouvelleD ouverte.append((voisinX,voisinY, nouvelleD)) # TODO Dijkstra -- tri liste ouverte par valeur ouverte = sorted(ouverte, key=itemgetter(2)) # affiche la liste ouverte et le chemin parcouru à chaque iteration dessinerChemin(tab) print(ouverte) print("--------------------------------") # fin retourner tableau return tab ###################################### # AFFICHAGE DES DISTANCES ###################################### def dessinerChemin(tab): """ permet de dessiner une matrice de distance dans un labyrinthe """ # dessine les lignes for j in range(0,len(tab[0])): # pour chaque colonnee for i in range(0,len(tab)): # recupere la valeur calculee val=tab[i][j] # si c'est 1000, c'est une case non visitee if val==1000: # affiche vide print(" ",end=' ') else: # affiche la valeur print(val,end=' ') # ajoute le bon nombre d'espaces en fonction de la taille du nombre if val<0: val=-val*10 if val==0: val=1 while (val<100): val=val*10 print(' ',end='') print() ###################################### # CALCUL DU CHEMIN ###################################### def getCheminDijkstra(laby,distance,depX,depY): """ retourne le chemin a partir d'une matrice de distance - depX : abscisse du depart - depY : ordoneee du depart """ # valeur maximale maxVal=1000 # on se place au depart x=depX y=depY chemin=[(x,y)] # liste des voisins connexite 4 voisins = [(1,0),(-1,0),(0,1),(0,-1)] # tant que 0 est non atteint while not distance[x][y] == 0 : # cherche plus petite case chez les voisins min = maxVal voisinMin =() # pour chaque voisin for voisin in voisins : # calcule case voisine vx = x + voisin[0] vy = y + voisin[1] # si meilleure et atteignable if distance[vx][vy] < min : # TODO Dijkstra : atteignable # calcule altitude altitude = abs(laby[x][y]-laby[vx][vy]) # verifie atteignable if distance[x][y] == distance[vx][vy] + altitude + 1 : min = distance[vx][vy] voisinMin = (vx,vy) # meilleureVoisin trouve remonte la case chemin.append(voisinMin) (x,y) = voisinMin # fin retourne chemin return chemin ###################################### # MAIN ###################################### def main(nameLaby): """ code appele par le __main__ creer et dessine un Labyrinthe """ # creer un labyrinthe laby, xDep, yDep = getLabyrintheAltitude() # affiche le labyrinthe dans la console dessinerTableau(laby) # consytruire cases print("############# DIJKSTRA ##############") tab = calculLabyDijkstra(laby,1,1) # recupere chemin chemin = getCheminDijkstra(laby,tab,xDep,yDep) print (chemin) ###################################### # lancement du module python ###################################### import sys if __name__ == "__main__": # labyrinthe a afficher nameLaby="" # si trop d'arguments, exit' if len(sys.argv) > 2 : print ("**ERROR** un seul argument max") print ("") print ("USAGE :") print ("'laby [name]'") print ("- avec name désignant le labyrinthe ('default' ou 'grand')") # si pas d'argument, labyrinthe defaut if len(sys.argv) == 1 : nameLaby = "default" # sinon arg 1 doit contenir le nom du labyrinthe else : nameLaby = sys.argv[1] main(nameLaby)