# DFS: Depth First Search
import random
import tkinter as tk
import json

class MazeGenerator:
    def __init__(self, width=10, height=10 ):
        self.width = width
        self.height = height
        self.generate_maze(width // 2)  # Use integer division for size
        self.window = tk.Tk()
        self.window.title("Maze")
        self.canvas = tk.Canvas(self.window, width=(self.width+1)*10, height=(self.height+1)*10)
        self.canvas.pack()
        self.arrival_point = (self.width - 1, self.height - 1)  # Set the arrival point near the bottom-right corner
        self.backtrack = []


    def generate_maze(self, size):
        # Initialize the maze with walls (True)
        self.maze = [[True for _ in range(size * 2 + 1)] for _ in range(size * 2 + 1)]
        
        # Define the directions (W, E, S, N)
        self.directions = [(-2, 0), (2, 0), (0, 2), (0, -2)]
        
        # Start from the upper-left cell
        start_x, start_y = (1, 1)
        self.maze[start_x][start_y] = False
        self.stack = [(start_x, start_y)]

    def stack_iteration(self):
        if not self.stack:  # Check if the stack is empty
            return
        
        current_x, current_y = self.stack[-1]

        # Function to get the unvisited neighbors
        def get_unvisited_neighbors(x, y):
            neighbors = []
            if not (self.arrival_point == (x,y)):
                for dx, dy in self.directions:
                    nx, ny = x + dx, y + dy
                    if 1 <= nx < len(self.maze) - 1 and 1 <= ny < len(self.maze[0]) - 1 and self.maze[nx][ny]:
                        neighbors.append((nx, ny))
            return neighbors

        neighbors = get_unvisited_neighbors(current_x, current_y)
        
        if neighbors:
            # Choose a random unvisited neighbor
            chosen_x, chosen_y = random.choice(neighbors)
            
            # Remove the wall between the current cell and the chosen cell
            self.maze[(current_x + chosen_x) // 2][(current_y + chosen_y) // 2] = False
            
            # Mark the chosen cell as visited
            self.maze[chosen_x][chosen_y] = False
            
            # Push the chosen cell to the stack
            self.stack.append((chosen_x, chosen_y))
        else:
            # Backtrack if no unvisited neighbors are found
            self.backtrack.append(self.stack.pop())

    def update_maze(self):
        self.stack_iteration()
        self.draw_maze()
        if self.stack:  # Continue updating only if there are cells left to visit
            self.window.after(10, self.update_maze)
        else:
            # After the maze is generated, remove some walls randomly
            for _ in range(int(self.width * self.height * 0.1)):  # Remove 10% of the total cells as walls
                x = random.randint(1, self.width - 2)
                y = random.randint(1, self.height - 2)
                self.maze[x][y] = False
            self.draw_maze()
            with open('maze.json', 'w') as json_file:
                json.dump(self.maze, json_file) 


    def draw_maze(self):
        self.canvas.delete("all")
        for i in range(len(self.maze)):
            for j in range(len(self.maze[i])):
                color = "black" if self.maze[i][j] else "white"
                # if (i, j) in self.backtrack:
                #     color="yellow"
                if (i, j) == self.arrival_point:
                    color = "green"  # Color the arrival point green
                elif (i, j) == (1 ,1):
                    color = "red"  # Color the arrival point green
                elif self.stack and (i, j) == self.stack[-1]:
                    color = "blue"  # Color the current position blue
                self.canvas.create_rectangle(j*10, i*10, (j+1)*10, (i+1)*10, fill=color)


    def run(self):
        self.update_maze()
        self.window.mainloop()

# Crea e avvia il generatore di labirinti
generator = MazeGenerator(20, 20)
generator.run()