Quoridor/project/Outils/Moteur_de_jeu/Pathfinding.py

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 )