import tkinter as tk
import math
import random


# Dimensions of the polar maze.
NUM_RINGS = 10           # Number of concentric circles (increasing this creates a deeper maze)
NUM_SECTORS = 24         # Number of angular divisions (must be >= 4 for a meaningful maze)
CANVAS_SIZE = 600        # Width/Height of the drawing canvas in pixels
MARGIN = 20              # Padding around the circular maze

# Each cell is identified by (ring, sector)
# We'll store whether each of its four "walls" exist:
#   'in'  -> wall between this ring and the ring below (toward center)
#   'out' -> wall between this ring and the ring above (toward outer edge)
#   'left'  / 'right' -> angular boundaries


def generate_polar_maze(rings, sectors):
    # Initialize all walls as present and mark cells as unvisited.
    maze = {}
    for r in range(rings):
        for s in range(sectors):
            maze[(r, s)] = {
                "visited": False,
                "in": True,
                "out": True,
                "left": True,
                "right": True
            }

    def neighbors(cell):
        r, s = cell
        nbs = []
        # inward neighbor
        if r > 0:
            nbs.append(((r - 1), s, "in"))
        # outward neighbor
        if r < rings - 1:
            nbs.append(((r + 1), s, "out"))
        # left/clockwise neighbor
        nbs.append((r, (s - 1) % sectors, "left"))
        # right / counterclockwise neighbor
        nbs.append((r, (s + 1) % sectors, "right"))
        return nbs

    # Carve maze using DFS
    stack = [(0, 0)]
    maze[(0, 0)]["visited"] = True
    while stack:
        cell = stack[-1]
        unvisited = []
        for nb_r, nb_s, direction in neighbors(cell):
            if not maze[(nb_r, nb_s)]["visited"]:
                unvisited.append((nb_r, nb_s, direction))

        if not unvisited:
            stack.pop()
        else:
            nb_r, nb_s, direction = random.choice(unvisited)
            # Knock down wall in the current cell and corresponding wall in neighbor
            if direction == "in":
                maze[(cell[0], cell[1])]["in"] = False
                maze[(nb_r, nb_s)]["out"] = False
            elif direction == "out":
                maze[(cell[0], cell[1])]["out"] = False
                maze[(nb_r, nb_s)]["in"] = False
            elif direction == "left":
                maze[(cell[0], cell[1])]["left"] = False
                maze[(nb_r, nb_s)]["right"] = False
            else:  # right
                maze[(cell[0], cell[1])]["right"] = False
                maze[(nb_r, nb_s)]["left"] = False

            maze[(nb_r, nb_s)]["visited"] = True
            stack.append((nb_r, nb_s))
    return maze


def draw_polar_maze(canvas, maze, rings, sectors):
    center = CANVAS_SIZE // 2
    radius_step = (CANVAS_SIZE // 2 - MARGIN) / rings

    for (r, s), walls in maze.items():
        r_inner = r * radius_step
        r_outer = (r + 1) * radius_step

        start_angle = (360 / sectors) * s
        end_angle = start_angle + (360 / sectors)

        # Inward wall
        if walls["in"]:
            canvas.create_arc(
                center - r_inner,
                center - r_inner,
                center + r_inner,
                center + r_inner,
                start=start_angle,
                extent=(360 / sectors),
                style=tk.ARC,
                width=2
            )

        # Outward wall
        if walls["out"]:
            canvas.create_arc(
                center - r_outer,
                center - r_outer,
                center + r_outer,
                center + r_outer,
                start=start_angle,
                extent=(360 / sectors),
                style=tk.ARC,
                width=2
            )

        # Left (clockwise) wall
        if walls["left"]:
            angle_rad = math.radians(start_angle)
            x0 = center + r_inner * math.cos(angle_rad)
            y0 = center - r_inner * math.sin(angle_rad)
            x1 = center + r_outer * math.cos(angle_rad)
            y1 = center - r_outer * math.sin(angle_rad)
            canvas.create_line(x0, y0, x1, y1, width=2)

        # Right (counterclockwise) wall
        if walls["right"]:
            angle_rad = math.radians(end_angle)
            x0 = center + r_inner * math.cos(angle_rad)
            y0 = center - r_inner * math.sin(angle_rad)
            x1 = center + r_outer * math.cos(angle_rad)
            y1 = center - r_outer * math.sin(angle_rad)
            canvas.create_line(x0, y0, x1, y1, width=2)


def main():
    root = tk.Tk()
    root.title("Circular Maze")

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

    maze = generate_polar_maze(NUM_RINGS, NUM_SECTORS)
    draw_polar_maze(canvas, maze, NUM_RINGS, NUM_SECTORS)

    root.mainloop()


if __name__ == "__main__":
    main()