pathfinder.py

"""
Circle-WFC Pathfinder

원주 기반 제약 충족 경로 탐색 알고리즘 메인 클래스
"""

from typing import List, Tuple, Optional, Set
from collections import deque

try:
    from .grid import Grid, Tile, TileState
    from .wfc import WFCEngine
    from .circle_layer import CircleLayer, Point, calculate_optimal_layers
    from .constraints import ConstraintManager, BasicRoadConstraint, PathConstraint
except ImportError:
    from grid import Grid, Tile, TileState
    from wfc import WFCEngine
    from circle_layer import CircleLayer, Point, calculate_optimal_layers
    from constraints import ConstraintManager, BasicRoadConstraint, PathConstraint


# 방향 상수 (리팩토링: 중복 제거)
DIRECTIONS_4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 4방향 (상하좌우)
DIRECTIONS_8 = DIRECTIONS_4 + [(1, 1), (1, -1), (-1, 1), (-1, -1)]  # 8방향 (대각선 포함)


class CircleWFC:
    """Circle-WFC 경로 탐색기

    중간 원주에서 시작하여 양방향으로 붕괴하며 경로 탐색
    """

    def __init__(self, grid: Grid, num_layers: Optional[int] = None):
        """
        Args:
            grid: 탐색할 그리드
            num_layers: 레이어 수 (None이면 자동 계산)
        """
        self.grid = grid
        self.num_layers = num_layers
        self.wfc_engine: Optional[WFCEngine] = None
        self.circle_layer: Optional[CircleLayer] = None
        self.path: List[Tuple[int, int]] = []

        # 동적 복잡도 추적
        self.contradiction_count = 0  # 모순 발생 횟수
        self.collapse_count = 0  # 총 붕괴 시도 횟수
        self.expansion_count = 0  # 터널 확장 횟수 (복잡도 지표)

    def find(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int],
        num_layers: Optional[int] = None
    ) -> List[Tuple[int, int]]:
        """경로 탐색

        Args:
            start: 시작점 (x, y)
            end: 끝점 (x, y)
            num_layers: 레이어 수 (None이면 자동)

        Returns:
            경로 좌표 리스트 [(x1, y1), (x2, y2), ...]
        """
        # 복잡도 추적 카운터 초기화
        self.contradiction_count = 0
        self.collapse_count = 0
        self.expansion_count = 0

        # 레이어 수 결정
        if num_layers is None:
            if self.num_layers is None:
                distance = ((end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2) ** 0.5
                num_layers = calculate_optimal_layers(distance)
            else:
                num_layers = self.num_layers

        # 원주 레이어 생성
        self.circle_layer = CircleLayer(start, end, num_layers)

        # 제약 조건 설정
        constraints = ConstraintManager()
        constraints.add(BasicRoadConstraint())
        constraints.add(PathConstraint(prefer_road=True))

        # WFC 엔진 생성 (대각선 지원 명시)
        self.wfc_engine = WFCEngine(self.grid, constraints, allow_diagonal=True)

        # 시작점과 끝점을 도로로 고정
        self.wfc_engine.collapse_at(start[0], start[1], TileState.ROAD)
        self.wfc_engine.collapse_at(end[0], end[1], TileState.ROAD)

        # 1. Bresenham 직선 힌트 제공
        line_points = self._bresenham_line(start[0], start[1], end[0], end[1])
        line_blocked = False
        line_hints = 0
        for x, y in line_points:
            if (x, y) == start or (x, y) == end:
                continue
            if 0 <= x < self.grid.width and 0 <= y < self.grid.height:
                tile = self.grid.get(x, y)
                if tile and tile.can_be_road() and not tile.is_collapsed:
                    self.wfc_engine.collapse_at(x, y, TileState.ROAD)
                    line_hints += 1
                elif tile and not tile.can_be_road():
                    line_blocked = True

        # 1-1. 직선이 막혔어도 WFC propagation이 알아서 우회 경로 찾음
        # (순수 WFC 방식: BFS detour 사용 안 함)

        # 2. Circle 교점 힌트 + 교점 간 연결 (미로 해결 핵심)
        waypoints = [start]  # 시작점부터

        if self.circle_layer:
            intersection_order = self.circle_layer.get_intersection_order_from_middle()
            for idx in intersection_order:
                if idx < len(self.circle_layer.intersection_points):
                    points = self.circle_layer.intersection_points[idx]
                    if points:
                        # 첫 번째 교점만 사용 (waypoint로)
                        grid_coord = points[0].to_grid()
                        x, y = grid_coord
                        if 0 <= x < self.grid.width and 0 <= y < self.grid.height:
                            tile = self.grid.get(x, y)
                            if tile and tile.can_be_road():
                                waypoints.append((x, y))

        waypoints.append(end)  # 끝점 추가

        # Waypoint 사이를 연결 (Bresenham 또는 BFS detour)
        for i in range(len(waypoints) - 1):
            p1 = waypoints[i]
            p2 = waypoints[i + 1]

            # 먼저 직선 시도
            segment = self._bresenham_line(p1[0], p1[1], p2[0], p2[1])
            can_use_line = all(
                self.grid.get(x, y) and self.grid.get(x, y).can_be_road()
                for x, y in segment
                if 0 <= x < self.grid.width and 0 <= y < self.grid.height
            )

            # 직선 가능하면 힌트로 제공 (막혔어도 WFC가 알아서 우회)
            if can_use_line:
                for x, y in segment:
                    if 0 <= x < self.grid.width and 0 <= y < self.grid.height:
                        tile = self.grid.get(x, y)
                        if tile and tile.can_be_road() and not tile.is_collapsed:
                            self.wfc_engine.collapse_at(x, y, TileState.ROAD)
            # 직선이 막혔어도 BFS 우회 경로 사용 안 함 (순수 WFC 방식)

        # 3. 계층적 WFC 전파: Circle layer 기반 chunk 붕괴
        self._hierarchical_collapse(start, end)

        # 경로 추출
        if self._verify_connection(start, end):
            self.path = self._extract_path(start, end)
            return self.path

        return []

    def _bidirectional_collapse(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> bool:
        """중간 원주에서 시작하여 양방향으로 붕괴

        Args:
            start: 시작점
            end: 끝점

        Returns:
            성공 여부
        """
        # 교점 순서 (중간부터 바깥으로)
        intersection_order = self.circle_layer.get_intersection_order_from_middle()

        if not intersection_order:
            # 레이어가 1개 이하면 직접 연결 시도
            return self._direct_connect(start, end)

        # 경로상의 모든 점 수집 (시작점 → 교점들 → 끝점)
        # 교점 중 하나를 선택 (첫 번째 교점 사용)
        waypoints = [start]

        # 원주 순서대로 교점 추가 (0, 1, 2, ... 순)
        for idx in range(len(self.circle_layer.intersection_points)):
            points = self.circle_layer.intersection_points[idx]
            if points:
                # 첫 번째 교점 사용 (또는 시작점에 가까운 교점)
                grid_coord = points[0].to_grid()
                if (0 <= grid_coord[0] < self.grid.width and
                    0 <= grid_coord[1] < self.grid.height):
                    waypoints.append(grid_coord)

        waypoints.append(end)

        # 연속된 waypoint 사이를 연결
        for i in range(len(waypoints) - 1):
            p1 = waypoints[i]
            p2 = waypoints[i + 1]

            # 먼저 직선 연결 시도
            line_points = self._bresenham_line(p1[0], p1[1], p2[0], p2[1])

            can_use_line = True
            for x, y in line_points:
                tile = self.grid.get(x, y)
                if tile is None or not tile.can_be_road():
                    can_use_line = False
                    break

            if can_use_line:
                # 직선 사용 가능
                for x, y in line_points:
                    tile = self.grid.get(x, y)
                    if tile and tile.can_be_road():
                        self.wfc_engine.collapse_at(x, y, TileState.ROAD)
            else:
                # 직선 불가 → BFS로 우회 경로 탐색
                detour = self._find_detour(p1, p2)
                for x, y in detour:
                    tile = self.grid.get(x, y)
                    if tile and tile.can_be_road():
                        self.wfc_engine.collapse_at(x, y, TileState.ROAD)

        # 시작점과 끝점이 도로로 연결되었는지 확인
        return self._verify_connection(start, end)

    def _find_detour(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        """BFS로 우회 경로 탐색 (장애물 회피, 8방향)"""
        visited = {start: None}
        queue = deque([start])

        while queue:
            x, y = queue.popleft()

            if (x, y) == end:
                # 경로 역추적
                path = []
                current = end
                while current is not None:
                    path.append(current)
                    current = visited[current]
                path.reverse()
                return path

            # 8방향 탐색 (대각선 포함)
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0),
                           (1, 1), (1, -1), (-1, 1), (-1, -1)]:
                nx, ny = x + dx, y + dy

                if (nx, ny) in visited:
                    continue

                if not (0 <= nx < self.grid.width and 0 <= ny < self.grid.height):
                    continue

                tile = self.grid.get(nx, ny)
                if tile and tile.can_be_road():
                    visited[(nx, ny)] = (x, y)
                    queue.append((nx, ny))

        # 경로 없음
        return []

    def _direct_connect(self, start: Tuple[int, int], end: Tuple[int, int]) -> bool:
        """레이어 없이 직접 연결 시도

        간단한 직선/맨해튼 경로로 연결
        """
        x1, y1 = start
        x2, y2 = end

        # Bresenham 알고리즘으로 직선 경로 생성
        points = self._bresenham_line(x1, y1, x2, y2)

        for x, y in points:
            tile = self.grid.get(x, y)
            if tile and tile.can_be_road():
                self.wfc_engine.collapse_at(x, y, TileState.ROAD)

        return self._verify_connection(start, end)

    def _bresenham_line(
        self,
        x1: int, y1: int,
        x2: int, y2: int
    ) -> List[Tuple[int, int]]:
        """4방향 연결을 보장하는 직선 알고리즘

        대각선 이동 대신 가로/세로 이동만 사용하여
        모든 점이 4방향으로 연결되도록 함
        """
        points = []

        dx = abs(x2 - x1)
        dy = abs(y2 - y1)
        sx = 1 if x1 < x2 else -1
        sy = 1 if y1 < y2 else -1

        x, y = x1, y1
        points.append((x, y))

        if dx >= dy:
            # x축 기준 이동
            err = dx // 2
            while x != x2:
                x += sx
                points.append((x, y))
                err -= dy
                if err < 0:
                    y += sy
                    points.append((x, y))
                    err += dx
            # 마지막 y 조정
            while y != y2:
                y += sy
                points.append((x, y))
        else:
            # y축 기준 이동
            err = dy // 2
            while y != y2:
                y += sy
                points.append((x, y))
                err -= dx
                if err < 0:
                    x += sx
                    points.append((x, y))
                    err += dy
            # 마지막 x 조정
            while x != x2:
                x += sx
                points.append((x, y))

        return points

    def _verify_connection(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> bool:
        """시작점과 끝점이 도로로 연결되었는지 확인 (BFS, 8방향)"""
        visited = set()
        queue = deque([start])
        visited.add(start)

        while queue:
            x, y = queue.popleft()

            if (x, y) == end:
                return True

            # 인접 타일 확인 (8방향 - 대각선 포함)
            for dx, dy in DIRECTIONS_8:
                nx, ny = x + dx, y + dy

                if (nx, ny) in visited:
                    continue

                if not (0 <= nx < self.grid.width and 0 <= ny < self.grid.height):
                    continue

                tile = self.grid.get(nx, ny)
                if tile and tile.is_road():
                    visited.add((nx, ny))
                    queue.append((nx, ny))

        return False

    def _extract_path(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        """도로 타일에서 경로 추출 (BFS로 최단 경로, 8방향)"""
        visited = {start: None}  # 이전 노드 저장
        queue = deque([start])

        while queue:
            x, y = queue.popleft()

            if (x, y) == end:
                # 경로 역추적
                path = []
                current = end
                while current is not None:
                    path.append(current)
                    current = visited[current]
                path.reverse()
                return path

            # 인접 타일 확인 (8방향 - 대각선 포함)
            for dx, dy in DIRECTIONS_8:
                nx, ny = x + dx, y + dy

                if (nx, ny) in visited:
                    continue

                if not (0 <= nx < self.grid.width and 0 <= ny < self.grid.height):
                    continue

                tile = self.grid.get(nx, ny)
                if tile and tile.is_road():
                    visited[(nx, ny)] = (x, y)
                    queue.append((nx, ny))

        return []

    def get_stats(self) -> dict:
        """탐색 통계 반환"""
        road_count = sum(
            1 for row in self.grid.tiles
            for tile in row
            if tile.is_road()
        )

        return {
            "grid_size": f"{self.grid.width}x{self.grid.height}",
            "num_layers": self.num_layers or (
                self.circle_layer.num_layers if self.circle_layer else 0
            ),
            "path_length": len(self.path),
            "road_tiles": road_count,
            "total_tiles": self.grid.width * self.grid.height,
            "collapse_count": self.collapse_count,
            "contradiction_count": self.contradiction_count,
            "expansion_count": self.expansion_count,
            "complexity_score": self._get_complexity_score(),
        }

    def _hierarchical_collapse(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> None:
        """광선 기반 붕괴: Line of Sight (LoS) 방식

        원을 확장하지 않고, 현재 위치에서 목표까지 광선을 쏴서
        보이는 만큼만 붕괴 → 막히면 우회 → 반복

        Args:
            start: 시작점
            end: 끝점
        """
        # 광선 기반 붕괴로 전환
        self._ray_based_collapse(start, end)

    def _ray_based_collapse(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> None:
        """Lazy Tunnel: ray-first, 실패 시 세그먼트별 터널 업그레이드

        전략:
        1. 모든 세그먼트를 ray-only로 시작 (터널 없음)
        2. WFC 붕괴 시도
        3. 연결 실패 시, 끊어진 세그먼트만 터널로 업그레이드
        4. 성공할 때까지 반복

        Args:
            start: 시작점
            end: 끝점
        """
        # 1. 앵커 포인트 찾기 (타입 정보 없이)
        anchors_raw = self._find_anchors_for_lazy_tunnel(start, end)

        # 1-1. 앵커 압축 (Greedy Anchor Compression)
        anchors = self._compress_anchors(anchors_raw)

        # 2. 세그먼트별 상태 추적
        # segments[i] = (p1, p2, is_tunnel)
        # 장애물이 있는 세그먼트는 초기부터 터널로 시작
        segments = []
        for i in range(len(anchors) - 1):
            p1 = anchors[i]
            p2 = anchors[i + 1]

            # 직선 경로에 장애물이 있는지 확인
            ray = self._bresenham_line(p1[0], p1[1], p2[0], p2[1])
            has_obstacle = False
            for x, y in ray:
                tile = self.grid.get(x, y)
                if tile and not tile.can_be_road():
                    has_obstacle = True
                    break

            segments.append({
                'p1': p1,
                'p2': p2,
                'is_tunnel': has_obstacle,  # 장애물 있으면 터널로 시작
                'tunnel_width': 1 if has_obstacle else 0
            })

        # 3. Lazy Tunnel 루프
        max_upgrade_rounds = 10  # 최대 업그레이드 라운드

        for round_idx in range(max_upgrade_rounds):
            # 3-1. 현재 세그먼트 설정으로 road_zone 생성
            road_zone_tiles = self._build_road_zone_from_segments(segments)

            # 3-2. WFC 붕괴 시도 (세그먼트 정보 전달)
            connected = self._try_wfc_collapse(start, end, road_zone_tiles, segments)

            if connected:
                return  # 성공!

            # 3-3. 실패 → 끊어진 세그먼트 찾기
            failed_segments = self._find_disconnected_segments(segments, start, end)

            if not failed_segments:
                # 끊어진 세그먼트 찾을 수 없음 → 전체 확장
                for seg in segments:
                    if not seg['is_tunnel']:
                        seg['is_tunnel'] = True
                        seg['tunnel_width'] = 1
                        break  # 하나씩만 업그레이드
                continue

            # 3-4. 실패한 세그먼트만 터널로 업그레이드
            upgraded = False
            for seg_idx in failed_segments:
                seg = segments[seg_idx]
                if not seg['is_tunnel']:
                    # ray → tunnel 업그레이드
                    seg['is_tunnel'] = True
                    seg['tunnel_width'] = 1
                    upgraded = True
                elif seg['tunnel_width'] < 3:
                    # 터널 폭 증가
                    seg['tunnel_width'] += 1
                    upgraded = True

            if not upgraded:
                # 모든 세그먼트가 이미 최대 터널 → 전역 확장
                road_zone_tiles = self._build_road_zone_from_segments(segments)
                new_tiles = self._expand_tunnel_around_roads(road_zone_tiles, radius=1)
                # 그리드 리셋 없이 계속 시도
                self.expansion_count += 1

    def _find_anchors_for_lazy_tunnel(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        """Lazy Tunnel용 앵커 찾기 (타입 없이 좌표만)

        Args:
            start: 시작점
            end: 끝점

        Returns:
            앵커 좌표 리스트 [start, anchor1, ..., end]
        """
        anchors = [start]
        current = start
        max_iterations = 100

        for _ in range(max_iterations):
            if current == end:
                break

            # 현재 → 목표 광선
            ray = self._bresenham_line(current[0], current[1], end[0], end[1])

            # 충돌 지점 찾기
            collision_point = None
            last_visible = current

            for x, y in ray:
                if (x, y) == current:
                    continue

                tile = self.grid.get(x, y)
                if tile and not tile.can_be_road():
                    collision_point = last_visible
                    break
                last_visible = (x, y)

            if collision_point:
                # 충돌 지점 추가
                if collision_point != current and collision_point not in anchors:
                    anchors.append(collision_point)

                # 우회 앵커 찾기
                next_anchor = self._find_nearest_empty_towards_goal(
                    collision_point, end, search_radius=20
                )

                if next_anchor and next_anchor != collision_point:
                    if next_anchor not in anchors:
                        anchors.append(next_anchor)
                    current = next_anchor
                else:
                    break
            else:
                # 목표까지 직선 가능
                break

        if end not in anchors:
            anchors.append(end)

        return anchors

    def _compress_anchors(
        self,
        anchors: List[Tuple[int, int]]
    ) -> List[Tuple[int, int]]:
        """앵커 압축: 불필요한 중간 앵커 제거 (Greedy Anchor Compression)

        역방향으로 훑으며 "건너뛰어도 LoS가 가능한" 앵커들을 제거

        Args:
            anchors: 원본 앵커 리스트 [start, ..., end]

        Returns:
            압축된 앵커 리스트
        """
        if len(anchors) <= 2:
            return anchors

        compressed = [anchors[0]]  # 시작점
        i = 0

        while i < len(anchors) - 1:
            # 현재 앵커에서 가장 멀리 보이는 앵커 찾기 (역방향 탐색)
            farthest = i + 1

            for j in range(len(anchors) - 1, i, -1):
                if self._has_line_of_sight(anchors[i], anchors[j]):
                    farthest = j
                    break

            compressed.append(anchors[farthest])
            i = farthest

        return compressed

    def _has_line_of_sight(
        self,
        p1: Tuple[int, int],
        p2: Tuple[int, int]
    ) -> bool:
        """두 점 사이에 장애물 없이 직선 연결 가능한지 확인 (LoS)

        Args:
            p1: 시작점
            p2: 끝점

        Returns:
            직선 연결 가능 여부
        """
        ray = self._bresenham_line(p1[0], p1[1], p2[0], p2[1])

        for x, y in ray:
            tile = self.grid.get(x, y)
            if tile and not tile.can_be_road():
                return False

        return True

    def _build_road_zone_from_segments(
        self,
        segments: List[dict]
    ) -> set:
        """세그먼트 설정에 따라 road_zone 생성

        Args:
            segments: 세그먼트 리스트 [{p1, p2, is_tunnel, tunnel_width}, ...]

        Returns:
            road_zone 타일 좌표 set
        """
        road_zone = set()

        for seg in segments:
            p1, p2 = seg['p1'], seg['p2']

            if seg['is_tunnel']:
                # 터널: 폭 있는 경로
                tunnel_tiles = self._bresenham_tunnel_fixed_width(
                    p1[0], p1[1], p2[0], p2[1],
                    width=seg['tunnel_width']
                )
                road_zone.update(tunnel_tiles)
            else:
                # Ray-only: 선만
                ray_points = self._bresenham_line(p1[0], p1[1], p2[0], p2[1])
                for x, y in ray_points:
                    if 0 <= x < self.grid.width and 0 <= y < self.grid.height:
                        road_zone.add((x, y))

        return road_zone

    def _bresenham_tunnel_fixed_width(
        self,
        x1: int, y1: int,
        x2: int, y2: int,
        width: int
    ) -> set:
        """고정 폭 터널 생성

        Args:
            x1, y1: 시작점
            x2, y2: 끝점
            width: 터널 폭

        Returns:
            터널 타일 좌표 set
        """
        tunnel_tiles = set()

        # 기본 선 생성
        line_points = self._bresenham_line(x1, y1, x2, y2)

        for x, y in line_points:
            # 폭만큼 확장
            for dx in range(-width, width + 1):
                for dy in range(-width, width + 1):
                    if abs(dx) + abs(dy) <= width:  # 맨해튼 거리
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < self.grid.width and 0 <= ny < self.grid.height:
                            tunnel_tiles.add((nx, ny))

        return tunnel_tiles

    def _try_wfc_collapse(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int],
        road_zone_tiles: set,
        segments: List[dict] = None
    ) -> bool:
        """road_zone 내에서 Coarse-to-Fine WFC 붕괴 시도

        전략: 디딤돌(stepping stones)만 먼저 붕괴 → 사이는 직선 보간

        Args:
            start: 시작점
            end: 끝점
            road_zone_tiles: 붕괴 대상 타일 set
            segments: 세그먼트 리스트 (디딤돌 선정용)

        Returns:
            연결 성공 여부
        """
        # Phase 1: 디딤돌 선정 (세그먼트 경로 기반)
        if segments:
            stepping_stones = self._select_stepping_stones_from_segments(segments, step=3)
        else:
            stepping_stones = list(road_zone_tiles)[::3]  # fallback

        # Phase 2: 디딤돌만 먼저 붕괴
        for x, y in stepping_stones:
            tile = self.grid.get(x, y)
            if tile and not tile.is_collapsed and tile.can_be_road():
                self.collapse_count += 1
                if self.wfc_engine.collapse_tile(tile, TileState.ROAD):
                    self.wfc_engine.propagate(tile)

        # Phase 3: 연결 확인 - 성공하면 바로 리턴
        if self._verify_connection(start, end):
            return True

        # Phase 4: 실패 시 촘촘하게 붕괴 (fallback)
        distance = ((end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2) ** 0.5
        max_steps = int(distance * 50)  # 줄임
        max_steps = max(500, min(max_steps, 5000))
        check_interval = 20

        for step in range(max_steps):
            tile = self._get_lowest_entropy_in_tiles(road_zone_tiles)

            if tile is None:
                # 타일 고갈 → 주변 확장
                new_tiles = self._expand_tunnel_around_roads(road_zone_tiles, radius=1)
                if new_tiles:
                    road_zone_tiles.update(new_tiles)
                    self.expansion_count += 1
                    continue
                break

            self.collapse_count += 1

            if not self.wfc_engine.collapse_tile(tile, TileState.ROAD):
                continue

            if not self.wfc_engine.propagate(tile):
                continue

            if step % check_interval == 0:
                if self._verify_connection(start, end):
                    return True

        return self._verify_connection(start, end)

    def _select_stepping_stones_from_segments(
        self,
        segments: List[dict],
        step: int = 3
    ) -> List[Tuple[int, int]]:
        """세그먼트 경로를 따라 디딤돌 선정

        각 세그먼트의 직선 경로에서 일정 간격으로 샘플링

        Args:
            segments: 세그먼트 리스트
            step: 샘플링 간격

        Returns:
            디딤돌 좌표 리스트
        """
        stepping_stones = []

        for seg in segments:
            p1, p2 = seg['p1'], seg['p2']

            # 세그먼트 직선 경로
            line = self._bresenham_line(p1[0], p1[1], p2[0], p2[1])

            # step 간격으로 샘플링
            for i, (x, y) in enumerate(line):
                if i % step == 0:
                    stepping_stones.append((x, y))

        return stepping_stones

    def _find_disconnected_segments(
        self,
        segments: List[dict],
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[int]:
        """끊어진 세그먼트 인덱스 찾기

        각 세그먼트의 시작/끝점이 도로로 연결되었는지 확인

        Args:
            segments: 세그먼트 리스트
            start: 전체 시작점
            end: 전체 끝점

        Returns:
            끊어진 세그먼트 인덱스 리스트
        """
        failed = []

        for i, seg in enumerate(segments):
            p1, p2 = seg['p1'], seg['p2']

            # p1에서 p2로 도로 연결 확인
            if not self._is_segment_connected(p1, p2):
                failed.append(i)

        return failed

    def _is_segment_connected(
        self,
        p1: Tuple[int, int],
        p2: Tuple[int, int]
    ) -> bool:
        """두 점이 도로로 연결되었는지 확인 (BFS)

        Args:
            p1: 시작점
            p2: 끝점

        Returns:
            연결 여부
        """
        # p1이 도로가 아니면 실패
        tile1 = self.grid.get(p1[0], p1[1])
        if not tile1 or not tile1.is_road():
            return False

        visited = set()
        queue = deque([p1])
        visited.add(p1)

        # 탐색 범위 제한 (세그먼트 주변만)
        min_x = min(p1[0], p2[0]) - 5
        max_x = max(p1[0], p2[0]) + 5
        min_y = min(p1[1], p2[1]) - 5
        max_y = max(p1[1], p2[1]) + 5

        while queue:
            x, y = queue.popleft()

            if (x, y) == p2:
                return True

            for dx, dy in DIRECTIONS_8:
                nx, ny = x + dx, y + dy

                if (nx, ny) in visited:
                    continue

                # 범위 제한
                if not (min_x <= nx <= max_x and min_y <= ny <= max_y):
                    continue

                if not (0 <= nx < self.grid.width and 0 <= ny < self.grid.height):
                    continue

                tile = self.grid.get(nx, ny)
                if tile and tile.is_road():
                    visited.add((nx, ny))
                    queue.append((nx, ny))

        return False

    def _get_lowest_entropy_in_tiles(
        self,
        tiles_set: set
    ) -> Optional[Tile]:
        """지정된 타일 set 내에서 가장 낮은 엔트로피 타일 찾기

        Args:
            tiles_set: 탐색 대상 타일 좌표 set {(x, y), ...}

        Returns:
            set 내 최저 엔트로피 타일 (없으면 None)
        """
        min_entropy = float('inf')
        best_tile = None

        for x, y in tiles_set:
            tile = self.grid.get(x, y)
            if not tile:
                continue

            if tile.is_collapsed:
                continue

            if tile.entropy == 0:
                continue

            # set 내에서 최저 엔트로피 찾기
            if tile.entropy < min_entropy:
                min_entropy = tile.entropy
                best_tile = tile

        return best_tile

    def _global_wfc_collapse(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> None:
        """전역 WFC 붕괴 (fallback)

        Circle layer 없을 때 사용
        """
        distance = ((end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2) ** 0.5
        max_steps = int(distance * 200)
        max_steps = max(5000, min(max_steps, 20000))
        check_interval = 30

        for step in range(max_steps):
            success, tile = self.wfc_engine.step(prefer_state=TileState.ROAD)

            if not success or tile is None:
                break

            if step % check_interval == 0:
                if self._verify_connection(start, end):
                    return

    def _bresenham_tunnel_with_error(
        self,
        x1: int, y1: int,
        x2: int, y2: int
    ) -> set:
        """Bresenham 오차항 기반 동적 터널

        핵심: 오차항(Decision Parameter)이 클수록 터널 확장
        - 직선 구간: 좁은 터널 (폭 2~3)
        - 꺾이는 구간: 넓은 터널 (폭 자동 증가)

        이건 휴리스틱이 아니라 기하학적 제약기(Constraint Filter)!

        Args:
            x1, y1: 시작점
            x2, y2: 끝점

        Returns:
            터널 타일 좌표 set
        """
        tunnel_tiles = set()

        dx = abs(x2 - x1)
        dy = abs(y2 - y1)
        sx = 1 if x1 < x2 else -1
        sy = 1 if y1 < y2 else -1

        err = dx - dy
        x, y = x1, y1

        # 기준 오차 (터널 폭 계산용)
        max_err = max(dx, dy)
        base_width = 1  # 최소 터널 폭 (좁게 시작 → 실패 시 동적 확장)

        while True:
            # 현재 점의 오차 비율
            if max_err > 0:
                error_ratio = abs(err) / max_err
            else:
                error_ratio = 0

            # 오차 비율에 따라 터널 폭 결정 (기하학적!)
            # error_ratio가 클수록 = 기울기 변화 큼 = 터널 넓어짐
            tunnel_width = base_width + int(error_ratio * 2)  # 1~3 범위 (좁게)

            # 현재 점 중심으로 터널 생성
            for dx_offset in range(-tunnel_width, tunnel_width + 1):
                for dy_offset in range(-tunnel_width, tunnel_width + 1):
                    # 원형 터널 (맨해튼 거리 기준)
                    if abs(dx_offset) + abs(dy_offset) <= tunnel_width:
                        nx = x + dx_offset
                        ny = y + dy_offset
                        if 0 <= nx < self.grid.width and 0 <= ny < self.grid.height:
                            tunnel_tiles.add((nx, ny))

            if x == x2 and y == y2:
                break

            # Bresenham step
            e2 = 2 * err
            if e2 > -dy:
                err -= dy
                x += sx
            if e2 < dx:
                err += dx
                y += sy

        return tunnel_tiles

    def _find_anchor_points(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        """앵커 포인트 기반 굴절 브레젠험

        직선이 장애물에 막히면 → 가장 가까운 빈 공간으로 점프
        Waveguide 효과: 좁은 통로 입구만 찾으면 나머지는 자동!

        Args:
            start: 시작점
            end: 끝점

        Returns:
            앵커 포인트 리스트 [start, anchor1, anchor2, ..., end]
        """
        anchors = [start]
        current = start
        max_attempts = 20  # 최대 굴절 횟수

        for attempt in range(max_attempts):
            if current == end:
                break

            # 현재→끝 직선 생성
            line = self._bresenham_line(current[0], current[1], end[0], end[1])

            # 첫 장애물 지점 찾기
            blocked_at = None
            for x, y in line[1:]:  # 현재 위치 제외
                tile = self.grid.get(x, y)
                if tile and not tile.can_be_road():
                    blocked_at = (x, y)
                    break

            if blocked_at is None:
                # 직선 성공 → 끝까지 연결!
                if end not in anchors:
                    anchors.append(end)
                break

            # 장애물 만남 → 가장 가까운 빈 공간 찾기 (앵커)
            anchor = self._find_nearest_empty_towards_goal(
                blocked_at,
                end,
                search_radius=7  # 8방향 7칸 범위 탐색
            )

            if anchor and anchor not in anchors:
                anchors.append(anchor)
                current = anchor  # 앵커로 점프!
            else:
                # 빈 공간 못 찾음 → 끝으로 직행 (터널 확장에 맡김)
                if end not in anchors:
                    anchors.append(end)
                break

        # 끝점이 없으면 추가
        if anchors[-1] != end:
            anchors.append(end)

        return anchors

    def _find_nearest_empty_towards_goal(
        self,
        blocked: Tuple[int, int],
        goal: Tuple[int, int],
        search_radius: int = 7
    ) -> Optional[Tuple[int, int]]:
        """장애물 근처에서 목표 방향으로 가장 가까운 빈 공간 찾기

        기하학적: 목표 방향 벡터를 우선시 (휴리스틱 아님!)

        Args:
            blocked: 장애물 위치
            goal: 목표 위치
            search_radius: 탐색 반경

        Returns:
            가장 가까운 빈 공간 좌표 (없으면 None)
        """
        bx, by = blocked
        gx, gy = goal

        # 목표 방향 벡터 (정규화 안 함, 정수 유지)
        goal_dx = gx - bx
        goal_dy = gy - by

        candidates = []

        # 장애물 주변 탐색
        for dx in range(-search_radius, search_radius + 1):
            for dy in range(-search_radius, search_radius + 1):
                if dx == 0 and dy == 0:
                    continue

                nx = bx + dx
                ny = by + dy

                if not (0 <= nx < self.grid.width and 0 <= ny < self.grid.height):
                    continue

                tile = self.grid.get(nx, ny)
                if not tile or not tile.can_be_road():
                    continue

                # 기하학적 점수: 목표 방향과의 내적 (Dot Product)
                # 내적이 클수록 = 목표 방향과 일치
                dot_product = dx * goal_dx + dy * goal_dy

                # 거리 (맨해튼)
                dist_from_blocked = abs(dx) + abs(dy)

                # 점수: 목표 방향 우선, 거리는 tie-breaker
                score = dot_product * 100 - dist_from_blocked

                candidates.append((score, (nx, ny)))

        if not candidates:
            return None

        # 점수 높은 순 정렬
        candidates.sort(reverse=True, key=lambda x: x[0])

        return candidates[0][1]

    def _expand_tunnel_at(
        self,
        x: int, y: int,
        radius: int
    ) -> set:
        """특정 위치 주변으로 터널 확장 (국지적)

        Args:
            x, y: 중심 좌표
            radius: 확장 반경

        Returns:
            새로 추가된 타일 set
        """
        new_tiles = set()

        for dx in range(-radius, radius + 1):
            for dy in range(-radius, radius + 1):
                if abs(dx) + abs(dy) <= radius:  # 맨해튼 거리
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < self.grid.width and 0 <= ny < self.grid.height:
                        new_tiles.add((nx, ny))

        return new_tiles

    def _expand_tunnel_around_roads(
        self,
        road_tiles: set,
        radius: int
    ) -> set:
        """현재 도로 주변으로 터널 확장 (전역)

        Args:
            road_tiles: 기존 도로 타일 set
            radius: 확장 반경

        Returns:
            새로 추가된 타일 set
        """
        new_tiles = set()

        # 이미 붕괴된 도로 타일 찾기
        collapsed_roads = []
        for x, y in road_tiles:
            tile = self.grid.get(x, y)
            if tile and tile.is_road():
                collapsed_roads.append((x, y))

        # 도로 주변 확장
        for x, y in collapsed_roads:
            for dx in range(-radius, radius + 1):
                for dy in range(-radius, radius + 1):
                    if abs(dx) + abs(dy) <= radius:
                        nx = x + dx
                        ny = y + dy
                        if 0 <= nx < self.grid.width and 0 <= ny < self.grid.height:
                            new_tiles.add((nx, ny))

        return new_tiles

    def _calculate_obstacle_density(
        self,
        center: Tuple[int, int],
        radius: int = 3
    ) -> float:
        """주변 장애물 밀도 계산 (0.0 ~ 1.0)

        Args:
            center: 중심점
            radius: 탐색 반경

        Returns:
            장애물 비율 (0.0 = 빈 공간, 1.0 = 완전 막힘)
        """
        obstacles = 0
        total = 0

        cx, cy = center
        for dx in range(-radius, radius + 1):
            for dy in range(-radius, radius + 1):
                nx = cx + dx
                ny = cy + dy

                if 0 <= nx < self.grid.width and 0 <= ny < self.grid.height:
                    total += 1
                    tile = self.grid.get(nx, ny)
                    if tile and not tile.can_be_road():
                        obstacles += 1

        return obstacles / total if total > 0 else 0.0

    def _get_complexity_score(self) -> float:
        """현재까지의 복잡도 점수 (동적)

        확장 빈도를 기반으로 실시간 복잡도 측정
        터널이 자주 확장된다 = 복잡한 환경

        Returns:
            복잡도 점수 (0.0 = 단순, 1.0 = 매우 복잡)
        """
        # 초반에는 충분한 데이터가 없으므로 저복잡도로 가정
        if self.collapse_count < 20:
            return 0.0

        # 확장 비율 = 복잡도
        # 붕괴 대비 확장이 많으면 복잡한 환경
        # 일반적으로 expansion/collapse는 0.01~0.1 정도
        # 0.05 이상이면 복잡한 환경으로 간주
        expansion_ratio = self.expansion_count / self.collapse_count

        # 0~1 범위로 정규화 (0.05를 0.5로 매핑)
        complexity = min(expansion_ratio * 10, 1.0)
        return complexity

    # ========================================================================
    # MLMC: Multi-Layer Midpoint Collapse (새로운 알고리즘)
    # ========================================================================

    def find_mlmc(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int],
        initial_layers: Optional[int] = None
    ) -> List[Tuple[int, int]]:
        """MLMC (Multi-Layer Midpoint Collapse) 경로 탐색

        CircleLayer 교점을 중간점으로 사용하고,
        WFC 붕괴로 벽 여부를 감지하여 순수 WFC만으로 경로 탐색

        특징:
        - BFS/A* 사용 안 함 (순수 WFC)
        - 중간점 유효성을 붕괴로 검증
        - 실패 시 레이어 수 증가로 자동 조정

        Args:
            start: 시작점 (x, y)
            end: 끝점 (x, y)
            initial_layers: 초기 레이어 수 (None이면 자동)

        Returns:
            경로 좌표 리스트 [(x1, y1), ...]
        """
        # 카운터 초기화
        self.contradiction_count = 0
        self.collapse_count = 0
        self.expansion_count = 0

        # 초기 레이어 수 결정
        distance = ((end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2) ** 0.5
        if initial_layers is None:
            initial_layers = max(1, int(distance ** 0.5))  # √D

        # 제약 조건 설정
        constraints = ConstraintManager()
        constraints.add(BasicRoadConstraint())
        constraints.add(PathConstraint(prefer_road=True))

        # 레이어 수를 늘려가며 시도
        max_layer_attempts = 5

        for layer_attempt in range(max_layer_attempts):
            num_layers = initial_layers + layer_attempt * 2  # 1, 3, 5, 7, ...

            # 그리드 리셋 (이전 시도 흔적 제거)
            self._reset_grid_for_mlmc()

            # WFC 엔진 생성
            self.wfc_engine = WFCEngine(self.grid, constraints, allow_diagonal=True)

            # CircleLayer 생성
            self.circle_layer = CircleLayer(start, end, num_layers)

            # 1. 시작/끝점 붕괴
            self.wfc_engine.collapse_at(start[0], start[1], TileState.ROAD)
            self.wfc_engine.collapse_at(end[0], end[1], TileState.ROAD)

            # 2. 중간점 검증 및 수집
            valid_midpoints = self._collect_valid_midpoints_mlmc(start, end)

            if not valid_midpoints:
                # 유효한 중간점 없음 → 레이어 증가
                continue

            # 3. 중간점 순차 연결 (순수 WFC)
            waypoints = [start] + valid_midpoints + [end]
            all_connected = self._connect_waypoints_pure_wfc(waypoints)

            if all_connected:
                # 4. 경로 추출
                if self._verify_connection(start, end):
                    self.path = self._extract_path(start, end)
                    return self.path

        # 모든 시도 실패
        return []

    def _reset_grid_for_mlmc(self) -> None:
        """MLMC용 그리드 리셋 (붕괴 상태만 초기화, 벽은 유지)"""
        for row in self.grid.tiles:
            for tile in row:
                # 벽(장애물)은 절대 리셋하지 않음
                # can_be_road()=False인 타일은 제약이 설정된 벽
                if tile.can_be_road():
                    tile.collapsed_state = None
                    tile.possible_states = {TileState.EMPTY, TileState.ROAD}

    def _collect_valid_midpoints_mlmc(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        """MLMC: 유효한 중간점 수집 (붕괴로 벽 감지)

        CircleLayer 교점을 순회하며:
        1. 붕괴 시도
        2. 실패 시 대안 교점 시도
        3. 성공한 점만 수집

        Args:
            start: 시작점
            end: 끝점

        Returns:
            유효한 중간점 리스트 (순서대로)
        """
        valid_midpoints = []

        if not self.circle_layer or not self.circle_layer.intersection_points:
            return valid_midpoints

        # 교점 그룹 순회 (start → end 방향)
        for idx, points in enumerate(self.circle_layer.intersection_points):
            if not points:
                continue

            midpoint = None

            # 첫 번째 교점 시도
            p1 = points[0].to_grid()
            if self._try_collapse_midpoint(p1):
                midpoint = p1
            elif len(points) > 1:
                # 대안 교점 시도 (두 번째 교점)
                p2 = points[1].to_grid()
                if self._try_collapse_midpoint(p2):
                    midpoint = p2

            if midpoint:
                valid_midpoints.append(midpoint)

        return valid_midpoints

    def _try_collapse_midpoint(
        self,
        point: Tuple[int, int]
    ) -> bool:
        """중간점 붕괴 시도 (벽 감지)

        붕괴 성공 = 유효한 중간점
        붕괴 실패 = 벽 안 또는 도달 불가

        Args:
            point: 검사할 좌표

        Returns:
            붕괴 성공 여부
        """
        x, y = point

        if not (0 <= x < self.grid.width and 0 <= y < self.grid.height):
            return False

        tile = self.grid.get(x, y)
        if not tile:
            return False

        # 이미 장애물이면 실패
        if not tile.can_be_road():
            return False

        # 이미 도로면 성공
        if tile.is_road():
            return True

        # 붕괴 시도
        self.collapse_count += 1
        success = self.wfc_engine.collapse_at(x, y, TileState.ROAD)

        if success:
            # 전파
            self.wfc_engine.propagate(tile)
            return True

        self.contradiction_count += 1
        return False

    def _connect_waypoints_pure_wfc(
        self,
        waypoints: List[Tuple[int, int]]
    ) -> bool:
        """웨이포인트 간 순수 WFC 연결 (BFS 없음)

        각 연속 웨이포인트 쌍 사이를 WFC propagation으로 연결

        Args:
            waypoints: [start, mid1, mid2, ..., end]

        Returns:
            모든 연결 성공 여부
        """
        for i in range(len(waypoints) - 1):
            p1 = waypoints[i]
            p2 = waypoints[i + 1]

            connected = self._wfc_connect_segment(p1, p2)
            if not connected:
                return False

        return True

    def _wfc_connect_segment(
        self,
        p1: Tuple[int, int],
        p2: Tuple[int, int],
        max_iterations: int = 500
    ) -> bool:
        """두 점 사이 WFC 연결 (순수 WFC, 휴리스틱 없음)

        전략:
        1. p1 → p2 직선 경로의 타일들을 후보로
        2. 후보 타일 중 엔트로피 낮은 순으로 붕괴
        3. 붕괴 실패 시 주변 확장

        Args:
            p1: 시작점
            p2: 끝점
            max_iterations: 최대 반복 횟수

        Returns:
            연결 성공 여부
        """
        # 초기 직선 경로 타일
        line_tiles = set(self._bresenham_line(p1[0], p1[1], p2[0], p2[1]))
        candidate_tiles = line_tiles.copy()

        for iteration in range(max_iterations):
            # 연결 확인
            if self._is_segment_connected(p1, p2):
                return True

            # 후보 중 붕괴 가능한 타일 찾기
            tile = self._get_best_tile_for_wfc_connect(candidate_tiles, p2)

            if tile is None:
                # 후보 고갈 → 주변 확장
                expanded = self._expand_candidates_around(candidate_tiles)
                if expanded:
                    candidate_tiles.update(expanded)
                    self.expansion_count += 1
                    continue
                else:
                    # 확장 불가 → 실패
                    return False

            # 붕괴 시도
            self.collapse_count += 1
            if self.wfc_engine.collapse_tile(tile, TileState.ROAD):
                self.wfc_engine.propagate(tile)

        return self._is_segment_connected(p1, p2)

    def _get_best_tile_for_wfc_connect(
        self,
        candidates: set,
        target: Tuple[int, int]
    ) -> Optional[Tile]:
        """WFC 연결을 위한 최적 타일 선택

        기준: 엔트로피 낮음 + 목표에 가까움 (기하학적)

        Args:
            candidates: 후보 좌표 set
            target: 목표점

        Returns:
            최적 타일 (없으면 None)
        """
        best_tile = None
        best_score = float('inf')

        for x, y in candidates:
            tile = self.grid.get(x, y)
            if not tile or tile.is_collapsed or not tile.can_be_road():
                continue

            # 점수: 엔트로피 우선, 거리는 2차
            # 엔트로피 낮을수록 좋음 (확실한 결정)
            dist_to_target = abs(x - target[0]) + abs(y - target[1])
            score = tile.entropy * 1000 + dist_to_target

            if score < best_score:
                best_score = score
                best_tile = tile

        return best_tile

    def _expand_candidates_around(
        self,
        candidates: set,
        radius: int = 1
    ) -> set:
        """후보 타일 주변 확장

        이미 붕괴된 도로 주변의 빈 타일 수집

        Args:
            candidates: 기존 후보 set
            radius: 확장 반경

        Returns:
            새 후보 타일 set
        """
        new_candidates = set()

        # 기존 후보 중 도로인 타일 찾기
        road_tiles = []
        for x, y in candidates:
            tile = self.grid.get(x, y)
            if tile and tile.is_road():
                road_tiles.append((x, y))

        # 도로 주변 확장
        for rx, ry in road_tiles:
            for dx in range(-radius, radius + 1):
                for dy in range(-radius, radius + 1):
                    if dx == 0 and dy == 0:
                        continue
                    nx, ny = rx + dx, ry + dy
                    if (nx, ny) in candidates:
                        continue
                    if not (0 <= nx < self.grid.width and 0 <= ny < self.grid.height):
                        continue
                    tile = self.grid.get(nx, ny)
                    if tile and not tile.is_collapsed and tile.can_be_road():
                        new_candidates.add((nx, ny))

        return new_candidates

    def _find_furthest_road_towards_goal(
        self,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        search_area: Optional[set] = None
    ) -> Tuple[int, int]:
        """현재까지 붕괴된 도로 중 목표에 가장 가까운 지점 찾기 (최적화)

        Args:
            start: 시작점
            goal: 목표점
            search_area: 탐색 영역 (None이면 전체 그리드)

        Returns:
            목표에 가장 가까운 도로 타일 좌표
        """
        best_pos = start
        best_dist = float('inf')

        if search_area:
            # 탐색 영역 내에서만 탐색 (O(|search_area|))
            for x, y in search_area:
                tile = self.grid.get(x, y)
                if tile and tile.is_road():
                    dist = ((x - goal[0]) ** 2 + (y - goal[1]) ** 2) ** 0.5
                    if dist < best_dist:
                        best_dist = dist
                        best_pos = (x, y)
        else:
            # 전체 그리드 탐색 (O(width × height)) - 최후 수단
            for y in range(self.grid.height):
                for x in range(self.grid.width):
                    tile = self.grid.get(x, y)
                    if tile and tile.is_road():
                        dist = ((x - goal[0]) ** 2 + (y - goal[1]) ** 2) ** 0.5
                        if dist < best_dist:
                            best_dist = dist
                            best_pos = (x, y)

        return best_pos

    # ========================================================================
    # MLMC-Ray: MLMC + Lazy Tunnel 융합 (Ray 기반 앵커 탐지)
    # ========================================================================

    def find_mlmc_ray(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int],
        initial_layers: Optional[int] = None
    ) -> List[Tuple[int, int]]:
        """MLMC-Ray: CircleLayer + Ray 기반 앵커 탐지 융합

        MLMC의 문제점(교차점이 벽 위에 있으면 실패)을 해결:
        1. CircleLayer 교차점 확인
        2. 벽이면 → 이전 앵커에서 ray를 쏴서 벽 직전 좌표를 앵커로 사용

        Args:
            start: 시작점 (x, y)
            end: 끝점 (x, y)
            initial_layers: 초기 레이어 수 (None이면 자동)

        Returns:
            경로 좌표 리스트 [(x1, y1), ...]
        """
        # 카운터 초기화
        self.contradiction_count = 0
        self.collapse_count = 0
        self.expansion_count = 0

        # 초기 레이어 수 결정
        distance = ((end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2) ** 0.5
        if initial_layers is None:
            initial_layers = max(2, int(distance ** 0.5))

        # 제약 조건 설정
        constraints = ConstraintManager()
        constraints.add(BasicRoadConstraint())
        constraints.add(PathConstraint(prefer_road=True))

        # Phase 1: 레이어 수를 늘려가며 시도 (기하학적 접근)
        max_layer_attempts = 5

        for layer_attempt in range(max_layer_attempts):
            num_layers = initial_layers + layer_attempt * 2

            # 그리드 리셋
            self._reset_grid_for_mlmc()

            # WFC 엔진 생성
            self.wfc_engine = WFCEngine(self.grid, constraints, allow_diagonal=True)

            # CircleLayer 생성
            self.circle_layer = CircleLayer(start, end, num_layers)

            # 1. 시작/끝점 붕괴
            self.wfc_engine.collapse_at(start[0], start[1], TileState.ROAD)
            self.wfc_engine.collapse_at(end[0], end[1], TileState.ROAD)

            # 2. Ray 기반 앵커 수집 (핵심 변경점)
            anchors = self._collect_anchors_with_ray(start, end)

            if not anchors:
                continue

            # 3. 앵커 간 WFC 연결
            waypoints = [start] + anchors + [end]
            all_connected = self._connect_waypoints_pure_wfc(waypoints)

            if all_connected:
                if self._verify_connection(start, end):
                    self.path = self._extract_path(start, end)
                    return self.path

        # Phase 2: 촘촘한 앵커 모드 (복잡한 미로용)
        # 벽 gap을 촘촘히 스캔해서 앵커 생성
        self._reset_grid_for_mlmc()
        self.wfc_engine = WFCEngine(self.grid, constraints, allow_diagonal=True)
        self.wfc_engine.collapse_at(start[0], start[1], TileState.ROAD)
        self.wfc_engine.collapse_at(end[0], end[1], TileState.ROAD)

        # 촘촘한 앵커 수집 (벽 gap 탐색)
        dense_anchors = self._collect_dense_anchors(start, end)

        if dense_anchors:
            waypoints = [start] + dense_anchors + [end]
            all_connected = self._connect_waypoints_pure_wfc(waypoints)

            if all_connected:
                if self._verify_connection(start, end):
                    self.path = self._extract_path(start, end)
                    return self.path

        # 모든 시도 실패
        return []

    def _collect_anchors_with_ray(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        """Ray 기반 앵커 수집 (MLMC + Lazy Tunnel 융합)

        우선순위:
        1. 교차점이 유효하면 그대로 사용
        2. 대안 교차점(두 번째) 시도
        3. ray로 벽 직전 좌표 찾기
        4. 벽 가장자리 우회점 찾기

        Args:
            start: 시작점
            end: 끝점

        Returns:
            유효한 앵커 리스트
        """
        anchors = []

        if not self.circle_layer or not self.circle_layer.intersection_points:
            # 교차점 없으면 직선 ray 기반 앵커 생성
            return self._generate_line_anchors(start, end)

        prev_anchor = start

        for idx, points in enumerate(self.circle_layer.intersection_points):
            if not points:
                continue

            anchor = None
            p1 = points[0].to_grid() if self._is_valid_grid_point(points[0].to_grid()) else None
            p2 = points[1].to_grid() if len(points) > 1 and self._is_valid_grid_point(points[1].to_grid()) else None

            # 1. 첫 번째 교차점 시도 (벽 아니고 LoS 있으면)
            if p1:
                tile = self.grid.get(p1[0], p1[1])
                if tile and tile.can_be_road():
                    if self._has_line_of_sight(prev_anchor, p1):
                        anchor = p1

            # 2. 대안 교차점 시도 (벽 아니고 LoS 있으면)
            if anchor is None and p2:
                tile = self.grid.get(p2[0], p2[1])
                if tile and tile.can_be_road():
                    if self._has_line_of_sight(prev_anchor, p2):
                        anchor = p2

            # 3. 교차점이 벽이거나 LoS 없으면 → 우회점 찾기
            if anchor is None:
                target = p1 or p2
                if target:
                    # 먼저 벽 직전 좌표
                    before_wall = self._find_anchor_before_wall(prev_anchor, target)
                    if before_wall and before_wall != prev_anchor:
                        # 벽 직전에서 벽 끝으로 우회
                        bypass = self._find_wall_bypass_anchor(before_wall, target, end)
                        if bypass:
                            anchor = bypass
                        else:
                            anchor = before_wall

            # 앵커 추가
            if anchor and anchor != prev_anchor:
                if self._try_collapse_midpoint(anchor):
                    anchors.append(anchor)
                    prev_anchor = anchor

        return anchors

    def _generate_line_anchors(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int],
        num_anchors: int = 5
    ) -> List[Tuple[int, int]]:
        """직선 기반 앵커 생성 (CircleLayer 없을 때)

        start→end 직선을 따라 균등 간격으로 앵커 생성
        벽을 만나면 우회점 찾기

        Args:
            start: 시작점
            end: 끝점
            num_anchors: 앵커 수

        Returns:
            앵커 리스트
        """
        anchors = []
        ray = self._bresenham_line(start[0], start[1], end[0], end[1])

        if len(ray) < 3:
            return anchors

        step = max(1, len(ray) // (num_anchors + 1))
        prev_anchor = start

        for i in range(1, num_anchors + 1):
            idx = min(i * step, len(ray) - 1)
            target = ray[idx]

            tile = self.grid.get(target[0], target[1])
            if tile and tile.can_be_road():
                anchors.append(target)
                prev_anchor = target
            else:
                # 벽 → 우회점 찾기
                bypass = self._find_wall_bypass_anchor(prev_anchor, target, end)
                if bypass:
                    anchors.append(bypass)
                    prev_anchor = bypass

        return anchors

    def _find_wall_bypass_anchor(
        self,
        from_point: Tuple[int, int],
        wall_point: Tuple[int, int],
        goal: Tuple[int, int]
    ) -> Optional[Tuple[int, int]]:
        """벽 우회 앵커 찾기

        벽 직전에서 위/아래/좌/우로 벽 가장자리를 따라가며
        goal 방향으로 갈 수 있는 우회점 찾기

        Args:
            from_point: 현재 위치
            wall_point: 벽 좌표
            goal: 최종 목표

        Returns:
            우회 앵커 좌표 (없으면 None)
        """
        # 벽 직전 좌표
        before_wall = self._find_anchor_before_wall(from_point, wall_point)
        if not before_wall:
            return None

        # 벽 가장자리를 따라 우회점 탐색
        # 방향: 벽의 상/하/좌/우 중 goal에 가까운 방향 우선
        bx, by = before_wall
        dx_to_goal = goal[0] - bx
        dy_to_goal = goal[1] - by

        # 우선순위: goal 방향과 수직인 방향
        if abs(dx_to_goal) > abs(dy_to_goal):
            # 주로 x 방향 이동 → y 방향 우회 시도
            search_dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        else:
            # 주로 y 방향 이동 → x 방향 우회 시도
            search_dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        best_bypass = None
        best_score = float('inf')

        # 벽의 좌표
        wall_x, wall_y = wall_point

        for dx, dy in search_dirs:
            # 벽 가장자리를 따라 이동
            for dist in range(1, 50):  # 최대 50칸 탐색 (벽 끝까지)
                nx, ny = bx + dx * dist, by + dy * dist

                if not (0 <= nx < self.grid.width and 0 <= ny < self.grid.height):
                    break

                tile = self.grid.get(nx, ny)
                if not tile or not tile.can_be_road():
                    continue

                # 조건 1: goal로 LoS 있으면 최우선
                if self._has_line_of_sight((nx, ny), goal):
                    score = ((nx - goal[0]) ** 2 + (ny - goal[1]) ** 2) ** 0.5
                    if score < best_score:
                        best_score = score
                        best_bypass = (nx, ny)
                    break

                # 조건 2: 벽 끝을 돌아서 goal 방향으로 전진 가능한지
                # 현재 위치에서 wall_x 방향으로 직선 이동이 가능한지 확인
                can_pass_wall = self._can_pass_wall_at(nx, ny, wall_x, goal)
                if can_pass_wall:
                    # 벽 끝을 돌아갈 수 있음!
                    score = ((nx - goal[0]) ** 2 + (ny - goal[1]) ** 2) ** 0.5
                    if score < best_score:
                        best_score = score
                        best_bypass = (nx, ny)
                    break

        return best_bypass

    def _can_pass_wall_at(
        self,
        x: int,
        y: int,
        wall_x: int,
        goal: Tuple[int, int]
    ) -> bool:
        """현재 위치에서 wall_x를 지나 goal 방향으로 갈 수 있는지"""
        # wall_x 위치의 타일이 통과 가능한지
        wall_tile = self.grid.get(wall_x, y)
        if wall_tile and wall_tile.can_be_road():
            # wall_x+1도 확인 (벽이 2칸 두께일 수 있음)
            next_tile = self.grid.get(wall_x + 1, y)
            if next_tile and next_tile.can_be_road():
                return True
        return False

    def _find_anchor_before_wall(
        self,
        from_point: Tuple[int, int],
        to_point: Tuple[int, int]
    ) -> Optional[Tuple[int, int]]:
        """벽 직전 좌표 찾기 (Ray 발사)

        from_point에서 to_point 방향으로 ray를 쏘고,
        벽 직전의 마지막 유효 좌표 반환

        Args:
            from_point: ray 시작점
            to_point: ray 목표점 (벽일 수 있음)

        Returns:
            벽 직전 좌표 (없으면 None)
        """
        ray = self._bresenham_line(
            from_point[0], from_point[1],
            to_point[0], to_point[1]
        )

        last_valid = None

        for x, y in ray:
            if not (0 <= x < self.grid.width and 0 <= y < self.grid.height):
                break

            tile = self.grid.get(x, y)
            if tile and tile.can_be_road():
                last_valid = (x, y)
            else:
                # 벽 만남 → 직전 좌표 반환
                break

        return last_valid

    def _is_valid_grid_point(self, point: Tuple[int, int]) -> bool:
        """그리드 내 유효한 좌표인지 확인"""
        x, y = point
        return 0 <= x < self.grid.width and 0 <= y < self.grid.height

    def _collect_dense_anchors(
        self,
        start: Tuple[int, int],
        end: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        """촘촘한 앵커 수집 (복잡한 미로용)

        start→end 방향으로 직선 ray를 쏘면서:
        1. 벽을 만나면 → 벽 gap(위/아래) 찾기
        2. gap 통과 후 → 다시 직선 진행
        3. 반복

        이 방식은 사실상 "벽 따라가기"지만,
        우리 알고리즘 프레임워크 내에서 수행

        Args:
            start: 시작점
            end: 끝점

        Returns:
            앵커 리스트
        """
        anchors = []
        current = start
        visited_walls = set()  # 무한 루프 방지
        max_iterations = 100

        for _ in range(max_iterations):
            # 현재 위치에서 end로 직선 ray
            if self._has_line_of_sight(current, end):
                # 직선 연결 가능 → 완료
                break

            # 벽 찾기
            wall_info = self._find_wall_on_ray(current, end)
            if not wall_info:
                break

            wall_x, wall_y = wall_info

            # 무한 루프 방지
            if (wall_x, wall_y) in visited_walls:
                break
            visited_walls.add((wall_x, wall_y))

            # 벽 gap 찾기 (위 또는 아래)
            gap_anchor = self._find_gap_around_wall(current, wall_x, wall_y, end)

            if gap_anchor:
                anchors.append(gap_anchor)
                current = gap_anchor
            else:
                # gap 못 찾음 → 실패
                break

        return anchors

    def _find_wall_on_ray(
        self,
        from_point: Tuple[int, int],
        to_point: Tuple[int, int]
    ) -> Optional[Tuple[int, int]]:
        """ray 경로에서 첫 번째 벽 좌표 찾기"""
        ray = self._bresenham_line(
            from_point[0], from_point[1],
            to_point[0], to_point[1]
        )

        for x, y in ray:
            if not (0 <= x < self.grid.width and 0 <= y < self.grid.height):
                return None

            tile = self.grid.get(x, y)
            if tile and not tile.can_be_road():
                return (x, y)

        return None

    def _find_gap_around_wall(
        self,
        from_point: Tuple[int, int],
        wall_x: int,
        wall_y: int,
        goal: Tuple[int, int]
    ) -> Optional[Tuple[int, int]]:
        """벽 주변에서 통과 가능한 gap 찾기

        벽의 위쪽/아래쪽 끝을 탐색해서
        goal 방향으로 갈 수 있는 gap 반환

        Args:
            from_point: 현재 위치
            wall_x: 벽 x 좌표
            wall_y: 벽 y 좌표
            goal: 목표점

        Returns:
            gap 앵커 좌표
        """
        # 벽 직전 좌표
        before_wall = self._find_anchor_before_wall(from_point, (wall_x, wall_y))
        if not before_wall:
            return None

        bx, by = before_wall

        # 위쪽/아래쪽 gap 탐색
        candidates = []

        # goal 방향 결정 (x 증가 or 감소)
        x_direction = 1 if goal[0] > bx else -1

        # 위쪽 탐색 (y 감소)
        for y in range(by - 1, max(-1, by - 50), -1):
            tile = self.grid.get(wall_x, y)
            if tile and tile.can_be_road():
                # 벽 끝 발견! 벽 반대편으로 앵커 설정
                # wall_x + x_direction으로 벽을 통과
                after_wall_x = wall_x + x_direction
                tile_after = self.grid.get(after_wall_x, y)
                if tile_after and tile_after.can_be_road():
                    anchor = (after_wall_x, y)  # 벽 통과 후 좌표
                    dist = ((after_wall_x - goal[0]) ** 2 + (y - goal[1]) ** 2) ** 0.5
                    candidates.append((anchor, dist))
                break

        # 아래쪽 탐색 (y 증가)
        for y in range(by + 1, min(self.grid.height, by + 50)):
            tile = self.grid.get(wall_x, y)
            if tile and tile.can_be_road():
                after_wall_x = wall_x + x_direction
                tile_after = self.grid.get(after_wall_x, y)
                if tile_after and tile_after.can_be_road():
                    anchor = (after_wall_x, y)
                    dist = ((after_wall_x - goal[0]) ** 2 + (y - goal[1]) ** 2) ** 0.5
                    candidates.append((anchor, dist))
                break

        if not candidates:
            return None

        # goal에 가까운 gap 선택
        candidates.sort(key=lambda x: x[1])
        return candidates[0][0]