import numpy as np def suppr (t, a) : # Elric et Baptiste 09/2016 """ On supprime tout les elements valant a dans le tableau t """ for i in t : if i == a : t.remove(i) def cases_voisines(plateau, x, y) : # Elric et Baptiste 09/2016 """ Retourne les cases adjacentes à la case (x,y) """ # On commence par tester les valeurs de x, puis on fait de même sur y. if x == 0 : if y == 0 : return [(0, 1), (1, 0)] elif y == plateau.ht - 1 : return [(1, y), (0, y-1)] else : return [(0, y-1), (0, y+1), (1, y)] elif x == plateau.lg - 1 : if y == 0 : return [(x, 1), (x-1, 0)] elif y == plateau.ht - 1 : return [(x-1, y), (x, y-1)] else : return [(x, y-1), (x, y+1), (x-1, y)] else : if y == 0 : return [(x-1, y), (x+1, y), (x, 1)] elif y == plateau.ht - 1 : return [(x-1, y), (x+1, y), (x, y-1)] else : return [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] def cases_accessibles(plateau, x, y) : # Elric et Baptiste 09/2016 """ Prend en compte les barrières """ t = cases_voisines ( plateau, x , y ) n = len(plateau.liste_barrieres) b = plateau.liste_barrieres for bar in b : if bar.x == x : if bar.y == y : if bar.orientation == "v" : suppr (t, (x+1, y)) else: suppr (t, (x, y+1)) elif bar.y == y-1 : if bar.orientation == "v" : suppr (t, (x+1, y)) else: suppr (t, (x, y-1)) elif bar.x == x-1 : if bar.y == y : if bar.orientation == "v" : suppr (t, (x-1, y)) else: suppr (t, (x, y+1)) elif bar.y == y-1 : if bar.orientation == "v" : suppr (t, (x-1, y)) else: suppr (t, (x, y-1)) return (t) def path_finding_mapping( plateau, xi, yi, yf ) : # Jovian : 4 octobre 2016 """ Calcule le chemin le plus court pour gagner. Argument plateau : argument self de python. Argument xi : abscisse de départ. Argument yi : ordonnée de départ. Argument yf : ordonnée qui désigne la ligne d'arrivée. Retour : Une liste des couples (x, y) des positions successives. Position de départ inclue. Liste vide si aucun chemin possible. """ # Cartographie les cases accessibles carte = map_distance( plateau, xi, yi ) w = plateau.lg h = plateau.ht # Position variable x = -1 y = yf # Détermination du point d'arrivée dist = -1 for k in range( w ) : if carte[ k ][ yf ] > 0 : if x == -1 or carte[ k ][ yf ] < dist : x = k dist = carte[ x ][ yf ] # Arrivée non joignable if x == -1 : return [] # Reconstitution du chemin rep = [(x, y)] while x != xi or y != yi : # Case actuelle x, y = rep[ len(rep) - 1 ] dist = carte[ x ][ y ] # Récupère les cases accessibles access = cases_accessibles( plateau, x, y ) # Recherche de la case la plus proche while len( access ) > 0 : u, v = access.pop(0) if carte[ u ][ v ] < dist : x = u y = v rep.append( (x, y) ) break # Renvoie le chemin return rep def map_distance( plateau, xi, yi ) : # Jovian : 4 octobre 2016 """ Calcule un tableau contenant la distance de chaque case par rapport au joueur. Tient compte de l'éloignement dû aux barrières. La case contient 0 si inaccessible. Argument plateau : argument self de python. Argument xi : abscisse de départ. Argument yi : ordonnée de départ. Retour : un tableau d'entiers indexé (x, y). """ # Création du tableau w = plateau.lg h = plateau.ht rep = np.zeros( (w, h) ) rep[ xi ][ yi ] = 1 # Création de la file fifo = [(xi, yi)] # Balayage du plateau depuis la position de départ while len( fifo ) > 0 : # Point sur un bord x, y = fifo.pop(0) dist = rep[ x ][ y ] # Récupère les cases accessibles access = cases_accessibles( plateau, x, y ) # Traitement des cases adjacentes while len( access ) > 0 : u, v = access.pop(0) if rep[ u ][ v ] == 0 : rep[ u ][ v ] = dist + 1 fifo.append( (u, v ) ) # Retourne le tableau return rep ## Version A* from heapq import * def get_path(start, target, parent) : # Jovian : 25 novembre 2016 """ Construit et retourne le chemin solution. """ path = [target] x, y = target while (x, y) != start: x, y = parent[x, y] path.append((x, y)) return list( reversed(path) ) def path_finding_a_star( plateau, xi, yi, yf, hcap = 0 ) : # Jovian : 7 décembre 2016 : éviter le contact barrières """ Calcule le chemin le plus court pour gagner. Argument plateau : argument self de python. Argument xi : abscisse de départ. Argument yi : ordonnée de départ. Argument yf : ordonnée qui désigne la ligne d'arrivée. Argument hcap : valeur malus ajoutée si le pion est en contact avec une barrière. Retour : Une liste des couples (x, y) des positions successives. Position de départ inclue. Liste vide si aucun chemin possible. """ # Variables open_set = [] closed = np.zeros( (plateau.lg, plateau.ht), dtype = bool ) parent = np.zeros( (plateau.lg, plateau.ht, 2), dtype = int ) cost_so_far = np.ones((plateau.lg, plateau.ht)) * np.inf # Estimation distance restante def heuristic( z ): # Distance directe x, y = z dist = abs(y - yf) return dist # Malus si contact avec une barrière def malus( z ): x , y = z if plateau.contact( x, y ) : return hcap else : return 0 # Ajoute un élément qui sera traité plus tard def push(open_set, z): priority = cost_so_far[z] + heuristic(z) + malus(z) heappush(open_set, (priority, z) ) # Retire la case potentiellement la plus proche def pop(open_set): _, current = heappop(open_set) return current # Initialisation start = xi, yi cost_so_far[start] = 0 push(open_set, start) current = (0, 0) # Parcours while open_set != []: # Case (x, y) en cours de traitement current = pop(open_set) x, y = current # Si on a atteint l'arrivée if current[1] == yf : break # Si la case a déjà été vue if closed[current] : continue # On dit qu'on a traité cette case closed[current] = True # Parcours des voisins for neighbor in cases_accessibles( plateau, x, y ): # Voisin déjà traité if closed[neighbor]: continue new_cost_neighbor = cost_so_far[current] + malus(neighbor) + 1 # Si notre chemin est plus court pour accéder à cette case if new_cost_neighbor < cost_so_far[neighbor]: cost_so_far[neighbor] = new_cost_neighbor push(open_set, neighbor) parent[neighbor] = current # Fin de parcours if current[1] == yf : # Chemin abouti return get_path(start, current, parent) else : # Chemin inexistant return [] ## Alias du pathfinding def path_finding( plateau, xi, yi, yf ) : # Jovian : 7 décembre 2016 : éviter le contact barrières """ Pour éviter le contact avec les barrières : mettez hcap = 0.05 Sinon hcap = 0.0 """ return path_finding_a_star( plateau, xi, yi, yf, hcap = 0.05 )