import tkinter as tk
import math
import random

# --- Configuration Constants ---
CANVAS_SIZE = 800
RINGS = 15  # Number of concentric rings in the maze
WALL_COLOR = "#1a237e"
PATH_COLOR = "#e8eaf6"
PLAYER_COLOR = "#ff5252"
WIN_COLOR = "#4caf50"
WALL_THICKNESS = 2

class CircularMaze:
    """
    This class handles the generation and drawing of the circular maze structure.
    It uses a recursive backtracking algorithm adapted for a polar grid.
    """
    def __init__(self, rings):
        self.rings = rings
        self.grid = []
        self._setup_grid()
        self._generate_maze()

    def _setup_grid(self):
        """Initializes the grid data structure for the maze."""
        # The center is a single cell, ring 0
        self.grid.append([{'N': True, 'E': True, 'S': True, 'W': True, 'visited': False}])

        for r in range(1, self.rings + 1):
            # The number of cells in a ring increases as it gets larger
            num_cells = self._get_cells_in_ring(r)
            ring_cells = [{'N': True, 'E': True, 'S': True, 'W': True, 'visited': False} for _ in range(num_cells)]
            self.grid.append(ring_cells)

    def _get_cells_in_ring(self, r):
        """Calculates the number of cells for a given ring."""
        # A simple formula to increase cells in outer rings
        return int(r * 4 * 1.5) if r > 0 else 1

    def _generate_maze(self):
        """
        Generates the maze paths using a randomized depth-first search
        (recursive backtracking) algorithm.
        """
        stack = [(0, 0)]  # Start at the center cell (ring 0, cell 0)
        self.grid[0][0]['visited'] = True

        while stack:
            r, c = stack[-1]
            neighbors = self._get_unvisited_neighbors(r, c)

            if neighbors:
                nr, nc, direction = random.choice(neighbors)

                # Carve a path between the current cell and the neighbor
                self._remove_wall((r, c), (nr, nc), direction)

                self.grid[nr][nc]['visited'] = True
                stack.append((nr, nc))
            else:
                # Backtrack
                stack.pop()

        # Create an exit at the top of the outermost ring
        exit_cell_index = len(self.grid[self.rings]) // 4
        self.grid[self.rings][exit_cell_index]['N'] = False


    def _get_unvisited_neighbors(self, r, c):
        """Finds all valid, unvisited neighbors for a given cell."""
        neighbors = []
        num_cells_current = self._get_cells_in_ring(r)

        # Clockwise neighbor (East)
        east_c = (c + 1) % num_cells_current
        if not self.grid[r][east_c]['visited']:
            neighbors.append((r, east_c, 'E'))

        # Counter-clockwise neighbor (West)
        west_c = (c - 1 + num_cells_current) % num_cells_current
        if not self.grid[r][west_c]['visited']:
            neighbors.append((r, west_c, 'W'))

        # Outward neighbor (South)
        if r + 1 <= self.rings:
            num_cells_outer = self._get_cells_in_ring(r + 1)
            # Find the corresponding cell in the outer ring
            ratio = num_cells_outer / num_cells_current
            for i in range(math.floor(ratio * c), math.floor(ratio * (c + 1))):
                 if not self.grid[r + 1][i]['visited']:
                    neighbors.append((r + 1, i, 'S'))

        # Inward neighbor (North)
        if r - 1 >= 0:
            num_cells_inner = self._get_cells_in_ring(r - 1)
            # Find the corresponding cell in the inner ring
            ratio = num_cells_current / num_cells_inner
            north_c = int(c // ratio)
            if not self.grid[r - 1][north_c]['visited']:
                neighbors.append((r - 1, north_c, 'N'))

        return neighbors

    def _remove_wall(self, cell1, cell2, direction):
        """Removes the wall between two adjacent cells."""
        r1, c1 = cell1
        r2, c2 = cell2

        if direction == 'E': # Moving Clockwise
            self.grid[r1][c1]['E'] = False
            self.grid[r2][c2]['W'] = False
        elif direction == 'W': # Moving Counter-Clockwise
            self.grid[r1][c1]['W'] = False
            self.grid[r2][c2]['E'] = False
        elif direction == 'S': # Moving Outward
            self.grid[r1][c1]['S'] = False
            self.grid[r2][c2]['N'] = False
        elif direction == 'N': # Moving Inward
            self.grid[r1][c1]['N'] = False
            self.grid[r2][c2]['S'] = False

    def draw(self, canvas):
        """Draws the entire maze on the tkinter canvas."""
        canvas.delete("all")
        canvas.create_rectangle(0, 0, CANVAS_SIZE, CANVAS_SIZE, fill=PATH_COLOR, outline="")

        center_x, center_y = CANVAS_SIZE / 2, CANVAS_SIZE / 2
        ring_width = (CANVAS_SIZE / 2) / (self.rings + 1)

        # Draw walls for each cell
        for r in range(1, self.rings + 1):
            num_cells = self._get_cells_in_ring(r)
            radius_inner = r * ring_width
            radius_outer = (r + 1) * ring_width

            for c in range(num_cells):
                angle_start = (c / num_cells) * 360
                angle_extent = (1 / num_cells) * 360

                # Draw clockwise wall (radial line)
                if self.grid[r][c]['E']:
                    x1 = center_x + radius_inner * math.cos(math.radians(angle_start + angle_extent))
                    y1 = center_y + radius_inner * math.sin(math.radians(angle_start + angle_extent))
                    x2 = center_x + radius_outer * math.cos(math.radians(angle_start + angle_extent))
                    y2 = center_y + radius_outer * math.sin(math.radians(angle_start + angle_extent))
                    canvas.create_line(x1, y1, x2, y2, fill=WALL_COLOR, width=WALL_THICKNESS)

                # Draw outward wall (arc)
                if self.grid[r][c]['S']:
                    # Tkinter's arc bounding box is defined by top-left and bottom-right corners
                    x0 = center_x - radius_outer
                    y0 = center_y - radius_outer
                    x1 = center_x + radius_outer
                    y1 = center_y + radius_outer
                    canvas.create_arc(x0, y0, x1, y1, start=angle_start, extent=angle_extent,
                                      style=tk.ARC, outline=WALL_COLOR, width=WALL_THICKNESS)

        # Draw the outermost boundary
        final_radius = (self.rings + 1) * ring_width
        x0 = center_x - final_radius
        y0 = center_y - final_radius
        x1 = center_x + final_radius
        y1 = center_y + final_radius

        exit_cell_index = len(self.grid[self.rings]) // 4
        num_cells_outer = self._get_cells_in_ring(self.rings)
        angle_start = (exit_cell_index / num_cells_outer) * 360
        angle_extent = (1 / num_cells_outer) * 360

        # Draw the boundary in two parts to leave an opening for the exit
        canvas.create_arc(x0, y0, x1, y1, start=angle_start + angle_extent, extent=360-angle_extent,
                          style=tk.ARC, outline=WALL_COLOR, width=WALL_THICKNESS * 2)


class Player:
    """Represents the player, handling movement, drawing, and win conditions."""
    def __init__(self, canvas, maze):
        self.canvas = canvas
        self.maze = maze
        self.r = 0  # Start at ring 0
        self.c = 0  # Start at cell 0
        self.player_obj = None
        self.has_won = False
        self.draw()

    def get_cell_center(self):
        """Calculates the pixel coordinates for the center of the player's current cell."""
        center_x, center_y = CANVAS_SIZE / 2, CANVAS_SIZE / 2
        ring_width = (CANVAS_SIZE / 2) / (self.maze.rings + 1)

        if self.r == 0:
            return center_x, center_y

        num_cells = self.maze._get_cells_in_ring(self.r)

        # Angle to the middle of the cell
        angle = ((self.c + 0.5) / num_cells) * 2 * math.pi

        # Radius to the middle of the ring
        radius = (self.r + 0.5) * ring_width

        x = center_x + radius * math.cos(angle)
        y = center_y + radius * math.sin(angle)
        return x, y

    def draw(self):
        """Draws or moves the player's icon on the canvas."""
        if self.player_obj:
            self.canvas.delete(self.player_obj)

        x, y = self.get_cell_center()
        ring_width = (CANVAS_SIZE / 2) / (self.maze.rings + 1)
        # Scale player size with the ring width
        player_radius = ring_width / 4

        self.player_obj = self.canvas.create_oval(
            x - player_radius, y - player_radius,
            x + player_radius, y + player_radius,
            fill=PLAYER_COLOR, outline=""
        )

    def move(self, event):
        """Handles key press events for player movement."""
        if self.has_won:
            return

        direction = event.keysym
        current_cell = self.maze.grid[self.r][self.c]

        moved = False
        # --- Movement Logic ---
        if direction == "Up": # Move Inward
            if not current_cell['N']:
                num_cells_current = self.maze._get_cells_in_ring(self.r)
                num_cells_inner = self.maze._get_cells_in_ring(self.r - 1)
                ratio = num_cells_current / num_cells_inner
                self.r -= 1
                self.c = int(self.c // ratio)
                moved = True
        elif direction == "Down": # Move Outward
            if not current_cell['S']:
                num_cells_current = self.maze._get_cells_in_ring(self.r)
                num_cells_outer = self.maze._get_cells_in_ring(self.r + 1)
                ratio = num_cells_outer / num_cells_current
                # This is a simplification; find a cell that shares a border
                # For this generation, any cell within the ratio range is a valid path
                self.r += 1
                self.c = int(self.c * ratio) + random.randint(0, int(ratio-1))
                moved = True
        elif direction == "Left": # Move Counter-Clockwise
            if not current_cell['W']:
                num_cells = self.maze._get_cells_in_ring(self.r)
                self.c = (self.c - 1 + num_cells) % num_cells
                moved = True
        elif direction == "Right": # Move Clockwise
            if not current_cell['E']:
                num_cells = self.maze._get_cells_in_ring(self.r)
                self.c = (self.c + 1) % num_cells
                moved = True

        if moved:
            self.draw()
            self.check_win()

    def check_win(self):
        """Checks if the player has reached the exit and displays a win message."""
        exit_cell_index = len(self.maze.grid[self.maze.rings]) // 4
        if self.r == self.maze.rings and self.c == exit_cell_index:
            self.has_won = True
            self.canvas.create_text(
                CANVAS_SIZE / 2, CANVAS_SIZE / 2,
                text="You Win!",
                font=("Helvetica", 60, "bold"),
                fill=WIN_COLOR
            )

def main():
    """Main function to set up the game window and start the application."""
    root = tk.Tk()
    root.title("Circular Maze")

    canvas = tk.Canvas(root, width=CANVAS_SIZE, height=CANVAS_SIZE, bg=PATH_COLOR)
    canvas.pack()

    # Generate and draw the maze
    maze = CircularMaze(RINGS)
    maze.draw(canvas)

    # Create the player
    player = Player(canvas, maze)

    # Bind arrow keys to player movement
    root.bind("<KeyPress>", player.move)

    # Center the window
    root.update_idletasks()
    width = root.winfo_width()
    height = root.winfo_height()
    x = (root.winfo_screenwidth() // 2) - (width // 2)
    y = (root.winfo_screenheight() // 2) - (height // 2)
    root.geometry('{}x{}+{}+{}'.format(width, height, x, y))

    root.mainloop()

if __name__ == "__main__":
    main()