"""
Demonstration Vibe-Coding:
Klicke wiederholt irgendwo auf die schwarze Fläche.
"""

import random
import turtle
from collections import deque

# --------------------------------------------------
# Einstellungen
# --------------------------------------------------

STEP = 12
DELAY = 8
STEPS_PER_FRAME = 3

WIDTH = 700
HEIGHT = 500

# Je kleiner, desto häufiger biegt die Turtle ab.
MIN_RUN = 1
MAX_RUN = 6

# Wahrscheinlichkeit für einen kurzen Umweg.
DETOUR_CHANCE = 0.38

# Größe des lokalen Planungsbereichs um Start und Ziel.
PADDING = 9


# --------------------------------------------------
# Turtle
# --------------------------------------------------

print("Klicke wiederholt irgendwo auf die schwarze Fläche.")
screen = turtle.Screen()
screen.setup(WIDTH, HEIGHT)
screen.bgcolor("white")
screen.title("Dichter Labyrinthweg – Klick zum Bewegen, Q zum Beenden")
screen.tracer(0, 0)

runner = turtle.Turtle()
runner.shape("turtle")
runner.color("#009ee3")
runner.pensize(2)
runner.speed(0)
runner.penup()
runner.goto(0, 0)
runner.pendown()

MAX_X = WIDTH // (2 * STEP) - 2
MAX_Y = HEIGHT // (2 * STEP) - 2

current = (0, 0)
visited = {current}

route = []
moving = False
pending_target = None

last_direction = None
run_length = 0


# --------------------------------------------------
# Rasterfunktionen
# --------------------------------------------------

DIRECTIONS = (
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
)


def add(a, b):
    return a[0] + b[0], a[1] + b[1]


def direction(a, b):
    return b[0] - a[0], b[1] - a[1]


def opposite(d):
    return -d[0], -d[1]


def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def grid_to_screen(cell):
    return cell[0] * STEP, cell[1] * STEP


def screen_to_grid(x, y):
    gx = round(x / STEP)
    gy = round(y / STEP)

    gx = max(-MAX_X, min(MAX_X, gx))
    gy = max(-MAX_Y, min(MAX_Y, gy))

    return gx, gy


def make_area(start, target):
    """
    Erzeugt einen lokalen rechteckigen Arbeitsbereich.

    Dadurch bleibt der Weg kompakt und verteilt sich nicht über
    die ganze Zeichenfläche.
    """
    min_x = max(-MAX_X, min(start[0], target[0]) - PADDING)
    max_x = min(MAX_X, max(start[0], target[0]) + PADDING)

    min_y = max(-MAX_Y, min(start[1], target[1]) - PADDING)
    max_y = min(MAX_Y, max(start[1], target[1]) + PADDING)

    return {
        (x, y)
        for x in range(min_x, max_x + 1)
        for y in range(min_y, max_y + 1)
    }


def neighbors(cell, area):
    for d in DIRECTIONS:
        next_cell = add(cell, d)

        if next_cell in area:
            yield next_cell


def boundary_cells(area):
    """Alle Zellen am Außenrand des Arbeitsbereichs."""
    result = set()

    for cell in area:
        x, y = cell

        for dx, dy in DIRECTIONS:
            if (x + dx, y + dy) not in area:
                result.add(cell)
                break

    return result


# --------------------------------------------------
# Hohlraumprüfung
# --------------------------------------------------

def free_cells_reach_boundary(area, blocked, position):
    """
    Prüft, ob jede freie Zelle noch mit dem Außenrand verbunden ist.

    Dadurch kann die Linie keinen vollständig eingeschlossenen
    Hohlraum erzeugen.
    """
    free = area - blocked

    if not free:
        return True

    boundary = boundary_cells(area) & free

    if not boundary:
        return False

    reachable = set(boundary)
    queue = deque(boundary)

    while queue:
        cell = queue.popleft()

        for neighbor in neighbors(cell, area):
            if neighbor in free and neighbor not in reachable:
                reachable.add(neighbor)
                queue.append(neighbor)

    return reachable == free


def safe_step(cell, area, temporary_visited):
    if cell in temporary_visited:
        return False

    blocked = temporary_visited | {cell}

    return free_cells_reach_boundary(
        area,
        blocked,
        cell,
    )


# --------------------------------------------------
# Weg zum Ziel suchen
# --------------------------------------------------

def shortest_path(start, target, area, blocked):
    """
    Sucht einen einfachen Restweg zum Ziel.
    """
    queue = deque([start])
    previous = {start: None}

    while queue:
        cell = queue.popleft()

        if cell == target:
            path = []

            while cell is not None:
                path.append(cell)
                cell = previous[cell]

            path.reverse()
            return path

        candidates = list(neighbors(cell, area))
        random.shuffle(candidates)

        for next_cell in candidates:
            if next_cell in previous:
                continue

            if next_cell in blocked and next_cell != target:
                continue

            previous[next_cell] = cell
            queue.append(next_cell)

    return None


# --------------------------------------------------
# Verschnörkelten Weg planen
# --------------------------------------------------

def choose_candidate(
    position,
    target,
    area,
    temporary_visited,
    current_direction,
    current_run,
):
    candidates = []

    for cell in neighbors(position, area):
        if not safe_step(cell, area, temporary_visited):
            continue

        new_direction = direction(position, cell)
        distance = manhattan(cell, target)

        score = distance * 1.2

        # Häufige Kurven bevorzugen.
        if current_direction is not None:
            if new_direction == current_direction:
                score += 3.5
            else:
                score -= 2.5

            # Nicht sofort zurücklaufen.
            if new_direction == opposite(current_direction):
                score += 100

        # Lange Geraden deutlich bestrafen.
        if current_run >= MAX_RUN and new_direction == current_direction:
            score += 100

        # Sehr kurze Geraden nicht immer sofort abbrechen.
        if current_run < MIN_RUN and new_direction != current_direction:
            score += 2

        # Zellen mit wenig freien Nachbarn früh verbrauchen.
        free_neighbors = sum(
            neighbor not in temporary_visited
            for neighbor in neighbors(cell, area)
        )

        score += free_neighbors * 0.5

        # Zufall erzeugt organischere Formen.
        score += random.uniform(-3.0, 3.0)

        # Gelegentlich Entfernung zum Ziel weniger wichtig nehmen.
        if random.random() < DETOUR_CHANCE:
            score -= distance * 0.8

        candidates.append((score, cell))

    if not candidates:
        return None

    candidates.sort(key=lambda item: item[0])
    return candidates[0][1]


def plan_route(start, target):
    """
    Plant zuerst einen verschnörkelten Teil und sucht anschließend
    einen sicheren Restweg zum Ziel.
    """
    area = make_area(start, target)

    temporary_visited = set(visited)
    temporary_visited.add(start)

    path = [start]
    position = start

    current_direction = None
    current_run = 0

    direct_distance = manhattan(start, target)

    # Länge des Umwegs abhängig von der direkten Entfernung.
    desired_steps = max(
        direct_distance + 12,
        int(direct_distance * 2.2),
    )

    max_steps = min(
        desired_steps,
        len(area) // 2,
    )

    for _ in range(max_steps):
        # Regelmäßig prüfen, ob das Ziel noch erreichbar ist.
        rest = shortest_path(
            position,
            target,
            area,
            temporary_visited,
        )

        if rest is None:
            break

        # Nahe am gewünschten Ende den Restweg verwenden.
        if len(path) >= desired_steps:
            path.extend(rest[1:])
            return path

        next_cell = choose_candidate(
            position,
            target,
            area,
            temporary_visited,
            current_direction,
            current_run,
        )

        if next_cell is None:
            break

        new_direction = direction(position, next_cell)

        if new_direction == current_direction:
            current_run += 1
        else:
            current_direction = new_direction
            current_run = 1

        position = next_cell
        temporary_visited.add(position)
        path.append(position)

        if position == target:
            return path

    rest = shortest_path(
        position,
        target,
        area,
        temporary_visited,
    )

    if rest:
        path.extend(rest[1:])
        return path

    return None


# --------------------------------------------------
# Animation
# --------------------------------------------------

HEADINGS = {
    (1, 0): 0,
    (0, 1): 90,
    (-1, 0): 180,
    (0, -1): 270,
}


def animate():
    global current
    global moving
    global pending_target

    completed = 0

    while route and completed < STEPS_PER_FRAME:
        next_cell = route.pop(0)

        move_direction = direction(current, next_cell)
        runner.setheading(HEADINGS[move_direction])
        runner.goto(grid_to_screen(next_cell))

        current = next_cell
        visited.add(current)
        completed += 1

    screen.update()

    if route:
        screen.ontimer(animate, DELAY)
        return

    moving = False

    if pending_target is not None:
        next_target = pending_target
        pending_target = None
        start_route(next_target)


def start_route(target):
    global route
    global moving

    if target == current:
        return

    if target in visited:
        print("Der Zielpunkt wurde bereits betreten.")
        return

    planned = plan_route(current, target)

    if not planned:
        print("Es wurde kein freier Weg zum Ziel gefunden.")
        return

    planned = planned[1:]

    if any(cell in visited for cell in planned):
        print("Der geplante Weg würde eine alte Linie berühren.")
        return

    route = planned
    moving = True
    animate()


# --------------------------------------------------
# Eingabe
# --------------------------------------------------

def clicked(x, y):
    global pending_target

    target = screen_to_grid(x, y)

    if moving:
        pending_target = target
    else:
        start_route(target)


def quit_program():
    try:
        screen.bye()
    except turtle.Terminator:
        pass


screen.onclick(clicked)

screen.listen()
screen.onkey(quit_program, "q")
screen.onkey(quit_program, "Q")
screen.onkey(quit_program, "Escape")

screen.update()
screen.mainloop()