# Conservative voxel navigation with directional stair transitions and supported ladders.
from collections import deque

from .blocks import passable, floor_support, name, split_state
from .materials import DIRECTIONS


def walkable(grid, p):
    """Test actual foot/head cells and the supporting floor."""
    x, y, z = p
    return passable(grid.get(x, y, z)) and passable(grid.get(x, y + 1, z)) and (floor_support(grid.get(x, y - 1, z)) or name(grid.get(x, y, z)) == 'ladder')


def neighbors(grid, p):
    """Yield traversable neighbors, allowing rises only on correctly facing stairs."""
    x, y, z = p
    for direction, (dx, dz) in DIRECTIONS.items():
        for dy in (0, 1, -1):
            q = (x + dx, y + dy, z + dz)
            if not walkable(grid, q):
                continue
            if dy:
                # Stair facing is the direction from the low end to the high end.
                high = q if dy == 1 else p
                block = grid.get(high[0], high[1] - 1, high[2])
                expected = direction if dy == 1 else {'north': 'south', 'south': 'north', 'east': 'west', 'west': 'east'}[direction]
                if not name(block).endswith('_stairs') or split_state(block)[1].get('facing') != expected:
                    # Leaving a ladder onto a landing is also a legal transition.
                    if name(grid.get(*p)) != 'ladder' and name(grid.get(*q)) != 'ladder':
                        continue
                # A rising player's head sweeps the higher source cell.
                if not passable(grid.get(x if dy == 1 else q[0], max(y, q[1]) + 1, z if dy == 1 else q[2])):
                    continue
            yield q
    if name(grid.get(*p)) == 'ladder':
        for dy in (-1, 1):
            q = x, y + dy, z
            if name(grid.get(*q)) == 'ladder' and walkable(grid, q):
                yield q


def flood(grid, start, allowed=None, maximum=200000):
    """Return reachable positions and a predecessor map from actual geometry."""
    start = tuple(start)
    if not walkable(grid, start):
        return {}
    parents = {start: None}
    queue = deque([start])
    while queue:
        p = queue.popleft()
        for q in neighbors(grid, p):
            if q in parents or allowed is not None and q not in allowed:
                continue
            parents[q] = p
            queue.append(q)
            if len(parents) > maximum:
                raise ValueError('navigation resource limit exceeded')
    return parents


def path_to(parents, target):
    """Recover one deterministic path from a reachable target."""
    p = tuple(target)
    result = []
    while p is not None:
        result.append(p)
        p = parents[p]
    return list(reversed(result))