######################################
# GESTION DES LABYRINTHES
######################################

def dessinerTableau(tab):
    """
    permet de dessiner le labyrinthe passe en parametre
    - les cases avec un 1 sont des murs => '#'
    - les cases avec un 0 sont des espaces vides => ' '
    """

    for j in range(0,len(tab[0])):
        for i in range(0,len(tab)):
            # mur
            if tab[i][j]==-1:
                print('#', end=' ')
            # vide
            elif tab[i][j]==0 :
                print(' ', end=' ')
            # altitude
            else :
                print(tab[i][j], end=' ')
        print()

###################

def transpose(laby):
    """
    permet d'inverser lignes et colonnes d'un labyrinthe
    (utile pour la creation simple)
    """
    # nouveau laby
    laby2=[]
    for i in range(0,len(laby[0])):
        ligne=[]
        for j in range(0,len(laby)):
            ligne+=[0]
        laby2+=[ligne]

    # transposition
    for i in range(0,len(laby[0])):
        for j in range(0,len(laby)):
            laby2[i][j]=laby[j][i]

    return laby2


###################

def getLabyrintheAltitude():
    """
    Construit et retourne un labyrinthe par defaut a parcourir
    (de taille 7x7)
    * mur = -1
    * autre case = altitude

    cout = difference altitude
    """

    # labyrinthe vide
    laby = []
    laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]]
    laby +=[[-1, 0, 0, 0, 0, 0, 0,-1]]
    laby +=[[-1, 0,-1, 0,-1, 1,-1,-1]]
    laby +=[[-1, 2, 2, 0,-1, 2, 0,-1]]
    laby +=[[-1,-1,-1, 2,-1, 3,-1,-1]]
    laby +=[[-1, 0, 0, 0, 0, 0, 0,-1]]
    laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]]

    # nouveau laby
    xDep = 6
    yDep = 5
    xArr = 1
    yArr = 1
    return transpose(laby), xDep, yDep, xArr, yArr

# labyrinthe sans altitude
def getLabyrintheSansAltitude():
    """
    Construit et retourne un labyrinthe par defaut a parcourir
    (de taille 7x7)
    * mur = -1
    * autre case = altitude

    cout = difference altitude
    """

    # labyrinthe vide
    laby = []
    laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]]
    laby +=[[-1, 0, 0, 0, 0, 0, 0,-1]]
    laby +=[[-1, 0,-1, 0,-1, 0,-1,-1]]
    laby +=[[-1, 0, 0, 0,-1, 0, 0,-1]]
    laby +=[[-1,-1,-1, 0,-1, 0,-1,-1]]
    laby +=[[-1, 0, 0, 0, 0, 0, 0,-1]]
    laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]]

    # nouveau laby
    xDep = 6
    yDep = 5
    xArr = 1
    yArr = 1
    return transpose(laby), xDep, yDep, xArr, yArr



# labyrinthe cul de sac
def getLabyrintheCulSac():
    """
    Construit et retourne un labyrinthe par defaut a parcourir
    (de taille 7x7)
    * mur = -1
    * autre case = altitude

    cout = difference altitude
    """

    # labyrinthe vide
    laby = []
    laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]]
    laby +=[[-1, 0, 0, 0, 0, 0,-1,-1]]
    laby +=[[-1, 0,-1,-1,-1,-1, 0,-1]]
    laby +=[[-1, 0,-1, 0,-1,-1, 0,-1]]
    laby +=[[-1, 0,-1, 0, 0,-1, 0,-1]]
    laby +=[[-1, 0, 0, 0, 0,-1, 0,-1]]
    laby +=[[-1, 0, 0, 0, 0,-1, 0,-1]]
    laby +=[[-1, 0,-1, 0, 0,-1, 0,-1]]
    laby +=[[-1, 0,-1, 0, 0, 0, 0,-1]]
    laby +=[[-1,-1,-1,-1,-1,-1,-1,-1]]

    # nouveau laby
    xDep = 6
    yDep = 5
    xArr = 5
    yArr = 1
    return transpose(laby), xDep, yDep, xArr, yArr



######################################
# AVEC LISTE OUVERTE
######################################


def calculLabyAStar(laby,xDep,yDep,xArr,yArr):
    """
    effectue le calcul des distances en utilisant une liste ouverte
    - strategie consiste à propager case par case
    - développer la case la plus proche + heuristique
    """
    # for sorting
    from operator import itemgetter;


    # faire un nouveau tableau avec 10000
    max = 1000
    tab=[]
    for i in range(len(laby)):
        t=[]
        for j in range(len(laby[0])) :
            t+=[max]
        tab+=[t]

    # voisins connexite 4
    voisins=[[0,1],[0,-1],[1,0],[-1,0]]

    # ouverte : cases à parcourir (x,y,valeur)
    heuristic = abs(xDep-xArr) + abs(yDep-yArr)
    valeur = 0 + heuristic
    ouverte = [(xDep,yDep,valeur)]

    # update tab
    tab[xDep][yDep] = 0

    # tant que non fini
    fini = False

    # tant qu'il reste des elements
    while len(ouverte)>0 :
        # get element
        # WARNING : pop(0) si on veut le fonctionnement d'une file
        #           sinon pop() prend en fin de liste

        # sort by value
        (i,j,val) = ouverte.pop(0)

        # TODO A* : si sortie est atteinte, break
        if i == xArr and j == yArr :
            break;

        # pour chaque voisin
        for v in voisins:
            # coordonnes du voisin
            voisinX = i + v[0]
            voisinY = j + v[1]

            # si case est pas un mur => la traiter
            if laby[voisinX][voisinY] != -1 :

                altitude = abs(laby[voisinX][voisinY]-laby[i][j])
                # calcule nouvelle distance
                nouvelleD = tab[i][j] + altitude + 1

                # si meilleur met a jour
                if nouvelleD < tab[voisinX][voisinY] :

                    # TODO A * : calcule heuristique
                    heuristic = abs (voisinX-xArr) + abs (voisinY-yArr)

                    # si existe deja
                    if tab[voisinX][voisinY] != max :
                        # supprime ancien element de la liste
                        oldval = tab[voisinX][voisinY] + heuristic
                        ouverte.remove((voisinX,voisinY,oldval))

                    # met a jour
                    tab[voisinX][voisinY] = nouvelleD
                    val = nouvelleD + heuristic
                    ouverte.append((voisinX,voisinY, val))

        # TODO A* -- tri liste ouverte par valeur + heuristic
        ouverte = sorted(ouverte, key=itemgetter(2))

        # affiche la liste ouverte et le chemin parcouru à chaque iteration
        dessinerChemin(tab)
        print(ouverte)
        print("--------------------------------")


    # fin retourner tableau
    return tab


######################################
# AFFICHAGE DES DISTANCES
######################################

def dessinerChemin(tab):
    """
    permet de dessiner une matrice de distance dans un labyrinthe
    """
    # dessine les lignes
    for j in range(0,len(tab[0])):

        # pour chaque colonnee
        for i in range(0,len(tab)):
            # recupere la valeur calculee
            val=tab[i][j]

            # si c'est 1000, c'est une case non visitee
            if val==1000:
                # affiche vide
                print("   ",end=' ')
            else:
                # affiche la valeur
                print(val,end=' ')
                # ajoute le bon nombre d'espaces en fonction de la taille du nombre
                if val<0:
                    val=-val*10
                if val==0:
                    val=1
                while (val<100):
                    val=val*10
                    print(' ',end='')
        print()

######################################
# CALCUL DU CHEMIN
######################################

def  getCheminDijkstra(laby,distance,depX,depY):
    """
    retourne le chemin a partir d'une matrice de distance
    - depX : abscisse du depart
    - depY : ordoneee du depart
    """
    # valeur maximale
    maxVal=1000

    # on se place au depart
    x=depX
    y=depY
    chemin=[(x,y)]

    # liste des voisins connexite 4
    voisins = [(1,0),(-1,0),(0,1),(0,-1)]

    # tant que 0 est non atteint
    while not distance[x][y] == 0 :
        # cherche plus petite case chez les voisins
        min = maxVal
        voisinMin =()
        # pour chaque voisin
        for voisin in voisins :
            # calcule case voisine
            vx = x + voisin[0]
            vy = y + voisin[1]

            # si meilleure et atteignable
            if distance[vx][vy] < min :

                # TODO Dijkstra : atteignable
                # calcule altitude
                altitude = abs(laby[x][y]-laby[vx][vy])

                # verifie atteignable
                if distance[x][y] == distance[vx][vy] + altitude + 1 :
                    min = distance[vx][vy]
                    voisinMin = (vx,vy)

        # meilleureVoisin trouve remonte la case
        chemin.append(voisinMin)
        (x,y) = voisinMin

    # fin retourne chemin
    return chemin

######################################
# MAIN
######################################

def main():
    """
    code appele par le __main__
    creer et dessine un Labyrinthe
    """
    # creer un labyrinthe
    laby, xDep, yDep, xArr, yArr = getLabyrintheCulSac()

    # affiche le labyrinthe dans la console
    dessinerTableau(laby)

    # consytruire cases
    print("############# A * ##############")
    tab = calculLabyAStar(laby,xDep,yDep,xArr,yArr)

    # recupere chemin
    chemin = getCheminDijkstra(laby,tab,xDep,yDep)
    print (chemin)


######################################
# lancement du module python
######################################


import sys

if __name__ == "__main__":
    # labyrinthe a afficher
    main()