path_finding/search/
probing.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2
3use crate::graph::{Edge, Graph};
4use crate::grid::{Direction, Grid};
5use crate::path;
6use crate::path::Waypoint;
7use crate::search::cost;
8
9pub(crate) type Callback = fn(list: &mut VecDeque<Waypoint>) -> Option<Waypoint>;
10
11pub(crate) fn pop(stack: &mut VecDeque<Waypoint>) -> Option<Waypoint> {
12    return stack.pop_back();
13}
14
15pub(crate) fn dequeue(queue: &mut VecDeque<Waypoint>) -> Option<Waypoint> {
16    return queue.pop_front();
17}
18
19pub(crate) fn probe_graph(start: usize, target: usize, graph: &Graph, control_flow: Callback) -> Graph {
20    let mut deque = VecDeque::from([Waypoint::from(None, start, None)]);
21    let mut visited: HashSet<usize> = HashSet::new();
22
23    while let Some(current) = control_flow(&mut deque) {
24        if let Some(node) = graph.nodes_lookup.get(&current.node_id) {
25            let edges = node.edges.clone();
26            visited.insert(current.node_id);
27
28            for edge in edges {
29                let destination = edge.destination;
30
31                if !visited.contains(&destination) {
32                    deque.push_back(Waypoint::from(
33                        Some(edge.clone()),
34                        destination,
35                        Some(Box::new(current.clone())),
36                    ));
37                }
38
39                if destination == target {
40                    let edges = deque.pop_back()
41                        .map_or_else(|| Vec::new(), |w| path::walk_back(w));
42                    return Graph::from(edges);
43                }
44            }
45        }
46    }
47
48    Graph::from(Vec::new())
49}
50
51pub(crate) fn probe_grid(start_coord: (usize, usize), target_coord: (usize, usize),
52                         grid: &Grid, directions: &[Direction], control_flow: Callback) -> Graph {
53    let start = grid.node_id(start_coord);
54    let target = grid.node_id(target_coord);
55
56    let mut deque = VecDeque::from([Waypoint::from(None, start, None)]);
57    let mut visited: HashMap<usize, Waypoint> = HashMap::new();
58
59    while let Some(current) = control_flow(&mut deque) {
60        visited.insert(current.node_id, current.clone());
61
62        if let Some(result) = go_directions(&mut deque, current, grid, directions, &visited, target) {
63            return result;
64        }
65    }
66
67    Graph::from(Vec::new())
68}
69
70pub(crate) fn go_directions(
71    deque: &mut VecDeque<Waypoint>,
72    current: Waypoint,
73    grid: &Grid,
74    directions: &[Direction],
75    visited: &HashMap<usize, Waypoint>,
76    target: usize,
77) -> Option<Graph> {
78    for direction in directions {
79        let dest_coord = direction.attempt_move(grid.coords(current.node_id));
80
81        if grid.outside(dest_coord) {
82            continue;
83        }
84
85        let dest_id = grid.node_id(dest_coord);
86        let cost = grid.cost(dest_id);
87
88        if !visited.contains_key(&dest_id) && cost < cost::INFINITY {
89            let edge = Edge::from(dest_id, current.node_id, dest_id, cost);
90            deque.push_back(Waypoint::from(Some(edge), dest_id, Some(Box::new(current.clone()))));
91        }
92
93        if dest_id == target {
94            return deque.pop_back()
95                .map(path::walk_back)
96                .map(Graph::from);
97        }
98    }
99
100    None
101}
path_finding/search/probing.rs

path_finding/search/
probing.rs
