Quoridor/project/Outils/Moteur_de_jeu/Distance.py

import numpy as np
from heapq import *

from Outils.Moteur_de_jeu.Pathfinding import cases_accessibles

def length_path(start, target, parent) : # Jovian : 17 janvier 2017
    """ Construit et retourne la longueur du chemin solution.
    """
    i = 0
    x, y = target
    while (x, y) != start:
        x, y = parent[x, y]
        i += 1
    return i


def distance_a_star( plateau ) : # Jovian : 17 janvier 2017
    """
        Calcule la distance entre deux cases tenant compte des barrières.
        Argument plateau : argument self de python.
        Argument hcap : valeur malus ajoutée si le pion est en contact avec une barrière.
        Retour : 
            None si chemin inexistant.
            Int comptant le nombre de cases.
            Positions de départ exclue et d'arrivée inclue.
    """
    # Points
    xi, yi = plateau.pions[0]
    xf, yf = plateau.pions[1]
    
    # 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) + abs(x - xf)
        return dist

    # Ajoute un élément qui sera traité plus tard
    def push(open_set, z):
        priority = cost_so_far[z] + heuristic(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 == ( xf, 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] + 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 == ( xf, yf ) :
        # Chemin abouti
        return length_path(start, current, parent)
    else :
        # Chemin inexistant
        return None