liquidwar7core 0.2.0

// Copyright (C) 2025 Christian Mauduit <ufoot@ufoot.org>

//! Quadtree-based mesh for optimized gradient computation.
//!
//! This mesh compacts large uniform walkable areas into bigger cells, reducing
//! the number of cells to process during gradient spreading.
//!
//! **Important**: This mesh only contains walkable cells. Walls are not part
//! of the mesh - they simply don't exist here. Use a separate occupation mesh
//! (like Compact25D) for tracking fighter positions.
//!
//! Uses f16 (half-precision float) for direction vectors and distances
//! to reduce memory footprint, important for WASM deployment.
//!
//! # Directions
//!
//! 14 total directions:
//! - 12 horizontal (3 per quadrant for smooth diagonal movement):
//!   - NNE, NE, ENE (northeast quadrant)
//!   - ESE, SE, SSE (southeast quadrant)
//!   - SSW, SW, WSW (southwest quadrant)
//!   - WNW, NW, NNW (northwest quadrant)
//! - 2 vertical: UP, DOWN
//!
//! ```text
//!           NNW   N   NNE
//!              \  |  /
//!          NW   \ | /   NE
//!            \   \|/   /
//!       WNW ---   *   --- ENE
//!            /   /|\   \
//!          SW   / | \   SE
//!              /  |  \
//!           SSW   S   SSE
//! ```
//!
//! Note: Cardinal directions (N, E, S, W) are handled by making adjacent
//! diagonal directions point to the same neighbor (e.g., NNE and NNW both
//! link to the N neighbor when at map edges).

use half::f16;
#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};
use shortestpath::mesh_25d::Compact25D;
use shortestpath::mesh_source::{CellType, Source3D};
#[cfg(feature = "image")]
use shortestpath::mesh_source::Source3DFromImage;
use shortestpath::{Error as SpError, Gate, Mesh};

/// Sentinel value indicating no cell at this coordinate (wall or out of bounds).
const NO_CELL: usize = usize::MAX;

/// Maximum allowed level width.
pub const LEVEL_MAX_W: usize = 512;

/// Maximum allowed level height.
pub const LEVEL_MAX_H: usize = 512;

/// Maximum allowed level depth (number of layers).
pub const LEVEL_MAX_D: usize = 8;

/// Maximum allowed total volume (width * height * depth).
/// This is checked BEFORE the ground layer is added, so the final
/// volume may be up to 2x this value (512 * 512 * 2).
pub const LEVEL_MAX_VOLUME: usize = 512 * 512;

/// Errors that can occur when creating a QuadMesh.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum QuadMeshError {
    /// Width exceeds the maximum allowed value.
    WidthExceeded { width: usize, max: usize },
    /// Height exceeds the maximum allowed value.
    HeightExceeded { height: usize, max: usize },
    /// Depth exceeds the maximum allowed value.
    DepthExceeded { depth: usize, max: usize },
    /// Total volume (width * height * depth) exceeds maximum.
    VolumeExceeded { volume: usize, max: usize },
    /// Error from shortestpath library.
    ShortestPath(String),
}

impl std::fmt::Display for QuadMeshError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            QuadMeshError::WidthExceeded { width, max } => {
                write!(f, "Level width {} exceeds maximum {}", width, max)
            }
            QuadMeshError::HeightExceeded { height, max } => {
                write!(f, "Level height {} exceeds maximum {}", height, max)
            }
            QuadMeshError::DepthExceeded { depth, max } => {
                write!(f, "Level depth {} exceeds maximum {}", depth, max)
            }
            QuadMeshError::VolumeExceeded { volume, max } => {
                write!(f, "Level volume {} exceeds maximum {}", volume, max)
            }
            QuadMeshError::ShortestPath(msg) => {
                write!(f, "Shortestpath error: {}", msg)
            }
        }
    }
}

impl std::error::Error for QuadMeshError {}

impl From<SpError> for QuadMeshError {
    fn from(err: SpError) -> Self {
        QuadMeshError::ShortestPath(err.to_string())
    }
}

/// The 14 directions in a quad mesh.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[repr(u8)]
pub enum QuadDirection {
    /// North-North-East (22.5° from N)
    NNE = 0,
    /// North-East (45° from N)
    NE = 1,
    /// East-North-East (67.5° from N)
    ENE = 2,
    /// East-South-East (112.5° from N)
    ESE = 3,
    /// South-East (135° from N)
    SE = 4,
    /// South-South-East (157.5° from N)
    SSE = 5,
    /// South-South-West (202.5° from N)
    SSW = 6,
    /// South-West (225° from N)
    SW = 7,
    /// West-South-West (247.5° from N)
    WSW = 8,
    /// West-North-West (292.5° from N)
    WNW = 9,
    /// North-West (315° from N)
    NW = 10,
    /// North-North-West (337.5° from N)
    NNW = 11,
    /// Up (to higher layer)
    UP = 12,
    /// Down (to lower layer)
    DOWN = 13,
}

impl QuadDirection {
    /// All 14 directions.
    pub const ALL: [QuadDirection; 14] = [
        QuadDirection::NNE,
        QuadDirection::NE,
        QuadDirection::ENE,
        QuadDirection::ESE,
        QuadDirection::SE,
        QuadDirection::SSE,
        QuadDirection::SSW,
        QuadDirection::SW,
        QuadDirection::WSW,
        QuadDirection::WNW,
        QuadDirection::NW,
        QuadDirection::NNW,
        QuadDirection::UP,
        QuadDirection::DOWN,
    ];

    /// The 12 horizontal directions only.
    pub const HORIZONTAL: [QuadDirection; 12] = [
        QuadDirection::NNE,
        QuadDirection::NE,
        QuadDirection::ENE,
        QuadDirection::ESE,
        QuadDirection::SE,
        QuadDirection::SSE,
        QuadDirection::SSW,
        QuadDirection::SW,
        QuadDirection::WSW,
        QuadDirection::WNW,
        QuadDirection::NW,
        QuadDirection::NNW,
    ];

    /// Returns the opposite direction.
    pub fn opposite(self) -> QuadDirection {
        match self {
            QuadDirection::NNE => QuadDirection::SSW,
            QuadDirection::NE => QuadDirection::SW,
            QuadDirection::ENE => QuadDirection::WSW,
            QuadDirection::ESE => QuadDirection::WNW,
            QuadDirection::SE => QuadDirection::NW,
            QuadDirection::SSE => QuadDirection::NNW,
            QuadDirection::SSW => QuadDirection::NNE,
            QuadDirection::SW => QuadDirection::NE,
            QuadDirection::WSW => QuadDirection::ENE,
            QuadDirection::WNW => QuadDirection::ESE,
            QuadDirection::NW => QuadDirection::SE,
            QuadDirection::NNW => QuadDirection::SSE,
            QuadDirection::UP => QuadDirection::DOWN,
            QuadDirection::DOWN => QuadDirection::UP,
        }
    }

    /// Returns the (dx, dy) offset for this direction.
    ///
    /// For the 12 horizontal directions, returns approximate offsets
    /// on a 2x2 grid scale (to handle the 22.5° angles):
    /// - Cardinal-adjacent (NNE, ENE, etc.): move 1 in primary, 2 in secondary
    /// - Diagonal (NE, SE, etc.): move 1 in both
    ///
    /// Returns (0, 0) for UP/DOWN (vertical movement).
    pub fn offset_2d(self) -> (i32, i32) {
        match self {
            // Northeast quadrant
            QuadDirection::NNE => (1, -2),  // Mostly north, bit east
            QuadDirection::NE => (1, -1),   // Diagonal
            QuadDirection::ENE => (2, -1),  // Mostly east, bit north
            // Southeast quadrant
            QuadDirection::ESE => (2, 1),   // Mostly east, bit south
            QuadDirection::SE => (1, 1),    // Diagonal
            QuadDirection::SSE => (1, 2),   // Mostly south, bit east
            // Southwest quadrant
            QuadDirection::SSW => (-1, 2),  // Mostly south, bit west
            QuadDirection::SW => (-1, 1),   // Diagonal
            QuadDirection::WSW => (-2, 1),  // Mostly west, bit south
            // Northwest quadrant
            QuadDirection::WNW => (-2, -1), // Mostly west, bit north
            QuadDirection::NW => (-1, -1),  // Diagonal
            QuadDirection::NNW => (-1, -2), // Mostly north, bit west
            // Vertical
            QuadDirection::UP | QuadDirection::DOWN => (0, 0),
        }
    }

    /// Returns a cardinal fallback offset for edge cases.
    ///
    /// When the full diagonal offset would go out of bounds, this returns
    /// the dominant cardinal direction (just the larger component).
    /// For example, NNE (1, -2) falls back to N (0, -1).
    pub fn cardinal_fallback(self) -> (i32, i32) {
        match self {
            // North-ish directions fall back to N
            QuadDirection::NNE | QuadDirection::NNW => (0, -1),
            // East-ish directions fall back to E
            QuadDirection::ENE | QuadDirection::ESE => (1, 0),
            // South-ish directions fall back to S
            QuadDirection::SSE | QuadDirection::SSW => (0, 1),
            // West-ish directions fall back to W
            QuadDirection::WSW | QuadDirection::WNW => (-1, 0),
            // Diagonals have no cardinal fallback (they're already minimal)
            QuadDirection::NE | QuadDirection::SE | QuadDirection::SW | QuadDirection::NW => {
                self.offset_2d()
            }
            // Vertical
            QuadDirection::UP | QuadDirection::DOWN => (0, 0),
        }
    }

    /// Returns the dz offset for this direction.
    ///
    /// Only UP (-1) and DOWN (+1) have vertical movement.
    /// All horizontal directions return 0.
    pub fn offset_z(self) -> i32 {
        match self {
            QuadDirection::UP => -1,
            QuadDirection::DOWN => 1,
            _ => 0,
        }
    }
}

/// A link to a neighboring cell with precomputed direction vector and distance.
///
/// Uses f16 (half-precision) for floats and u32 for index to reduce memory
/// (12 bytes vs 24 bytes per link with Option). Optimized for WASM deployment.
#[derive(Debug, Clone, Copy, PartialEq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct NeighborLink {
    /// Index of the neighbor cell in the mesh (u32 for memory efficiency).
    pub target_index: u32,
    /// Euclidean distance from this cell's center to neighbor's center (f16).
    pub distance: f16,
    /// Normalized direction X component (f16).
    pub dir_x: f16,
    /// Normalized direction Y component (f16).
    pub dir_y: f16,
    /// Normalized direction Z component (f16).
    pub dir_z: f16,
}

impl NeighborLink {
    /// Creates a new neighbor link with the given parameters.
    pub fn new(target_index: usize, distance: f32, dir_x: f32, dir_y: f32, dir_z: f32) -> Self {
        Self {
            target_index: target_index as u32,
            distance: f16::from_f32(distance),
            dir_x: f16::from_f32(dir_x),
            dir_y: f16::from_f32(dir_y),
            dir_z: f16::from_f32(dir_z),
        }
    }

    /// Creates a neighbor link from a Gate (target + distance) with a direction vector.
    pub fn from_gate(gate: &Gate, dir_x: f32, dir_y: f32, dir_z: f32) -> Self {
        Self::new(gate.target(), gate.distance, dir_x, dir_y, dir_z)
    }

    /// Returns the target index as usize for array indexing.
    #[inline]
    pub fn target(&self) -> usize {
        self.target_index as usize
    }

    /// Returns the direction as a tuple of f32 values.
    pub fn direction(&self) -> (f32, f32, f32) {
        (self.dir_x.to_f32(), self.dir_y.to_f32(), self.dir_z.to_f32())
    }

    /// Returns the distance as f32.
    pub fn distance_f32(&self) -> f32 {
        self.distance.to_f32()
    }

}

/// A cell in the quad mesh.
///
/// All cells in the mesh are walkable by definition - walls are simply not
/// included in the mesh.
///
/// Cells can represent areas of different sizes (1x1, 2x2, 4x4, etc.)
/// through the quadtree structure.
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct QuadCell {
    /// Origin X coordinate (top-left corner of this cell).
    pub x: u32,
    /// Origin Y coordinate (top-left corner of this cell).
    pub y: u32,
    /// The layer (z-level) this cell is on.
    pub z: u32,
    /// The size of this cell (1, 2, 4, 8, etc. - always power of 2).
    /// A size of 1 means a single unit cell.
    /// A size of 4 means this cell covers a 4x4 area.
    pub size: u32,
    /// Connections to neighboring cells (variable length, from Compact25D).
    pub neighbors: Vec<NeighborLink>,
}

impl QuadCell {
    /// Creates a new cell of size 1 at the given coordinates with neighbors from Compact25D.
    pub fn new_with_neighbors(x: u32, y: u32, z: u32, neighbors: Vec<NeighborLink>) -> Self {
        Self {
            x,
            y,
            z,
            size: 1,
            neighbors,
        }
    }

    /// Creates a merged cell from smaller cells.
    pub fn new_merged(x: u32, y: u32, z: u32, size: u32, neighbors: Vec<NeighborLink>) -> Self {
        Self {
            x,
            y,
            z,
            size,
            neighbors,
        }
    }

    /// Returns the area covered by this cell.
    pub fn area(&self) -> u32 {
        self.size * self.size
    }

    /// Checks if the given coordinates fall within this cell's bounds.
    ///
    /// A cell at (x, y, z) with size s covers coordinates from (x, y, z) to (x+s-1, y+s-1, z).
    #[inline]
    pub fn contains(&self, px: usize, py: usize, pz: usize) -> bool {
        let x = self.x as usize;
        let y = self.y as usize;
        let z = self.z as usize;
        let size = self.size as usize;
        pz == z && px >= x && px < x + size && py >= y && py < y + size
    }

    /// Returns the center coordinates of this cell.
    pub fn center(&self) -> (f32, f32) {
        let half = self.size as f32 / 2.0;
        (self.x as f32 + half, self.y as f32 + half)
    }
}

/// A quadtree-based mesh for gradient computation.
///
/// This mesh only contains walkable cells. Walls are not represented - they
/// simply don't exist in the mesh. This optimizes gradient spreading by
/// compacting large uniform walkable areas into bigger cells.
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct QuadMesh {
    /// The cells in the mesh, indexed by their ID. All cells are walkable.
    cells: Vec<QuadCell>,
    /// The original width of the source map.
    width: usize,
    /// The original height of the source map.
    height: usize,
    /// The number of layers (depth).
    depth: usize,
    /// Mapping from (x, y, z) coordinates to cell index.
    /// NO_CELL means no cell at that coordinate (wall or uncompacted).
    /// For compacted cells, multiple coordinates map to the same index.
    coord_to_cell: Vec<usize>,
    /// Cached count of walkable coordinates (computed once at construction).
    walkable_coords_cached: usize,
}

/// Helper struct to implement Source3D from a closure.
struct FnSource<F> {
    width: usize,
    height: usize,
    depth: usize,
    is_passable: F,
}

impl<F: Fn(usize, usize, usize) -> bool> Source3D for FnSource<F> {
    fn get(&self, x: usize, y: usize, z: usize) -> Result<CellType, SpError> {
        if x >= self.width || y >= self.height || z >= self.depth {
            return Err(SpError::invalid_xyz(x, y, z));
        }
        Ok(if (self.is_passable)(x, y, z) {
            CellType::FLOOR
        } else {
            CellType::WALL
        })
    }

    fn width(&self) -> usize {
        self.width
    }

    fn height(&self) -> usize {
        self.height
    }

    fn depth(&self) -> usize {
        self.depth
    }
}

impl QuadMesh {
    /// Checks if dimensions are within allowed limits.
    ///
    /// Returns `Ok(())` if all dimensions are valid, otherwise returns an error.
    /// Note: Volume is checked separately in `check_volume` before ground layer addition.
    fn check_dimensions(width: usize, height: usize, depth: usize) -> Result<(), QuadMeshError> {
        if width > LEVEL_MAX_W {
            return Err(QuadMeshError::WidthExceeded {
                width,
                max: LEVEL_MAX_W,
            });
        }
        if height > LEVEL_MAX_H {
            return Err(QuadMeshError::HeightExceeded {
                height,
                max: LEVEL_MAX_H,
            });
        }
        if depth > LEVEL_MAX_D {
            return Err(QuadMeshError::DepthExceeded {
                depth,
                max: LEVEL_MAX_D,
            });
        }
        Ok(())
    }

    /// Checks if the input volume (before ground layer) is within limits.
    ///
    /// This is called BEFORE the ground layer is added, so w*h*d <= 512*512
    /// means the final volume may be up to 512*512*2.
    fn check_volume(width: usize, height: usize, depth: usize) -> Result<(), QuadMeshError> {
        let volume = width * height * depth;
        if volume > LEVEL_MAX_VOLUME {
            return Err(QuadMeshError::VolumeExceeded {
                volume,
                max: LEVEL_MAX_VOLUME,
            });
        }
        Ok(())
    }

    /// Creates a new quad mesh from a source map.
    ///
    /// The `is_passable` function determines if a cell at (x, y, z) is walkable.
    /// Only walkable cells are included in the mesh.
    /// Uniform regions are automatically compacted into larger cells.
    ///
    /// **Ceiling layer**: If the topmost layer contains any walkable cells,
    /// an extra layer of walls is automatically added above it. This ensures
    /// there's always a solid ground. This operation is idempotent - if the
    /// top layer is already all walls, no extra layer is added.
    ///
    /// # Errors
    ///
    /// Returns an error if dimensions exceed limits:
    /// - Width > 512
    /// - Height > 512
    /// - Depth > 8
    /// - Volume (width * height * depth) > 512 * 512 (checked BEFORE ground layer)
    ///
    /// Note: The volume check happens before the ground layer is added,
    /// so a 512x512x1 map is valid (becomes 512x512x2 after ground).
    ///
    /// Uses `Compact25D` from shortestpath to build initial connections,
    /// ensuring proper bidirectional links.
    pub fn new<F>(width: usize, height: usize, depth: usize, is_passable: F) -> Result<Self, QuadMeshError>
    where
        F: Fn(usize, usize, usize) -> bool,
    {
        use shortestpath::mesh_3d::Index3D;

        // Check ALL limits on input dimensions BEFORE adding ground layer
        Self::check_dimensions(width, height, depth)?;
        Self::check_volume(width, height, depth)?;

        // Check if topmost layer has any passable cells
        let top_z = depth.saturating_sub(1);
        let top_has_passable = (0..height)
            .any(|y| (0..width).any(|x| is_passable(x, y, top_z)));

        // If top layer has passable cells, add ground layer (all walls)
        let final_depth = if top_has_passable { depth + 1 } else { depth };

        let total = width * height * final_depth;

        // Step 1: Create Compact25D from the source (gives us proper bidirectional connections)
        // Use final_depth so ground layer is included (will be all walls)
        // Wrap is_passable to ensure ground layer (z >= depth) is always walls
        let wrapped_passable = |x: usize, y: usize, z: usize| {
            if z >= depth {
                false // Ceiling layer is all walls
            } else {
                is_passable(x, y, z)
            }
        };
        let source = FnSource {
            width,
            height,
            depth: final_depth,
            is_passable: wrapped_passable,
        };
        let base_mesh = Compact25D::from_source(&source)
            .expect("Failed to create Compact25D")
            .unique(); // Filter to connected zone only

        // Step 2: Build QuadCells from Compact25D
        let mut cells = Vec::with_capacity(base_mesh.len());
        let mut coord_to_cell = vec![NO_CELL; total];

        for compact_idx in 0..base_mesh.len() {
            let (x, y, z) = base_mesh
                .index_to_xyz(compact_idx)
                .expect("Invalid compact index");

            let full_idx = z * width * height + y * width + x;
            coord_to_cell[full_idx] = cells.len();

            // Get neighbors from Compact25D and convert to NeighborLinks with direction vectors
            let successors: Vec<_> = base_mesh.successors(compact_idx, false).collect();
            let mut neighbors = Vec::with_capacity(successors.len());

            let cx = x as f32 + 0.5; // Center of this cell
            let cy = y as f32 + 0.5;
            let cz = z as f32;

            for gate in successors {
                let (nx, ny, nz) = base_mesh
                    .index_to_xyz(gate.target())
                    .expect("Invalid neighbor index");
                let ncx = nx as f32 + 0.5;
                let ncy = ny as f32 + 0.5;
                let ncz = nz as f32;

                let dx = ncx - cx;
                let dy = ncy - cy;
                let dz = ncz - cz;
                let dist = (dx * dx + dy * dy + dz * dz).sqrt();
                let (dir_x, dir_y, dir_z) = if dist > 0.0 {
                    (dx / dist, dy / dist, dz / dist)
                } else {
                    (0.0, 0.0, 0.0)
                };

                neighbors.push(NeighborLink::from_gate(&gate, dir_x, dir_y, dir_z));
            }

            cells.push(QuadCell::new_with_neighbors(x as u32, y as u32, z as u32, neighbors));
        }

        let mut mesh = Self {
            cells,
            width,
            height,
            depth: final_depth,
            coord_to_cell,
            walkable_coords_cached: 0, // Will be computed after compaction
        };

        // Step 3: Compact uniform regions (rewires existing links)
        mesh.compact();

        // Cache walkable coords count (coord_to_cell may have changed during compact)
        mesh.walkable_coords_cached = mesh.coord_to_cell.iter().filter(|&&idx| idx != NO_CELL).count();

        Ok(mesh)
    }

    /// Compacts uniform walkable regions into larger cells using quadtree merging.
    ///
    /// Iteratively merges 2x2 groups of cells into larger cells.
    /// This reduces the total cell count for maps with large uniform areas.
    /// Maximum cell size after compaction (8x8 is enough for good optimization
    /// while keeping cells small enough for navigation).
    const MAX_CELL_SIZE: u32 = 8;

    fn compact(&mut self) {
        let mut current_size = 1u32;

        // Compact 1x1 -> 2x2 -> 4x4 -> 8x8, stop at 8x8
        // All z-layers are processed in each pass to keep sizes roughly in sync
        while current_size < Self::MAX_CELL_SIZE {
            let next_size = current_size * 2;
            self.compact_pass(current_size, next_size);
            current_size = next_size;
        }

        // Rebuild coord_to_cell mapping after compaction
        self.rebuild_coord_mapping();
    }

    /// Maximum allowed size ratio for vertical links.
    /// A 2x2 cell can connect to 1x1, 2x2, or 4x4, but not 8x8.
    const MAX_VERTICAL_SIZE_RATIO: u32 = 2;

    /// Checks if a coordinate is a wall (not passable).
    fn is_wall(&self, x: usize, y: usize, z: usize) -> bool {
        if x >= self.width || y >= self.height || z >= self.depth {
            return true; // Out of bounds = wall
        }
        let idx = z * self.width * self.height + y * self.width + x;
        self.coord_to_cell[idx] == NO_CELL
    }

    /// Checks if a cell at (x, y, z) with given size would touch a wall or map border.
    fn touches_wall_or_border(&self, x: usize, y: usize, z: usize, size: usize) -> bool {
        // Border check - if cell touches any edge of the map
        if x == 0 || y == 0 || x + size >= self.width || y + size >= self.height {
            return true;
        }

        // Wall check - check all adjacent cells around the perimeter
        // North edge (y - 1)
        for px in x..x + size {
            if self.is_wall(px, y - 1, z) {
                return true;
            }
        }
        // South edge (y + size)
        for px in x..x + size {
            if self.is_wall(px, y + size, z) {
                return true;
            }
        }
        // West edge (x - 1)
        for py in y..y + size {
            if self.is_wall(x - 1, py, z) {
                return true;
            }
        }
        // East edge (x + size)
        for py in y..y + size {
            if self.is_wall(x + size, py, z) {
                return true;
            }
        }

        false
    }

    /// One pass of compaction: merge cells of `current_size` into `next_size`.
    fn compact_pass(&mut self, current_size: u32, next_size: u32) {
        for z in 0..self.depth {
            let mut y = 0;
            while y + next_size as usize <= self.height {
                let mut x = 0;
                while x + next_size as usize <= self.width {
                    self.try_merge_group(x, y, z, current_size, next_size);
                    x += next_size as usize;
                }
                y += next_size as usize;
            }
        }
    }

    /// Try to merge a 2x2 group of cells into one larger cell.
    /// When merging, rewires all existing links:
    /// - Merged cell gets union of external neighbors from all 4 source cells
    /// - All cells pointing to source cells get redirected to merged cell
    fn try_merge_group(
        &mut self,
        x: usize,
        y: usize,
        z: usize,
        current_size: u32,
        next_size: u32,
    ) {
        // Don't merge if resulting cell would touch wall or border
        if self.touches_wall_or_border(x, y, z, next_size as usize) {
            return;
        }

        let step = current_size as usize;
        let positions = [
            (x, y),
            (x + step, y),
            (x, y + step),
            (x + step, y + step),
        ];

        // Get cell indices for each position
        let mut cell_indices = Vec::with_capacity(4);
        for (px, py) in positions {
            if let Some(idx) = self.cell_at(px, py, z) {
                cell_indices.push(idx);
            } else {
                return; // Wall or out of bounds, can't merge
            }
        }

        // Check if all 4 cells have the same size
        let first = &self.cells[cell_indices[0]];
        if first.size != current_size {
            return;
        }

        for &idx in &cell_indices[1..] {
            let cell = &self.cells[idx];
            if cell.size != current_size {
                return; // Can't merge: different size
            }
        }

        // Check vertical neighbors: don't merge if it would create invalid size ratio
        // Merged cell size (next_size) must be at most 2x the size of any vertical neighbor
        for &idx in &cell_indices {
            for link in &self.cells[idx].neighbors {
                let neighbor = &self.cells[link.target()];
                // Is this a vertical link (different z)?
                if neighbor.z != z as u32 {
                    // Would merged cell be too big compared to this vertical neighbor?
                    if next_size > neighbor.size * Self::MAX_VERTICAL_SIZE_RATIO {
                        return; // Can't merge: would violate vertical size constraint
                    }
                }
            }
        }

        // All 4 cells are uniform and vertical constraints satisfied! Merge them.
        let merged_idx = cell_indices[0];
        let absorbed_indices: std::collections::HashSet<usize> =
            cell_indices.iter().copied().collect();

        // Collect external neighbors from all 4 cells (excluding the 4 cells themselves)
        let mut external_neighbors: Vec<NeighborLink> = Vec::new();
        let mut seen_targets: std::collections::HashSet<usize> = std::collections::HashSet::new();

        // Compute center of merged cell
        let merged_cx = x as f32 + next_size as f32 / 2.0;
        let merged_cy = y as f32 + next_size as f32 / 2.0;
        let merged_cz = z as f32;

        for &cell_idx in &cell_indices {
            for link in &self.cells[cell_idx].neighbors {
                // Skip links to other cells being merged
                if absorbed_indices.contains(&link.target()) {
                    continue;
                }
                // Skip if we already have a link to this target
                if seen_targets.contains(&link.target()) {
                    continue;
                }
                seen_targets.insert(link.target());

                // Recompute direction from merged cell center to target center
                let target = &self.cells[link.target()];
                let (tcx, tcy) = target.center();
                let tcz = target.z as f32;

                let dx = tcx - merged_cx;
                let dy = tcy - merged_cy;
                let dz = tcz - merged_cz;
                let dist = (dx * dx + dy * dy + dz * dz).sqrt();
                let (dir_x, dir_y, dir_z) = if dist > 0.0 {
                    (dx / dist, dy / dist, dz / dist)
                } else {
                    (0.0, 0.0, 0.0)
                };

                external_neighbors.push(NeighborLink::new(link.target(), dist, dir_x, dir_y, dir_z));
            }
        }

        // Find cells that need back-link updates (only cells that had links TO the merged cells)
        // These are exactly the external neighbors we just collected
        let cells_to_update: std::collections::HashSet<usize> = external_neighbors
            .iter()
            .map(|link| link.target())
            .collect();

        // Update only those cells that pointed to merged cells
        for &cell_idx in &cells_to_update {
            if cell_idx >= self.cells.len() {
                continue;
            }
            let cell = &mut self.cells[cell_idx];
            if cell.size == 0 {
                continue;
            }

            // Pre-compute cell center before borrowing neighbors
            let (cx, cy) = cell.center();
            let cz = cell.z as f32;

            for link in &mut cell.neighbors {
                if absorbed_indices.contains(&link.target()) && link.target() != merged_idx {
                    // Redirect to merged cell and update direction
                    link.target_index = merged_idx as u32;

                    // Recompute direction from this cell to merged cell
                    let dx = merged_cx - cx;
                    let dy = merged_cy - cy;
                    let dz = merged_cz - cz;
                    let dist = (dx * dx + dy * dy + dz * dz).sqrt();
                    if dist > 0.0 {
                        link.dir_x = f16::from_f32(dx / dist);
                        link.dir_y = f16::from_f32(dy / dist);
                        link.dir_z = f16::from_f32(dz / dist);
                        link.distance = f16::from_f32(dist);
                    }
                }
            }
            // Deduplicate: if multiple links now point to merged_idx, keep only one
            let mut seen = std::collections::HashSet::new();
            cell.neighbors.retain(|link| {
                if seen.contains(&link.target_index) {
                    false
                } else {
                    seen.insert(link.target_index);
                    true
                }
            });
        }

        // Create the merged cell
        self.cells[merged_idx] = QuadCell::new_merged(
            x as u32,
            y as u32,
            z as u32,
            next_size,
            external_neighbors,
        );

        // Mark other 3 cells as "absorbed" by setting their size to 0
        for &idx in &cell_indices[1..] {
            self.cells[idx].size = 0;
            self.cells[idx].neighbors.clear();
        }
    }

    /// Rebuild the coord_to_cell mapping after compaction.
    /// Also remaps all neighbor indices to account for removed cells.
    fn rebuild_coord_mapping(&mut self) {
        // Build old-to-new index mapping
        let mut old_to_new: Vec<Option<usize>> = vec![None; self.cells.len()];
        let mut new_idx = 0usize;

        for (old_idx, cell) in self.cells.iter().enumerate() {
            if cell.size > 0 {
                old_to_new[old_idx] = Some(new_idx);
                new_idx += 1;
            }
        }

        // Filter to non-absorbed cells and remap neighbor indices
        let mut new_cells = Vec::with_capacity(new_idx);
        for cell in &self.cells {
            if cell.size > 0 {
                let mut new_cell = cell.clone();
                // Remap all neighbor indices
                for link in &mut new_cell.neighbors {
                    if let Some(new_target) = old_to_new[link.target()] {
                        link.target_index = new_target as u32;
                    }
                }
                // Remove any links to absorbed cells (shouldn't happen but safety check)
                new_cell.neighbors.retain(|link| old_to_new.get(link.target()).copied().flatten().is_some() || link.target() < new_idx);
                new_cells.push(new_cell);
            }
        }

        self.cells = new_cells;

        // Reset coord_to_cell to NO_CELL
        for val in &mut self.coord_to_cell {
            *val = NO_CELL;
        }

        // Rebuild: iterate over cells and fill in coordinates they cover
        // This is O(total_coordinates) instead of O(coordinates * cells)
        for (cell_idx, cell) in self.cells.iter().enumerate() {
            let size = cell.size as usize;
            for dz in 0..1 {
                // Currently 2D, z is always 1-sized
                for dy in 0..size {
                    for dx in 0..size {
                        let x = cell.x as usize + dx;
                        let y = cell.y as usize + dy;
                        let z = cell.z as usize + dz;
                        if x < self.width && y < self.height && z < self.depth {
                            let coord_idx = z * self.width * self.height + y * self.width + x;
                            self.coord_to_cell[coord_idx] = cell_idx;
                        }
                    }
                }
            }
        }
    }

    /// Returns the number of cells in the mesh.
    pub fn cell_count(&self) -> usize {
        self.cells.len()
    }

    /// Returns the total volume of the coordinate space (width * height * depth).
    pub fn total_volume(&self) -> usize {
        self.width * self.height * self.depth
    }

    /// Returns the number of walkable coordinates (coordinates that map to a cell).
    ///
    /// This value is cached at construction time for O(1) access.
    pub fn walkable_coords(&self) -> usize {
        self.walkable_coords_cached
    }

    /// Returns the cell at the given index.
    pub fn cell(&self, index: usize) -> Option<&QuadCell> {
        self.cells.get(index)
    }

    /// Returns the cell index for the given coordinates.
    ///
    /// Returns None if the coordinate is a wall or out of bounds.
    pub fn cell_at(&self, x: usize, y: usize, z: usize) -> Option<usize> {
        if x < self.width && y < self.height && z < self.depth {
            let idx = z * self.width * self.height + y * self.width + x;
            let cell_idx = self.coord_to_cell[idx];
            if cell_idx != NO_CELL {
                Some(cell_idx)
            } else {
                None
            }
        } else {
            None
        }
    }

    /// Returns the original dimensions of the source map.
    pub fn dimensions(&self) -> (usize, usize, usize) {
        (self.width, self.height, self.depth)
    }

    /// Returns the direction vector from cell `from` to cell `to`.
    ///
    /// Returns `None` if `to` is not a direct neighbor of `from`.
    pub fn direction_to_neighbor(&self, from: usize, to: usize) -> Option<(f32, f32, f32)> {
        self.link_to_neighbor(from, to).map(|link| link.direction())
    }

    /// Returns the full NeighborLink from cell `from` to cell `to`.
    ///
    /// Returns `None` if `to` is not a direct neighbor of `from`.
    pub fn link_to_neighbor(&self, from: usize, to: usize) -> Option<&NeighborLink> {
        let cell = self.cells.get(from)?;
        cell.neighbors.iter().find(|link| link.target() == to)
    }

    /// Creates a QuadMesh from ASCII art text.
    ///
    /// The text should be a grid where:
    /// - `#` represents walls (not included in mesh)
    /// - Any other character (typically space or `.`) represents floor (included)
    ///
    /// Lines are separated by newlines. All lines should have the same length.
    /// For multi-layer 3D maps, layers are separated by lines containing only
    /// separator characters (`-`, `_`, `=`).
    ///
    /// # Example
    ///
    /// ```
    /// use liquidwar7core::quad_mesh::QuadMesh;
    ///
    /// // Single layer (2D) - ground added since top has walkable cells
    /// let mesh_2d = QuadMesh::from_text("...\n.#.\n...").unwrap();
    /// assert_eq!(mesh_2d.dimensions(), (3, 3, 2)); // 1 user layer + 1 ground
    ///
    /// // Multi-layer (3D) - layers separated by "---", ground added
    /// let mesh_3d = QuadMesh::from_text("...\n.#.\n---\n...\n...").unwrap();
    /// assert_eq!(mesh_3d.dimensions(), (3, 2, 3)); // 2 user layers + 1 ground
    /// ```
    pub fn from_text(text: &str) -> Result<Self, QuadMeshError> {
        Self::from_lines(text.lines())
    }

    /// Creates a QuadMesh from a slice of string slices.
    pub fn from_slice(input: &[&str]) -> Result<Self, QuadMeshError> {
        Self::from_lines(input.iter().copied())
    }

    /// Creates a QuadMesh from a slice of Strings.
    pub fn from_strings(input: &[String]) -> Result<Self, QuadMeshError> {
        Self::from_lines(input.iter().map(|s| s.as_str()))
    }

    /// Checks if a line is a separator line (used to delimit 3D layers).
    ///
    /// A line is a separator if it contains only separator characters (`-`, `_`, `=`) and spaces.
    fn is_sep_line(line: &str) -> bool {
        if line.is_empty() {
            return false;
        }
        let mut has_sep_char = false;
        for chr in line.chars() {
            if chr == '-' || chr == '_' || chr == '=' {
                has_sep_char = true;
            } else if chr != ' ' {
                return false;
            }
        }
        has_sep_char
    }

    /// Creates a QuadMesh from an iterator of string slices.
    ///
    /// Layers are separated by lines containing only separator characters (`-`, `_`, `=`).
    pub fn from_lines<'a, I>(input: I) -> Result<Self, QuadMeshError>
    where
        I: Iterator<Item = &'a str>,
    {
        let mut layers: Vec<Vec<&str>> = Vec::new();
        let mut current_layer: Vec<&str> = Vec::new();

        for line in input {
            if Self::is_sep_line(line) {
                if !current_layer.is_empty() {
                    layers.push(current_layer);
                    current_layer = Vec::new();
                }
            } else {
                current_layer.push(line);
            }
        }
        if !current_layer.is_empty() {
            layers.push(current_layer);
        }

        // Calculate dimensions
        let depth = layers.len().max(1);
        let height = layers.iter().map(|l| l.len()).max().unwrap_or(0);
        let width = layers
            .iter()
            .flat_map(|l| l.iter())
            .map(|line| line.len())
            .max()
            .unwrap_or(0);

        Self::new(width, height, depth, |x, y, z| {
            layers
                .get(z)
                .and_then(|layer| layer.get(y))
                .and_then(|line| line.chars().nth(x))
                .map(|c| c != '#')
                .unwrap_or(false)
        })
    }

    /// Creates a QuadMesh from a Source3D.
    ///
    /// This is the core constructor that converts any Source3D implementation
    /// into a QuadMesh. Floor cells become walkable, wall cells are excluded.
    pub fn from_source(source: &impl Source3D) -> Result<Self, QuadMeshError> {
        let width = source.width();
        let height = source.height();
        let depth = source.depth();

        Self::new(width, height, depth, |x, y, z| {
            source
                .get(x, y, z)
                .map(|cell| cell.can_go())
                .unwrap_or(false)
        })
    }

    /// Creates a QuadMesh from a vector of image file paths.
    ///
    /// Each image file represents one layer (z-level) in the mesh.
    /// Pixels are converted to walkable or wall cells based on their brightness.
    /// Bright pixels (above 50% brightness) become walkable, dark pixels become walls.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `paths` - Vector of file paths, one per layer (ordered from z=0 to z=depth-1)
    ///
    /// # Example
    ///
    /// ```no_run
    /// use liquidwar7core::quad_mesh::QuadMesh;
    ///
    /// let paths = vec!["layer0.png", "layer1.png", "layer2.png"];
    /// let mesh = QuadMesh::from_paths(&paths).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_paths<P: AsRef<std::path::Path>>(paths: &[P]) -> Result<Self, QuadMeshError> {
        Self::from_paths_with_threshold(paths, Source3DFromImage::DEFAULT_THRESHOLD)
    }

    /// Creates a QuadMesh from image paths with a custom brightness threshold.
    ///
    /// Each image file represents one layer (z-level) in the mesh.
    /// Pixels with brightness below the threshold are considered walls.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `paths` - Vector of file paths, one per layer
    /// * `threshold` - Brightness threshold (0.0-1.0). Pixels darker than this are walls.
    ///
    /// # Example
    ///
    /// ```no_run
    /// use liquidwar7core::quad_mesh::QuadMesh;
    ///
    /// let paths = vec!["layer0.png", "layer1.png"];
    /// let mesh = QuadMesh::from_paths_with_threshold(&paths, 0.5).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_paths_with_threshold<P: AsRef<std::path::Path>>(
        paths: &[P],
        threshold: f32,
    ) -> Result<Self, QuadMeshError> {
        let source = Source3DFromImage::from_paths(paths, threshold)?;
        Self::from_source(&source)
    }

    /// Creates a QuadMesh from a slice of DynamicImages.
    ///
    /// Each image represents one layer (z-level) in the mesh.
    /// All images must have the same dimensions.
    /// Uses the default threshold (0.5).
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `images` - Slice of images, one per layer
    ///
    /// # Example
    ///
    /// ```no_run
    /// use liquidwar7core::quad_mesh::QuadMesh;
    ///
    /// let layer0 = image::open("layer0.png").unwrap();
    /// let layer1 = image::open("layer1.png").unwrap();
    /// let mesh = QuadMesh::from_images(&[layer0, layer1]).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_images(images: &[image::DynamicImage]) -> Result<Self, QuadMeshError> {
        Self::from_images_with_threshold(images, Source3DFromImage::DEFAULT_THRESHOLD)
    }

    /// Creates a QuadMesh from a slice of DynamicImages with a custom brightness threshold.
    ///
    /// Each image represents one layer (z-level) in the mesh.
    /// All images must have the same dimensions.
    /// Pixels with brightness below the threshold are considered walls.
    ///
    /// Requires the `image` feature.
    ///
    /// # Arguments
    ///
    /// * `images` - Slice of images, one per layer
    /// * `threshold` - Brightness threshold (0.0-1.0). Pixels darker than this are walls.
    ///
    /// # Example
    ///
    /// ```no_run
    /// use liquidwar7core::quad_mesh::QuadMesh;
    ///
    /// let layer0 = image::open("layer0.png").unwrap();
    /// let layer1 = image::open("layer1.png").unwrap();
    /// let mesh = QuadMesh::from_images_with_threshold(&[layer0, layer1], 0.5).unwrap();
    /// ```
    #[cfg(feature = "image")]
    pub fn from_images_with_threshold(
        images: &[image::DynamicImage],
        threshold: f32,
    ) -> Result<Self, QuadMeshError> {
        let source = Source3DFromImage::from_images(images, threshold)?;
        Self::from_source(&source)
    }
}

impl Mesh for QuadMesh {
    type IntoIter = std::vec::IntoIter<Gate>;

    fn successors(&self, from: usize, backward: bool) -> Self::IntoIter {
        let mut gates = Vec::new();

        if let Some(cell) = self.cells.get(from) {
            // All cells in the mesh are walkable, so just iterate neighbors
            for link in &cell.neighbors {
                gates.push(Gate::new(link.target(), link.distance_f32()));
            }
        }

        if backward {
            gates.reverse();
        }
        gates.into_iter()
    }

    fn len(&self) -> usize {
        self.cells.len()
    }
}

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

    #[test]
    fn test_direction_opposite() {
        assert_eq!(QuadDirection::NE.opposite(), QuadDirection::SW);
        assert_eq!(QuadDirection::UP.opposite(), QuadDirection::DOWN);
        assert_eq!(QuadDirection::NNE.opposite(), QuadDirection::SSW);
    }

    #[test]
    fn test_direction_offset() {
        assert_eq!(QuadDirection::NE.offset_2d(), (1, -1));
        assert_eq!(QuadDirection::SW.offset_2d(), (-1, 1));
        assert_eq!(QuadDirection::NNE.offset_2d(), (1, -2));
        assert_eq!(QuadDirection::UP.offset_2d(), (0, 0));
        assert_eq!(QuadDirection::UP.offset_z(), -1);
        assert_eq!(QuadDirection::DOWN.offset_z(), 1);
    }

    #[test]
    fn test_quad_mesh_creation() {
        // Create a simple 4x4x1 mesh, all passable
        // Border cells can't compact, so 4x4 stays uncompacted (16 cells)
        let mesh = QuadMesh::new(4, 4, 1, |_, _, _| true).unwrap();

        assert_eq!(mesh.cell_count(), 16); // No compaction - all cells touch border
        // Depth is 2: 1 user layer + 1 ground layer
        assert_eq!(mesh.dimensions(), (4, 4, 2));
    }

    #[test]
    fn test_quad_mesh_with_walls() {
        // Create a 3x3x1 mesh with a wall in the center
        let mesh = QuadMesh::new(3, 3, 1, |x, y, _| !(x == 1 && y == 1)).unwrap();

        // Should have 8 cells (9 - 1 wall)
        assert_eq!(mesh.cell_count(), 8);

        // Center cell should not exist
        assert!(mesh.cell_at(1, 1, 0).is_none());

        // Corner cells should exist
        assert!(mesh.cell_at(0, 0, 0).is_some());
        assert!(mesh.cell_at(2, 2, 0).is_some());
    }

    #[test]
    fn test_neighbor_connections() {
        // Create a 5x5x1 mesh with a checkerboard pattern (can't be compacted)
        let mesh = QuadMesh::new(5, 5, 1, |x, y, _| (x + y) % 2 == 0).unwrap();

        // Cell at (2,2) should exist and have diagonal neighbors
        let center = mesh.cell_at(2, 2, 0).unwrap();
        let cell = mesh.cell(center).unwrap();

        // Check that neighbor connections exist
        let neighbor_count = cell.neighbors.len();
        assert!(neighbor_count > 0, "Cell should have neighbors");

        // Verify the mesh Mesh trait works - successors should return neighbors
        use shortestpath::Mesh;
        let successors: Vec<_> = mesh.successors(center, false).collect();
        assert!(!successors.is_empty(), "Should have successors via Mesh trait");

        // Verify all neighbor targets are valid cell indices
        for neighbor in &cell.neighbors {
            assert!(
                mesh.cell(neighbor.target()).is_some(),
                "Neighbor target should be a valid cell"
            );
        }
    }

    #[test]
    fn test_compaction_uniform_4x4() {
        // Create a 4x4 mesh, all passable
        // All cells touch border, so no compaction possible
        let mesh = QuadMesh::new(4, 4, 1, |_, _, _| true).unwrap();

        assert_eq!(mesh.cell_count(), 16); // No compaction at borders
    }

    #[test]
    fn test_compaction_uniform_8x8() {
        // Create an 8x8 mesh, all passable
        // Border cells stay size 1, only interior cells at (2,2), (4,2), (2,4), (4,4)
        // can form 2x2 cells: 64 - 16 + 4 = 52 cells
        let mesh = QuadMesh::new(8, 8, 1, |_, _, _| true).unwrap();

        assert_eq!(mesh.cell_count(), 52);

        // Check that some interior cells are size 2
        let interior_cell = mesh.cell_at(2, 2, 0).unwrap();
        assert_eq!(mesh.cell(interior_cell).unwrap().size, 2);
    }

    #[test]
    fn test_compaction_with_obstacle() {
        // Create a 4x4 mesh with one wall cell, with compaction
        let mesh = QuadMesh::new(4, 4, 1, |x, y, _| !(x == 0 && y == 0)).unwrap();

        // Should not fully compact due to the wall
        // The bottom-right 2x2 should compact, but top-left quadrant can't
        assert!(mesh.cell_count() > 1);
        assert!(mesh.cell_count() < 16);
    }

    #[test]
    fn test_compaction_checkerboard() {
        // Checkerboard pattern can't be compacted at all
        let mesh = QuadMesh::new(4, 4, 1, |x, y, _| (x + y) % 2 == 0).unwrap();

        // Should have 8 cells (half of 16), no compaction possible
        assert_eq!(mesh.cell_count(), 8);
    }

    #[test]
    fn test_compaction_preserves_coord_lookup() {
        // After compaction, coord lookup should still work
        let mesh = QuadMesh::new(8, 8, 1, |_, _, _| true).unwrap();

        // All coordinates should map to some cell
        for y in 0..8 {
            for x in 0..8 {
                let idx = mesh.cell_at(x, y, 0);
                assert!(idx.is_some(), "Expected cell at ({}, {})", x, y);
            }
        }

        // Interior compacted cells should share an index
        // (2,2), (2,3), (3,2), (3,3) should all map to the same 2x2 cell
        let idx_2_2 = mesh.cell_at(2, 2, 0).unwrap();
        let idx_2_3 = mesh.cell_at(2, 3, 0).unwrap();
        let idx_3_2 = mesh.cell_at(3, 2, 0).unwrap();
        let idx_3_3 = mesh.cell_at(3, 3, 0).unwrap();
        assert_eq!(idx_2_2, idx_2_3);
        assert_eq!(idx_2_2, idx_3_2);
        assert_eq!(idx_2_2, idx_3_3);
    }

    #[test]
    fn test_euclidean_distance_calculation() {
        // Create a simple 3x1 mesh
        let mesh = QuadMesh::new(3, 1, 1, |_, _, _| true).unwrap();

        // Get cells at positions 0 and 2
        let cell_0 = mesh.cell_at(0, 0, 0).unwrap();
        let _cell_2 = mesh.cell_at(2, 0, 0).unwrap();

        // Check that cell 0 has neighbors with reasonable distances
        let cell = mesh.cell(cell_0).unwrap();
        assert!(!cell.neighbors.is_empty(), "Cell should have neighbors");

        // Distance to adjacent cell should be close to 1.0
        for link in &cell.neighbors {
            let dist = link.distance_f32();
            assert!(dist > 0.0 && dist < 3.0, "Distance should be reasonable");
        }
    }

    #[test]
    fn test_mesh_trait_with_gradient() {
        use shortestpath::Gradient;

        // Create a 5x5 mesh with a wall in the middle
        let mesh = QuadMesh::new(5, 5, 1, |x, y, _| !(x == 2 && y == 2)).unwrap();

        // Create a gradient and set a source
        let mut gradient = Gradient::from_mesh(&mesh);

        // Find a valid cell index
        let source_idx = mesh.cell_at(0, 0, 0).unwrap();
        gradient.set_distance(source_idx, 0.0);

        // Spread the gradient
        gradient.spread(&mesh);

        // All reachable cells should have finite distances
        for i in 0..mesh.cell_count() {
            let dist = gradient.get_distance(i);
            assert!(dist < f32::INFINITY, "Cell {} should be reachable", i);
        }
    }

    #[test]
    fn test_mesh_trait_compacted() {
        use shortestpath::Gradient;

        // Create a partially compacted 8x8 mesh
        let mesh = QuadMesh::new(8, 8, 1, |_, _, _| true).unwrap();

        // 52 cells (border cells stay size 1, interior gets some compaction)
        assert_eq!(mesh.cell_count(), 52);

        // Gradient should work with the compacted mesh
        let mut gradient = Gradient::from_mesh(&mesh);
        let source = mesh.cell_at(0, 0, 0).unwrap();
        gradient.set_distance(source, 0.0);
        gradient.spread(&mesh);

        // All cells should be reachable
        for i in 0..mesh.cell_count() {
            assert!(gradient.get_distance(i) < f32::INFINITY);
        }
    }

    #[test]
    fn test_connection_reciprocity() {
        // Verify that all connections are bidirectional
        let mesh = QuadMesh::new(10, 10, 1, |x, y, _| {
            // Create some walls to force different cell sizes
            !(x == 5 && y < 8)
        })
        .unwrap();

        // For every cell, for every neighbor link, verify the neighbor links back
        for cell_idx in 0..mesh.cell_count() {
            let cell = mesh.cell(cell_idx).unwrap();
            for link in &cell.neighbors {
                let neighbor_idx = link.target();
                let neighbor = mesh.cell(neighbor_idx).unwrap();

                // Neighbor must have a link back to this cell
                let has_back_link = neighbor.neighbors.iter().any(|l| l.target() == cell_idx);

                assert!(
                    has_back_link,
                    "Cell {} links to cell {}, but cell {} has no link back",
                    cell_idx, neighbor_idx, neighbor_idx
                );
            }
        }
    }

    #[test]
    fn test_compaction_large_interior() {
        // Create a 16x16 mesh, all passable
        // Interior cells should compact significantly
        let mesh = QuadMesh::new(16, 16, 1, |_, _, _| true).unwrap();

        // Without border restriction: would be 4 cells (4x 8x8)
        // With border restriction: border cells stay size 1
        // Interior can have larger cells
        assert!(mesh.cell_count() < 256, "Should have some compaction");
        assert!(mesh.cell_count() > 4, "Borders prevent full compaction");

        // Check that deep interior cells are larger
        // (4,4) to (7,7) should be in a size-4 cell (if 4x4 compaction succeeded)
        let interior_cell = mesh.cell_at(4, 4, 0).unwrap();
        let cell = mesh.cell(interior_cell).unwrap();
        assert!(cell.size >= 2, "Interior should compact to at least 2x2");
    }

    #[test]
    fn test_from_text() {
        let text = "...\n.#.\n...";
        let mesh = QuadMesh::from_text(text).unwrap();

        // Depth is 2: 1 user layer + 1 ground layer (since top has walkable cells)
        assert_eq!(mesh.dimensions(), (3, 3, 2));
        // 8 walkable cells (9 - 1 wall)
        assert_eq!(mesh.cell_count(), 8);
        // Center is wall
        assert!(mesh.cell_at(1, 1, 0).is_none());
    }

    #[test]
    fn test_vertical_link_size_constraint() {
        // Create a 16x16x2 mesh where layer 0 has walls that prevent compaction
        // but layer 1 is fully open - compaction on layer 1 should be limited
        // by vertical neighbors on layer 0
        let mesh = QuadMesh::new(16, 16, 2, |x, y, z| {
            if z == 0 {
                // Layer 0: walls creating pattern to limit compaction
                !(x == 5 && y < 12) && !(y == 5 && x < 12)
            } else {
                // Layer 1: fully open, but compaction limited by layer 0 neighbors
                true
            }
        })
        .unwrap();

        // Count vertical links to ensure they weren't removed
        let mut vertical_link_count = 0;

        // Verify vertical links exist AND respect the size constraint
        for (cell_idx, cell) in mesh.cells.iter().enumerate() {
            for link in &cell.neighbors {
                let neighbor = mesh.cell(link.target()).unwrap();

                // If this is a vertical link (different z)
                if neighbor.z != cell.z {
                    vertical_link_count += 1;

                    let (larger, smaller) = if cell.size >= neighbor.size {
                        (cell.size, neighbor.size)
                    } else {
                        (neighbor.size, cell.size)
                    };

                    assert!(
                        larger <= smaller * 2,
                        "Cell {} (size {}) has vertical link to cell {} (size {}), ratio {} > 2",
                        cell_idx,
                        cell.size,
                        link.target(),
                        neighbor.size,
                        larger / smaller
                    );
                }
            }
        }

        // Should have vertical links (compaction didn't remove them)
        assert!(
            vertical_link_count > 0,
            "Should have vertical links between layers"
        );
    }

    #[test]
    fn test_ground_layer_added_when_top_has_walkable() {
        // Create a 3x3x1 mesh where layer 0 has walkable cells
        // Ceiling layer should be automatically added
        let mesh = QuadMesh::new(3, 3, 1, |_, _, _| true).unwrap();

        // Should have depth 2 (original + ground)
        assert_eq!(mesh.depth, 2, "Should add ground layer when top has walkable cells");

        // Top layer (z=1) should have no cells (all walls)
        for y in 0..3 {
            for x in 0..3 {
                assert!(mesh.cell_at(x, y, 1).is_none(), "Ceiling should be all walls");
            }
        }

        // Original layer should still work
        assert!(mesh.cell_at(0, 0, 0).is_some(), "Original layer should have cells");
    }

    #[test]
    fn test_ground_layer_not_added_when_top_is_walls() {
        // Create a 3x3x2 mesh where layer 1 is all walls
        let mesh = QuadMesh::new(3, 3, 2, |_, _, z| z == 0).unwrap();

        // Should stay at depth 2 (no extra layer needed)
        assert_eq!(mesh.depth, 2, "Should not add ground when top is already walls");
    }

    #[test]
    fn test_ground_layer_idempotent() {
        // Create mesh with walkable top - ground added (depth 1 -> 2)
        let mesh1 = QuadMesh::new(3, 3, 1, |_, _, _| true).unwrap();
        assert_eq!(mesh1.depth, 2);

        // If we were to "re-process" with the same logic, using depth=2
        // and a closure that returns false for z=1, no extra layer should be added
        let mesh2 = QuadMesh::new(3, 3, 2, |_, _, z| z == 0).unwrap();
        assert_eq!(mesh2.depth, 2, "Ceiling layer addition should be idempotent");

        // Both meshes should have same effective structure
        assert_eq!(mesh1.depth, mesh2.depth);
        assert_eq!(mesh1.cell_count(), mesh2.cell_count());
    }

    #[test]
    fn test_volume_limit_checked_before_ground_layer() {
        // 512*512*1 = 262144 which equals LEVEL_MAX_VOLUME
        // This should pass, even though ground layer makes it 512*512*2
        let result = QuadMesh::new(512, 512, 1, |_, _, _| true);
        assert!(result.is_ok(), "512x512x1 should be valid (volume check before ground)");

        let mesh = result.unwrap();
        // Final depth should be 2 (1 + ground layer)
        assert_eq!(mesh.depth, 2, "Should add ground layer");
        assert_eq!(mesh.dimensions(), (512, 512, 2));
    }

    #[test]
    fn test_volume_limit_exceeded() {
        // 512*512*2 = 524288 which exceeds LEVEL_MAX_VOLUME
        let result = QuadMesh::new(512, 512, 2, |_, _, _| true);
        assert!(result.is_err(), "512x512x2 should exceed volume limit");

        match result {
            Err(QuadMeshError::VolumeExceeded { volume, max }) => {
                assert_eq!(volume, 512 * 512 * 2);
                assert_eq!(max, LEVEL_MAX_VOLUME);
            }
            _ => panic!("Expected VolumeExceeded error"),
        }
    }

    #[test]
    fn test_max_dimensions_512x512() {
        // Test that 512x512 is allowed for both width and height
        let result = QuadMesh::new(512, 512, 1, |_, _, _| true);
        assert!(result.is_ok(), "512x512x1 should be valid");

        // Test width > 512 fails
        let result = QuadMesh::new(513, 1, 1, |_, _, _| true);
        assert!(matches!(result, Err(QuadMeshError::WidthExceeded { .. })));

        // Test height > 512 fails
        let result = QuadMesh::new(1, 513, 1, |_, _, _| true);
        assert!(matches!(result, Err(QuadMeshError::HeightExceeded { .. })));
    }

    #[test]
    fn test_volume_128x256x8() {
        // 128 * 256 * 8 = 262144 which equals LEVEL_MAX_VOLUME exactly
        // This should pass - it's a common 3D map configuration
        let result = QuadMesh::new(128, 256, 8, |_, _, z| z < 7);
        assert!(result.is_ok(), "128x256x8 should be valid (volume = 262144)");

        let mesh = result.unwrap();
        // Top layer (z=7) has no walkable cells, so no ground layer added
        assert_eq!(mesh.dimensions(), (128, 256, 8));
    }

    #[test]
    fn test_volume_220x220x6_exceeds() {
        // 220 * 220 * 6 = 290400 which exceeds LEVEL_MAX_VOLUME (262144)
        let result = QuadMesh::new(220, 220, 6, |_, _, _| true);
        assert!(result.is_err(), "220x220x6 should exceed volume limit");

        match result {
            Err(QuadMeshError::VolumeExceeded { volume, max }) => {
                assert_eq!(volume, 220 * 220 * 6);
                assert_eq!(max, LEVEL_MAX_VOLUME);
            }
            _ => panic!("Expected VolumeExceeded error"),
        }
    }

    #[test]
    fn test_width_600x200x1_exceeds() {
        // 600 * 200 * 1 = 120000 (volume OK), but 600 > 512 (width limit)
        let result = QuadMesh::new(600, 200, 1, |_, _, _| true);
        assert!(result.is_err(), "600x200x1 should exceed width limit");

        match result {
            Err(QuadMeshError::WidthExceeded { width, max }) => {
                assert_eq!(width, 600);
                assert_eq!(max, LEVEL_MAX_W);
            }
            _ => panic!("Expected WidthExceeded error"),
        }
    }

    #[test]
    fn test_height_200x600x1_exceeds() {
        // 200 * 600 * 1 = 120000 (volume OK), but 600 > 512 (height limit)
        let result = QuadMesh::new(200, 600, 1, |_, _, _| true);
        assert!(result.is_err(), "200x600x1 should exceed height limit");

        match result {
            Err(QuadMeshError::HeightExceeded { height, max }) => {
                assert_eq!(height, 600);
                assert_eq!(max, LEVEL_MAX_H);
            }
            _ => panic!("Expected HeightExceeded error"),
        }
    }

    #[test]
    fn test_depth_100x100x9_exceeds() {
        // 100 * 100 * 9 = 90000 (volume OK), but 9 > 8 (depth limit)
        let result = QuadMesh::new(100, 100, 9, |_, _, _| true);
        assert!(result.is_err(), "100x100x9 should exceed depth limit");

        match result {
            Err(QuadMeshError::DepthExceeded { depth, max }) => {
                assert_eq!(depth, 9);
                assert_eq!(max, LEVEL_MAX_D);
            }
            _ => panic!("Expected DepthExceeded error"),
        }
    }
}