import random
import tkinter as tk
from typing import List, Tuple, Optional, Set
from collections import deque

# ============================================================
# 1. ENVIRONNEMENT : représente la grille + distances + utilitaires
# ============================================================

# Pour plus de lisibilité
Coord = Tuple[int, int]


class Environment:
    """
    Classe qui encapsule TOUT ce qui concerne le labyrinthe :
    - la grille
    - la position du départ et de l'arrivée
    - les distances calculées via BFS
    - les fonctions de déplacement / vérification
    """

    def __init__(self, grid: List[str]):
        # Je convertis la grille en liste de listes pour modifier plus facilement
        self.grid = [list(row) for row in grid]
        self.height = len(self.grid)
        self.width = len(self.grid[0]) if self.height > 0 else 0

        # Ces deux valeurs sont trouvées automatiquement
        self.start: Optional[Coord] = None
        self.end: Optional[Coord] = None
        self._find_start_end()

        # BFS pour savoir le chemin le plus court entre S et E
        self.optimal_path_length = self._compute_optimal_path_length()

        # Je génère une carte complète des distances de CHAQUE case jusqu'à la sortie
        # → utile pour une fitness intelligente
        self.distance_map, self.max_distance_to_end = self._compute_distance_map()

    # ------------------------------------------------------------
    # Localisation des points start (S) et end (E)
    # ------------------------------------------------------------
    def _find_start_end(self):
        # Je parcours toute la grille pour trouver S et E
        for y in range(self.height):
            for x in range(self.width):
                if self.grid[y][x] == 'S':
                    self.start = (x, y)
                elif self.grid[y][x] == 'E':
                    self.end = (x, y)

    # ------------------------------------------------------------
    # Fonctions utilitaires pour naviguer dans la grille
    # ------------------------------------------------------------

    def is_inside(self, x: int, y: int) -> bool:
        # Vérifie si la coordonnée existe dans la grille
        return 0 <= x < self.width and 0 <= y < self.height

    def is_wall(self, x: int, y: int) -> bool:
        # Toute case invalide est aussi considérée comme un mur
        if not self.is_inside(x, y):
            return True
        return self.grid[y][x] == '#'

    def is_valid_move(self, x: int, y: int) -> bool:
        # Un mouvement est valide si la case existe et n’est pas un mur
        return self.is_inside(x, y) and not self.is_wall(x, y)

    def move(self, pos: Coord, move: str) -> Coord:
        # Je déplace le point selon les lettres H, B, G, D
        x, y = pos
        if move == 'H': y -= 1
        elif move == 'B': y += 1
        elif move == 'G': x -= 1
        elif move == 'D': x += 1
        return (x, y)

    # ------------------------------------------------------------
    # BFS → distance optimale entre S et E (juste pour référence)
    # ------------------------------------------------------------
    def _compute_optimal_path_length(self) -> float:
        """
        BFS classique pour récupérer la distance minimale S → E.
        Permet juste de savoir ce qu'est un "chemin parfait".
        """
        if self.start is None or self.end is None:
            return float("inf")

        sx, sy = self.start
        ex, ey = self.end

        queue = deque([(sx, sy, 0)])
        visited = {(sx, sy)}

        while queue:
            x, y, d = queue.popleft()

            if (x, y) == (ex, ey):
                return d

            for dx, dy in [(0,-1), (0,1), (-1,0), (1,0)]:
                nx, ny = x + dx, y + dy
                if self.is_valid_move(nx, ny) and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, d + 1))

        return float("inf")

    # ------------------------------------------------------------
    # Carte complète des distances → distance réelle jusqu'à E
    # (extrêmement important pour guider l’évolution)
    # ------------------------------------------------------------
    def _compute_distance_map(self):
        """
        Génère une "heatmap" : pour chaque case, la distance la plus courte
        jusqu'à la sortie E, en respectant les murs.
        → Permet d'éviter que l’AG tombe dans de fausses voies "proches en Manhattan".
        """
        dist = [[float("inf")] * self.width for _ in range(self.height)]
        max_val = 0

        if self.end is None:
            return dist, max_val

        ex, ey = self.end
        queue = deque([(ex, ey)])
        dist[ey][ex] = 0

        while queue:
            x, y = queue.popleft()
            d = dist[y][x]
            max_val = max(max_val, d)

            # On explore les voisins
            for dx, dy in [(0,-1),(0,1),(-1,0),(1,0)]:
                nx, ny = x + dx, y + dy
                if self.is_valid_move(nx, ny) and dist[ny][nx] == float("inf"):
                    dist[ny][nx] = d + 1
                    queue.append((nx, ny))

        # En cas de labyrinthe bizarre
        if max_val <= 0:
            max_val = self.width + self.height

        return dist, max_val

    def get_distance_to_end(self, x: int, y: int) -> float:
        # Renvoie la distance "réelle" jusqu'à E pour aider la fitness
        if not self.is_inside(x, y):
            return float("inf")
        return self.distance_map[y][x]


# ============================================================
# 2. CLASSE INDIVIDU : une suite de mouvements + infos
# ============================================================

class Individual:
    """
    Un individu représente un chemin potentiel dans le labyrinthe.
    Il contient :
    - une liste de mouvements H / B / G / D
    - des métriques d’exécution
    """

    def __init__(self, path_moves: List[str]):
        self.path_moves = path_moves
        self.current_position: Coord = (0, 0)
        self.has_collided: bool = False
        self.has_reached_end: bool = False
        self.fitness: float = float("-inf")

        # Infos utiles pour debug / afficher le chemin
        self.path_positions: List[Coord] = []
        self.distance_record: float = float("inf")
        self.valid_moves: int = 0


# ============================================================
# 3. FONCTION DE FITNESS : cœur de l'évolution
# ============================================================

def calculate_fitness(ind: Individual, env: Environment) -> float:
    """
    La fitness évalue :
    - si l’individu arrive à la sortie (jackpot)
    - sinon : à quel point il s’en rapproche réellement (via distance_map)
    - un léger bonus à l’exploration et un malus aux collisions
    """
    position = env.start
    ind.has_collided = False
    ind.has_reached_end = False
    ind.path_positions = []

    if position is None:
        ind.fitness = float('-inf')
        return ind.fitness

    ind.path_positions.append(position)
    visited = {position}

    min_distance = env.get_distance_to_end(*position)
    ind.distance_record = min_distance
    path_length = 0
    ind.valid_moves = 0

    for m in ind.path_moves:
        new_pos = env.move(position, m)
        x, y = new_pos

        # Si mur → on arrête (collision)
        if not env.is_valid_move(x, y):
            ind.has_collided = True
            break

        position = new_pos
        path_length += 1
        ind.valid_moves = path_length
        ind.path_positions.append(position)
        visited.add(position)

        # Mise à jour de la meilleure distance atteinte
        d = env.get_distance_to_end(x, y)
        if d < min_distance:
            min_distance = d
            ind.distance_record = d

        if position == env.end:
            ind.has_reached_end = True
            break

    ind.current_position = position

    # ---------------------------
    # CAS 1 : l’individu a gagné
    # ---------------------------
    if ind.has_reached_end:
        used = max(1, path_length)
        optimal = env.optimal_path_length or used
        efficiency = optimal / used  # 1 = parfait

        ind.fitness = (
            1_000_000
            + 100_000 * efficiency
            + 100 * len(visited)
        )
        return ind.fitness

    # ---------------------------
    # CAS 2 : pas arrivé → score partiel
    # ---------------------------

    max_dist = env.max_distance_to_end or (env.width + env.height)

    if min_distance == float("inf"):
        min_distance = max_dist

    # Score de progression (plus on se rapproche de E, mieux c'est)
    progress = 1 - (min_distance / max_dist)
    progress = max(0, min(progress, 1))

    exploration = len(visited) / (env.width * env.height)
    collision_penalty = 0.3 if ind.has_collided else 0
    length_penalty = 0.001 * path_length

    ind.fitness = (
        progress * 10 +
        exploration * 5 -
        collision_penalty -
        length_penalty
    )

    return ind.fitness


# ============================================================
# 4. ALGORITHME GÉNÉTIQUE
# ============================================================

class GeneticAlgorithm:
    MOVES = ['H', 'B', 'G', 'D']

    def __init__(
        self,
        environment: Environment,
        population_size=200,
        mutation_rate=0.25,
        elitism_rate=0.3,
        tournament_size=5,
        max_generations=800
    ):
        self.env = environment
        self.population_size = population_size
        self.mutation_rate = mutation_rate
        self.elitism_rate = elitism_rate
        self.tournament_size = tournament_size
        self.max_generations = max_generations

        self.population: List[Individual] = []
        self.current_generation = 0
        self.best_overall: Optional[Individual] = None
        self.is_running = False

    # ------------------------------------------------------------
    # Outils : mouvements aléatoires + mouvement glouton
    # ------------------------------------------------------------

    def random_move(self):
        return random.choice(self.MOVES)

    def greedy_move(self, pos: Coord, greediness=0.8):
        """
        Mouvement glouton :
        - la plupart du temps je choisis le mouvement qui RAPPROCHE
          *réellement* de la sortie (via distance_map)
        - parfois je fais exprès un move aléatoire (pour éviter l'hyper-local)
        """
        if random.random() > greediness:
            return self.random_move()

        best = []
        best_dist = float("inf")

        for m in self.MOVES:
            nx, ny = self.env.move(pos, m)
            if not self.env.is_valid_move(nx, ny):
                continue

            d = self.env.get_distance_to_end(nx, ny)

            if d < best_dist:
                best = [m]
                best_dist = d
            elif d == best_dist:
                best.append(m)

        return random.choice(best) if best else self.random_move()

    def greedy_path(self, length, greediness=0.8):
        """
        Construit un chemin semi-glouton qui tend naturellement à suivre
        le bon couloir du labyrinthe.
        """
        if self.env.start is None:
            return [self.random_move() for _ in range(length)]

        pos = self.env.start
        moves = []

        for _ in range(length):
            m = self.greedy_move(pos, greediness)
            nx, ny = self.env.move(pos, m)
            if self.env.is_valid_move(nx, ny):
                pos = (nx, ny)
            moves.append(m)
            if pos == self.env.end:
                break

        # On complète si trop court
        while len(moves) < length:
            moves.append(self.random_move())

        return moves

    # ------------------------------------------------------------
    # Initialisation → 40% gloutons, 60% random
    # ------------------------------------------------------------

    def initialize_population(self):
        """
        Population initiale équilibrée :
        - une partie gloutonne (pour donner une direction générale)
        - une majorité aléatoire (pour la diversité)
        """
        self.population = []

        base_length = 40
        if self.env.optimal_path_length != float("inf"):
            base_length = max(25, int(self.env.optimal_path_length * 1.2))

        strategies = [
            (0.40, lambda: self.greedy_path(base_length, 0.85)),
            (0.60, lambda: [self.random_move() for _ in range(base_length)]),
        ]

        for ratio, strat in strategies:
            num = int(self.population_size * ratio)
            for _ in range(num):
                ind = Individual(strat())
                calculate_fitness(ind, self.env)
                self.population.append(ind)

        self.population.sort(key=lambda i: i.fitness, reverse=True)
        self.best_overall = self.population[0]

    # ------------------------------------------------------------
    # Sélection / Croisement / Mutation
    # ------------------------------------------------------------

    def tournament_selection(self):
        # Je prends k individus au hasard et garde le meilleur
        contenders = random.sample(self.population, self.tournament_size)
        return max(contenders, key=lambda x: x.fitness)

    def crossover(self, p1: Individual, p2: Individual):
        # Croisement en un point
        L = min(len(p1.path_moves), len(p2.path_moves))
        cut = random.randint(1, L-1)
        return Individual(p1.path_moves[:cut] + p2.path_moves[cut:])

    def mutate(self, ind: Individual):
        # Quelques mutations légères
        if random.random() < self.mutation_rate:
            num = max(1, len(ind.path_moves) // 20)
            for _ in range(num):
                i = random.randrange(len(ind.path_moves))
                ind.path_moves[i] = self.random_move()

    # ------------------------------------------------------------
    # Une génération de plus de l’AG
    # ------------------------------------------------------------

    def step_evolution(self):
        """Exécute une génération entière."""
        if not self.population:
            self.initialize_population()

        # Évaluation
        for ind in self.population:
            calculate_fitness(ind, self.env)

        # Tri + mise à jour du meilleur global
        self.population.sort(key=lambda i: i.fitness, reverse=True)
        if self.best_overall is None or self.population[0].fitness > self.best_overall.fitness:
            self.best_overall = self.population[0]

        self.current_generation += 1

        # Si on a trouvé la sortie → arrêt immédiat
        if self.best_overall.has_reached_end:
            return False

        # Si longueur max atteinte
        if self.current_generation >= self.max_generations:
            return False

        # Nouvelle population
        new_pop = []

        # Élites (on les garde tels quels)
        elite_count = int(self.elitism_rate * self.population_size)
        new_pop.extend(self.population[:elite_count])

        # Reproduction pour le reste
        while len(new_pop) < self.population_size:
            p1 = self.tournament_selection()
            p2 = self.tournament_selection()
            child = self.crossover(p1, p2)
            self.mutate(child)
            calculate_fitness(child, self.env)
            new_pop.append(child)

        self.population = new_pop
        return True


# ============================================================
# 5. INTERFACE TKINTER : affichage + boucle AG
# ============================================================

CELL_SIZE = 20


class MazeGUI:
    """
    Interface graphique :
    - affiche le labyrinthe
    - met à jour le chemin du meilleur individu
    - exécute plusieurs générations par frame pour aller plus vite
    """

    def __init__(self, root: tk.Tk, ga: GeneticAlgorithm, delay_ms=60):
        self.root = root
        self.ga = ga
        self.delay_ms = delay_ms

        root.title("Labyrinthe - Algorithme génétique")

        # Canvas où je dessine la grille + le chemin bleu
        self.canvas = tk.Canvas(
            root,
            width=ga.env.width * CELL_SIZE,
            height=ga.env.height * CELL_SIZE,
            bg="white"
        )
        self.canvas.pack()

        controls = tk.Frame(root)
        controls.pack()

        tk.Button(controls, text="Start", command=self.start).pack(side=tk.LEFT)
        tk.Button(controls, text="Pause", command=self.pause).pack(side=tk.LEFT)
        tk.Button(controls, text="Reset", command=self.reset).pack(side=tk.LEFT)

        self.info_label = tk.Label(root, text="Génération: 0 | Meilleure fitness: -inf")
        self.info_label.pack()

        self.running = False

        self.draw_grid()

    def start(self):
        self.running = True
        self.update_loop()

    def pause(self):
        self.running = False

    def reset(self):
        self.pause()
        self.ga.population = []
        self.ga.current_generation = 0
        self.ga.best_overall = None
        self.canvas.delete("all")
        self.draw_grid()
        self.info_label.config(text="Génération: 0 | Meilleure fitness: -inf")

    # ------------------------------------------------------------
    # Dessin de la grille
    # ------------------------------------------------------------
    def draw_grid(self):
        env = self.ga.env
        for y in range(env.height):
            for x in range(env.width):
                c = env.grid[y][x]
                color = (
                    "black" if c == '#'
                    else "green" if c == 'S'
                    else "red" if c == 'E'
                    else "white"
                )
                self.canvas.create_rectangle(
                    x * CELL_SIZE, y * CELL_SIZE,
                    (x+1)*CELL_SIZE, (y+1)*CELL_SIZE,
                    fill=color, outline="gray"
                )

    def draw_best_path(self):
        ind = self.ga.best_overall
        if not ind or not ind.path_positions:
            return

        for x, y in ind.path_positions:
            self.canvas.create_rectangle(
                x*CELL_SIZE+4, y*CELL_SIZE+4,
                (x+1)*CELL_SIZE-4, (y+1)*CELL_SIZE-4,
                fill="blue", outline=""
            )

    # ------------------------------------------------------------
    # Boucle principale d'animation
    # ------------------------------------------------------------
    def update_loop(self):
        if not self.running:
            return

        # Plusieurs générations d’un coup (accélère énormément)
        STEPS_PER_FRAME = 10
        cont = True
        for _ in range(STEPS_PER_FRAME):
            cont = self.ga.step_evolution()
            if not cont:
                break

        self.canvas.delete("all")
        self.draw_grid()
        self.draw_best_path()

        best = self.ga.best_overall
        self.info_label.config(
            text=f"Génération: {self.ga.current_generation} | Fitness: {best.fitness:.1f}"
        )

        if cont:
            self.root.after(self.delay_ms, self.update_loop)
        else:
            self.running = False


# ============================================================
# 6. GÉNÉRATEUR DFS DE LABYRINTHE
# ============================================================

class MazeGeneratorDFS:
    """
    Génère un labyrinthe parfait avec DFS (un seul chemin entre deux points).
    """

    def __init__(self, h: int, w: int):
        # Dimensions volontairement impaires pour garantir les couloirs
        self.height = h if h % 2 else h + 1
        self.width = w if w % 2 else w + 1

        # O = mur, . = chemin
        self.grid = [['O'] * self.width for _ in range(self.height)]
        self.visited = [[False] * self.width for _ in range(self.height)]

    def _is_valid(self, r, c):
        return (
            0 <= r < self.height and
            0 <= c < self.width and
            not self.visited[r][c]
        )

    def _generate_path(self, r, c):
        # Je marque la cellule comme visitée et la transforme en chemin
        self.visited[r][c] = True
        self.grid[r][c] = '.'

        # Les déplacements possibles dans un labyrinthe parfait
        dirs = [(0,-2),(0,2),(-2,0),(2,0)]
        random.shuffle(dirs)  # pour la variété

        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if self._is_valid(nr, nc):
                # Je casse le mur intermédiaire entre la case actuelle et la suivante
                self.grid[r + dr//2][c + dc//2] = '.'
                self._generate_path(nr, nc)

    def generate(self):
        # Je démarre en (1,1) pour rester dans la grille impaire
        self._generate_path(1, 1)

        # Départ et arrivée
        self.grid[0][0] = 'S'
        self.grid[self.height-1][self.width-1] = 'E'

        # Je m'assure qu'on peut sortir des deux
        for x, y in [(0,1),(1,0),(self.width-2,self.height-1),(self.width-1,self.height-2)]:
            if self.grid[y][x] == 'O':
                self.grid[y][x] = '.'

        # Conversion en chaînes
        return ["".join(row) for row in self.grid]


# ============================================================
# 7. MAIN
# ============================================================

def main():
    # Taille du labyrinthe généré
    maze_h = 25
    maze_w = 35

    # Je génère un labyrinthe complet via DFS
    generator = MazeGeneratorDFS(maze_h, maze_w)
    raw_grid = generator.generate()

    # Conversion O → # et . → ' ' pour l'affichage et l'AG
    grid = []
    for row in raw_grid:
        row = row.replace('O', '#').replace('.', ' ')
        grid.append(row)

    env = Environment(grid)

    ga = GeneticAlgorithm(
        env,
        population_size=200,
        mutation_rate=0.25,
        elitism_rate=0.3,
        tournament_size=5,
        max_generations=800
    )

    root = tk.Tk()
    MazeGUI(root, ga, delay_ms=60)
    root.mainloop()


if __name__ == "__main__":
    main()