dreamwell_engine/

spatial.rs

// Spatial math utilities. Pure functions for cell computation and distance.

/// Cell size in world units.
pub const CELL_SIZE: i32 = 128;

/// Compute cell coordinate from world position (floor division).
///
/// Uses `div_euclid` to correctly handle all negative values including `i32::MIN`.
pub fn cell_coord(pos: i32) -> i32 {
    pos.div_euclid(CELL_SIZE)
}

/// Compute deterministic cell ID from world/region/position.
pub fn compute_cell_id(world_id: &str, region_id: &str, x: i32, y: i32) -> String {
    let cx = cell_coord(x);
    let cy = cell_coord(y);
    format!("cell:{}:{}:{}:{}", world_id, region_id, cx, cy)
}

/// Compute squared distance between two points. Integer-only, no sqrt.
pub fn distance_squared(x1: i32, y1: i32, x2: i32, y2: i32) -> i64 {
    let dx = (x2 as i64) - (x1 as i64);
    let dy = (y2 as i64) - (y1 as i64);
    dx.saturating_mul(dx).saturating_add(dy.saturating_mul(dy))
}

/// Return 3x3 neighbor cell coordinates for AOI queries.
pub fn action_horizon_cells(cx: i32, cy: i32) -> [(i32, i32); 9] {
    [
        (cx - 1, cy - 1),
        (cx, cy - 1),
        (cx + 1, cy - 1),
        (cx - 1, cy),
        (cx, cy),
        (cx + 1, cy),
        (cx - 1, cy + 1),
        (cx, cy + 1),
        (cx + 1, cy + 1),
    ]
}

/// Compute field-of-view positions from (ox, oy) with given radius.
/// Uses 8-octant recursive shadowcasting.
pub fn compute_fov<F>(ox: i32, oy: i32, radius: i32, blocks_sight_fn: F) -> Vec<(i32, i32)>
where
    F: Fn(i32, i32) -> bool,
{
    let mut visible = Vec::with_capacity((radius as usize * 2 + 1).pow(2));
    visible.push((ox, oy));

    for octant in 0..8u8 {
        cast_light(&mut visible, &blocks_sight_fn, ox, oy, radius, 1, 1.0, 0.0, octant);
    }
    visible
}

fn cast_light<F>(
    visible: &mut Vec<(i32, i32)>,
    blocks: &F,
    ox: i32,
    oy: i32,
    radius: i32,
    row: i32,
    mut start_slope: f64,
    end_slope: f64,
    octant: u8,
) where
    F: Fn(i32, i32) -> bool,
{
    if start_slope < end_slope || row > radius {
        return;
    }

    let mut prev_blocked = false;
    let mut saved_start = start_slope;

    for j in row..=radius {
        let mut blocked = false;
        let dy = -(j as f64);
        let dx_f = dy * start_slope;
        let dx_start = dx_f.round() as i32;

        for dx in ((-j)..=dx_start).rev() {
            let dx_f = dx as f64;
            let slope_l = (dx_f + 0.5) / (dy - 0.5);
            let slope_r = (dx_f - 0.5) / (dy + 0.5);

            if slope_l < end_slope {
                break;
            }
            if slope_r > start_slope {
                continue;
            }

            let (mx, my) = transform_octant(dx, j, octant);
            let ax = ox + mx;
            let ay = oy + my;

            if dx * dx + j * j <= radius * radius {
                visible.push((ax, ay));
            }

            if blocks(ax, ay) {
                if !prev_blocked {
                    saved_start = start_slope;
                }
                prev_blocked = true;
                blocked = true;
                start_slope = slope_r;
            } else if prev_blocked {
                prev_blocked = false;
                cast_light(visible, blocks, ox, oy, radius, j + 1, saved_start, slope_l, octant);
            }
        }

        if blocked {
            return;
        }
    }
}

fn transform_octant(dx: i32, dy: i32, octant: u8) -> (i32, i32) {
    match octant {
        0 => (dx, -dy),
        1 => (-dx, -dy),
        2 => (dx, dy),
        3 => (-dx, dy),
        4 => (-dy, dx),
        5 => (-dy, -dx),
        6 => (dy, dx),
        7 => (dy, -dx),
        _ => (0, 0),
    }
}

// =============================================================================
// Observer Visibility Masks — CPU-side meshlet visibility for Quantum Culling.
// =============================================================================

/// Compute observer visibility mask: 1 for visible meshlets, 0 for culled.
/// `fov_cells` is the output of `compute_fov`.
/// `meshlet_coords` are the (x, y) cell positions of each meshlet.
pub fn compute_observer_visibility_mask(fov_cells: &[(i32, i32)], meshlet_coords: &[(i32, i32)]) -> Vec<u32> {
    let visible_set: rustc_hash::FxHashSet<(i32, i32)> = fov_cells.iter().copied().collect();
    meshlet_coords
        .iter()
        .map(|coord| if visible_set.contains(coord) { 1 } else { 0 })
        .collect()
}

/// Zero-allocation version: writes into caller-provided output slice.
/// `out` must be at least `meshlet_coords.len()` long.
pub fn fill_observer_visibility_mask(fov_cells: &[(i32, i32)], meshlet_coords: &[(i32, i32)], out: &mut [u32]) {
    let visible_set: rustc_hash::FxHashSet<(i32, i32)> = fov_cells.iter().copied().collect();
    for (i, coord) in meshlet_coords.iter().enumerate() {
        if i < out.len() {
            out[i] = if visible_set.contains(coord) { 1 } else { 0 };
        }
    }
}

// =============================================================================
// A* Pathfinding — Bounded, deterministic, integer-only heuristic.
// =============================================================================

/// A* node for the open set. Uses integer cost (no floats in authoritative logic).
struct AStarNode {
    x: i32,
    y: i32,
    g: u32,
    f: u32,
}

/// Integer heuristic: Chebyshev distance (allows 8-directional movement).
fn heuristic(x1: i32, y1: i32, x2: i32, y2: i32) -> u32 {
    let dx = (x2 - x1).unsigned_abs();
    let dy = (y2 - y1).unsigned_abs();
    if dx > dy {
        dx
    } else {
        dy
    }
}

/// 4-directional neighbors. Deterministic iteration order.
const DIRS: [(i32, i32); 4] = [(0, -1), (1, 0), (0, 1), (-1, 0)];

/// Bounded A* pathfinding. Returns path as Vec<(i32, i32)> excluding start.
/// `cost_fn` returns movement cost (999 = impassable) for a given (x, y).
/// Bounded by `max_steps` to prevent unbounded work.
pub fn astar<F>(
    start_x: i32,
    start_y: i32,
    goal_x: i32,
    goal_y: i32,
    max_steps: u32,
    cost_fn: F,
) -> Option<Vec<(i32, i32)>>
where
    F: Fn(i32, i32) -> u32,
{
    use std::collections::BTreeMap;

    if start_x == goal_x && start_y == goal_y {
        return Some(Vec::new());
    }

    // Encode (x, y) as a single i64 key for map lookups (no alloc per node).
    let key = |x: i32, y: i32| -> i64 { (x as i64) << 32 | (y as i64 & 0xFFFFFFFF) };

    // g_score: best known cost to reach each node.
    let mut g_score: BTreeMap<i64, u32> = BTreeMap::new();
    // came_from: parent link for path reconstruction.
    let mut came_from: BTreeMap<i64, i64> = BTreeMap::new();

    // Open set as sorted Vec (poor man's priority queue — bounded by max_steps).
    // Each entry: (f_score, g_score, x, y).
    let mut open: Vec<AStarNode> = Vec::with_capacity(max_steps as usize);
    let start_h = heuristic(start_x, start_y, goal_x, goal_y);
    open.push(AStarNode {
        x: start_x,
        y: start_y,
        g: 0,
        f: start_h,
    });
    g_score.insert(key(start_x, start_y), 0);

    let mut iterations: u32 = 0;

    while let Some(best_idx) = find_min_f(&open) {
        iterations += 1;
        if iterations > max_steps {
            return None; // Bounded work exceeded.
        }

        let current = open.swap_remove(best_idx);

        if current.x == goal_x && current.y == goal_y {
            // Reconstruct path.
            let mut path = Vec::new();
            let mut ck = key(goal_x, goal_y);
            let sk = key(start_x, start_y);
            while ck != sk {
                let cx = (ck >> 32) as i32;
                let cy = ck as i32;
                path.push((cx, cy));
                ck = match came_from.get(&ck) {
                    Some(&parent) => parent,
                    None => break,
                };
            }
            path.reverse();
            return Some(path);
        }

        for &(dx, dy) in &DIRS {
            let nx = current.x + dx;
            let ny = current.y + dy;
            let move_cost = cost_fn(nx, ny);
            if move_cost >= 999 {
                continue;
            } // Impassable.

            let tentative_g = current.g + move_cost;
            let nk = key(nx, ny);

            if let Some(&existing_g) = g_score.get(&nk) {
                if tentative_g >= existing_g {
                    continue;
                }
            }

            g_score.insert(nk, tentative_g);
            came_from.insert(nk, key(current.x, current.y));
            let h = heuristic(nx, ny, goal_x, goal_y);
            open.push(AStarNode {
                x: nx,
                y: ny,
                g: tentative_g,
                f: tentative_g + h,
            });
        }
    }

    None // No path found.
}

// =============================================================================
// SpatialGrid — O(1) per-tick entity index for area-of-interest queries.
// =============================================================================
//
// Built ephemerally at the start of each `tick_advance` and discarded after.
// Provides O(1) amortized cell lookup and O(cells) neighbor scan (9 cells max).
// Not persisted — all writes are to a local HashMap in the current tick context.

/// Key into the spatial grid: (cell_x, cell_y).
type CellKey = (i32, i32);

/// In-memory spatial grid mapping cell coordinates to entity ID lists.
///
/// Intended lifetime: one tick. Build with `SpatialGrid::new()`, populate
/// with `insert`, query with `query_cell`/`query_neighbors`, then drop.
#[derive(Default)]
pub struct SpatialGrid {
    cells: std::collections::HashMap<CellKey, Vec<String>>,
}

impl SpatialGrid {
    /// Create an empty spatial grid.
    #[inline]
    pub fn new() -> Self {
        Self {
            cells: std::collections::HashMap::new(),
        }
    }

    /// Create a grid pre-allocated for at least `capacity` entities.
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            cells: std::collections::HashMap::with_capacity(capacity),
        }
    }

    /// Insert an entity at world position (x, y).
    ///
    /// Computes the cell coordinate and appends `entity_id` to that cell's list.
    /// An entity may appear in multiple calls (e.g. once per owned component),
    /// but callers are responsible for deduplication if required.
    #[inline]
    pub fn insert(&mut self, entity_id: &str, x: i32, y: i32) {
        let key = (cell_coord(x), cell_coord(y));
        self.cells.entry(key).or_default().push(entity_id.to_string());
    }

    /// Remove an entity from its current cell at world position (x, y).
    ///
    /// Removes the first occurrence of `entity_id` in the cell.
    /// No-ops if the entity is not present.
    #[inline]
    pub fn remove(&mut self, entity_id: &str, x: i32, y: i32) {
        let key = (cell_coord(x), cell_coord(y));
        if let Some(list) = self.cells.get_mut(&key) {
            if let Some(pos) = list.iter().position(|id| id == entity_id) {
                list.swap_remove(pos);
            }
        }
    }

    /// Return all entity IDs in the cell containing world position (x, y).
    ///
    /// Returns an empty slice if the cell is unpopulated.
    #[inline]
    pub fn query_cell(&self, x: i32, y: i32) -> &[String] {
        let key = (cell_coord(x), cell_coord(y));
        match self.cells.get(&key) {
            Some(list) => list.as_slice(),
            None => &[],
        }
    }

    /// Return all entity IDs in the 3x3 neighborhood of cell (cx, cy).
    ///
    /// Results are unsorted and may contain duplicates if an entity spans cells.
    /// Allocates a Vec bounded by 9 * max_entities_per_cell.
    pub fn query_neighbors(&self, cx: i32, cy: i32) -> Vec<&str> {
        let mut result = Vec::new();
        for (ncx, ncy) in action_horizon_cells(cx, cy) {
            if let Some(list) = self.cells.get(&(ncx, ncy)) {
                for id in list {
                    result.push(id.as_str());
                }
            }
        }
        result
    }

    /// Return all entity IDs within `range` of world position (x, y).
    ///
    /// Queries the 3x3 cell neighborhood and excludes cells whose closest
    /// point to (x, y) exceeds `range`. Because the grid stores cell
    /// assignment — not exact entity positions — this is cell-granularity
    /// filtering. Callers with exact entity coordinates should apply a
    /// final `distance_squared` check for precise results.
    ///
    /// Each returned tuple is `(entity_id, cell_origin_x, cell_origin_y)`.
    pub fn query_radius(&self, x: i32, y: i32, range: i32) -> Vec<(&str, i32, i32)> {
        let cx = cell_coord(x);
        let cy = cell_coord(y);
        let range_sq = (range as i64) * (range as i64);

        let mut result = Vec::new();
        for (ncx, ncy) in action_horizon_cells(cx, cy) {
            // Compute the closest point on this cell's bounding box to (x, y).
            let cell_min_x = ncx * CELL_SIZE;
            let cell_max_x = cell_min_x + CELL_SIZE - 1;
            let cell_min_y = ncy * CELL_SIZE;
            let cell_max_y = cell_min_y + CELL_SIZE - 1;

            let nearest_x = x.clamp(cell_min_x, cell_max_x);
            let nearest_y = y.clamp(cell_min_y, cell_max_y);

            if distance_squared(x, y, nearest_x, nearest_y) > range_sq {
                continue;
            }

            if let Some(list) = self.cells.get(&(ncx, ncy)) {
                for id in list {
                    result.push((id.as_str(), cell_min_x, cell_min_y));
                }
            }
        }
        result
    }

    /// Return the number of occupied cells.
    #[inline]
    pub fn cell_count(&self) -> usize {
        self.cells.len()
    }

    /// Return the total number of entity references across all cells.
    #[inline]
    pub fn entity_count(&self) -> usize {
        self.cells.values().map(|v| v.len()).sum()
    }

    /// Clear all cells. Retains allocated capacity.
    #[inline]
    pub fn clear(&mut self) {
        self.cells.clear();
    }
}

// =============================================================================
// SpatialHashGrid — Dense spatial grid for O(1) entity lookup by position.
// =============================================================================
//
// Uses u64 entity IDs (numeric handles) instead of String IDs.
// Supports configurable cell size and variable-radius queries beyond 3x3.
// Designed for GPU-side entity systems, sub-area queries, and scale scenarios
// where entity counts exceed the 3x3 neighborhood scan of SpatialGrid.

/// Dense spatial grid for O(1) entity lookup by position.
/// Grid cells are `cell_size` x `cell_size` world units.
/// Uses u64 entity handles — zero-copy, no per-entity String allocation.
pub struct SpatialHashGrid {
    cells: std::collections::HashMap<(i32, i32), Vec<u64>>,
    cell_size: i32,
}

impl SpatialHashGrid {
    /// Create a new spatial hash grid with the given cell size.
    pub fn new(cell_size: i32) -> Self {
        Self {
            cells: std::collections::HashMap::with_capacity(256),
            cell_size,
        }
    }

    /// Compute the cell key for a world-space position.
    #[inline]
    pub fn cell_key(&self, x: i32, y: i32) -> (i32, i32) {
        (x.div_euclid(self.cell_size), y.div_euclid(self.cell_size))
    }

    /// Insert an entity at world position (x, y).
    pub fn insert(&mut self, entity_id: u64, x: i32, y: i32) {
        let key = self.cell_key(x, y);
        self.cells
            .entry(key)
            .or_insert_with(|| Vec::with_capacity(16))
            .push(entity_id);
    }

    /// Remove an entity from its cell at world position (x, y).
    /// Removes the first occurrence. No-ops if not present.
    pub fn remove(&mut self, entity_id: u64, x: i32, y: i32) {
        let key = self.cell_key(x, y);
        if let Some(cell) = self.cells.get_mut(&key) {
            cell.retain(|&id| id != entity_id);
        }
    }

    /// Query all entities within `radius` world units of (cx, cy).
    /// Scans `O(radius^2 / cell_size^2)` cells.
    pub fn query_radius(&self, cx: i32, cy: i32, radius: i32) -> Vec<u64> {
        let mut result = Vec::new();
        let cell_radius = (radius / self.cell_size) + 1;
        let center_key = self.cell_key(cx, cy);
        for dx in -cell_radius..=cell_radius {
            for dy in -cell_radius..=cell_radius {
                let key = (center_key.0 + dx, center_key.1 + dy);
                if let Some(cell) = self.cells.get(&key) {
                    result.extend_from_slice(cell);
                }
            }
        }
        result
    }

    /// Return all entity IDs in the cell containing world position (x, y).
    pub fn query_cell(&self, x: i32, y: i32) -> &[u64] {
        let key = self.cell_key(x, y);
        match self.cells.get(&key) {
            Some(list) => list.as_slice(),
            None => &[],
        }
    }

    /// Clear all cells. Retains allocated capacity.
    pub fn clear(&mut self) {
        self.cells.clear();
    }

    /// Return the total number of entity references across all cells.
    pub fn entity_count(&self) -> usize {
        self.cells.values().map(|c| c.len()).sum()
    }

    /// Return the number of occupied cells.
    pub fn cell_count(&self) -> usize {
        self.cells.len()
    }

    /// Return the cell size.
    pub fn cell_size(&self) -> i32 {
        self.cell_size
    }
}

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

    #[test]
    fn insert_and_query_finds_entity() {
        let mut grid = SpatialHashGrid::new(128);
        grid.insert(42, 100, 100);
        let found = grid.query_cell(100, 100);
        assert_eq!(found, &[42]);
    }

    #[test]
    fn remove_and_query_does_not_find_entity() {
        let mut grid = SpatialHashGrid::new(128);
        grid.insert(42, 100, 100);
        grid.remove(42, 100, 100);
        let found = grid.query_cell(100, 100);
        assert!(found.is_empty());
    }

    #[test]
    fn query_radius_returns_only_nearby() {
        let mut grid = SpatialHashGrid::new(128);
        // Entity at origin
        grid.insert(1, 0, 0);
        // Entity far away (cell 10,10 = world 1280,1280)
        grid.insert(2, 1280, 1280);
        // Query radius 200 from origin — should only find entity 1
        let found = grid.query_radius(0, 0, 200);
        assert!(found.contains(&1));
        assert!(!found.contains(&2));
    }

    #[test]
    fn empty_grid_returns_empty() {
        let grid = SpatialHashGrid::new(128);
        assert!(grid.query_cell(0, 0).is_empty());
        assert!(grid.query_radius(0, 0, 500).is_empty());
        assert_eq!(grid.entity_count(), 0);
        assert_eq!(grid.cell_count(), 0);
    }

    #[test]
    fn multiple_entities_same_cell() {
        let mut grid = SpatialHashGrid::new(128);
        grid.insert(1, 10, 10);
        grid.insert(2, 50, 50);
        grid.insert(3, 100, 100);
        // All in cell (0, 0)
        let found = grid.query_cell(0, 0);
        assert_eq!(found.len(), 3);
        assert_eq!(grid.entity_count(), 3);
        assert_eq!(grid.cell_count(), 1);
    }

    #[test]
    fn negative_coordinates() {
        let mut grid = SpatialHashGrid::new(128);
        grid.insert(99, -200, -300);
        let found = grid.query_cell(-200, -300);
        assert_eq!(found, &[99]);
        // Should not appear in positive cell
        assert!(grid.query_cell(200, 300).is_empty());
    }

    #[test]
    fn clear_resets_all() {
        let mut grid = SpatialHashGrid::new(128);
        grid.insert(1, 0, 0);
        grid.insert(2, 128, 0);
        grid.clear();
        assert_eq!(grid.entity_count(), 0);
        assert_eq!(grid.cell_count(), 0);
    }

    #[test]
    fn custom_cell_size() {
        let mut grid = SpatialHashGrid::new(64);
        grid.insert(1, 0, 0); // cell (0, 0)
        grid.insert(2, 64, 0); // cell (1, 0)
        grid.insert(3, 63, 0); // still cell (0, 0)
        assert_eq!(grid.query_cell(0, 0).len(), 2); // entities 1 and 3
        assert_eq!(grid.query_cell(64, 0).len(), 1); // entity 2
        assert_eq!(grid.cell_size(), 64);
    }

    #[test]
    fn query_radius_covers_adjacent_cells() {
        let mut grid = SpatialHashGrid::new(128);
        // Entity at (130, 0) = cell (1, 0)
        grid.insert(10, 130, 0);
        // Query from origin with radius 200 — should reach cell (1, 0)
        let found = grid.query_radius(0, 0, 200);
        assert!(found.contains(&10));
    }
}

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

    #[test]
    fn insert_and_query_same_cell() {
        let mut grid = SpatialGrid::new();
        grid.insert("e1", 0, 0);
        grid.insert("e2", 50, 50); // same cell as (0,0): cell (0,0)
        let found = grid.query_cell(0, 0);
        assert_eq!(found.len(), 2);
    }

    #[test]
    fn insert_different_cells() {
        let mut grid = SpatialGrid::new();
        grid.insert("e1", 0, 0); // cell (0,0)
        grid.insert("e2", 128, 0); // cell (1,0)
        assert_eq!(grid.query_cell(0, 0).len(), 1);
        assert_eq!(grid.query_cell(128, 0).len(), 1);
        assert_eq!(grid.cell_count(), 2);
    }

    #[test]
    fn query_empty_cell_returns_empty_slice() {
        let grid = SpatialGrid::new();
        assert!(grid.query_cell(999, 999).is_empty());
    }

    #[test]
    fn remove_entity() {
        let mut grid = SpatialGrid::new();
        grid.insert("e1", 0, 0);
        grid.insert("e2", 0, 0);
        grid.remove("e1", 0, 0);
        let found = grid.query_cell(0, 0);
        assert_eq!(found.len(), 1);
        assert_eq!(found[0], "e2");
    }

    #[test]
    fn remove_nonexistent_is_noop() {
        let mut grid = SpatialGrid::new();
        grid.insert("e1", 0, 0);
        grid.remove("e2", 0, 0); // e2 not in this cell
        assert_eq!(grid.query_cell(0, 0).len(), 1);
    }

    #[test]
    fn query_neighbors_returns_all_9_cells() {
        let mut grid = SpatialGrid::new();
        // Place one entity in each of the 9 neighbor cells around (0,0).
        grid.insert("c", 64, 64); // cell (0,0)
        grid.insert("n", 64, -64); // cell (0,-1)
        grid.insert("s", 64, 192); // cell (0,1)
        grid.insert("w", -64, 64); // cell (-1,0)
        grid.insert("e", 192, 64); // cell (1,0)
        grid.insert("nw", -64, -64); // cell (-1,-1)
        grid.insert("ne", 192, -64); // cell (1,-1)
        grid.insert("sw", -64, 192); // cell (-1,1)
        grid.insert("se", 192, 192); // cell (1,1)
        let neighbors = grid.query_neighbors(0, 0);
        assert_eq!(neighbors.len(), 9);
    }

    #[test]
    fn entity_count_tracks_insertions() {
        let mut grid = SpatialGrid::new();
        grid.insert("a", 0, 0);
        grid.insert("b", 0, 0);
        grid.insert("c", 128, 0);
        assert_eq!(grid.entity_count(), 3);
    }

    #[test]
    fn clear_resets_grid() {
        let mut grid = SpatialGrid::new();
        grid.insert("a", 0, 0);
        grid.clear();
        assert_eq!(grid.entity_count(), 0);
        assert_eq!(grid.cell_count(), 0);
    }

    #[test]
    fn negative_coords_map_correctly() {
        let mut grid = SpatialGrid::new();
        grid.insert("neg", -1, -1); // cell (-1,-1)
        assert_eq!(grid.query_cell(-1, -1).len(), 1);
        assert_eq!(grid.query_cell(0, 0).len(), 0);
    }

    #[test]
    fn with_capacity_works() {
        let mut grid = SpatialGrid::with_capacity(1000);
        grid.insert("e", 0, 0);
        assert_eq!(grid.entity_count(), 1);
    }

    // -- Negative coordinate tests (E12) --------------------------------------

    #[test]
    fn cell_coord_negative_one() {
        // -1 should map to cell -1 (floor division).
        assert_eq!(cell_coord(-1), -1);
    }

    #[test]
    fn cell_coord_negative_128() {
        // -128 is exactly -1 * CELL_SIZE, so should map to cell -1.
        assert_eq!(cell_coord(-128), -1);
    }

    #[test]
    fn cell_coord_negative_129() {
        // -129 should map to cell -2 (one past the -1 cell boundary).
        assert_eq!(cell_coord(-129), -2);
    }

    #[test]
    fn cell_coord_i32_min() {
        // i32::MIN should not panic and should produce a valid cell coord.
        let result = cell_coord(i32::MIN);
        // i32::MIN = -2147483648; -2147483648 / 128 = -16777216
        assert_eq!(result, -16777216);
    }

    #[test]
    fn grid_negative_coordinates() {
        let mut grid = SpatialGrid::new();
        grid.insert("neg_entity", -200, -300);
        // -200 / 128 -> cell -2, -300 / 128 -> cell -3
        let found = grid.query_cell(-200, -300);
        assert_eq!(found.len(), 1);
        assert_eq!(found[0], "neg_entity");

        // Positive coords should not find it.
        assert!(grid.query_cell(200, 300).is_empty());
    }

    #[test]
    fn grid_negative_positive_boundary() {
        let mut grid = SpatialGrid::new();
        // Entity at -1 (cell -1) should not appear in cell 0.
        grid.insert("boundary", -1, -1);
        assert_eq!(grid.query_cell(-1, -1).len(), 1);
        assert_eq!(grid.query_cell(0, 0).len(), 0);
    }

    #[test]
    fn cell_coord_negative_exact_boundary() {
        // -256 = -2 * CELL_SIZE -> cell -2
        assert_eq!(cell_coord(-256), -2);
        // -257 -> cell -3
        assert_eq!(cell_coord(-257), -3);
    }
}

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

    #[test]
    fn visibility_mask_all_visible() {
        let fov = vec![(0, 0), (1, 0), (0, 1)];
        let meshlets = vec![(0, 0), (1, 0)];
        let mask = compute_observer_visibility_mask(&fov, &meshlets);
        assert_eq!(mask, vec![1, 1]);
    }

    #[test]
    fn visibility_mask_none_visible() {
        let fov = vec![(10, 10)];
        let meshlets = vec![(0, 0), (1, 1)];
        let mask = compute_observer_visibility_mask(&fov, &meshlets);
        assert_eq!(mask, vec![0, 0]);
    }

    #[test]
    fn visibility_mask_partial() {
        let fov = vec![(0, 0), (1, 0)];
        let meshlets = vec![(0, 0), (5, 5), (1, 0)];
        let mask = compute_observer_visibility_mask(&fov, &meshlets);
        assert_eq!(mask, vec![1, 0, 1]);
    }

    #[test]
    fn fill_visibility_mask_zero_alloc() {
        let fov = vec![(0, 0), (2, 2)];
        let meshlets = vec![(0, 0), (1, 1), (2, 2)];
        let mut out = vec![0u32; 3];
        fill_observer_visibility_mask(&fov, &meshlets, &mut out);
        assert_eq!(out, vec![1, 0, 1]);
    }

    #[test]
    fn visibility_mask_empty_fov() {
        let fov: Vec<(i32, i32)> = vec![];
        let meshlets = vec![(0, 0)];
        let mask = compute_observer_visibility_mask(&fov, &meshlets);
        assert_eq!(mask, vec![0]);
    }
}

/// Find the index of the node with minimum f-score in the open list.
fn find_min_f(open: &[AStarNode]) -> Option<usize> {
    if open.is_empty() {
        return None;
    }
    let mut min_idx = 0;
    let mut min_f = open[0].f;
    for (i, node) in open.iter().enumerate().skip(1) {
        if node.f < min_f {
            min_f = node.f;
            min_idx = i;
        }
    }
    Some(min_idx)
}