segmentation.py

"""
segmentation.py
----------------
Multi-signal sprite sheet segmentation.

Why not just connected components
----------------------------------
A single sprite (e.g. a plant) can be made of several pixel groups that are
NOT 4/8-connected to each other -- there might be a 1-2 pixel gap between a
leaf and a stem due to anti-aliasing removal or the original artist's pixel
placement. Naive connected-component labelling would split that single
sprite into multiple "sprites".

Conversely, two genuinely different sprites can sit close together on a
sheet (dense tilesets, cramped sheets) with only a couple of pixels of gap
between them -- naive dilation-based merging would fuse them into one.

This module resolves that tension with a two-stage pipeline:

  1. `find_components()` -- raw 8-connected components on the foreground
     mask. This is the ONLY step that looks at raw connectivity.

  2. `merge_related_components()` -- decides, pairwise, whether two raw
     components are parts of the same logical sprite. This is where all of
     the extra signals from the spec are combined:
        - component distance (gap gets bigger relative to component size)
        - horizontal gap / vertical gap independently
        - bounding boxes / overlap
        - component size (small components merge more readily -- they're
          more likely to be a stray anti-aliasing remnant or dithering
          pixel of a bigger sprite)
        - alignment (components whose centers line up on the same
          row/column band are more likely part of one sprite, e.g. a
          plant stem + leaf, vs. two independent sprites placed on a
          shared baseline of a *sheet*, which is handled by keeping the
          merge radius small relative to sprite size)
        - local density (in a densely packed region of the sheet, the
          merge radius shrinks so we don't fuse neighbouring sprites)

  3. `detect_sprite_boundaries()` -- turns each merged group into a
     BBox plus its exact pixel mask.

  4. `calculate_segmentation_confidence()` -- heuristic score per sprite,
     flagging the sprite for mandatory manual review when low.

This is intentionally NOT a single "smart" algorithm -- it is a small
pipeline of clearly separated, independently testable functions, so a
better algorithm can be swapped in later per component (see spec:
"Tek bir algoritmaya bağımlı olma").

Grid modes
----------
The gap-based pipeline above assumes sprites are separated by at least a
sliver of background, and that a sprite's own parts are never separated
by more than a few pixels. Real sheets break that assumption in two
opposite directions, and each has its own detector.

**Over-merge -- no gaps at all.** Portrait/expression sheets (the
standard Stardew Valley format: a fixed grid of 64x64 cells with ZERO
gap between them) and tilesets drawn edge to edge have no background
between cells, so the gap pipeline sees one giant connected blob instead
of one sprite per cell. Three detectors cover this:

  - `detect_tile_grid()` reads the cell pitch straight off the sheet's
    own edge periodicity -- the average colour discontinuity along a
    candidate pitch's cut lines versus the sheet's average. This is the
    only signal available when there is no background anywhere. Note
    that every MULTIPLE of the true pitch also lines up with real tile
    boundaries, so it deliberately takes the smallest pitch scoring near
    the best, or a 16px tileset reads as 32 or 80.
  - `detect_grid_layout()` scores cell sizes the sheet divides evenly by
    against content occupancy and uniformity.
  - `segment_grid()` then cuts along those lines regardless of pixel
    connectivity.

**Shattering -- too many gaps.** Animation and effect sheets have frames
made of flying debris or scattered sparkles: parts of ONE frame sit far
apart, and individual particles are small enough that
`find_components()` discards them as speckle, so whole frames go
missing. `detect_separator_grid()` finds the frame pitch by searching
for a period AND phase whose every cut line is a fully background row or
column -- a cut that cannot, by construction, slice through any pixel
blob. `regroup_by_grid()` then collapses the gap result into those
cells. That step is merge-only: a sprite the gap stage already joined
across a background gap unions its cells rather than being split, so the
disconnected-leaf-and-stem case survives untouched.

`segment_sheet(mode="auto")` runs the gap pipeline, diagnoses which (if
either) failure signature is present, and applies the matching
correction; with no signature, the gap result is returned untouched.
`mode="grid"` forces a grid cut; `mode="gap"` forces the original
pipeline and skips every correction.
"""

from __future__ import annotations

from dataclasses import dataclass, field

import numpy as np
from scipy import ndimage

from config import (
    COMPONENT_MERGE_GAP_BASE,
    COMPONENT_MERGE_GAP_MAX,
    MAX_SPRITE_AREA_FRACTION,
    MIN_SPRITE_SIZE_PX,
)
from image_utils import BBox


@dataclass
class RawComponent:
    """A single 8-connected pixel blob before any merging."""
    label_id: int
    bbox: BBox
    pixel_count: int
    mask_slice: tuple[slice, slice]  # slice into the full-sheet label array


@dataclass
class SpriteGroup:
    """One or more RawComponents merged into a single logical sprite."""
    components: list[RawComponent]
    bbox: BBox = field(init=False)
    pixel_count: int = field(init=False)

    def __post_init__(self):
        box = self.components[0].bbox
        total_px = 0
        for c in self.components[1:]:
            box = box.union(c.bbox)
        for c in self.components:
            total_px += c.pixel_count
        self.bbox = box
        self.pixel_count = total_px


@dataclass
class DetectedSprite:
    sprite_index: int
    bbox: BBox
    confidence: float
    confidence_reasons: list[str]
    component_count: int
    pixel_count: int
    # Which path produced this sprite: "gap", "tile", "separator" or
    # "divisor". Downstream consumers use it as a provenance fact rather
    # than a guess -- a sprite cut from a detected tile grid IS a tileset
    # tile, and one cut from a separator grid IS an animation frame.
    source: str = "gap"


# ---------------------------------------------------------------------------
# Stage 1: raw connected components
# ---------------------------------------------------------------------------

def find_foreground_regions(foreground_mask: np.ndarray) -> np.ndarray:
    """
    Light morphological cleanup: remove single-pixel salt noise that would
    otherwise create thousands of spurious 1px "components" on scraped /
    lightly-compressed sheets. Does NOT touch the sprites that will actually
    be exported (this mask is used only to decide component membership).
    """
    # Fill tiny 1-pixel holes inside otherwise-solid foreground (common with
    # lossy-compressed sheets that have single stray background-colored
    # pixels inside a sprite body).
    filled = ndimage.binary_closing(foreground_mask, structure=np.ones((2, 2)), iterations=1)
    return filled | foreground_mask  # never remove pixels, only ever add back


def find_components(foreground_mask: np.ndarray) -> tuple[np.ndarray, list[RawComponent], list[RawComponent]]:
    """
    8-connected component labelling on the foreground mask.

    Returns the integer label array, a RawComponent per usable label, and a
    THIRD list holding the sub-MIN_SPRITE_SIZE_PX blobs that were rejected
    as noise. The gap-based pipeline ignores that third list exactly as
    before -- a lone 1px speck really is speckle and must not become a
    sprite. It is returned rather than discarded because a scattered
    1-2px particle is indistinguishable from speckle *locally*, and only
    becomes meaningful once a grid tells us it belongs inside a specific
    animation frame (see `regroup_by_grid`). Sheets whose frames are made
    of loose particles used to lose those frames entirely here.
    """
    structure = np.ones((3, 3), dtype=int)  # 8-connectivity
    labels, num = ndimage.label(foreground_mask, structure=structure)

    components: list[RawComponent] = []
    noise: list[RawComponent] = []
    objects = ndimage.find_objects(labels)
    for label_id, slc in enumerate(objects, start=1):
        if slc is None:
            continue
        ys, xs = slc
        sub_mask = labels[slc] == label_id
        pixel_count = int(sub_mask.sum())
        if pixel_count == 0:
            continue
        bbox = BBox(x=xs.start, y=ys.start, width=xs.stop - xs.start, height=ys.stop - ys.start)
        comp = RawComponent(label_id=label_id, bbox=bbox, pixel_count=pixel_count, mask_slice=slc)
        if max(bbox.width, bbox.height) < MIN_SPRITE_SIZE_PX and pixel_count < MIN_SPRITE_SIZE_PX:
            noise.append(comp)
            continue
        components.append(comp)

    return labels, components, noise


# ---------------------------------------------------------------------------
# Stage 2: decide which raw components belong to the same sprite
# ---------------------------------------------------------------------------

# Largest factor `_should_merge` can ever apply on top of the adaptive gap
# threshold (the axis-alignment bonus for small fragments). Kept as a named
# constant because `merge_related_components` relies on it to compute a
# provably-safe pre-filter bound: no pair whose bounding-box gap exceeds
# COMPONENT_MERGE_GAP_MAX * this can possibly merge.
ALIGNMENT_BONUS_MULTIPLIER = 1.4


def _adaptive_gap_threshold(a: RawComponent, b: RawComponent) -> float:
    """
    The allowed gap between two components scales with how *small* they
    are. Two tiny (e.g. 2x2) fragments a few pixels apart are very likely
    stray parts of the same small sprite (like the disconnected leaf/stem
    example in the spec). Two large, well-formed components a similar
    absolute distance apart are much more likely to be separate sprites --
    so the allowed gap shrinks as component size grows.
    """
    size_a = max(a.bbox.width, a.bbox.height)
    size_b = max(b.bbox.width, b.bbox.height)
    smaller = min(size_a, size_b)

    # Small components (<=6px) get a generous relative allowance -- they're
    # the disconnected-fragment case (a stray leaf/stem pixel group a couple
    # of pixels away from the rest of its own sprite). As components grow
    # past that, a real sprite's own internal gaps are rarely more than 1-2
    # px, so the threshold drops toward the base gap quickly to avoid
    # bridging two separately-placed sprites on the sheet.
    if smaller <= 6:
        factor = COMPONENT_MERGE_GAP_MAX
    elif smaller <= 12:
        factor = COMPONENT_MERGE_GAP_BASE + 1
    else:
        factor = COMPONENT_MERGE_GAP_BASE

    return max(1.0, min(COMPONENT_MERGE_GAP_MAX, factor))


def _should_merge(a: RawComponent, b: RawComponent, local_density: float) -> bool:
    """
    Combine every signal from the spec into one merge decision:
      - horizontal gap / vertical gap (independently, via BBox.gap_to)
      - component distance overall
      - component size (adaptive threshold, see above)
      - bounding box overlap short-circuits to True
      - local density shrinks the allowed gap in crowded sheet regions
      - alignment: components that overlap substantially on one axis are
        more likely a single sprite's disconnected parts (e.g. stem below
        leaf) than two side-by-side sprites
    """
    dx, dy = a.bbox.gap_to(b.bbox)

    # Overlapping or touching bounding boxes -> always the same sprite.
    if dx <= 0 and dy <= 0:
        return True

    threshold = _adaptive_gap_threshold(a, b)
    # Crowded regions of the sheet (many small sprites close together)
    # shrink the merge radius so neighbours don't get fused.
    threshold *= max(0.4, 1.0 - 0.5 * local_density)

    # Axis alignment bonus: only meaningful for small fragments (the
    # disconnected-part case). For components already large enough to be
    # plausible standalone sprites on their own, two boxes sharing a row/
    # column band is completely normal for a *grid* of separate sprites, so
    # alignment must NOT be used to justify a bigger merge radius there.
    smaller_size = min(max(a.bbox.width, a.bbox.height), max(b.bbox.width, b.bbox.height))
    if smaller_size <= 8:
        x_overlap = min(a.bbox.x2, b.bbox.x2) - max(a.bbox.x, b.bbox.x)
        y_overlap = min(a.bbox.y2, b.bbox.y2) - max(a.bbox.y, b.bbox.y)
        aligned = (x_overlap > 0.3 * min(a.bbox.width, b.bbox.width)) or \
                  (y_overlap > 0.3 * min(a.bbox.height, b.bbox.height))
        if aligned:
            threshold *= ALIGNMENT_BONUS_MULTIPLIER

    # The effective distance is the max of the two independent gaps (a
    # diagonal gap of e.g. dx=1,dy=1 should not need a huge threshold).
    effective_gap = max(dx, dy)
    return effective_gap <= threshold


def _local_density(
    index: int,
    all_components: list[RawComponent],
    radius: float,
    buckets: dict[tuple[int, int], list[int]],
) -> float:
    """
    Fraction-like density signal: how many other component centers fall
    within `radius` pixels of this component's center, normalized to a
    0..1-ish range. Used to shrink merge distance in crowded sheet areas.

    `buckets` must be a `_spatial_buckets` index built at this same
    radius; it only restricts which candidates are enumerated, so the
    counted set is exactly the same as a full scan would produce.
    """
    component = all_components[index]
    cx, cy = component.bbox.cx, component.bbox.cy
    count = 0
    for j in _bucket_neighbours(buckets, component, radius):
        if j == index:
            continue
        other = all_components[j]
        ox, oy = other.bbox.cx, other.bbox.cy
        if ((ox - cx) ** 2 + (oy - cy) ** 2) ** 0.5 <= radius:
            count += 1
    return min(1.0, count / 6.0)


def _spatial_buckets(components: list[RawComponent], cell_size: float) -> dict[tuple[int, int], list[int]]:
    """
    Index component centers into a uniform grid of `cell_size` squares.

    Both pairwise passes below only ever care about components within some
    radius R of each other, and bucketing at cell_size=R means every such
    partner is in one of the 9 surrounding buckets. That turns two O(n^2)
    sweeps into roughly linear ones, WITHOUT changing which pairs are
    considered: the same distance test still decides every pair, only the
    hopeless ones are never enumerated. A 2048x2048 sheet holding ~16k
    components used to spend minutes here.
    """
    buckets: dict[tuple[int, int], list[int]] = {}
    for i, c in enumerate(components):
        key = (int(c.bbox.cx // cell_size), int(c.bbox.cy // cell_size))
        buckets.setdefault(key, []).append(i)
    return buckets


def _bucket_neighbours(
    buckets: dict[tuple[int, int], list[int]], component: RawComponent, cell_size: float,
):
    """Indices of components in the 3x3 bucket block around `component`."""
    kx = int(component.bbox.cx // cell_size)
    ky = int(component.bbox.cy // cell_size)
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            yield from buckets.get((kx + dx, ky + dy), ())


def merge_related_components(components: list[RawComponent]) -> list[SpriteGroup]:
    """
    Union-find over raw components using `_should_merge` as the edge test.
    Runs in O(n^2) which is fine up to a few thousand components (typical
    sprite sheets); for pathologically dense sheets this is still bounded
    by MAX_FILES_PER_ZIP / practical sheet sizes.
    """
    n = len(components)
    if n == 0:
        return []

    parent = list(range(n))

    def find(i: int) -> int:
        while parent[i] != i:
            parent[i] = parent[parent[i]]
            i = parent[i]
        return i

    def union(i: int, j: int) -> None:
        ri, rj = find(i), find(j)
        if ri != rj:
            parent[ri] = rj

    # Precompute a density radius from the median component size so it
    # adapts to the sheet's own scale (16px sprites vs 128px sprites).
    sizes = sorted(max(c.bbox.width, c.bbox.height) for c in components)
    median_size = sizes[len(sizes) // 2] if sizes else 16
    density_radius = max(24.0, median_size * 3.0)

    density_buckets = _spatial_buckets(components, density_radius)
    densities = [_local_density(i, components, density_radius, density_buckets) for i in range(n)]

    # Only compare components that are reasonably close (broad-phase via a
    # generous bounding radius) to keep this fast on large sheets.
    broad_radius = max(64.0, median_size * (COMPONENT_MERGE_GAP_MAX + 4))
    merge_buckets = _spatial_buckets(components, broad_radius)

    # Vectorised narrow phase. `_should_merge` can only ever return True
    # when the two bounding boxes overlap or their gap is within
    # COMPONENT_MERGE_GAP_MAX * ALIGNMENT_BONUS_MULTIPLIER (every other
    # factor in it only ever shrinks the threshold), so gap-testing whole
    # candidate arrays at once and calling the real decision function only
    # for survivors is exact -- it changes nothing about which pairs merge,
    # it just stops evaluating the hopeless majority one at a time.
    max_gap = COMPONENT_MERGE_GAP_MAX * ALIGNMENT_BONUS_MULTIPLIER
    x1 = np.array([c.bbox.x for c in components], dtype=np.float64)
    y1 = np.array([c.bbox.y for c in components], dtype=np.float64)
    x2 = np.array([c.bbox.x2 for c in components], dtype=np.float64)
    y2 = np.array([c.bbox.y2 for c in components], dtype=np.float64)
    cxs = np.array([c.bbox.cx for c in components], dtype=np.float64)
    cys = np.array([c.bbox.cy for c in components], dtype=np.float64)

    for i in range(n):
        ci = components[i]
        cand = np.fromiter(
            (j for j in _bucket_neighbours(merge_buckets, ci, broad_radius) if j > i),
            dtype=np.int64,
        )
        if cand.size == 0:
            continue
        dcx = cxs[i] - cxs[cand]
        dcy = cys[i] - cys[cand]
        near = (dcx * dcx + dcy * dcy) <= broad_radius * broad_radius
        gap_x = np.maximum(x1[cand] - x2[i], x1[i] - x2[cand])
        gap_y = np.maximum(y1[cand] - y2[i], y1[i] - y2[cand])
        keep = near & (np.maximum(gap_x, gap_y) <= max_gap)
        for j in cand[keep]:
            j = int(j)
            local_density = max(densities[i], densities[j])
            if _should_merge(ci, components[j], local_density):
                union(i, j)

    groups: dict[int, list[RawComponent]] = {}
    for i, comp in enumerate(components):
        root = find(i)
        groups.setdefault(root, []).append(comp)

    return [SpriteGroup(components=comps) for comps in groups.values()]


# ---------------------------------------------------------------------------
# Stage 3: boundaries
# ---------------------------------------------------------------------------

def detect_sprite_boundaries(groups: list[SpriteGroup], sheet_shape: tuple[int, int]) -> list[SpriteGroup]:
    """
    Clip each group's bounding box to the sheet bounds and drop groups that
    are implausibly large (almost certainly a background-detection failure
    rather than a real sprite -- e.g. background bled through as
    foreground). Those cases still show up to the user, just via the
    confidence step, not silently dropped here; this stage only clips.
    """
    h, w = sheet_shape
    out = []
    sheet_area = h * w
    for g in groups:
        b = g.bbox
        clipped = BBox(
            x=max(0, b.x),
            y=max(0, b.y),
            width=min(w, b.x2) - max(0, b.x),
            height=min(h, b.y2) - max(0, b.y),
        )
        if clipped.width <= 0 or clipped.height <= 0:
            continue
        g.bbox = clipped
        # Sanity clamp -- extreme outliers are kept (never silently drop a
        # detection) but will receive a low confidence score below.
        out.append(g)
        _ = sheet_area  # reserved for future area-ratio heuristics
    return out


# ---------------------------------------------------------------------------
# Stage 4: confidence scoring
# ---------------------------------------------------------------------------

def calculate_segmentation_confidence(
    group: SpriteGroup,
    sheet_shape: tuple[int, int],
    all_groups: list[SpriteGroup],
) -> tuple[float, list[str]]:
    """
    Heuristic 0-100 confidence that a SpriteGroup is a single, cleanly
    segmented sprite. Lower confidence => surfaced to the user as
    "possible segmentation problem" and excluded from batch auto-accept.
    """
    has_close_neighbour = any(
        max(*group.bbox.gap_to(g.bbox)) < NEIGHBOUR_GAP_THRESHOLD
        for g in all_groups if g is not group
    )
    return _confidence_for(
        bbox=group.bbox,
        pixel_count=group.pixel_count,
        component_count=len(group.components),
        sheet_shape=sheet_shape,
        has_close_neighbour=has_close_neighbour,
    )


# A sprite whose nearest neighbour is closer than this is flagged as a
# possible under/over-merge right at the boundary.
NEIGHBOUR_GAP_THRESHOLD = 2


def _close_neighbour_flags(bboxes: list[BBox], threshold: int = NEIGHBOUR_GAP_THRESHOLD) -> list[bool]:
    """
    Per bounding box: is any OTHER box closer than `threshold` pixels?

    Answering this by comparing every pair is O(n^2), which is invisible
    on a 20-sprite sheet and ruinous on a large tileset -- a 1024x1024
    sheet cut into 4096 tiles spent ~45s here alone. Boxes are instead
    bucketed into a uniform grid; two boxes that close necessarily share
    a bucket once each is expanded by `threshold`, so the answer is
    identical, just without enumerating the hopeless pairs.
    """
    n = len(bboxes)
    flags = [False] * n
    if n < 2:
        return flags

    sizes = sorted(max(b.width, b.height) for b in bboxes)
    cell = float(max(8, sizes[len(sizes) // 2]))

    buckets: dict[tuple[int, int], list[int]] = {}
    oversized: list[int] = []
    for i, b in enumerate(bboxes):
        kx0, kx1 = int((b.x - threshold) // cell), int((b.x2 + threshold) // cell)
        ky0, ky1 = int((b.y - threshold) // cell), int((b.y2 + threshold) // cell)
        # A box far larger than the sheet's typical sprite would be
        # registered in a huge number of buckets; compare those few
        # against everything instead.
        if (kx1 - kx0 + 1) * (ky1 - ky0 + 1) > 256:
            oversized.append(i)
            continue
        for kx in range(kx0, kx1 + 1):
            for ky in range(ky0, ky1 + 1):
                buckets.setdefault((kx, ky), []).append(i)

    def mark(i: int, j: int) -> None:
        if flags[i] and flags[j]:
            return
        gap_x, gap_y = bboxes[i].gap_to(bboxes[j])
        if max(gap_x, gap_y) < threshold:
            flags[i] = True
            flags[j] = True

    for members in buckets.values():
        for a in range(len(members)):
            for b in range(a + 1, len(members)):
                mark(members[a], members[b])

    for i in oversized:
        for j in range(n):
            if i != j:
                mark(i, j)

    return flags


def _confidence_for(
    bbox: BBox,
    pixel_count: int,
    component_count: int,
    sheet_shape: tuple[int, int],
    has_close_neighbour: bool,
    grid_backed: bool = False,
) -> tuple[float, list[str]]:
    """
    Shared confidence heuristic.

    `grid_backed=True` means the sprite's boundaries came from a validated
    grid (every cut line was verified to be pure background, or a tile
    pitch confirmed by the sheet's own edge periodicity) rather than from
    the gap heuristic. For those, "several disconnected pieces" and "sparse
    bounding box" are the EXPECTED shape of a correct result -- a single
    explosion frame is legitimately a cloud of loose particles -- so those
    two penalties are skipped. The structural penalties (extreme aspect
    ratio, covering most of the sheet) still apply, because those would
    indicate a bad grid rather than an unusual sprite.
    """
    reasons: list[str] = []
    score = 100.0
    h, w = sheet_shape
    b = bbox

    # Signal: many disconnected raw components merged together is riskier
    # than a single clean component.
    if not grid_backed and component_count > 1:
        penalty = min(25, (component_count - 1) * 8)
        score -= penalty
        reasons.append("Multiple disconnected regions")

    # Signal: extreme aspect ratio (long thin fence/wall segments are
    # legitimate per the spec, but they ARE harder to segment correctly,
    # so flag rather than silently trust).
    aspect = b.width / max(1, b.height)
    if aspect > 6 or aspect < (1 / 6):
        score -= 12
        reasons.append("Unusual bounding box (extreme aspect ratio)")

    # Signal: sprite occupies a very large fraction of the whole sheet --
    # likely a background/segmentation failure rather than one sprite.
    area_fraction = b.area / max(1, h * w)
    if area_fraction > MAX_SPRITE_AREA_FRACTION:
        score -= 30
        reasons.append("Bounding box covers most of the sheet")

    # Signal: pixel density inside the bbox (sparse boxes suggest a bad
    # merge that bridged two things with a lot of empty space between).
    density = pixel_count / max(1, b.area)
    if not grid_backed and density < 0.08:
        score -= 15
        reasons.append("Very sparse bounding box (large empty gaps)")

    # Signal: very small gap to nearest neighbour sprite -> risk of an
    # under-merge or over-merge right at the boundary. Meaningless for a
    # grid-backed sprite: tiles in a tileset touch their neighbours by
    # definition, so this would fire on every single correct tile.
    if not grid_backed and has_close_neighbour:
        score -= 10
        reasons.append("Very small gap between neighboring regions")

    score = max(0.0, min(100.0, score))
    return score, reasons


# ---------------------------------------------------------------------------
# Grid segmentation (portrait/expression sheets with zero gap between cells)
# ---------------------------------------------------------------------------

@dataclass
class GridLayout:
    cell_width: int
    cell_height: int
    columns: int
    rows: int
    offset_x: int  # leading border/padding before the first column, if any
    offset_y: int  # leading border/padding before the first row, if any
    score: float    # 0-100 confidence this is really the sheet's grid
    # Which detector produced this layout: "divisor" (cell size the sheet
    # divides evenly by, scored on content), "separator" (every cut line
    # verified to be pure background) or "tile" (cell pitch confirmed by
    # the sheet's own edge periodicity).
    source: str = "divisor"
    # Cells that actually contain foreground. 0 when not computed.
    occupied_cells: int = 0


def _grid_candidate_divisors(length: int) -> list[tuple[int, int, int]]:
    """
    For a sheet dimension `length`, return (cell_size, count, offset)
    triples for every candidate cell size in GRID_CANDIDATE_SIZES that
    divides it evenly into 2+ cells (within GRID_DIVISION_TOLERANCE_PX of
    a whole number of cells, allowing a small leading border/offset).

    NOTE: single-row/single-column grids (count==1 on one axis) are
    intentionally NOT included here. This detector only scores a cell
    size against content statistics, which cannot reliably tell "this
    cell correctly covers one sprite" from "this cell is too big and
    merges two stacked sprites into one" -- accepting single-axis
    candidates here regressed real multi-row sheets. Horizontal
    animation strips, which is what needed them, are handled by
    `detect_separator_grid()` instead: it verifies that every cut line is
    actually background rather than inferring it from occupancy, and its
    cell size does not have to divide the sheet evenly at all.
    """
    from config import GRID_CANDIDATE_SIZES, GRID_DIVISION_TOLERANCE_PX

    out = []
    for size in GRID_CANDIDATE_SIZES:
        if size > length:
            continue
        # Try zero offset first (most common), then small offsets to
        # tolerate a thin border/padding strip before the grid starts.
        for offset in range(0, GRID_DIVISION_TOLERANCE_PX + 1):
            usable = length - offset
            count = usable // size
            remainder = usable % size
            if count >= 2 and remainder <= GRID_DIVISION_TOLERANCE_PX:
                out.append((size, count, offset))
                break  # smallest working offset for this size is enough
    return out


def detect_grid_layout(foreground_mask: np.ndarray) -> GridLayout | None:
    """
    Look for a regular cell grid the sheet's width and height both divide
    evenly by, then score each candidate by how well actual foreground
    content aligns with it: a real grid should have most cells containing
    a meaningful amount of foreground (not mostly-empty cells), and
    foreground density shouldn't spike right at the cell boundaries in a
    way that suggests the boundary is cutting through the middle of a
    sprite rather than between sprites.

    Returns the best-scoring GridLayout, or None if nothing plausible was
    found (e.g. a sheet with an irregular sprite count/spacing that
    genuinely isn't a grid).
    """
    h, w = foreground_mask.shape
    width_candidates = _grid_candidate_divisors(w)
    height_candidates = _grid_candidate_divisors(h)
    if not width_candidates or not height_candidates:
        return None

    best: GridLayout | None = None
    for cell_w, cols, off_x in width_candidates:
        for cell_h, rows, off_y in height_candidates:
            if cols * rows < 2:
                continue  # a single "grid cell" isn't a grid
            score = _score_grid_candidate(foreground_mask, cell_w, cell_h, cols, rows, off_x, off_y)
            if best is None or score > best.score:
                best = GridLayout(
                    cell_width=cell_w, cell_height=cell_h, columns=cols, rows=rows,
                    offset_x=off_x, offset_y=off_y, score=score,
                )

    return best


def _score_grid_candidate(
    foreground_mask: np.ndarray, cell_w: int, cell_h: int, cols: int, rows: int, off_x: int, off_y: int,
) -> float:
    """
    0-100 plausibility score for one grid candidate. Combines:
      - occupancy: fraction of cells that actually contain a meaningful
        amount of foreground (an empty-looking grid is probably the
        wrong cell size, e.g. treating one sprite's sub-region as if it
        were a whole grid)
      - uniformity: how similar each occupied cell's foreground pixel
        count is to the others (real per-cell sprites tend to be
        similarly sized; wildly uneven cell content suggests the grid
        lines are cutting sprites in half rather than falling between
        them)
      - a size prior: prefers fewer, larger cells over many tiny ones
        when both fit equally well, since spurious small-cell-size
        matches are common (e.g. 8px dividing evenly almost always) but
        rarely the sheet's *actual* sprite grid
    """
    h, w = foreground_mask.shape
    cell_pixel_counts = []
    for r in range(rows):
        for c in range(cols):
            y0 = off_y + r * cell_h
            x0 = off_x + c * cell_w
            cell = foreground_mask[y0:y0 + cell_h, x0:x0 + cell_w]
            cell_pixel_counts.append(int(cell.sum()))

    total_cells = len(cell_pixel_counts)
    if total_cells == 0:
        return 0.0

    cell_area = cell_w * cell_h
    occupied = [c for c in cell_pixel_counts if c > 0.02 * cell_area]
    occupancy_fraction = len(occupied) / total_cells

    if len(occupied) < 2:
        return 0.0  # can't judge uniformity with 0-1 real cells; not a usable grid

    mean_occ = sum(occupied) / len(occupied)
    if mean_occ == 0:
        return 0.0
    variance = sum((v - mean_occ) ** 2 for v in occupied) / len(occupied)
    coefficient_of_variation = (variance ** 0.5) / mean_occ
    uniformity = max(0.0, 1.0 - min(1.0, coefficient_of_variation))

    size_prior = min(1.0, cell_area / 1024.0)  # favors cells >= ~32x32 fully, tapers below that

    score = 100.0 * (0.5 * occupancy_fraction + 0.35 * uniformity + 0.15 * size_prior)
    return score


def _occupied_grid_cells(
    foreground_mask: np.ndarray, layout: GridLayout,
) -> dict[tuple[int, int], dict]:
    """
    Per grid cell that holds any foreground: its pixel bounds, its tight
    content bbox and its pixel count. Keyed by (row, column).
    """
    h, w = foreground_mask.shape
    row_range, col_range = _content_cell_ranges(foreground_mask, layout)
    cells: dict[tuple[int, int], dict] = {}
    for r in row_range:
        y0, y1 = _cell_bounds(layout.offset_y, layout.cell_height, r, h)
        if y1 <= y0:
            continue
        band = foreground_mask[y0:y1]
        if not band.any():
            continue
        for c in col_range:
            x0, x1 = _cell_bounds(layout.offset_x, layout.cell_width, c, w)
            if x1 <= x0:
                continue
            cell = band[:, x0:x1]
            if not cell.any():
                continue
            ys, xs = np.nonzero(cell)
            cells[(r, c)] = {
                "bounds": (x0, y0, x1, y1),
                "bbox": BBox(
                    x=x0 + int(xs.min()), y=y0 + int(ys.min()),
                    width=int(xs.max()) - int(xs.min()) + 1,
                    height=int(ys.max()) - int(ys.min()) + 1,
                ),
                "pixels": int(cell.sum()),
            }
    return cells


def _composite_cell_groups(
    foreground_mask: np.ndarray, layout: GridLayout, cells: dict[tuple[int, int], dict],
) -> list[list[tuple[int, int]]]:
    """
    Group grid cells that are all part of ONE connected piece of artwork
    into a single composite object.

    A ladder, door or pillar drawn across two or three cells is one object;
    cutting it into per-cell fragments produces training samples that mean
    nothing on their own. What identifies such an object is that it is a
    self-contained island of artwork -- background all around it -- that
    happens to be wider or taller than one cell.

    Merging is deliberately keyed on connected-component identity rather
    than on "do these two neighbouring cells touch at the border". The
    border test looks equivalent but is not: two adjacent flat filler tiles
    touch along their whole shared edge and would be fused into a nonsense
    sprite, while genuinely interchangeable terrain tiles all touch each
    other as well.

    Component identity alone is still not enough, because a dungeon's
    floor and walls are also one enormous connected region. The two are
    told apart by extent: a composite object covers a handful of cells,
    terrain covers dozens. Components over GRID_COMPOSITE_MAX_CELLS, or
    too scattered to fill their own cell bounding box, stay per-cell.

    Note this is inherently a no-op for separator grids: their cut lines
    are pure background by construction, so no component can ever span one.
    """
    from config import GRID_COMPOSITE_MAX_CELLS, GRID_COMPOSITE_MIN_FILL

    labels, count = ndimage.label(foreground_mask, structure=np.ones((3, 3), dtype=int))
    if count == 0:
        return [[key] for key in cells]

    # Each cell is attributed to whichever component owns most of its
    # pixels, so a stray speck from a neighbouring object cannot drag a
    # cell into the wrong group.
    by_component: dict[int, list[tuple[int, int]]] = {}
    for key, info in cells.items():
        x0, y0, x1, y1 = info["bounds"]
        patch = labels[y0:y1, x0:x1]
        patch = patch[patch > 0]
        if patch.size == 0:
            by_component.setdefault(-hash(key), []).append(key)
            continue
        values, counts = np.unique(patch, return_counts=True)
        dominant = int(values[int(np.argmax(counts))])
        by_component.setdefault(dominant, []).append(key)

    out: list[list[tuple[int, int]]] = []
    for members in by_component.values():
        if len(members) == 1:
            out.append(members)
            continue
        rows = [r for r, _ in members]
        cols = [c for _, c in members]
        span = (max(rows) - min(rows) + 1) * (max(cols) - min(cols) + 1)
        fill = len(members) / max(1, span)
        if len(members) <= GRID_COMPOSITE_MAX_CELLS and fill >= GRID_COMPOSITE_MIN_FILL:
            out.append(members)
        else:
            out.extend([[m] for m in members])
    return out


def segment_grid(
    foreground_mask: np.ndarray, layout: GridLayout, merge_composites: bool = True,
) -> list[DetectedSprite]:
    """
    Cut the sheet strictly along the given grid lines, tightly cropped to
    each cell's actual foreground content (so a character portrait's bbox
    doesn't include the cell's empty margin). Cells with no foreground at
    all are skipped (e.g. a grid sized for the fullest row, where a later
    row has fewer expressions than others).

    With `merge_composites` (the default), neighbouring cells whose artwork
    runs across the shared border are rejoined into one sprite -- see
    `_composite_cell_groups`.
    """
    h, w = foreground_mask.shape
    cells = _occupied_grid_cells(foreground_mask, layout)
    if not cells:
        return []

    groups = (
        _composite_cell_groups(foreground_mask, layout, cells)
        if merge_composites
        else [[key] for key in cells]
    )

    entries = []
    for members in groups:
        box = None
        pixels = 0
        for key in members:
            info = cells[key]
            box = info["bbox"] if box is None else box.union(info["bbox"])
            pixels += info["pixels"]
        entries.append((box, pixels, len(members)))

    entries.sort(key=lambda e: (round(e[0].y / 8), e[0].x))

    base_reason = f"Grid cell ({layout.cell_width}x{layout.cell_height}, {layout.source})"
    detected: list[DetectedSprite] = []
    for idx, (box, pixels, cell_count) in enumerate(entries, start=1):
        reasons = [base_reason]
        if cell_count > 1:
            reasons.append(f"Composite object spanning {cell_count} grid cells")
        detected.append(
            DetectedSprite(
                sprite_index=idx,
                bbox=box,
                confidence=min(100.0, 80.0 + layout.score * 0.2),
                confidence_reasons=reasons,
                component_count=cell_count,
                pixel_count=pixels,
                source=layout.source,
            )
        )
    return detected


# ---------------------------------------------------------------------------
# Separator grid (animation strips / frame sheets with background gutters)
# ---------------------------------------------------------------------------

def _empty_run_widths(empty: np.ndarray) -> np.ndarray:
    """
    For every index, the length of the run of empty lines it belongs to
    (0 for non-empty indices). Used to tell a real frame gutter from an
    incidental one-pixel gap that happens to fall inside a frame.
    """
    widths = np.zeros(empty.shape, dtype=np.int32)
    n = len(empty)
    i = 0
    while i < n:
        if not empty[i]:
            i += 1
            continue
        j = i
        while j < n and empty[j]:
            j += 1
        widths[i:j] = j - i
        i = j
    return widths


def _axis_separator_period(empty: np.ndarray, min_cell: int) -> tuple[int, int, int] | None:
    """
    Best (cell_size, first_cut_line, cut_line_count) along one axis such
    that EVERY cut line the grid would make falls on a fully-background
    row/column.

    That constraint is the whole point: a cut line made of pure background
    cannot possibly slice through a connected pixel blob, so this grid can
    never chop a sprite in half.

    Both the period AND its phase have to be searched. A 10x10 lattice of
    8px sprites at an 11px pitch has its gutters at 8, 19, 30, ... -- the
    period is 11 but the phase is 8, and searching only phase 0 finds a
    much coarser (and badly wrong) period instead.

    Among the legal candidates, "smallest period" is NOT a safe choice on
    its own: a frame made of scattered particles usually contains some
    incidental empty line, and a short period threading those gaps is
    legal yet cuts frames in half. So candidates are scored by

        number of cells  x  min(width of the thinnest gutter used, cap)

    which rewards a fine partition, but only one whose every cut sits in a
    gutter wide enough to be a real frame separator rather than a lucky
    1px gap inside one. The cap stops a huge trailing empty margin from
    buying a needlessly coarse grid.

    Returns None when the axis has no usable periodic gutter structure
    (e.g. an edge-to-edge tileset with no background columns at all, or a
    sheet holding a single sprite).
    """
    from config import GRID_SEPARATOR_GUTTER_CAP_PX, GRID_SEPARATOR_MAX_CELL_PX

    content = np.nonzero(~empty)[0]
    if content.size == 0:
        return None
    first, last = int(content[0]), int(content[-1])
    span = last - first + 1

    max_cell = min(GRID_SEPARATOR_MAX_CELL_PX, max(min_cell, span // 2))

    # Every content position except the very first one (cut lines are only
    # meaningful strictly inside the content span).
    interior = content[1:]
    if interior.size == 0:
        return None

    widths = _empty_run_widths(empty)
    cap = GRID_SEPARATOR_GUTTER_CAP_PX

    best_score = 0.0
    best: tuple[int, int, int] | None = None

    for cell in range(min_cell, max_cell + 1):
        # No phase at this period can beat the incumbent any more, and the
        # bound only shrinks as cells get larger -- stop entirely.
        if (span // cell + 1) * cap <= best_score:
            break

        # A phase is disqualified by any single content pixel sitting on
        # it, so the whole phase sweep is one modulo pass -- far cheaper
        # than testing each phase's lines separately.
        blocked = np.zeros(cell, dtype=bool)
        blocked[np.unique(interior % cell)] = True

        for phase in np.nonzero(~blocked)[0]:
            start = int(phase) + ((first - int(phase)) // cell + 1) * cell
            if start <= first:
                start += cell
            if start > last:
                continue
            lines = np.arange(start, last + 1, cell)
            score = (lines.size + 1) * min(cap, int(widths[lines].min()))
            if score > best_score:
                best_score = score
                best = (cell, start, int(lines.size))

    return best


def _cell_bounds(origin: int, cell: int, index: int, length: int) -> tuple[int, int]:
    """
    Pixel range of grid cell `index`, where cell i spans
    [origin + i*cell, origin + (i+1)*cell).

    `origin` may be negative (a separator grid's first cut line can sit
    partway into the sheet, making cell 0 a short leading cell). Cell 0 is
    additionally extended back to 0 and the last cell forward to `length`,
    so a thin border strip outside the grid proper is never dropped.
    """
    start = 0 if index == 0 else max(0, origin + index * cell)
    end = min(length, origin + (index + 1) * cell)
    return start, max(start, end)


def _content_cell_ranges(
    foreground_mask: np.ndarray, layout: GridLayout,
) -> tuple[range, range]:
    """
    Row and column cell indices that can possibly hold content.

    A grid can nominally span the whole sheet in cells only a few pixels
    wide, which on a large sheet is millions of cells -- almost all of
    them provably empty. Walking only the cells intersecting the
    foreground's bounding box visits the same non-empty cells while
    keeping the loops proportional to the content, not the canvas.
    """
    h, w = foreground_mask.shape
    rows_any = np.nonzero(foreground_mask.any(axis=1))[0]
    cols_any = np.nonzero(foreground_mask.any(axis=0))[0]
    if rows_any.size == 0 or cols_any.size == 0:
        return range(0), range(0)

    def span(origin: int, cell: int, lo: int, hi: int, count: int) -> range:
        first = max(0, (lo - origin) // cell)
        last = min(count - 1, (hi - origin) // cell)
        return range(int(first), int(last) + 1)

    return (
        span(layout.offset_y, layout.cell_height, int(rows_any[0]), int(rows_any[-1]), layout.rows),
        span(layout.offset_x, layout.cell_width, int(cols_any[0]), int(cols_any[-1]), layout.columns),
    )


def _grid_cell_counts(foreground_mask: np.ndarray, layout: GridLayout) -> int:
    """Number of grid cells holding at least one foreground pixel."""
    h, w = foreground_mask.shape
    row_range, col_range = _content_cell_ranges(foreground_mask, layout)
    occupied = 0
    for r in row_range:
        y0, y1 = _cell_bounds(layout.offset_y, layout.cell_height, r, h)
        if y1 <= y0:
            continue
        band = foreground_mask[y0:y1]
        if not band.any():
            continue
        for c in col_range:
            x0, x1 = _cell_bounds(layout.offset_x, layout.cell_width, c, w)
            if x1 > x0 and band[:, x0:x1].any():
                occupied += 1
    return occupied


def detect_separator_grid(foreground_mask: np.ndarray) -> GridLayout | None:
    """
    Detect a periodic frame layout whose every cut line is pure background.

    This is the detector for animation strips and effect sheets: frames
    separated by a background gutter, frame size NOT necessarily a divisor
    of the sheet size (a 256px sheet of 48px frames with 16px of trailing
    padding is completely normal), and frames that are internally just a
    scatter of loose particles.

    Returns None unless both axes (or one axis, with the other treated as
    a single band) yield a period explaining at least
    GRID_SEPARATOR_MIN_CELLS occupied cells.
    """
    from config import GRID_SEPARATOR_MIN_CELL_PX, GRID_SEPARATOR_MIN_CELLS

    h, w = foreground_mask.shape
    if h == 0 or w == 0 or not foreground_mask.any():
        return None

    col_empty = ~foreground_mask.any(axis=0)
    row_empty = ~foreground_mask.any(axis=1)

    x_period = _axis_separator_period(col_empty, GRID_SEPARATOR_MIN_CELL_PX)
    y_period = _axis_separator_period(row_empty, GRID_SEPARATOR_MIN_CELL_PX)
    if x_period is None and y_period is None:
        return None

    # The layout's origin is one full cell before the first cut line, so
    # cell 0 is the (possibly short) leading cell in front of it.
    cell_w, origin_x = (x_period[0], x_period[1] - x_period[0]) if x_period else (w, 0)
    cell_h, origin_y = (y_period[0], y_period[1] - y_period[0]) if y_period else (h, 0)

    columns = max(1, -(-(w - origin_x) // cell_w))
    rows = max(1, -(-(h - origin_y) // cell_h))

    layout = GridLayout(
        cell_width=cell_w, cell_height=cell_h, columns=columns, rows=rows,
        offset_x=origin_x, offset_y=origin_y, score=90.0, source="separator",
    )
    layout.occupied_cells = _grid_cell_counts(foreground_mask, layout)
    if layout.occupied_cells < GRID_SEPARATOR_MIN_CELLS:
        return None
    return layout


# ---------------------------------------------------------------------------
# Tile grid (edge-to-edge tilesets, detected from image edge periodicity)
# ---------------------------------------------------------------------------

def _edge_energy_profiles(rgba: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
    """
    Mean absolute RGBA difference between each pair of adjacent columns and
    rows. Index i holds the discontinuity between line i and line i+1.

    A tileset's tile boundaries are where unrelated artwork meets, so they
    carry a much larger discontinuity than the (usually smooth, repetitive)
    interior of a tile -- which makes this profile a direct read-out of the
    tile pitch even when there is no background gutter anywhere on the
    sheet for `detect_separator_grid` to find.
    """
    a = rgba.astype(np.int32)
    dx = np.abs(a[:, 1:, :] - a[:, :-1, :]).sum(axis=2).mean(axis=0)
    dy = np.abs(a[1:, :, :] - a[:-1, :, :]).sum(axis=2).mean(axis=1)
    return dx, dy


def _tile_pitch_scores(profile: np.ndarray, length: int) -> dict[int, float]:
    """
    For every candidate tile size dividing `length` evenly, how much
    stronger the discontinuity along that size's cut lines is than the
    sheet's average discontinuity. 1.0 means "no better than an arbitrary
    line", i.e. no evidence of a grid at that pitch.
    """
    from config import TILE_MIN_BOUNDARY_LINES, TILE_MIN_CELL_PX

    mean_all = float(profile.mean()) if profile.size else 0.0
    if mean_all <= 0:
        return {}

    scores: dict[int, float] = {}
    for cell in range(TILE_MIN_CELL_PX, length // 2 + 1):
        if length % cell:
            continue
        lines = np.arange(1, length // cell) * cell - 1
        if lines.size < TILE_MIN_BOUNDARY_LINES:
            continue
        scores[cell] = float(profile[lines].mean() / mean_all)
    return scores


def detect_tile_grid(rgba: np.ndarray | None, foreground_mask: np.ndarray) -> GridLayout | None:
    """
    Detect a square tile pitch from the sheet's own edge periodicity.

    Every multiple of the true tile size also lines up with real tile
    boundaries (its cut lines are a subset of the true ones), so scoring
    alone always favours the largest multiple -- which is exactly how a
    16x16 dungeon tileset gets misread as 32x32 or 80x80. The search
    therefore takes the SMALLEST pitch that scores within
    TILE_EDGE_RELATIVE_TOLERANCE of the best one.

    Needs the actual RGBA pixels (a boolean foreground mask has no colour
    discontinuities to measure), and returns None without them.
    """
    from config import TILE_EDGE_MIN_RATIO, TILE_EDGE_RELATIVE_TOLERANCE

    h, w = foreground_mask.shape
    if rgba is None or rgba.ndim != 3 or rgba.shape[0] != h or rgba.shape[1] != w:
        return None
    if h < 8 or w < 8:
        return None

    dx, dy = _edge_energy_profiles(rgba)
    x_scores = _tile_pitch_scores(dx, w)
    y_scores = _tile_pitch_scores(dy, h)

    # Square tiles only -- the convention for tilesets, and requiring both
    # axes to agree is what keeps animation sheets (which show a strong
    # pitch on one axis only) out of this detector.
    shared = {c: min(x_scores[c], y_scores[c]) for c in x_scores if c in y_scores}
    if not shared:
        return None

    best = max(shared.values())
    if best < TILE_EDGE_MIN_RATIO:
        return None

    for cell in sorted(shared):
        if shared[cell] < TILE_EDGE_RELATIVE_TOLERANCE * best:
            continue
        columns, rows = w // cell, h // cell
        # Cross-check against the content-based score so a pitch that lines
        # up with strong edges but carves the content nonsensically (mostly
        # empty or wildly uneven cells) is still rejected.
        content_score = _score_grid_candidate(foreground_mask, cell, cell, columns, rows, 0, 0)
        if content_score < 50.0:
            continue
        layout = GridLayout(
            cell_width=cell, cell_height=cell, columns=columns, rows=rows,
            offset_x=0, offset_y=0,
            score=min(100.0, 0.5 * content_score + 50.0), source="tile",
        )
        layout.occupied_cells = _grid_cell_counts(foreground_mask, layout)
        return layout
    return None


# ---------------------------------------------------------------------------
# Merge-only regrouping against a validated grid
# ---------------------------------------------------------------------------

def regroup_by_grid(
    foreground_mask: np.ndarray,
    groups: list[SpriteGroup],
    noise: list[RawComponent],
    layout: GridLayout,
) -> list[DetectedSprite]:
    """
    Rebuild the sprite list by grid cell instead of by pixel adjacency,
    WITHOUT ever splitting something the gap pipeline already decided was
    one sprite.

    Any gap-based group whose bounding box straddles a cut line unions
    those cells together, so the plant-leaf-and-stem case (two blobs with
    background between them, correctly merged upstream) survives even if
    the grid would otherwise have cut between them. Everything else in a
    cell -- including the sub-MIN_SPRITE_SIZE_PX particles the gap
    pipeline discarded -- collapses into that cell's single sprite.

    The result is therefore a pure coarsening of the gap result: it can
    only ever merge, never split.
    """
    h, w = foreground_mask.shape
    cols, rows = layout.columns, layout.rows
    if cols * rows == 0:
        return []

    # Sparse union-find: a fine grid over a large canvas has far more
    # nominal cells than occupied ones, so cells are only materialised
    # when something actually refers to them.
    parent: dict[int, int] = {}

    def find(i: int) -> int:
        parent.setdefault(i, i)
        while parent[i] != i:
            parent[i] = parent.setdefault(parent[i], parent[i])
            i = parent[i]
        return i

    def union(i: int, j: int) -> None:
        ri, rj = find(i), find(j)
        if ri != rj:
            parent[ri] = rj

    def cell_index(x: int, y: int) -> tuple[int, int]:
        c = (x - layout.offset_x) // layout.cell_width
        r = (y - layout.offset_y) // layout.cell_height
        return min(cols - 1, max(0, int(c))), min(rows - 1, max(0, int(r)))

    # A group spanning several cells fuses them, so it stays one sprite.
    for g in groups:
        b = g.bbox
        c0, r0 = cell_index(b.x, b.y)
        c1, r1 = cell_index(b.x2 - 1, b.y2 - 1)
        anchor = r0 * cols + c0
        for r in range(r0, r1 + 1):
            for c in range(c0, c1 + 1):
                union(anchor, r * cols + c)

    # Per-cell geometry straight from the mask, so nothing the component
    # stage rejected as noise gets lost.
    component_counts: dict[int, int] = {}
    for g in groups:
        c, r = cell_index(int(g.bbox.cx), int(g.bbox.cy))
        component_counts[r * cols + c] = component_counts.get(r * cols + c, 0) + len(g.components)
    for n in noise:
        c, r = cell_index(int(n.bbox.cx), int(n.bbox.cy))
        component_counts[r * cols + c] = component_counts.get(r * cols + c, 0) + 1

    row_range, col_range = _content_cell_ranges(foreground_mask, layout)
    buckets: dict[int, dict] = {}
    for r in row_range:
        y0, y1 = _cell_bounds(layout.offset_y, layout.cell_height, r, h)
        if y1 <= y0:
            continue
        band = foreground_mask[y0:y1]
        if not band.any():
            continue
        for c in col_range:
            x0, x1 = _cell_bounds(layout.offset_x, layout.cell_width, c, w)
            if x1 <= x0:
                continue
            cell = band[:, x0:x1]
            if not cell.any():
                continue
            ys, xs = np.nonzero(cell)
            box = BBox(
                x=x0 + int(xs.min()), y=y0 + int(ys.min()),
                width=int(xs.max()) - int(xs.min()) + 1,
                height=int(ys.max()) - int(ys.min()) + 1,
            )
            idx = r * cols + c
            bucket = buckets.setdefault(find(idx), {"bbox": None, "pixels": 0, "components": 0})
            bucket["bbox"] = box if bucket["bbox"] is None else bucket["bbox"].union(box)
            bucket["pixels"] += int(cell.sum())
            bucket["components"] += component_counts.get(idx, 0)

    ordered = sorted(buckets.values(), key=lambda b: (round(b["bbox"].y / 8), b["bbox"].x))

    detected: list[DetectedSprite] = []
    for idx, bucket in enumerate(ordered, start=1):
        confidence, reasons = _confidence_for(
            bbox=bucket["bbox"],
            pixel_count=bucket["pixels"],
            component_count=max(1, bucket["components"]),
            sheet_shape=(h, w),
            has_close_neighbour=False,  # unused for grid-backed sprites
            grid_backed=True,
        )
        reasons = [f"Grid cell ({layout.cell_width}x{layout.cell_height}, {layout.source})"] + reasons
        detected.append(
            DetectedSprite(
                sprite_index=idx,
                bbox=bucket["bbox"],
                confidence=confidence,
                confidence_reasons=reasons,
                component_count=max(1, bucket["components"]),
                pixel_count=bucket["pixels"],
                source=layout.source,
            )
        )
    return detected


def _gap_based_result_looks_like_grid_failure(
    detected: list[DetectedSprite],
    sheet_shape: tuple[int, int],
    tile_layout: GridLayout | None = None,
) -> bool:
    """
    Heuristic for "the gap-based pipeline probably fused a whole row/
    column into one blob because this sheet has no real gaps between
    sprites" -- see the module docstring's Grid mode section.

    The real fingerprint of this failure is a detected region that spans
    almost the FULL HEIGHT or FULL WIDTH of the sheet (e.g. one column of
    a portrait grid, with cells touching top-to-bottom, becomes a single
    bbox as tall as the entire sheet). Average area fraction alone is not
    a safe signal: a sheet with just two genuinely separate, reasonably
    large sprites can easily average >8% of the sheet's area without
    being a grid-failure case at all (e.g. two 10x10 sprites on a small
    40x20 sheet is 12.5% each, and is exactly the "should stay separate"
    scenario this pipeline is otherwise designed to get right). Requiring
    near-full-span on at least one axis avoids that false positive.
    """
    from config import (
        GRID_FALLBACK_MAX_REGIONS,
        GRID_FALLBACK_SPAN_FRACTION,
        GRID_OVERMERGE_AREA_FRACTION,
        GRID_SEPARATOR_MIN_CELLS,
    )

    if not detected:
        return False

    h, w = sheet_shape
    sheet_area = max(1, h * w)

    # A single detected region is normally not a grid failure -- a sheet
    # that's genuinely just one sprite must never be routed into grid
    # mode. The exception is a fully opaque tileset, which fuses into ONE
    # sheet-sized blob and would otherwise be unreachable; that is only
    # believed when the sheet's own edge periodicity independently reports
    # a real tile grid, which a lone sprite never does.
    if len(detected) < 2:
        if tile_layout is None or tile_layout.occupied_cells < GRID_SEPARATOR_MIN_CELLS:
            return False
        b = detected[0].bbox
        spans = b.height >= GRID_FALLBACK_SPAN_FRACTION * h or b.width >= GRID_FALLBACK_SPAN_FRACTION * w
        return spans and b.area >= GRID_OVERMERGE_AREA_FRACTION * sheet_area
    for d in detected:
        spans_height = d.bbox.height >= GRID_FALLBACK_SPAN_FRACTION * h
        spans_width = d.bbox.width >= GRID_FALLBACK_SPAN_FRACTION * w
        if not (spans_height or spans_width):
            continue
        if len(detected) <= GRID_FALLBACK_MAX_REGIONS:
            return True
        # Many regions AND one of them still swallows a large share of the
        # sheet: a tileset whose contiguous floor/wall area fused into one
        # blob while its loose items segmented fine. The area condition is
        # what separates this from a legitimate full-width fence sprite,
        # which spans an axis but covers almost none of the sheet.
        if d.bbox.area >= GRID_OVERMERGE_AREA_FRACTION * sheet_area:
            return True
    return False


def _gap_based_result_looks_shattered(
    gap_group_count: int, noise_pixel_fraction: float, layout: GridLayout | None,
) -> bool:
    """
    Heuristic for the opposite failure: one logical frame torn into many
    pieces, because its parts are separated by more background than the
    adaptive merge radius allows (an explosion's flying debris, a sparkle
    burst's scattered stars).

    Two independent symptoms, either of which is enough:

      - the gap pipeline reports substantially more regions than the
        validated grid has occupied cells, i.e. cells are being cut up;
      - a noticeable share of the sheet's ink was thrown away as
        sub-MIN_SPRITE_SIZE_PX speckle. Frames built from loose 1-2px
        particles hit this even when the region COUNT looks reasonable,
        because the shattered pieces are not merely split -- they are
        dropped, and whole frames silently disappear.
    """
    from config import GRID_NOISE_PIXEL_FRACTION, GRID_SHATTER_RATIO

    if layout is None or layout.occupied_cells <= 0:
        return False
    if noise_pixel_fraction >= GRID_NOISE_PIXEL_FRACTION:
        return True
    return gap_group_count >= GRID_SHATTER_RATIO * layout.occupied_cells


# ---------------------------------------------------------------------------
# Orchestration
# ---------------------------------------------------------------------------

def _detect_cutting_grid(
    foreground_mask: np.ndarray,
    rgba: np.ndarray | None,
    tile_layout: GridLayout | None = None,
    allow_separator: bool = False,
) -> GridLayout | None:
    """
    Best available grid layout for a sheet that has to be re-cut wholesale,
    tried strongest-evidence first:

      1. tile pitch from edge periodicity -- the only detector that works
         on an edge-to-edge tileset, where there is no background gutter
         anywhere to measure;
      2. optionally a separator grid, whose every cut line is verified to
         be pure background;
      3. the divisor/occupancy detector -- the original path, which is
         what handles a fixed-cell portrait/expression sheet (neither a
         measurable tile pitch nor a gutter to find).

    `allow_separator` is off by default. A separator grid guarantees only
    that its cuts fall on background, not that they fall BETWEEN sprites:
    a frame containing a one-pixel internal gap offers a legal cut straight
    through itself. That is harmless in the merge-only regrouping path,
    which cannot split a sprite the gap stage joined, but it is not safe
    when the layout is used to re-cut the sheet outright. Explicit
    `mode="grid"` turns it on, since there the caller has asked for a grid
    cut and the separator grid is the best answer for a frame sheet.
    """
    layout = tile_layout if tile_layout is not None else detect_tile_grid(rgba, foreground_mask)
    if layout is not None:
        return layout

    if allow_separator:
        layout = detect_separator_grid(foreground_mask)
        if layout is not None:
            return layout

    layout = detect_grid_layout(foreground_mask)
    if layout is not None and layout.score >= 50.0:
        return layout

    return None


def segment_sheet(
    foreground_mask: np.ndarray, mode: str = "auto", rgba: np.ndarray | None = None,
) -> tuple[list[DetectedSprite], np.ndarray, list[SpriteGroup]]:
    """
    Full pipeline entry point.

    `rgba` is the sheet's original HxWx4 pixels. It is optional -- every
    mask-only caller keeps working exactly as before -- but supplying it
    enables `detect_tile_grid`, which is the only way to recover the cell
    pitch of a tileset drawn edge to edge with no background between tiles.

    `mode`:
      - "auto" (default): run the gap-based pipeline, then correct it if
        it shows one of the two failure signatures this sheet type causes:

          * OVER-MERGE -- a region swallowing a whole row/column or a
            large share of the sheet, which is what an edge-to-edge
            tileset or portrait grid collapses into. The sheet is re-cut
            along a detected grid (see `_detect_cutting_grid`).
          * SHATTERING -- one logical animation frame torn into many
            regions, or its loose particles dropped as speckle. The gap
            result is regrouped by a separator grid, a MERGE-ONLY
            operation that cannot split anything the gap stage joined
            (see `regroup_by_grid`).

        With no failure signature, or no confident grid, the gap-based
        result is returned untouched -- irregular sheets are unaffected.
      - "gap": always use the original gap-based pipeline, never grid.
      - "grid": always use grid segmentation (a usable layout must be
        found, otherwise raises ValueError -- this mode is for explicit
        user override, so silently falling back to something else would
        be confusing).

    Returns:
      - list of DetectedSprite (index, bbox, confidence, reasons)
      - the raw label array (for building exact per-sprite pixel masks;
        None in grid mode, since there is no connected-component label
        array -- callers needing exact per-sprite masks in grid mode
        should crop directly from the sheet using each DetectedSprite's
        bbox instead)
      - the SpriteGroup list (empty in grid mode, for the same reason)
    """
    if mode not in ("auto", "gap", "grid"):
        raise ValueError(f"Unknown segmentation mode: {mode!r}")

    if mode == "grid":
        layout = _detect_cutting_grid(foreground_mask, rgba, allow_separator=True)
        if layout is None:
            raise ValueError("No usable grid layout detected for this sheet.")
        return segment_grid(foreground_mask, layout), None, []

    gap_detected, labels, groups, noise = _segment_sheet_gap_based(foreground_mask)

    if mode == "gap":
        return gap_detected, labels, groups

    # mode == "auto"
    tile_layout = detect_tile_grid(rgba, foreground_mask)
    if _gap_based_result_looks_like_grid_failure(gap_detected, foreground_mask.shape, tile_layout):
        layout = _detect_cutting_grid(foreground_mask, rgba, tile_layout=tile_layout)
        if layout is not None:
            return segment_grid(foreground_mask, layout), None, []
        return gap_detected, labels, groups

    total_pixels = int(foreground_mask.sum())
    noise_pixels = sum(n.pixel_count for n in noise)
    noise_fraction = noise_pixels / max(1, total_pixels)

    separator = detect_separator_grid(foreground_mask)
    if _gap_based_result_looks_shattered(len(groups), noise_fraction, separator):
        regrouped = regroup_by_grid(foreground_mask, groups, noise, separator)
        if regrouped:
            return regrouped, labels, groups

    return gap_detected, labels, groups


def _segment_sheet_gap_based(
    foreground_mask: np.ndarray,
) -> tuple[list[DetectedSprite], np.ndarray, list[SpriteGroup], list[RawComponent]]:
    """The original gap-based pipeline, unchanged -- see module docstring."""
    cleaned = find_foreground_regions(foreground_mask)
    labels, components, noise = find_components(cleaned)
    groups = merge_related_components(components)
    groups = detect_sprite_boundaries(groups, foreground_mask.shape)

    # Stable ordering: reading order (top-to-bottom, then left-to-right),
    # which is what the "[1] [2] [3] ..." preview numbering in the spec
    # expects.
    groups.sort(key=lambda g: (round(g.bbox.y / 8), g.bbox.x))

    close_flags = _close_neighbour_flags([g.bbox for g in groups])

    detected: list[DetectedSprite] = []
    for idx, g in enumerate(groups, start=1):
        confidence, reasons = _confidence_for(
            bbox=g.bbox,
            pixel_count=g.pixel_count,
            component_count=len(g.components),
            sheet_shape=foreground_mask.shape,
            has_close_neighbour=close_flags[idx - 1],
        )
        detected.append(
            DetectedSprite(
                sprite_index=idx,
                bbox=g.bbox,
                confidence=confidence,
                confidence_reasons=reasons,
                component_count=len(g.components),
                pixel_count=g.pixel_count,
            )
        )

    return detected, labels, groups, noise