condor-pathfinding-grid 0.4.0

//! Shared 4-way Jump Point Search primitives for online JPS and JPS+.
//!
//! Not a public solver entrypoint. Classifies free cells (corridor / branch / elbow /
//! dead-end), steps along cardinal rays, and materializes jump edges for
//! [`super::jump_point_search`] and [`super::jps_plus`].
//!
//! Cost model helpers sum per-cell `traversal_cost` along scanned segments; point-kind
//! classification is geometry-only (Manhattan / neighbor mask).

use crate::{Grid, Path, Point};

/// Cardinal scan axis for 4-connected jump rays.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Direction {
    Left,
    Right,
    Up,
    Down,
}

impl Direction {
    /// All four scan axes in fixed Left/Right/Up/Down order.
    pub(crate) const ALL: [Self; 4] = [Self::Left, Self::Right, Self::Up, Self::Down];
}

/// Free-space role of a walkable cell from its 4-connected neighbor mask.
///
/// Used to decide whether a ray must stop (branch / elbow / dead-end / goal) versus
/// continue through a straight corridor. Geometry-only: ignores `traversal_cost`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum PointKind {
    /// Exactly two opposite open neighbors (horizontal or vertical corridor).
    StraightCorridor,
    /// Three or four open neighbors (true branching junction).
    Branch,
    /// Exactly two adjacent open neighbors (forced turn).
    ElbowTurn,
    /// Zero or one open neighbor (cul-de-sac or isolated cell).
    DeadEnd,
}

/// One walkable cardinal step from `point`/`index`, or `None` at a wall/boundary.
pub(crate) fn step(
    grid: &Grid,
    point: Point,
    index: usize,
    direction: Direction,
) -> Option<(Point, usize)> {
    match direction {
        Direction::Left if point.x > 0 => {
            let next = Point::new(point.x - 1, point.y);
            grid.is_walkable(next).then_some((next, index - 1))
        }
        Direction::Right if point.x + 1 < grid.width() => {
            let next = Point::new(point.x + 1, point.y);
            grid.is_walkable(next).then_some((next, index + 1))
        }
        Direction::Up if point.y > 0 => {
            let next = Point::new(point.x, point.y - 1);
            grid.is_walkable(next)
                .then_some((next, index - grid.width()))
        }
        Direction::Down if point.y + 1 < grid.height() => {
            let next = Point::new(point.x, point.y + 1);
            grid.is_walkable(next)
                .then_some((next, index + grid.width()))
        }
        _ => None,
    }
}

/// Classifies a free cell as corridor, branch, elbow, or dead-end from its neighbor mask.
pub(crate) fn classify_point_kind(grid: &Grid, point: Point) -> PointKind {
    let neighbors = walkable_neighbor_mask(grid, point);
    let degree = neighbors.iter().filter(|walkable| **walkable).count();

    if degree != 2 {
        return if degree <= 1 {
            PointKind::DeadEnd
        } else {
            PointKind::Branch
        };
    }

    if neighbors[0] && neighbors[1] || neighbors[2] && neighbors[3] {
        PointKind::StraightCorridor
    } else {
        PointKind::ElbowTurn
    }
}

/// Walkability of the four cardinal neighbors as `[Left, Right, Up, Down]`.
pub(crate) fn walkable_neighbor_mask(grid: &Grid, point: Point) -> [bool; 4] {
    [
        point.x > 0 && grid.is_walkable(Point::new(point.x - 1, point.y)),
        point.x + 1 < grid.width() && grid.is_walkable(Point::new(point.x + 1, point.y)),
        point.y > 0 && grid.is_walkable(Point::new(point.x, point.y - 1)),
        point.y + 1 < grid.height() && grid.is_walkable(Point::new(point.x, point.y + 1)),
    ]
}

/// Manhattan hop distance on the integer cell lattice (heuristic / segment length).
pub(crate) fn manhattan_distance(from: Point, to: Point) -> usize {
    from.x.abs_diff(to.x) + from.y.abs_diff(to.y)
}

/// Intermediate cells of an axis-aligned jump from `from` exclusive through `to` inclusive.
///
/// Assumes a cardinal (no diagonal) jump already validated by the caller.
pub(crate) fn straight_segment(from: Point, to: Point) -> Vec<Point> {
    let mut points = Vec::with_capacity(manhattan_distance(from, to));
    let mut current = from;

    while current.x != to.x {
        current = if current.x < to.x {
            Point::new(current.x + 1, current.y)
        } else {
            Point::new(current.x - 1, current.y)
        };
        points.push(current);
    }

    while current.y != to.y {
        current = if current.y < to.y {
            Point::new(current.x, current.y + 1)
        } else {
            Point::new(current.x, current.y - 1)
        };
        points.push(current);
    }

    points
}

/// Expands jump-parent indices into a dense cell path with the settled `goal_cost`.
///
/// Each parent edge is an axis-aligned jump; intermediate corridor cells are filled via
/// [`straight_segment`] so the returned [`Path`] is a contiguous 4-connected walk.
pub(crate) fn reconstruct_jump_path(
    grid: &Grid,
    parents: &[Option<usize>],
    start_index: usize,
    goal_index: usize,
    goal_cost: usize,
) -> Path {
    let mut segments = Vec::new();
    let mut current_index = goal_index;

    while let Some(parent_index) = parents[current_index] {
        let parent = grid.point_from_index(parent_index);
        let current = grid.point_from_index(current_index);
        segments.push(straight_segment(parent, current));
        current_index = parent_index;
    }

    let mut steps = vec![grid.point_from_index(start_index)];
    for segment in segments.iter().rev() {
        steps.extend(segment.iter().copied());
    }

    Path::from_steps_with_cost(steps, goal_cost).expect("path contains at least one point")
}