path_finding/search/
probing_bi.rs

1use std::collections::{HashMap, VecDeque};
2
3use crate::graph::{Edge, Graph};
4use crate::grid::{Direction, Grid};
5use crate::node::Node;
6use crate::path;
7use crate::path::Waypoint;
8use crate::search::probing::go_directions;
9
10pub(crate) fn probe_grid(start_coord: (usize, usize), target_coord: (usize, usize),
11                         grid: &Grid, dirs: &[Direction]) -> Graph {
12    let start = grid.node_id(start_coord);
13    let target = grid.node_id(target_coord);
14
15    let start_queue = &mut VecDeque::from([Waypoint::from(None, start, None)]);
16    let target_queue = &mut VecDeque::from([Waypoint::from(None, target, None)]);
17
18    let mut start_vis: HashMap<usize, Waypoint> = HashMap::new();
19    let mut target_vis: HashMap<usize, Waypoint> = HashMap::new();
20
21    while !start_queue.is_empty() || !target_queue.is_empty() {
22        if let Some(start_result) = process_dequeue(start_queue, grid, dirs, &mut start_vis,
23                                                    &mut target_vis, target) {
24            return start_result;
25        }
26
27        if let Some(end_result) = process_dequeue(target_queue, grid, dirs, &mut target_vis,
28                                                  &mut start_vis, start) {
29            return end_result;
30        }
31    }
32
33    Graph::from(Vec::new())
34}
35
36fn process_dequeue(
37    deque: &mut VecDeque<Waypoint>,
38    grid: &Grid,
39    directions: &[Direction],
40    visited: &mut HashMap<usize, Waypoint>,
41    other_visited: &mut HashMap<usize, Waypoint>,
42    target: usize,
43) -> Option<Graph> {
44    if let Some(current) = deque.pop_front() {
45        let current_id = current.node_id;
46        visited.insert(current_id, current.clone());
47
48        if current_id == target {
49            return Some(Graph::from(path::walk_back(current)));
50        }
51
52        if other_visited.contains_key(&current_id) {
53            let mut from_current = path::walk_back(current);
54            let other_edges = other_visited
55                .get(&current_id)
56                .map_or_else(|| Vec::new(), |w| path::walk_back(w.clone()));
57            from_current.extend(other_edges);
58            return Some(Graph::from(from_current));
59        }
60
61        if let Some(result) = go_directions(deque, current, grid, directions, &visited, target) {
62            return Some(result);
63        }
64    }
65
66    None
67}
68
69pub(crate) fn probe_graph(start: Node, target: Node, graph: &Graph) -> Graph {
70    let start_queue = &mut VecDeque::from([Waypoint::from(None, start.id, None)]);
71    let target_queue = &mut VecDeque::from([Waypoint::from(None, target.id, None)]);
72
73    let mut start_visited: HashMap<usize, Waypoint> = HashMap::new();
74    let mut target_visited: HashMap<usize, Waypoint> = HashMap::new();
75
76    while !start_queue.is_empty() || !target_queue.is_empty() {
77        if let Some(result_start) = process_node(start_queue, &mut start_visited,
78                                                 &mut target_visited, &target, graph) {
79            return Graph::from(result_start);
80        }
81
82        if let Some(result_target) = process_node(target_queue, &mut target_visited,
83                                                  &mut start_visited, &start, graph) {
84            return Graph::from(result_target);
85        }
86    }
87
88    Graph::from(Vec::new())
89}
90
91fn process_node(queue: &mut VecDeque<Waypoint>, visited: &mut HashMap<usize, Waypoint>,
92                end_visited: &mut HashMap<usize, Waypoint>,
93                end: &Node, graph: &Graph, ) -> Option<Vec<Edge>> {
94    if let Some(current) = queue.pop_front() {
95        let result = process_edges(queue, &current, end.id, graph, &visited, &end_visited);
96        visited.insert(current.node_id, current);
97        result
98    } else {
99        None
100    }
101}
102
103fn process_edges(
104    queue: &mut VecDeque<Waypoint>,
105    current: &Waypoint,
106    target: usize,
107    graph: &Graph,
108    visited: &HashMap<usize, Waypoint>,
109    other_visited: &HashMap<usize, Waypoint>) -> Option<Vec<Edge>>
110{
111    let edges = graph.nodes_lookup.get(&current.node_id).unwrap().edges.clone();
112
113    for edge in edges {
114        let destination = edge.destination;
115
116        let waypoint = Waypoint::from(Some(edge), destination,
117                                      Some(Box::new(current.clone())));
118
119        if destination == target {
120            return Some(path::walk_back(waypoint));
121        }
122
123        if !visited.contains_key(&destination) {
124            queue.push_back(waypoint)
125        }
126
127        if other_visited.contains_key(&destination) {
128            let mut from_current = queue.pop_back().map_or_else(|| Vec::new(), |w| path::walk_back(w));
129            let other_edges = other_visited.get(&destination)
130                .map_or_else(|| Vec::new(), |w| path::walk_back(w.clone()));
131            from_current.extend(other_edges);
132            return Some(from_current);
133        }
134    }
135
136    None
137}
path_finding/search/probing_bi.rs

path_finding/search/
probing_bi.rs
