rustial_engine/terrain/

backfill.rs

// ---------------------------------------------------------------------------
//! # DEM edge backfilling -- eliminate elevation seams at tile boundaries
//!
//! ## Problem
//!
//! When adjacent DEM tiles are decoded independently, hillshade and
//! terrain normal kernels read one sample beyond the tile edge and fall
//! back to clamping, producing an incorrect (flat) gradient that appears
//! as a visible seam.
//!
//! ## Solution (hybrid in-place patching -- MapLibre-style)
//!
//! MapLibre GL JS solves this with `DEMData.backfillBorder`: each DEM
//! tile is allocated with a 1-pixel border at decode time
//! (`stride = dim + 2`).  The border is initially clamped to the
//! nearest interior sample.  When a neighbour loads,
//! `backfillBorder(dx, dy)` copies the neighbour's edge directly into
//! the border -- zero allocation, one row/column copy per event.
//!
//! Rustial follows the same strategy:
//!
//! 1. **On decode** -- [`expand_with_clamped_border`] wraps the raw grid
//!    in a 1-sample border filled by clamping.  The result is stored in
//!    the terrain manager's cache.  One allocation per tile, at load
//!    time only.
//!
//! 2. **On neighbour arrival** -- [`patch_border_edge`] overwrites the
//!    affected border strip in-place.  Cost: one `memcpy` of a single
//!    row or column (typically 256 x 4 bytes = 1 KB).  No heap
//!    allocation.
//!
//! ## Border-sample layout
//!
//! After expansion a grid with interior dimensions `W x H` is stored as
//! `(W + 2) x (H + 2)`:
//!
//! ```text
//!    NW | ---- north ---- | NE
//!   ----+------------------+----
//!   w   |   interior WxH   |  e
//!   e   |                   |  a
//!   s   |                   |  s
//!   t   |                   |  t
//!   ----+------------------+----
//!    SW | ---- south ---- | SE
//! ```
//!
//! Interior dimensions are always `(stored_width - 2, stored_height - 2)`.
//!
//! ## Integration point
//!
//! The terrain manager calls these functions automatically:
//! - `expand_with_clamped_border` when inserting poll results into the
//!   cache.
//! - `patch_border_edge` for each cached tile whose neighbour just
//!   loaded (or whose own data just loaded, triggering neighbour
//!   patching of its own borders).
// ---------------------------------------------------------------------------

use rustial_math::{ElevationGrid, TileId};
use std::collections::HashMap;

// ---------------------------------------------------------------------------
// Public API
// ---------------------------------------------------------------------------

/// Interior (source) dimensions of an expanded grid.
///
/// The cache stores grids at `(W+2) x (H+2)`.  This helper returns the
/// original `(W, H)` before the border was added.
#[inline]
pub fn interior_dims(grid: &ElevationGrid) -> (u32, u32) {
    (grid.width.saturating_sub(2), grid.height.saturating_sub(2))
}

/// Wrap a raw elevation grid in a 1-sample border, clamped to the
/// nearest interior sample.
///
/// The returned grid has dimensions `(W+2) x (H+2)` and the same
/// `tile` field as the input.  The border serves as a scratch area
/// that [`patch_border_edge`] can overwrite in-place when neighbour
/// data becomes available.
///
/// This function allocates exactly once (`(W+2)*(H+2` f32 samples).
/// It should be called **once** per tile, immediately after the
/// elevation source delivers decoded data.
pub fn expand_with_clamped_border(src: &ElevationGrid) -> ElevationGrid {
    let w = src.width;
    let h = src.height;
    let new_w = w + 2;
    let new_h = h + 2;
    let mut data = vec![0.0f32; (new_w * new_h) as usize];

    // Copy interior at offset (1, 1).
    for row in 0..h {
        let src_start = (row * w) as usize;
        let dst_start = ((row + 1) * new_w + 1) as usize;
        data[dst_start..dst_start + w as usize]
            .copy_from_slice(&src.data[src_start..src_start + w as usize]);
    }

    // Clamp north border (row 0, cols 1..=w) to interior row 0.
    for col in 0..w {
        data[(col + 1) as usize] = src.data[col as usize];
    }
    // Clamp south border (row h+1, cols 1..=w) to interior last row.
    for col in 0..w {
        data[((h + 1) * new_w + col + 1) as usize] =
            src.data[((h - 1) * w + col) as usize];
    }
    // Clamp west border (col 0, rows 1..=h) to interior col 0.
    for row in 0..h {
        data[((row + 1) * new_w) as usize] = src.data[(row * w) as usize];
    }
    // Clamp east border (col w+1, rows 1..=h) to interior last col.
    for row in 0..h {
        data[((row + 1) * new_w + w + 1) as usize] =
            src.data[(row * w + w - 1) as usize];
    }

    // Clamp four corners.
    data[0] = src.data[0]; // NW
    data[(w + 1) as usize] = src.data[(w - 1) as usize]; // NE
    data[((h + 1) * new_w) as usize] = src.data[((h - 1) * w) as usize]; // SW
    data[((h + 1) * new_w + w + 1) as usize] =
        src.data[((h - 1) * w + w - 1) as usize]; // SE

    // min/max stay the same -- the border is a subset of interior values.
    ElevationGrid {
        width: new_w,
        height: new_h,
        min_elev: src.min_elev,
        max_elev: src.max_elev,
        data,
        tile: src.tile,
    }
}

/// Overwrite one border strip of `target` with edge data from
/// `neighbor`, in place.
///
/// `dx` and `dy` describe the relative position of the **neighbour**
/// with respect to the target tile:
///
/// | (dx, dy) | meaning           | border written |
/// |----------|-------------------|----------------|
/// | ( 0, -1) | neighbour is north | top row        |
/// | ( 0,  1) | neighbour is south | bottom row     |
/// | (-1,  0) | neighbour is west  | left column    |
/// | ( 1,  0) | neighbour is east  | right column   |
/// | (-1, -1) | neighbour is NW    | NW corner      |
/// | ( 1, -1) | neighbour is NE    | NE corner      |
/// | (-1,  1) | neighbour is SW    | SW corner      |
/// | ( 1,  1) | neighbour is SE    | SE corner      |
///
/// Both grids must be in expanded form (`(W+2) x (H+2)`) and have the
/// same interior dimensions.  If they differ, the call is a no-op.
///
/// After patching, `target.min_elev` / `max_elev` are updated if the
/// newly written samples extend the range.
pub fn patch_border_edge(
    target: &mut ElevationGrid,
    neighbor: &ElevationGrid,
    dx: i32,
    dy: i32,
) {
    let (tw, th) = interior_dims(target);
    let (nw, nh) = interior_dims(neighbor);
    if tw != nw || th != nh || tw == 0 || th == 0 {
        return;
    }

    let stride = target.width; // == tw + 2

    // Clamp border values to a generous window around the target's
    // interior elevation range.  This preserves seamless transitions
    // between land tiles while preventing extreme ocean depths or
    // corrupt neighbour data from producing displacement spikes in the
    // GPU shader's bilinear sampling.
    let interior_range = target.max_elev - target.min_elev;
    let margin = (interior_range * 0.5).max(200.0);
    let clamp_lo = target.min_elev - margin;
    let clamp_hi = target.max_elev + margin;

    let mut write = |idx: usize, val: f32| {
        target.data[idx] = val.clamp(clamp_lo, clamp_hi);
    };

    match (dx, dy) {
        // Cardinal neighbours -- copy a full row or column.
        (0, -1) => {
            // Neighbour is north: write target's top border row.
            // Source: neighbour's last interior row (row `nh` in expanded coords).
            let src_row = nh;
            for col in 0..tw {
                let src_idx = (src_row * stride + col + 1) as usize;
                let dst_idx = (col + 1) as usize; // row 0
                write(dst_idx, neighbor.data[src_idx]);
            }
        }
        (0, 1) => {
            // Neighbour is south: write target's bottom border row.
            // Source: neighbour's first interior row (row 1 in expanded).
            let src_row = 1u32;
            let dst_row = th + 1;
            for col in 0..tw {
                let src_idx = (src_row * stride + col + 1) as usize;
                let dst_idx = (dst_row * stride + col + 1) as usize;
                write(dst_idx, neighbor.data[src_idx]);
            }
        }
        (-1, 0) => {
            // Neighbour is west: write target's left border column.
            // Source: neighbour's last interior column (col `nw` in expanded).
            let src_col = nw;
            for row in 0..th {
                let src_idx = ((row + 1) * stride + src_col) as usize;
                let dst_idx = ((row + 1) * stride) as usize; // col 0
                write(dst_idx, neighbor.data[src_idx]);
            }
        }
        (1, 0) => {
            // Neighbour is east: write target's right border column.
            // Source: neighbour's first interior column (col 1 in expanded).
            let src_col = 1u32;
            let dst_col = tw + 1;
            for row in 0..th {
                let src_idx = ((row + 1) * stride + src_col) as usize;
                let dst_idx = ((row + 1) * stride + dst_col) as usize;
                write(dst_idx, neighbor.data[src_idx]);
            }
        }

        // Diagonal neighbours -- single corner sample.
        (-1, -1) => {
            // NW corner: source = neighbour's SE interior corner.
            let src_idx = (nh * stride + nw) as usize;
            write(0, neighbor.data[src_idx]);
        }
        (1, -1) => {
            // NE corner: source = neighbour's SW interior corner.
            let src_idx = (nh * stride + 1) as usize;
            write((tw + 1) as usize, neighbor.data[src_idx]);
        }
        (-1, 1) => {
            // SW corner: source = neighbour's NE interior corner.
            let src_idx = (1 * stride + nw) as usize;
            write(((th + 1) * stride) as usize, neighbor.data[src_idx]);
        }
        (1, 1) => {
            // SE corner: source = neighbour's NW interior corner.
            let src_idx = (1 * stride + 1) as usize;
            write(((th + 1) * stride + tw + 1) as usize, neighbor.data[src_idx]);
        }

        _ => {} // Unsupported offset -- silently ignore.
    }
}

/// The eight (dx, dy) neighbour offsets -- four cardinal, four diagonal.
pub const NEIGHBOR_OFFSETS: [(i32, i32); 8] = [
    (0, -1),  // north
    (0, 1),   // south
    (-1, 0),  // west
    (1, 0),   // east
    (-1, -1), // NW
    (1, -1),  // NE
    (-1, 1),  // SW
    (1, 1),   // SE
];

/// Per-tile record of which neighbour borders have been backfilled.
///
/// Each flag corresponds to one of the eight [`NEIGHBOR_OFFSETS`].
/// When a flag is `true`, the border strip for that direction contains
/// real neighbour data rather than clamped self-data.
#[derive(Debug, Clone, Default)]
pub struct BackfillState {
    /// Indexed by the same order as [`NEIGHBOR_OFFSETS`]:
    /// `[N, S, W, E, NW, NE, SW, SE]`.
    pub filled: [bool; 8],
}

impl BackfillState {
    /// Reset all flags to `false` (all borders need re-patching).
    pub fn reset(&mut self) {
        self.filled = [false; 8];
    }

    /// Mark the direction at `offset_index` as backfilled.
    #[inline]
    pub fn mark(&mut self, offset_index: usize) {
        if offset_index < 8 {
            self.filled[offset_index] = true;
        }
    }

    /// Check whether the direction at `offset_index` has been filled.
    #[inline]
    pub fn is_filled(&self, offset_index: usize) -> bool {
        offset_index < 8 && self.filled[offset_index]
    }
}

/// Run incremental backfill patching on all tiles affected by a set of
/// newly loaded tiles.
///
/// For each tile in `changed`, its own borders are patched from any
/// cached neighbours, and each cached neighbour's border facing the
/// changed tile is also patched.
///
/// `backfill_states` tracks which borders have already been filled so
/// that redundant copies are skipped.
///
/// Returns the set of tiles whose cached grid was actually modified
/// (useful for generation bumping / hillshade invalidation).
pub fn patch_changed_tiles(
    cache: &mut HashMap<TileId, ElevationGrid>,
    backfill_states: &mut HashMap<TileId, BackfillState>,
    changed: &std::collections::HashSet<TileId>,
) -> std::collections::HashSet<TileId> {
    let mut modified = std::collections::HashSet::new();

    // Collect the list of (target, neighbor, offset_index, dx, dy)
    // pairs that need patching.  We must collect first because we
    // cannot borrow `cache` mutably while iterating neighbour lookups.
    struct PatchOp {
        target: TileId,
        neighbor: TileId,
        offset_index: usize,
        dx: i32,
        dy: i32,
    }

    let mut ops: Vec<PatchOp> = Vec::new();

    // Reset backfill states for changed tiles so all borders are
    // re-patched with fresh data.
    for &tile in changed {
        backfill_states.entry(tile).or_default().reset();
    }

    for &tile in changed {
        // 1) Patch this tile's borders from its cached neighbours.
        for (idx, &(dx, dy)) in NEIGHBOR_OFFSETS.iter().enumerate() {
            if let Some(nb) = tile.neighbor(dx, dy) {
                if cache.contains_key(&nb) {
                    ops.push(PatchOp {
                        target: tile,
                        neighbor: nb,
                        offset_index: idx,
                        dx,
                        dy,
                    });
                }
            }
        }

        // 2) Patch each cached neighbour's border that faces this tile.
        for (_idx, &(dx, dy)) in NEIGHBOR_OFFSETS.iter().enumerate() {
            if let Some(nb) = tile.neighbor(dx, dy) {
                if cache.contains_key(&nb) {
                    // The reverse direction: if this tile is the east
                    // neighbour of `nb`, then `nb`'s east border should
                    // contain data from this tile (offset (-dx, -dy)).
                    let rev_idx = NEIGHBOR_OFFSETS
                        .iter()
                        .position(|&(rdx, rdy)| rdx == -dx && rdy == -dy);
                    if let Some(ri) = rev_idx {
                        let nb_state = backfill_states.entry(nb).or_default();
                        if !nb_state.is_filled(ri) {
                            ops.push(PatchOp {
                                target: nb,
                                neighbor: tile,
                                offset_index: ri,
                                dx: -dx,
                                dy: -dy,
                            });
                        }
                    }
                }
            }
        }
    }

    // Apply all patch operations.
    // We need split borrows: read from `neighbor`, write to `target`.
    // Since target != neighbor for all valid operations (a tile is never
    // its own neighbour), we clone the neighbour grid to avoid aliasing.
    // For 256x256 grids the clone is ~260KB -- acceptable since this
    // only happens when new tiles load (not every frame).
    for op in &ops {
        if op.target == op.neighbor {
            continue;
        }

        let neighbor_grid = cache.get(&op.neighbor).cloned();
        if let Some(ref nb_grid) = neighbor_grid {
            if let Some(target_grid) = cache.get_mut(&op.target) {
                patch_border_edge(target_grid, nb_grid, op.dx, op.dy);
                backfill_states
                    .entry(op.target)
                    .or_default()
                    .mark(op.offset_index);
                modified.insert(op.target);
            }
        }
    }

    modified
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;

    /// Helper: create a simple NxN grid filled with a constant value.
    fn const_grid(tile: TileId, size: u32, value: f32) -> ElevationGrid {
        ElevationGrid::from_data(tile, size, size, vec![value; (size * size) as usize])
            .expect("valid grid")
    }

    /// Helper: create a grid with sequentially increasing sample values.
    fn sequential_grid(tile: TileId, size: u32, base_val: f32) -> ElevationGrid {
        let data: Vec<f32> = (0..size * size)
            .map(|i| base_val + i as f32)
            .collect();
        ElevationGrid::from_data(tile, size, size, data).expect("valid grid")
    }

    // -- expand_with_clamped_border ----------------------------------------

    #[test]
    fn expand_produces_correct_dimensions() {
        let tile = TileId::new(3, 4, 4);
        let src = const_grid(tile, 4, 100.0);
        let expanded = expand_with_clamped_border(&src);
        assert_eq!(expanded.width, 6);
        assert_eq!(expanded.height, 6);
        assert_eq!(interior_dims(&expanded), (4, 4));
    }

    #[test]
    fn expand_interior_unchanged() {
        let tile = TileId::new(3, 4, 4);
        let src = sequential_grid(tile, 4, 0.0);
        let expanded = expand_with_clamped_border(&src);

        // Interior at (row+1, col+1) in expanded must match original.
        for row in 0..4u32 {
            for col in 0..4u32 {
                let orig = src.data[(row * 4 + col) as usize];
                let exp = expanded.data[((row + 1) * 6 + (col + 1)) as usize];
                assert!(
                    (orig - exp).abs() < 1e-6,
                    "interior mismatch at ({col},{row}): {orig} vs {exp}"
                );
            }
        }
    }

    #[test]
    fn expand_borders_clamp_to_nearest_interior() {
        let tile = TileId::new(3, 4, 4);
        let src = sequential_grid(tile, 4, 0.0);
        let expanded = expand_with_clamped_border(&src);
        let s = 6u32; // expanded stride

        // North border (row 0) should equal interior row 0.
        for col in 0..4u32 {
            assert!(
                (expanded.data[(col + 1) as usize] - src.data[col as usize]).abs() < 1e-6,
                "north border mismatch at col {col}"
            );
        }
        // South border (row 5) should equal interior row 3.
        for col in 0..4u32 {
            assert!(
                (expanded.data[(5 * s + col + 1) as usize]
                    - src.data[(3 * 4 + col) as usize])
                .abs()
                    < 1e-6,
                "south border mismatch at col {col}"
            );
        }
        // West border (col 0) should equal interior col 0.
        for row in 0..4u32 {
            assert!(
                (expanded.data[((row + 1) * s) as usize]
                    - src.data[(row * 4) as usize])
                .abs()
                    < 1e-6,
                "west border mismatch at row {row}"
            );
        }
        // East border (col 5) should equal interior col 3.
        for row in 0..4u32 {
            assert!(
                (expanded.data[((row + 1) * s + 5) as usize]
                    - src.data[(row * 4 + 3) as usize])
                .abs()
                    < 1e-6,
                "east border mismatch at row {row}"
            );
        }
        // NW corner = interior (0,0).
        assert!((expanded.data[0] - src.data[0]).abs() < 1e-6);
        // SE corner = interior (3,3).
        assert!(
            (expanded.data[(5 * s + 5) as usize] - src.data[(3 * 4 + 3) as usize]).abs()
                < 1e-6
        );
    }

    // -- patch_border_edge -------------------------------------------------

    #[test]
    fn patch_north_border() {
        let tile = TileId::new(3, 4, 4);
        let mut target = expand_with_clamped_border(&const_grid(tile, 4, 100.0));

        let north_tile = TileId::new(3, 4, 3);
        let neighbor = expand_with_clamped_border(&const_grid(north_tile, 4, 200.0));

        patch_border_edge(&mut target, &neighbor, 0, -1);

        let s = 6u32;
        // North border (row 0, cols 1..=4) should now be 200.
        for col in 1..=4u32 {
            let val = target.data[col as usize];
            assert!(
                (val - 200.0).abs() < 1e-6,
                "north border at col {col}: expected 200, got {val}"
            );
        }
        // South border should still be clamped to 100.
        for col in 1..=4u32 {
            let val = target.data[(5 * s + col) as usize];
            assert!(
                (val - 100.0).abs() < 1e-6,
                "south border should still be 100 at col {col}, got {val}"
            );
        }
    }

    #[test]
    fn patch_east_border() {
        let tile = TileId::new(3, 4, 4);
        let mut target = expand_with_clamped_border(&const_grid(tile, 4, 100.0));

        let east_tile = TileId::new(3, 5, 4);
        let neighbor = expand_with_clamped_border(&const_grid(east_tile, 4, 300.0));

        patch_border_edge(&mut target, &neighbor, 1, 0);

        let s = 6u32;
        // East border (col 5, rows 1..=4) should now be 300.
        for row in 1..=4u32 {
            let val = target.data[(row * s + 5) as usize];
            assert!(
                (val - 300.0).abs() < 1e-6,
                "east border at row {row}: expected 300, got {val}"
            );
        }
    }

    #[test]
    fn patch_nw_corner() {
        let tile = TileId::new(3, 4, 4);
        let mut target = expand_with_clamped_border(&const_grid(tile, 4, 100.0));

        let nw_tile = TileId::new(3, 3, 3);
        let mut nw_src = const_grid(nw_tile, 4, 500.0);
        // Set bottom-right interior sample to a unique value.
        nw_src.data[(3 * 4 + 3) as usize] = 999.0;
        let neighbor = expand_with_clamped_border(&nw_src);

        patch_border_edge(&mut target, &neighbor, -1, -1);

        // Target interior is all 100.0 → range=0, margin=200 → clamp=[−100, 300].
        // The neighbour's NW sample (999.0) is clamped to 300.
        assert!(
            (target.data[0] - 300.0).abs() < 1e-6,
            "NW corner should be clamped to 300.0, got {}",
            target.data[0]
        );
    }

    #[test]
    fn patch_mismatched_dims_is_noop() {
        let tile = TileId::new(3, 4, 4);
        let mut target = expand_with_clamped_border(&const_grid(tile, 4, 100.0));

        // Neighbour with different interior dims (8x8 instead of 4x4).
        let nb_tile = TileId::new(3, 5, 4);
        let neighbor = expand_with_clamped_border(&const_grid(nb_tile, 8, 999.0));

        patch_border_edge(&mut target, &neighbor, 1, 0);

        // East border should still be clamped to 100 (no-op).
        let s = 6u32;
        for row in 1..=4u32 {
            let val = target.data[(row * s + 5) as usize];
            assert!(
                (val - 100.0).abs() < 1e-6,
                "east border should still be 100 at row {row}, got {val}"
            );
        }
    }

    // -- patch_changed_tiles integration -----------------------------------

    #[test]
    fn patch_changed_two_horizontal_neighbours() {
        let left = TileId::new(3, 3, 4);
        let right = TileId::new(3, 4, 4);

        let mut cache = HashMap::new();
        cache.insert(left, expand_with_clamped_border(&const_grid(left, 4, 100.0)));
        cache.insert(
            right,
            expand_with_clamped_border(&const_grid(right, 4, 200.0)),
        );

        let mut states = HashMap::new();
        let changed: std::collections::HashSet<TileId> =
            [left, right].iter().copied().collect();

        let modified = patch_changed_tiles(&mut cache, &mut states, &changed);

        // Both tiles should have been modified.
        assert!(modified.contains(&left));
        assert!(modified.contains(&right));

        let s = 6u32;
        // Left tile's east border should be 200.
        let left_grid = cache.get(&left).unwrap();
        for row in 1..=4u32 {
            let val = left_grid.data[(row * s + 5) as usize];
            assert!(
                (val - 200.0).abs() < 1e-6,
                "left east border at row {row}: expected 200, got {val}"
            );
        }

        // Right tile's west border should be 100.
        let right_grid = cache.get(&right).unwrap();
        for row in 1..=4u32 {
            let val = right_grid.data[(row * s) as usize];
            assert!(
                (val - 100.0).abs() < 1e-6,
                "right west border at row {row}: expected 100, got {val}"
            );
        }
    }

    #[test]
    fn patch_changed_vertical_neighbours() {
        let upper = TileId::new(3, 4, 3);
        let lower = TileId::new(3, 4, 4);

        let mut cache = HashMap::new();
        cache.insert(
            upper,
            expand_with_clamped_border(&const_grid(upper, 4, 50.0)),
        );
        cache.insert(
            lower,
            expand_with_clamped_border(&const_grid(lower, 4, 150.0)),
        );

        let mut states = HashMap::new();
        let changed: std::collections::HashSet<TileId> =
            [upper, lower].iter().copied().collect();

        patch_changed_tiles(&mut cache, &mut states, &changed);

        let s = 6u32;
        // Upper's south border (row 5) should be 150.
        let upper_grid = cache.get(&upper).unwrap();
        for col in 1..=4u32 {
            let val = upper_grid.data[(5 * s + col) as usize];
            assert!(
                (val - 150.0).abs() < 1e-6,
                "upper south border at col {col}: expected 150, got {val}"
            );
        }
        // Lower's north border (row 0) should be 50.
        let lower_grid = cache.get(&lower).unwrap();
        for col in 1..=4u32 {
            let val = lower_grid.data[col as usize];
            assert!(
                (val - 50.0).abs() < 1e-6,
                "lower north border at col {col}: expected 50, got {val}"
            );
        }
    }

    #[test]
    fn backfill_state_tracks_filled_directions() {
        let mut state = BackfillState::default();
        assert!(!state.is_filled(0));
        state.mark(0);
        assert!(state.is_filled(0));
        state.reset();
        assert!(!state.is_filled(0));
    }

    #[test]
    fn incremental_patch_skips_already_filled() {
        // Simulate: left tile loaded first, then right tile loaded.
        let left = TileId::new(3, 3, 4);
        let right = TileId::new(3, 4, 4);

        let mut cache = HashMap::new();
        let mut states = HashMap::new();

        // Step 1: left tile arrives.
        cache.insert(left, expand_with_clamped_border(&const_grid(left, 4, 100.0)));
        let changed1: std::collections::HashSet<TileId> = [left].iter().copied().collect();
        patch_changed_tiles(&mut cache, &mut states, &changed1);

        // Left's east border should still be clamped (no right neighbour yet).
        let s = 6u32;
        let left_grid = cache.get(&left).unwrap();
        for row in 1..=4u32 {
            let val = left_grid.data[(row * s + 5) as usize];
            assert!(
                (val - 100.0).abs() < 1e-6,
                "left east should be clamped 100 before right arrives, got {val}"
            );
        }

        // Step 2: right tile arrives.
        cache.insert(
            right,
            expand_with_clamped_border(&const_grid(right, 4, 200.0)),
        );
        let changed2: std::collections::HashSet<TileId> = [right].iter().copied().collect();
        patch_changed_tiles(&mut cache, &mut states, &changed2);

        // Left's east border should now be 200 (patched from right).
        let left_grid = cache.get(&left).unwrap();
        for row in 1..=4u32 {
            let val = left_grid.data[(row * s + 5) as usize];
            assert!(
                (val - 200.0).abs() < 1e-6,
                "left east border should be 200 after right arrives, got {val}"
            );
        }

        // Right's west border should be 100 (patched from left).
        let right_grid = cache.get(&right).unwrap();
        for row in 1..=4u32 {
            let val = right_grid.data[(row * s) as usize];
            assert!(
                (val - 100.0).abs() < 1e-6,
                "right west border should be 100, got {val}"
            );
        }
    }

    // -- TileId::neighbor --------------------------------------------------

    #[test]
    fn neighbor_east() {
        let tile = TileId::new(3, 4, 4);
        let east = tile.neighbor(1, 0).expect("east");
        assert_eq!(east, TileId::new(3, 5, 4));
    }

    #[test]
    fn neighbor_west_wrap() {
        let tile = TileId::new(3, 0, 4);
        let west = tile.neighbor(-1, 0).expect("west wrap");
        assert_eq!(west, TileId::new(3, 7, 4));
    }

    #[test]
    fn neighbor_east_wrap() {
        let tile = TileId::new(3, 7, 4);
        let east = tile.neighbor(1, 0).expect("east wrap");
        assert_eq!(east, TileId::new(3, 0, 4));
    }

    #[test]
    fn neighbor_north_pole() {
        let tile = TileId::new(3, 4, 0);
        assert!(tile.neighbor(0, -1).is_none());
    }

    #[test]
    fn neighbor_south_pole() {
        let tile = TileId::new(3, 4, 7);
        assert!(tile.neighbor(0, 1).is_none());
    }
}