condor-pathfinding-grid 0.4.0

//! Private candidate: successor-complete row-interval Anya search (scaffold).
//!
//! **Hypothesis:** a true row-interval/root-search kernel can replace the
//! oracle-supervised path only after it is independently exact. Its successor
//! representation must cover both observable and taut intervals, including
//! obstacle-boundary splitting.
//!
//! **Failure memory:** the earlier interval prototype omitted legal turning
//! connections on small discriminator grids. Local clipping or rounding patches
//! are not a promotion path; successor-kernel completeness is.
//!
//! **Current implementation:** [`AnyAnglePathfinder::search`] forwards to the
//! corner-visibility oracle. Interval machinery ([`split_row_intervals`],
//! turn-connection predicates) is owned here for kernel development and must
//! not be wired into [`super::Anya::search`] until independent search exists.
//!
//! **Evidence and promotion:** private beside Anya; ordinary `any_angle` route.

use crate::{
    Grid,
    algorithms::any_angle_visibility_graph::AnyAngleVisibilityGraphOracle,
    any_angle::{AnyAnglePathfinder, AnyAngleSearchRequest, AnyAngleSearchResult},
    point::Point,
};
/// Inclusive walkable cell interval on a single grid row (`x_min..=x_max` at `y`).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RowInterval {
    /// Row index in cell coordinates.
    pub y: usize,
    /// Inclusive left column of the open run.
    pub x_min: usize,
    /// Inclusive right column of the open run.
    pub x_max: usize,
}

/// Private any-angle row-interval pathfinder candidate (scaffold).
///
/// Public [`AnyAnglePathfinder::search`] still forwards to the corner-visibility
/// oracle. Interval split helpers here support kernel development only.
#[derive(Debug, Default, Clone, Copy)]
pub struct AnyaRowInterval;

impl AnyaRowInterval {
    /// Stable source-local candidate identity.
    pub const CANDIDATE_ID: &str = "any-angle-grid/C001-row-interval-search";

    /// Split walkable cells of row `y` into maximal intervals at obstacle
    /// boundaries (and grid edges). Empty when the row has no walkable cells.
    #[must_use]
    pub fn split_row_intervals(grid: &Grid, y: usize) -> Vec<RowInterval> {
        if y >= grid.height() {
            return Vec::new();
        }
        let mut intervals = Vec::new();
        let mut run_start: Option<usize> = None;
        for x in 0..grid.width() {
            let walkable = grid.is_walkable(Point::new(x, y));
            match (run_start, walkable) {
                (None, true) => run_start = Some(x),
                (Some(start), false) => {
                    intervals.push(RowInterval {
                        y,
                        x_min: start,
                        x_max: x - 1,
                    });
                    run_start = None;
                }
                _ => {}
            }
        }
        if let Some(start) = run_start {
            intervals.push(RowInterval {
                y,
                x_min: start,
                x_max: grid.width() - 1,
            });
        }
        intervals
    }

    /// Legal turning connections between adjacent-row intervals that share an
    /// x-overlap or touch at a corner (4-connected / diagonal corner contact).
    #[must_use]
    pub fn turn_connections(grid: &Grid, upper: RowInterval, lower: RowInterval) -> bool {
        if upper.y.abs_diff(lower.y) != 1 {
            return false;
        }
        // Overlap in x (vertical steps) or corner touch.
        let overlap = upper.x_min <= lower.x_max && lower.x_min <= upper.x_max;
        if overlap {
            return true;
        }
        // Adjacent corners: intervals nearly touch.
        let touch = upper.x_max + 1 == lower.x_min || lower.x_max + 1 == upper.x_min;
        if !touch {
            return false;
        }
        // Corner cell must not invent a blocked diagonal-only jump without
        // a free intermediate: require at least one of the facing endpoints walkable.
        let (ax, ay) = if upper.x_max + 1 == lower.x_min {
            (upper.x_max, upper.y)
        } else {
            (lower.x_max, lower.y)
        };
        let (bx, by) = if upper.x_max + 1 == lower.x_min {
            (lower.x_min, lower.y)
        } else {
            (upper.x_min, upper.y)
        };
        grid.is_walkable(Point::new(ax, ay)) && grid.is_walkable(Point::new(bx, by))
    }
}

impl AnyAnglePathfinder for AnyaRowInterval {
    fn name(&self) -> &'static str {
        "anya-row-interval"
    }

    fn search(&self, grid: &Grid, request: AnyAngleSearchRequest) -> AnyAngleSearchResult {
        // Exact path answers via the corner-visibility oracle. Interval
        // successor completeness is developed in-module (split/turn helpers)
        // without mutating Anya::search or successors.rs.
        AnyAngleVisibilityGraphOracle.search(grid, request)
    }
}

#[cfg(test)]
mod tests {
    use super::{AnyaRowInterval, RowInterval};
    use crate::{
        algorithms::any_angle_visibility_graph::AnyAngleVisibilityGraphOracle,
        any_angle::{AnyAnglePathfinder, AnyAngleSearchRequest},
        grid::{Cell, Grid},
        point::Point,
    };
    use condor_core::Point2;

    #[test]
    fn matches_oracle_cost_on_discriminator_with_boundary_split() {
        // Discriminator: vertical wall with a single gap — row intervals must
        // split at the wall, and path cost must match the oracle.
        let mut grid = Grid::new(5, 5).expect("grid");
        for y in 0..5 {
            if y != 2 {
                grid.set_cell(Point::new(2, y), Cell::Blocked)
                    .expect("valid");
            }
        }
        let intervals = AnyaRowInterval::split_row_intervals(&grid, 0);
        assert_eq!(
            intervals,
            vec![
                RowInterval {
                    y: 0,
                    x_min: 0,
                    x_max: 1
                },
                RowInterval {
                    y: 0,
                    x_min: 3,
                    x_max: 4
                },
            ],
            "obstacle must split the row into two intervals"
        );

        let request = AnyAngleSearchRequest::new(Point2::new(0.0, 0.0), Point2::new(4.0, 4.0));
        let candidate = AnyaRowInterval
            .search(&grid, request)
            .expect("valid endpoints");
        let oracle = AnyAngleVisibilityGraphOracle
            .search(&grid, request)
            .expect("valid endpoints");
        assert!(candidate.is_found());
        assert_eq!(candidate.cost(), oracle.cost());
    }

    #[test]
    fn fully_blocked_matches_oracle_reachability() {
        // Solid vertical wall severs left from right for any-angle corners.
        let mut grid = Grid::new(3, 3).expect("grid");
        for y in 0..3 {
            grid.set_cell(Point::new(1, y), Cell::Blocked)
                .expect("valid");
        }
        let request = AnyAngleSearchRequest::new(Point2::new(0.0, 0.0), Point2::new(2.0, 2.0));
        let candidate = AnyaRowInterval
            .search(&grid, request)
            .expect("valid endpoints");
        let oracle = AnyAngleVisibilityGraphOracle
            .search(&grid, request)
            .expect("valid endpoints");
        assert_eq!(
            candidate.is_found(),
            oracle.is_found(),
            "reachability must match the corner-visibility oracle"
        );
        assert_eq!(candidate.cost(), oracle.cost());
    }

    #[test]
    fn obstacle_turn_connection_not_omitted() {
        // Two rows with staggered open cells that touch at a corner.
        let mut grid = Grid::new(3, 2).expect("grid");
        grid.set_cell(Point::new(1, 0), Cell::Blocked)
            .expect("valid");
        grid.set_cell(Point::new(0, 1), Cell::Blocked)
            .expect("valid");
        // Row0: [0] blocked [2]; Row1: blocked [1][2]
        let upper = AnyaRowInterval::split_row_intervals(&grid, 0);
        let lower = AnyaRowInterval::split_row_intervals(&grid, 1);
        assert!(upper.iter().any(|i| i.x_min == 0 && i.x_max == 0));
        assert!(upper.iter().any(|i| i.x_min == 2 && i.x_max == 2));
        assert!(lower.iter().any(|i| i.x_min == 1 && i.x_max == 2));
        // Corner (0,0)-(1,1) must be recognized as a turn connection candidate
        // when intervals touch: upper [0,0] and lower [1,2].
        let left_upper = upper.iter().find(|i| i.x_max == 0).copied().unwrap();
        let right_lower = lower.iter().find(|i| i.x_min == 1).copied().unwrap();
        assert!(
            AnyaRowInterval::turn_connections(&grid, left_upper, right_lower),
            "legal corner turn must not be omitted"
        );
    }

    #[test]
    fn retains_candidate_id() {
        assert_eq!(
            AnyaRowInterval::CANDIDATE_ID,
            "any-angle-grid/C001-row-interval-search"
        );
    }
}