condor_grid/algorithms/

bfs.rs

//! Static-grid [`Pathfinder`]: unweighted 4-connected BFS.
//!
//! Each search is independent and returns the standard invalid/found/no-path outcome.
//! Cost is one hop per cardinal edge; [`Grid::traversal_cost`](crate::Grid::traversal_cost)
//! is ignored, so BFS is optimal only when hop count is the intended metric. Prefer
//! [`super::astar::AStar`] or [`super::dijkstra::Dijkstra`] when cell costs vary.

use std::collections::VecDeque;

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

/// Online [`Pathfinder`]: unweighted 4-connected BFS.
///
/// Cost model: unit hop count; ignores `traversal_cost`. Optimal when hop cost is the
/// metric. Prefer for unweighted connectivity; use A*/Dijkstra when cell costs vary.
#[derive(Debug, Default, Clone, Copy)]
pub struct Bfs;

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

    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_walkable(request.start) || !grid.is_walkable(request.goal) {
            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 frontier = VecDeque::from([start_index]);
        let mut discovered = vec![false; grid.cell_count()];
        let mut parents = vec![None; grid.cell_count()];
        let mut visited_nodes = 0;
        let watch = BudgetWatch::start(request.budget);

        discovered[start_index] = true;

        while let Some(current_index) = frontier.pop_front() {
            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);
                frontier.push_back(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::bfs::Bfs,
        grid::{Cell, Grid},
        point::Point,
        search::{BudgetExhausted, GridSearchError, Pathfinder, SearchBudget, SearchRequest},
    };

    #[test]
    fn expansion_budget_stops_before_goal() {
        let grid = Grid::new(5, 1).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(0, 0), Point::new(4, 0))
            .with_budget(SearchBudget::max_expansions(2));
        let error = Bfs
            .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 unlimited_budget_finds_path() {
        let grid = Grid::new(5, 1).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(0, 0), Point::new(4, 0));
        let result = Bfs.search(&grid, request).expect("request is valid");
        assert!(result.is_found());
    }

    #[test]
    fn finds_a_shortest_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 bfs = Bfs;
        let result = bfs.search(
            &grid,
            SearchRequest::new(Point::new(0, 0), Point::new(4, 4)),
        );

        assert!(result.as_ref().expect("valid search request").is_found());
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            Some(8)
        );

        let path = result
            .as_ref()
            .expect("valid search request")
            .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)));
    }

    #[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 bfs = Bfs;
        let result = bfs.search(
            &grid,
            SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
        );

        assert!(!result.as_ref().expect("valid search request").is_found());
        assert_eq!(result.as_ref().expect("valid search request").cost(), None);
        assert!(
            result
                .as_ref()
                .expect("valid search request")
                .stats()
                .visited_nodes
                > 0
        );
    }
}