################################################################################
################################################################################
#   EX005
################################################################################
################################################################################

from ClassePile import *
import numpy as np, numpy.random as rd, matplotlib.pyplot as plt

###############################################################################
#   LABYRINTHE
################################################################################

# 2 : mur
# 0 : couloir
# 1 : couloir visité

laby=[[0,0,2,2,2,2,2], [0,2,2,0,0,2,0], [0,0,0,2,0,0,2],
    [0,2,0,2,2,0,0], [2,0,0,0,2,0,2], [2,0,2,0,0,0,2],[2,2,2,2,2,2,2]]

# Déplacements

h=lambda pos:[pos[0]-1,pos[1]]
b=lambda pos:[pos[0]+1,pos[1]]
g=lambda pos:[pos[0],pos[1]-1]
d=lambda pos:[pos[0],pos[1]+1]

# Etat, case visitée

def etat(laby,pos):
    """Renvoie l'état de pos dans laby
    Les positions hors du cadre sont des murs"""
    L,C=len(laby),len(laby[0])
    if pos[0]<0 or pos[0]>=L or pos[1]<0 or pos[1]>=C:
        return 2
    else:
        return laby[pos[0]][pos[1]]

def visite(laby,pos):
    """Bascule pos dans laby en état visité"""
    laby[pos[0]][pos[1]]=1
    
# Voisinage pas exploré

def voisinage(laby,pos):
    """Indique si pos dans laby admet un voisin pas encore visité"""
    L_pos=[g,d,h,b]
    res=1
    for f in L_pos:
        res*=etat(laby,f(pos))
    return res==0

# Voisin

def voisin(laby,pos):
    """Renvoie un voisin de pos dans laby pas encore visité"""
    L_pos=[g,d,h,b]
    for f in L_pos:
        if etat(laby,f(pos))==0:
            return f(pos)


# Parcours du labyrinthe

def dedale(laby,deb,fin):
    """Résout le labyrinthe laby en partant de la position deb"""
    chemin=Pile()
    chemin.empiler(deb)
    pos=deb
    while pos!=fin and not chemin.vide():
        visite(laby,pos)
        if voisinage(laby,pos):
            chemin.empiler(pos)
            pos=voisin(laby,pos)
        else:
            pos=chemin.depiler()
    if pos==fin:
        visite(laby,pos)
    return not chemin.vide(),chemin
            
# Experimentation

plt.imshow(np.array(laby),cmap='Greys',interpolation='nearest')
plt.show()
deb=[0,0]
fin=[3,6] # ou [1,6] pour pas de chemin
print("Recherche de chemin - origine :", deb)
print("priorité de transition : gauche/droite/haut/bas")
res,chemin=dedale(laby,deb,fin)
print("Résultat :")
print(res)
plt.imshow(np.array(laby),cmap='Greys',interpolation='nearest')
plt.show()