import numpy
import scipy
import matplotlib
from pylab import *
from random import *

########### INSERTION DE L'ALGORITHME DE DIJKSTRA #############
### Remarque : on pourrait aussi importer le module os afin de se placer dans le bon répertoire de travail puis importer le module (c'est-à-dire le fichier .py) dans lequel se trouvent les deux fonctions utilisées ci-après.


def Dijkstra(M,dep,arr) :
    somme=inf
    M_Temp=M.copy()
    S,A,L=[dep],[],[x for x in range(len(M[:,0])) if x != dep]
    # S = sommets marqués
    # A = arêtes marquées
    # L = sommets non encore marqués
    Test_Mise_A_Jour=True
    # pour tester si on n'a pas d'impasse 
    while S[-1] != arr and Test_Mise_A_Jour :
        Test_Mise_A_Jour=False
        cout_Temp=somme 
        #initialisation du coût à la somme des coûts
        arete_Temp=[]
        for i in S :
            for j in L :
                if M[i,j]>0 and M_Temp[i,i]+M_Temp[i,j]<=cout_Temp :
                    ### problème de mise à jour des coeff de M_Temp
                    # on teste une arête [i,j] avec j non marqué
                    Test_Mise_A_Jour=True
                    arete_Temp=[i,j]
                    cout_Temp=M_Temp[i,i]+M_Temp[i,j]
        # en sortie ici, on a une arête optimale en coût si Test_Mise_A_Jour est vrai
        
        
        
        if Test_Mise_A_Jour :
            S.append(arete_Temp[1])
            Test=False
        
            for index in range(len(A))  :
                if not(Test) :
                    # si on n'a pas encore encore greffé l'arête sur un chemin
                    chemin_Temp=A[index]
                    for l in range(len(chemin_Temp)) :
                        if chemin_Temp[l]==arete_Temp[0] :
                            A.append(chemin_Temp[:l+1]+[arete_Temp[1]])
                            Test=True
                            break
                            # une seule greffe de l'arête
            if not(Test) :
                # l'arête trouvée  n'est pas greffable sur un chemin existant
                A.append(arete_Temp)
            L.remove(S[-1])
            M_Temp[arete_Temp[1],arete_Temp[1]]=cout_Temp
            # mise à jour de l'arête
            
        
    if  dep==arr :
        # départ = arrivée : on sort de la boucle immédiatement
        return [[dep],0]
    elif S[-1]==arr :
        # on trouve une connexion possible
        chemin_optimal=[c for c in A if c[-1]==arr][0] 
        cout_total=M_Temp[arr,arr]
        return [chemin_optimal,cout_total]        
    else :
        # on ne trouve pas de connexion possible
        return "pas de chemin possible"
    
####### fin de l'insertion ########



########## caractéristiques du labyrinthe

########## Dans tout ce qui suit, les cases du labytinthe sont indexées par (i,j) correspondant à la case délimitée par (i,j) et (i+c,j+c). La diagonale du damier est (0,0) et (largeur,hauteur)

######### petit labyrinthe

c=20
largeur=40
hauteur=20
  

Taille_largeur=c*largeur
Taille_hauteur=c*hauteur


############ mise en place graphique #############

from tkinter import *

######### initialisation du labyrinthe ###########

dico = {} #dictionnaire contenant les coordonnées de chaque case : 0 pour passage libre et 1 pour obstacle

for i in range(largeur+1) :
    for j in range(hauteur+1) :
            dico[i,j]=0
            



def Voisins(M)  : 
    """ calcule la liste des voisins d'une position M relativement au labyrinthe"""
    global largeur, hauteur ,dico
    Liste_Voisins=[]
    if M[0]==0 : 
        A=[1]
    elif M[0]==largeur : 
        A=[-1]
    else :
        A=[-1,1]
        
    for i in A :
        if  dico[M[0]+i,M[1]]==0 :
                    Liste_Voisins.append([M[0]+i,M[1]])
                
    if M[1]==0 : 
        B=[1]
    elif M[1]==hauteur : 
        B=[-1]
    else :
        B=[-1,1]
        
    for j in B :
        if  dico[M[0],M[1]+j]==0 :
                    Liste_Voisins.append([M[0],M[1]+j])
    return Liste_Voisins


def Test_Adj(M,N) :  
    """teste si deux positions sont adjacentes"""
    return abs(M[0]-N[0])+abs(M[1]-N[1])==1


#print(Test_Adj([5,6],[6,6]))



def Suppression(L,objet) :   
    """enlève objet de L """ 
    return [x for x in L if x!=objet]
    


def click_depart(event): 
    """fonction qui choisit le point de départ"""
    global dico,Dep,Arr
    x=event.x
    y=event.y
    i=x//c
    j=y//c
    Dep=[i,j]
    canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='green')
    
    
    text_arr=Label(fenetre,text="Choix de la case d'arrivée ",fg="red")
    text_arr.pack(side=LEFT)
    
    canevas.bind("<Button-1>", click_arrivee)
    
### INSERTION DU SCRIPT ICI POUR QUE LES FONCTIONS SOIENT RECONNUES PAR click_arrivee

### définition des sommets grâce au dictionnaire établi via l'interface




def F(P) :
    """ renvoie le numéro de la case P lorsque le tableau bi-dimensionnel du labyrinthe est mis en ligne """
    return (largeur+1)*P[1]+P[0]
    
def G(P) :
    """ renvoie les coordonnées de la case associée à P  : c'est la fonction inverse de F"""
    return (P%(largeur+1),P//(largeur+1))

def Voisins_bis(P,Sommets,largeur,hauteur) :
    L=[]
    i,j=P[0],P[1]
    if i>0 :
        L.append((i-1,j))
    if j>0 :
        L.append((i,j-1))
    if i<largeur :
        L.append((i+1,j))
    if j<hauteur :
        L.append((i,j+1))
    return [P for P in L if P in Sommets] # on enlève les obstacles

#print(Voisins_bis((2,4),Sommets,largeur,hauteur)) # ok

taille=(largeur+1)*(hauteur+1)


def Mat_Adj(Sommets,largeur,hauteur) :
    """ renvoie la matrice d'adjacence avec les cases sans obstacles et les arêtes uniformément pondérées par 1 """
    Matrice_Adjacence=zeros((taille,taille))

    for S in Sommets :
        for P in Voisins_bis(S,Sommets,largeur,hauteur) :
            Matrice_Adjacence[F(S),F(P)]=1
            Matrice_Adjacence[F(P),F(S)]=1
        ## matrice symétrique : graphe non orientée
        
    return Matrice_Adjacence
### PROBLEME DANS LA MATRICE D'ADJACENCE....
### SI aucun obstacle, matrice adjacence nulle ...

def Tracer_Chemin() :
    global dico,Dep,Arr,Sommets
    Sommets=[cle for cle in dico.keys() if dico[cle]==0]
    M=Mat_Adj(Sommets,largeur,hauteur)
    Chemin=Dijkstra(M,F(Dep),F(Arr))
    
    
    if Chemin != "pas de chemin possible" :  # si le problème a une solution...
        Liste=[G(P) for P in Chemin[0]]
        ## Disjkstra renvoie une liste avec un chemin minimal et le coût de ce chemin
        # on transforme la modélisation linéaire des cases en modélisation bi-dimensionnelle
        for P in Liste[1:len(Liste)-1] : # pour ne pas colorier la dernière case d'arrivée
            canevas.create_rectangle(P[0]*c, P[1]*c, (P[0]+1)*c, (P[1]+1)*c, fill='#FF00BF')
            fenetre.after(30)
            fenetre.update()
    else :
        for j in range(7) :
            canevas.create_rectangle(Dep[0]*c, Dep[1]*c, (Dep[0]+1)*c, (Dep[1]+1)*c, fill='#FF8000')
            canevas.create_rectangle(Arr[0]*c, Arr[1]*c, (Arr[0]+1)*c, (Arr[1]+1)*c, fill='#0101DF')
            fenetre.after(250)
            fenetre.update()
            canevas.create_rectangle(Dep[0]*c, Dep[1]*c, (Dep[0]+1)*c, (Dep[1]+1)*c, fill='#0101DF')
            canevas.create_rectangle(Arr[0]*c, Arr[1]*c, (Arr[0]+1)*c, (Arr[1]+1)*c, fill='#FF8000')
            fenetre.after(250)
            fenetre.update()

############### fin de l'insertion #################
  
def click_arrivee(event): 
    """fonction qui choisit le point d'arrivée"""
    global dico,Dep,Arr
    x=event.x
    y=event.y
    i=x//c
    j=y//c
    if [i,j] != Dep :
        Arr=[i,j]
        canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='red')
    
    
        text_obst=Label(fenetre,text="Choix des obstacles ",fg="black")
        text_obst.pack(side=LEFT)
    
        canevas.bind("<Button-1>", click_gauche)
        canevas.bind("<Button-3>", click_droit)
        ### insertion du widget de Recherche ###
        b1 = Button(fenetre, text ='Effectuer la recherche', command =Tracer_Chemin)
        ###
        b3 = Button(fenetre, text ='Recommencer', command =recommencer)
        
        b4 = Button(fenetre, text ='Quitter', command =fenetre.quit)
        b5 = Button(fenetre, text ='Obstacles aléatoires', command =laby_alea)
        ### insertion dans la fenêtre
        b1.pack(side =LEFT, padx =3, pady =3)
        ###
        b4.pack(side =RIGHT, padx =3, pady =3)
        b3.pack(side =RIGHT, padx =3, pady =3)
        b5.pack(side =RIGHT, padx =3, pady =3)
        dessiner()

def laby_alea() : 
    """créé un labyrinthe aléatoire"""
    canevas.delete(ALL)
    for i in range(largeur+1) :
        for j in range(hauteur+1) :
            if [i,j]!=Dep and [i,j]!=Arr :
                if randint(0,2) ==2 : # deux fois plus de cases blanches que de cases noires, en moyenne
                    dico[i,j]=1
                else :
                    dico[i,j]=0
    dessiner()
                
def click_gauche(event): 
    """fonction rendant vivante la cellule cliquée donc met la valeur 1 pour la cellule cliquée au dico"""
    global dico
    x=event.x
    y=event.y
    i=x//c
    j=y//c
    if [i,j]!=Dep and   [i,j]!=Arr :
        canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='black')
        dico[i,j]=1

def click_droit(event): 
    """fonction tuant la cellule cliquée donc met la valeur 0 pour la cellule cliquée au dico"""
    global dico
    x=event.x
    y=event.y
    i=x//c
    j=y//c
    if [i,j]!=Dep and [i,j]!=Arr :
        canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='white')
        dico[i,j]=0


def dessiner(): # dessins le tableau à partir des états
    global dico,Dep,Arr
    for i in range(largeur+2) :
        canevas.create_line(i*c,0,i*c,Taille_hauteur+c,width=1,fill='black')
    for j in range(hauteur+2) :
        canevas.create_line(0,j*c,Taille_largeur+c,j*c,width=1,fill='black')
    canevas.create_rectangle(Dep[0]*c,Dep[1]*c,Dep[0]*c+c,Dep[1]*c+c, fill='green') # case de départ
    canevas.create_rectangle(Arr[0]*c,Arr[1]*c,Arr[0]*c+c,Arr[1]*c+c, fill='red') # case d'arrivée
    for i in range(largeur+1) :
        for j in range(hauteur+1) :
            if dico[i,j]==1 :
                canevas.create_rectangle(i*c,j*c,(i+1)*c,(j+1)*c, fill='black')
    fenetre.update()

def recommencer() :
    global dico
    canevas.delete(ALL)
    dico = {} #dictionnaire contenant les coordonnées de chaque cellule et une valeur 0 ou 1 si elles sont respectivement mortes ou vivantes

    for i in range(largeur+1) :
        for j in range(hauteur+1) :
                dico[i,j]=0
    dessiner()
########## interface graphique ##########


fenetre = Tk()
canevas = Canvas(fenetre, width =Taille_largeur+c, height =Taille_hauteur+c, bg ='white')

canevas.bind("<Button-1>", click_depart)
    
canevas.pack(side =TOP, padx =5, pady =5)
for i in range(largeur+2) :
    canevas.create_line(i*c,0,i*c,Taille_hauteur+c,width=1,fill='black')
    for j in range(hauteur+2) :
        canevas.create_line(0,j*c,Taille_largeur+c,j*c,width=1,fill='black')

text_dep=Label(fenetre,text="Choix de la case de départ ",fg="green")
text_dep.pack(side=LEFT)

fenetre.mainloop()
fenetre.destroy()


  
### le labyrinthe est modélisé par un dictionnaire du type dico[i,j]=0 ou 1 pour signifier que la case [i,j] est un obstacle ou non : les positions sont les clés du dictionnaire et le statut de la case cle est dico[cle] renseignant l'obstacle ou non ; à noter que les clés sont des tuples (i,j) et donc que les sommets de la grille sont des tuples (i,j)

### regarder pour importer le module Dijkstra plutôt que de copier la fonction dans ce script


### performance : Dijkstra assez lent par rapport à l'algorithme A*