#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun May 29 23:52:56 2022

@author: fjunier

Génération de labyrinthe par fusion 
des chemins.

Une méthode plus efficace serait d'utiliser Union-Find
"""

import pyxel
import random

NB_LIG = 20
NB_COL = 20
VITESSE = 3

pyxel.init(2 * NB_COL  + 1, 2 * NB_LIG + 1, "Labyrinthe")


def numero_case(col, lig, nbcol, nblig):
    """
    Renvoie un numéro de case associé à un couple (col, lig)
    """
    return lig * nbcol + col

def liste_MURS(nbcol, nblig):
    """
    Renvoie une liste des MURS internes
    Chaque mur est une liste de deux tuples :
    (col_case1, lig_case1) et (col_case2, lig_case2)    
    """
    MURS = []
    # MURS horizontaux
    for lig in range(nblig - 1):
        for col in range(nbcol):
            MURS.append([(col, lig), (col, lig + 1)])
    # MURS verticaux
    for lig in range(nblig):
        for col in range(nbcol - 1):
            MURS.append([(col, lig), (col + 1, lig)])
    return MURS
    
def choisir_mur():
    """
    Extrait un mur (deux cases adjacentes)
    de la liste MURS tel que les deux cases adjacentes
    n'aient pas le même numéro dans GRILLE    
    """
    index = random.randint(0, len(MURS) - 1)
    case1, case2 = MURS[index]
    col1, lig1 = case1
    col2, lig2 = case2
    while GRILLE[lig1][col1] == GRILLE[lig2][col2]:        
        index = random.randint(0, len(MURS) - 1)
        case1, case2 = MURS[index]
        col1, lig1 = case1
        col2, lig2 = case2
    MURS_DETRUITS.append(MURS.pop(index))
    return case1, case2

def case_possible(col, lig, nbcol, nblig):
    return (0 <= lig < nblig) and (0 <= col < nbcol)

def voisinage(col, lig, nbcol, nblig):
    return [(col + dcol, lig + dlig)  for (dcol, dlig) in [(-1,0), (1,0), (0,-1), (0,1)] 
            if case_possible(col + dcol, lig + dlig, nbcol, nblig)]

                
MURS = liste_MURS(NB_COL, NB_LIG)
MURS_DETRUITS = []
# GRILLE [col][lig] contient un numéro de case
# deux cases auront le même numéro de cases lorsqu'elles appartiendront au même graphe connexe acyclique / arbre
GRILLE = [[numero_case(col, lig, NB_COL, NB_LIG) for col in range(NB_COL)] for lig in range(NB_LIG)]
# FORET[numero] est un graphe connexe acyclique / un arbre représenté sous forme de dictionnaire de listes d'ajacences
FORET = {numero_case(col, lig, NB_COL, NB_LIG):{(col,lig):[]} for lig in range(NB_LIG) for col in range(NB_COL)} 


def numeroter_dfs(case, graphe, numero):
    """
    Parcours DFS de graphe à partir de case
    Numérote toutes les cases du graphe avec numéro        
    """
    col, lig = case
    GRILLE[lig][col] = numero
    for voisin in graphe[case]:
        colv, ligv = voisin
        if GRILLE[ligv][colv] != numero:
            numeroter_dfs(voisin, graphe, numero)


def update():
    if pyxel.frame_count % VITESSE == 0:
        if len(FORET) > 1:
            case1, case2 = choisir_mur()
            col1, lig1 = case1
            col2, lig2 = case2
            numero1 = GRILLE[lig1][col1]
            numero2 = GRILLE[lig2][col2]
            graphe2 = FORET[numero2]
            #on renumérote toutes les cases de graphe2 avec numero1
            numeroter_dfs(case2, graphe2, numero1)
            graphe1 = FORET[numero1]
            # on rattache graphe2 à graphe1
            graphe1[case1].append(case2)        
            graphe1.update(graphe2)  # mise à jour de dictionnaire avec un autre dictionnaire !
            graphe1[case2].append(case1)
            # on élimine graphe2 de la forêt
            del FORET[numero2]

                    
                    
def draw():
    if pyxel.frame_count % VITESSE == 0:
        pyxel.cls(0)
        for lig in range(1, 2 * NB_LIG):
            for col in range(1, 2 * NB_COL):
                if lig % 2 == 1 and col % 2 == 1:
                    couleur = GRILLE[lig // 2][col // 2] % 16
                    if couleur == 0:
                        couleur = 1
                    pyxel.rect(col, lig, 1, 1, couleur)      
        for case1, case2 in MURS_DETRUITS:
            col1, lig1 = case1
            col2, lig2 = case2
            if col1 == col2:
                couleur = GRILLE[lig1][col1] % 16
                if couleur == 0:
                    couleur = 1
                pyxel.rect(2 * col1 + 1, 2 * min(lig1, lig2) + 2, 1, 1, couleur)
            else:
                couleur = GRILLE[lig2][col2] % 16
                if couleur == 0:
                    couleur = 1
                pyxel.rect(2 * min(col1, col2) + 2, 2 * lig1 + 1, 1, 1, couleur)
                 
        
pyxel.run(update, draw)