backend/game/map_compiler.py

"""
Compile walkable polygons into a single figure: one exterior boundary + holes (internal non-walkable zones).
Produces compiled_map.json used by pathfinding for walkable test and optional nav points.
"""

from __future__ import annotations

import json
from pathlib import Path


def _signed_area(polygon: list[tuple[float, float]]) -> float:
    """Signed area (positive = CCW)."""
    n = len(polygon)
    if n < 3:
        return 0.0
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += polygon[i][0] * polygon[j][1]
        area -= polygon[j][0] * polygon[i][1]
    return area / 2.0


def _centroid(polygon: list[tuple[float, float]]) -> tuple[float, float]:
    n = len(polygon)
    if n == 0:
        return (0.0, 0.0)
    cx = sum(p[0] for p in polygon) / n
    cy = sum(p[1] for p in polygon) / n
    return (cx, cy)


def _point_in_polygon(x: float, y: float, polygon: list[tuple[float, float]]) -> bool:
    n = len(polygon)
    inside = False
    j = n - 1
    for i in range(n):
        xi, yi = polygon[i]
        xj, yj = polygon[j]
        if ((yi > y) != (yj > y)) and (x < (xj - xi) * (y - yi) / (yj - yi) + xi):
            inside = not inside
        j = i
    return inside


def compile_walkable(
    polygons: list[list[tuple[float, float]]],
) -> tuple[list[tuple[float, float]], list[list[tuple[float, float]]]]:
    """
    From a list of polygons (each list of (x,y) in 0-100 space),
    return (exterior, holes).
    Exterior = polygon with largest absolute area.
    Holes = polygons whose centroid is inside the exterior.
    """
    if not polygons:
        return ([], [])

    # Filter to valid polygons
    valid = [p for p in polygons if len(p) >= 3]
    if not valid:
        return ([], [])

    # Exterior = largest area
    by_area = [(abs(_signed_area(p)), p) for p in valid]
    by_area.sort(key=lambda x: -x[0])
    exterior = by_area[0][1]
    others = [p for _, p in by_area[1:]]

    holes: list[list[tuple[float, float]]] = []
    for poly in others:
        cx, cy = _centroid(poly)
        if _point_in_polygon(cx, cy, exterior):
            holes.append(poly)

    return (exterior, holes)


def build_nav_points(
    polygons: list[list[tuple[float, float]]],
    scale_x: float,
    scale_y: float,
    step: float = 2.0,
) -> list[list[float]]:
    """
    Generate navigation points (in game coordinates) for ALL walkable polygons.
    Used for pathfinding graph: units can path between these points.
    """
    if not polygons:
        return []

    all_xs = [p[0] for poly in polygons for p in poly]
    all_ys = [p[1] for poly in polygons for p in poly]
    min_x, max_x = min(all_xs), max(all_xs)
    min_y, max_y = min(all_ys), max(all_ys)

    def is_walkable_100(x: float, y: float) -> bool:
        return any(_point_in_polygon(x, y, poly) for poly in polygons)

    points: list[list[float]] = []
    x = min_x
    while x <= max_x:
        y = min_y
        while y <= max_y:
            if is_walkable_100(x, y):
                points.append([x * scale_x / 100.0, y * scale_y / 100.0])
            y += step
        x += step
    return points


def run_compiler(
    walkable_path: Path,
    output_path: Path,
    map_width: float = 80.0,
    map_height: float = 80.0,
    nav_step: float = 1.5,
) -> None:
    """Load walkable.json, compile to exterior + holes, write compiled_map.json."""
    scale_x = map_width / 100.0
    scale_y = map_height / 100.0

    if not walkable_path.exists():
        raise FileNotFoundError(f"Walkable file not found: {walkable_path}")

    with open(walkable_path, encoding="utf-8") as f:
        data = json.load(f)

    raw = data.get("polygons", [])
    if not raw and data.get("polygon"):
        raw = [data["polygon"]]

    polygons: list[list[tuple[float, float]]] = []
    for poly in raw:
        if len(poly) < 3:
            continue
        polygons.append([(float(p[0]), float(p[1])) for p in poly])

    exterior, holes = compile_walkable(polygons)

    nav_points_game = build_nav_points(polygons, map_width, map_height, step=nav_step)

    out = {
        "exterior": [[round(x, 4), round(y, 4)] for x, y in exterior],
        "holes": [[[round(x, 4), round(y, 4)] for x, y in h] for h in holes],
        "nav_points": [[round(x, 4), round(y, 4)] for x, y in nav_points_game],
        # All walkable zones in 0-100 space (for visualization and multi-zone support)
        "walkable_zones": [[[round(p[0], 4), round(p[1], 4)] for p in poly] for poly in polygons],
    }
    with open(output_path, "w", encoding="utf-8") as f:
        json.dump(out, f, indent=2)


if __name__ == "__main__":
    static_dir = Path(__file__).resolve().parent.parent / "static"
    run_compiler(
        static_dir / "walkable.json",
        static_dir / "compiled_map.json",
    )