################################################################################
################################################################################
#   EX004
################################################################################
################################################################################

import numpy as np, numpy.random as rd
import matplotlib.pyplot as plt
from copy import deepcopy

################################################################################
#   PREMIER EXEMPLE
################################################################################

config=[[0,0,2,0,2,0,0,0],
        [0,2,0,0,0,0,0,2],
        [0,0,0,0,2,0,0,0],
        [0,0,0,2,0,0,0,0],
        [0,2,0,0,0,0,0,0]]

plt.pcolormesh(np.array(config),cmap='Greys',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()


################################################################################
#   CREATION D'UNE CONFIGURATION ALEATOIRE
################################################################################


L,C=50,50
config=[[0]*C for k in range(L)]

p=.2
deb,fin=(0,0),(L-1,C-1)
for i in range(L):
    for j in range(C):
        if (i,j)!=deb and (i,j)!=fin:
            if rd.random()<p:
                config[i][j]=2

plt.imshow(np.array(config),cmap='Greys',interpolation='nearest')
plt.show()


################################################################################
#   ALGO A*
################################################################################

def d2(A,B):
    xA,yA=A
    xB,yB=B
    return np.sqrt((xA-xB)**2+(yA-yB)**2)

def Astar_deb_fin(S,A,deb,fin):
    nb=0
    def h(s):
        return d2(s,fin)
    cout,dist,predec,djvu={},{},{},{}
    for s in S:
        cout[s]=np.inf
        dist[s]=np.inf
        djvu[s]=False
    cout[deb]=h(deb)
    dist[deb]=0
    while not djvu[fin]:
        nb+=1
        # recherche elt à cout minimal
        smin,cmin=deb,np.inf
        for s in S:
            if not djvu[s] and cout[s]<cmin: # ici ??
                smin,cmin=s,cout[s]
        djvu[smin]=True
        # relachement chez les successeurs
        for s,nu in A[smin]:
            if not djvu[s] and dist[s]>dist[smin]+nu:
                dist[s]=dist[smin]+nu
                cout[s]=dist[s]+h(s)
                predec[s]=smin
    return cout,dist,predec,nb


def gener(config):
    """Genere un graphe à partir d'une matrice (liste de listes)
    remplie de 0 (cases vides) et de 2 (murs)"""
    L=len(config)
    C=len(config[0])
    S,A=[],{}
    for i in range(L):
        for j in range(C):
            if config[i][j]==0:
                S.append((i,j))
                A[(i,j)]=[]
    for s in S:
        i,j=s
        if i>0 and config[i-1][j]==0:
            A[(i,j)].append(((i-1,j),1))
        if i<L-1 and config[i+1][j]==0:
            A[(i,j)].append(((i+1,j),1))
        if j>0 and config[i][j-1]==0:
            A[(i,j)].append(((i,j-1),1))
        if j<C-1 and config[i][j+1]==0:
            A[(i,j)].append(((i,j+1),1))
    return S,A

def color_ppc(config,predec,deb,fin):
    config[deb[0]][deb[1]]=1
    config[fin[0]][fin[1]]=1
    s=fin
    while predec[s]!=deb:
        s=predec[s]
        config[s[0]][s[1]]=1

deb,fin=(0,0),(L-1,C-1)
S,A=gener(config)
cout,dist,predec,nb=Astar_deb_fin(S,A,deb,fin)
print("A* - cout=", dist[(L-1,C-1)])
A_ppc=deepcopy(config)
color_ppc(A_ppc,predec,deb,fin)


plt.imshow(np.array(A_ppc),cmap='Greys',interpolation='nearest')
plt.show()

################################################################################
#   GENERATION ASC PPC
################################################################################

def poids(i,j):
    if config[i][j]==2:
        return float('inf')
    return 1

def ppc_tab(config):
    L,C=len(config),len(config[0])
    tab=[[0]*C for k in range(L)]
    #
    # A COMPLETER!
    #
    pass

def ppc(config):
    L,C=len(config),len(config[0])
    chemin=deepcopy(config)
    tab=ppc_tab(config)
    #
    # A COMPLETER
    #
    pass



chemin,cout=ppc(config)
if chemin==False:
    print("Echec")
else:
    print("PPC dyn - cout=",cout)
    plt.imshow(np.array(chemin),cmap='Greys',interpolation='nearest')
    plt.show()

################################################################################
#   CONFIGURATION ECHEC PPC
################################################################################

config=[[0,0,2,0,2,0,0,0],
        [0,2,0,0,0,0,0,2],
        [0,0,0,0,2,0,0,0],
        [0,0,0,2,0,0,0,0],
        [0,2,0,0,0,0,2,0]]

L,C=len(config),len(config[0])
deb,fin=(0,0),(L-1,C-1)
S,A=gener(config)
cout,dist,predec,nb=Astar_deb_fin(S,A,deb,fin)
print("A* - cout=", dist[(L-1,C-1)])
A_ppc=deepcopy(config)
color_ppc(A_ppc,predec,deb,fin)
plt.pcolormesh(np.array(config),cmap='Greys',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()



chemin,cout=ppc(config)
if chemin==False:
    print("Echec")
else:
    print("PPC dyn - cout=",cout)
    plt.imshow(np.array(chemin),cmap='Greys',interpolation='nearest')
    plt.show()