################################################################################
################################################################################
#   LABY
################################################################################
################################################################################

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]]

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

def h(pos):
    return [pos[0]-1,pos[1]]

def b(pos):
    return [pos[0]+1,pos[1]]

def g(pos):
    return [pos[0],pos[1]-1]

def d(pos):
    return [pos[0],pos[1]+1]

def visite(laby,pos):
    i,j=pos
    laby[i][j]=1

def etat(laby,pos):
    L,C=len(laby),len(laby[0])
    # test si hors du labyrinthe
    if pos[0]<0 or pos[0]>=L or pos[1]<0 or pos[1]>=C:
        return 2
    else:
        i,j=pos
        return laby[i][j]

def voisinage(laby,pos):
    return etat(laby,h(pos))*etat(laby,b(pos))*etat(laby,g(pos))*etat(laby,d(pos))==0

def voisin(laby,pos):
    if etat(laby,h(pos))==0:
        return h(pos)
    if etat(laby,b(pos))==0:
        return b(pos)
    if etat(laby,g(pos))==0:
        return g(pos)
    if etat(laby,d(pos))==0:
        return d(pos)

def dedale(laby,deb,fin):
    chemin=Pile()
    chemin.empiler(deb)
    pos=deb
    while pos!=fin and not chemin.vide():
        visite(laby,pos)
        if voisinage(laby,pos): # si je peux bouger
            chemin.empiler(pos) # je mémorise d'où je viens
            pos=voisin(laby,pos) # et je bouge
        else:
            pos=chemin.depiler() # sinon, je reviens sur mes pas en dépilant
    if pos==fin:
        visite(laby,pos)
    return not chemin.vide(),chemin


plt.imshow(np.array(laby),cmap='Greys',interpolation='nearest')
plt.show()
deb=[0,0]
fin=[3,6]
res,chemin=dedale(laby,deb,fin)
plt.imshow(np.array(laby),cmap='Greys',interpolation='nearest')
plt.show()