condor-pathfinding-grid 0.4.0

//! Private candidate contract: depth-first search for static 4-connected grids.
//!
//! **Hypothesis:** a plain iterative DFS gives the cheapest possible "any path"
//! answer on open maps where path quality does not matter (existence probes,
//! maze-like corridors), undercutting BFS frontier memory.
//!
//! **Non-negotiable behavior:** standard invalid/found/no-path outcome, budget
//! enforcement through [`BudgetWatch`], and no optimality claim: the returned
//! path is *a* path, not a shortest one. Prefer [`super::bfs::Bfs`] whenever hop
//! optimality matters.
//!
//! **Evidence and promotion:** ordinary `grid_core` route
//! (`just test-fast grid_core`, `just clippy-target grid_core`); promotion
//! requires end-to-end evidence that the non-optimal answer has a real consumer.
//! This remains private: no feature, fixture, target, or separate harness route.

use crate::{
    grid::Grid,
    path::Path,
    search::{BudgetWatch, Pathfinder, SearchRequest, SearchResult},
};

/// Online [`Pathfinder`] candidate: unweighted 4-connected depth-first search.
///
/// Cost model: unit hop count; ignores `traversal_cost`. **Not optimal** — it
/// returns the first path discovered in fixed axis order.
#[derive(Debug, Default, Clone, Copy)]
pub struct Dfs;

impl Pathfinder for Dfs {
    fn name(&self) -> &'static str {
        "dfs"
    }

    fn search(&self, grid: &Grid, request: SearchRequest) -> SearchResult {
        crate::search::validate_request(grid, request)?;
        let Some(start_index) = grid.index_of(request.start) else {
            return crate::search::not_found(0);
        };
        let Some(goal_index) = grid.index_of(request.goal) else {
            return crate::search::not_found(0);
        };

        if !grid.is_reachable(request.start, request.goal) {
            return crate::search::not_found(0);
        }

        if request.start == request.goal {
            return crate::search::found(
                Path::from_steps(vec![request.start]).expect("path contains at least one point"),
                1,
            );
        }

        let mut stack = vec![start_index];
        let mut discovered = vec![false; grid.cell_count()];
        let mut parents = vec![None; grid.cell_count()];
        let mut visited_nodes = 0usize;
        let watch = BudgetWatch::start(request.budget);

        discovered[start_index] = true;

        while let Some(current_index) = stack.pop() {
            visited_nodes += 1;

            if current_index == goal_index {
                break;
            }

            if let Err(reason) = watch.check(visited_nodes) {
                return Err(crate::search::budget_error(reason));
            }

            let current = grid.point_from_index(current_index);
            for neighbor in grid.neighbors4(current) {
                let neighbor_index = grid
                    .index_of(neighbor)
                    .expect("walkable neighbors must exist inside the grid");

                if discovered[neighbor_index] {
                    continue;
                }

                discovered[neighbor_index] = true;
                parents[neighbor_index] = Some(current_index);
                stack.push(neighbor_index);
            }
        }

        if !discovered[goal_index] {
            return crate::search::not_found(visited_nodes);
        }

        crate::search::found(
            reconstruct_path(grid, &parents, start_index, goal_index),
            visited_nodes,
        )
    }
}

fn reconstruct_path(
    grid: &Grid,
    parents: &[Option<usize>],
    start_index: usize,
    goal_index: usize,
) -> Path {
    let mut current_index = goal_index;
    let mut steps = vec![grid.point_from_index(goal_index)];

    while current_index != start_index {
        current_index =
            parents[current_index].expect("a discovered goal must have a complete parent chain");
        steps.push(grid.point_from_index(current_index));
    }

    steps.reverse();
    Path::from_steps(steps).expect("path contains at least one point")
}

#[cfg(test)]
mod tests {
    use crate::{
        algorithms::dfs::Dfs,
        grid::{Cell, Grid},
        point::Point,
        search::{BudgetExhausted, GridSearchError, Pathfinder, SearchBudget, SearchRequest},
    };

    #[test]
    fn finds_some_path_through_the_only_gap() {
        let mut grid = Grid::new(5, 5).expect("grid dimensions are valid");
        for y in 0..5 {
            if y != 2 {
                grid.set_cell(Point::new(2, y), Cell::Blocked)
                    .expect("valid grid edit");
            }
        }

        let result = Dfs
            .search(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(4, 4)),
            )
            .expect("endpoints are walkable");

        assert!(result.is_found());
        let path = result.path().expect("path should exist");
        assert_eq!(path.start(), Point::new(0, 0));
        assert_eq!(path.goal(), Point::new(4, 4));
        assert!(path.steps().contains(&Point::new(2, 2)));
        for window in path.steps().windows(2) {
            let dx = window[0].x.abs_diff(window[1].x);
            let dy = window[0].y.abs_diff(window[1].y);
            assert_eq!(dx + dy, 1, "steps must be 4-connected");
        }
    }

    #[test]
    fn reports_when_no_path_exists() {
        let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
        for x in 0..3 {
            grid.set_cell(Point::new(x, 1), Cell::Blocked)
                .expect("valid grid edit");
        }

        let result = Dfs
            .search(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
            )
            .expect("endpoints are walkable");
        assert!(!result.is_found());
    }

    #[test]
    fn expansion_budget_stops_before_goal() {
        let grid = Grid::new(6, 1).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(0, 0), Point::new(5, 0))
            .with_budget(SearchBudget::max_expansions(2));
        let error = Dfs
            .search(&grid, request)
            .expect_err("budget should exhaust on a long corridor");
        assert_eq!(
            error,
            GridSearchError::BudgetExhausted(BudgetExhausted::Expansions {
                limit: 2,
                expansions: 2
            })
        );
    }

    #[test]
    fn trivial_start_equals_goal() {
        let grid = Grid::new(2, 2).expect("grid dimensions are valid");
        let result = Dfs
            .search(
                &grid,
                SearchRequest::new(Point::new(1, 1), Point::new(1, 1)),
            )
            .expect("endpoints are walkable");
        assert_eq!(result.path().map(super::Path::len), Some(1));
    }
}