import numpy as np
from random import randint
import matplotlib.pyplot as plt

N = 8


# Q1
est_visitee = [ [False for k in range(N)] for k in range(N) ]
    
    
# Q1.b il s'agit de booléen

# Q2
def case_possible(c):
    i,j = c
    return  0 <= i < N and 0 <= j < N
    
    

# Q3
def visite(c):
    i,j = c
    if case_possible(c):
        est_visitee[i][j] = True

# Q4
# def valeur(c):
#     x,y = c
#     if x<0 or x>=N or y<0 or y>=N :
#         return True
#     else : 
#         return TestPassage[x,y]

# Q5
def cases_voisines(c):
    i,j = c
    case_non_atteinte = []
    for voisin in [ [i+1,j],[i-1,j],[i,j+1],[i,j-1] ]:
        x,y = voisin
        if  case_possible(voisin) and not est_visitee[x][y] :
            case_non_atteinte.append(voisin)
    return case_non_atteinte
         
        
 # Q4
def case_alea(L):
    if len(L)!=0:
        return L[randint(0,len(L)-1)]


# Q5
def labyrinthe():
     #initialisation
    chemin = []
    p = []
    p.append( [0,0] )
    #
    while len(p)!=0:
        c = p.pop()
        visite(c)
        chemin.append(c)
        case_non_atteinte = cases_voisines(c)
        if len(case_non_atteinte)!=0:
            p.append(c)
            p.append(case_alea(case_non_atteinte))
    return chemin



    



def trace_porte(chemin):
    N = len(chemin)
    liste_porte =[]
    for k in range(0,N-1):
        case = chemin[k]
        case_suivante = chemin[k+1]
        direction = [case_suivante[0]-case[0],case_suivante[1]-case[1] ]
        
        if direction == [1,0]:
            porte = [[case[0]+0.5,case[1] -0.5],[case[0]+0.5,case[1]  +0.5]]
        elif direction == [0,1]:
            porte = [[case[0]-0.5,case[1] +0.5],[case[0]+0.5,case[1]  +0.5]]
        elif direction == [-1,0]:
            porte = [[case[0]-0.5,case[1] +0.5],[case[0]-0.5,case[1] -0.5] ]
        elif direction ==[0,-1]:
            porte = [[case[0]-0.5,case[1]-0.5],[case[0]+0.5,case[1] -0.5] ]
        liste_porte.append(porte)
        
    return liste_porte

def structure(chemin):        
    N = len(chemin)
    porte =[0,0,0,0]
    M=[]
    for k in range(N):
        ligne = []
        for k in range(N):
            ligne.append(porte[:])
        M.append(ligne)    
    
        
    for k in range(0,N-1):
        case = chemin[k]
        case_suivante = chemin[k+1]
        direction = [case_suivante[0]-case[0],case_suivante[1]-case[1] ]
        # print('direction',direction)
        if direction == [-1,0]:
            M[case[0]][case[1]][0] = 1 
        elif direction == [0,-1]:
            M[case[0]][case[1]][1] = 1 
        elif direction == [1,0]:
            M[case[0]][case[1]][2] = 1 
        elif direction == [0,1]:
            M[case[0]][case[1]][3] = 1 
        # print('case :',case[0],case[1],' ',M[case[0]][case[1]])
        # print('case :0,0 ',M[0][0])
        
    return M
    
            
def trace_mur(M):
    for x in range(N):
        for y in range(N):
            if M[x][y][0] == 0:
                plt.plot([x-0.5,x-0.5],[y-.5,y+.5],'k')
            if M[x][y][1] == 0:
                plt.plot([x-0.5,x+0.5],[y-.5,y-.5],'k')
            if M[x][y][2] == 0:
                plt.plot([x+0.5,x+0.5],[y-.5,y+.5],'k')
            if M[x][y][3] == 0:
                plt.plot([x-0.5,x+0.5],[y+.5,y+.5],'k')
            # 


            
            
##  MAIN  
def dessine(chemin):
    L_x = []
    L_y = []
    for k in range(len(chemin)):
        L_x.append(chemin[k][0])
        L_y.append(chemin[k][1])
    plt.plot(L_x,L_y,'-o')
    

# le chemin du labyrinthe
chemin = labyrinthe()           
# dessine(chemin)

# les portes
liste_porte = trace_porte(chemin)
for porte in liste_porte:
    p1,p2 = porte
    porte_x =[p1[0],p2[0]]
    porte_y = [p1[1],p2[1]] 
#    plt.plot(porte_x,porte_y,'-r')
 
#les murs
M =structure(chemin)
trace_mur(M)

plt.axis([-1,N,-1,N])
plt.show()