basic_pathfinding/
search.rs

1use std::collections::BinaryHeap;
2use std::collections::HashMap;
3
4use crate::coord::Coord;
5use crate::grid::Grid;
6use crate::node::Node;
7
8#[derive(Default, Deserialize)]
9#[serde(rename_all = "camelCase")]
10pub struct SearchOpts {
11  pub cost_threshold: Option<i32>,
12  pub end_on_unstoppable: bool,
13  pub path_to_threshold: bool,
14  pub path_adjacent: bool,
15}
16
17pub struct Search {
18  pub start: Coord,
19  pub end: Vec<Coord>,
20  pub dest: Option<Coord>,
21  pub heap: BinaryHeap<Node>,
22  pub cache: HashMap<i32, HashMap<i32, Node>>,
23  pub opts: SearchOpts,
24}
25
26impl Search {
27  pub fn new(start: Coord, end: Vec<Coord>, dest: Option<Coord>, opts: SearchOpts) -> Search {
28    Search {
29      start: start,
30      dest: dest,
31      end: end,
32      heap: BinaryHeap::new(),
33      cache: HashMap::new(),
34      opts: opts,
35    }
36  }
37
38  pub fn reached_destination(&self) -> bool {
39    match self.peek() {
40      Some(curr) => self
41        .end
42        .iter()
43        .find(|c| c.matches(curr.x, curr.y))
44        .is_some(),
45      _ => false,
46    }
47  }
48
49  pub fn push(&mut self, node: Node) {
50    self.heap.push(node.clone());
51    self.cache(node);
52  }
53
54  pub fn cache(&mut self, node: Node) {
55    match self.cache.remove(&node.y) {
56      None => {
57        let mut inner_hash = HashMap::new();
58        inner_hash.insert(node.x, node);
59        self.cache.insert(node.y, inner_hash);
60      }
61      Some(mut inner_hash) => {
62        inner_hash.insert(node.x, node);
63        self.cache.insert(node.y, inner_hash);
64      }
65    }
66  }
67
68  pub fn peek(&self) -> Option<&Node> {
69    match self.heap.peek() {
70      None => None,
71      Some(node) => self.get_node(node.x, node.y),
72    }
73  }
74
75  pub fn pop(&mut self) -> Option<Node> {
76    self.heap.pop()
77  }
78
79  pub fn size(&self) -> usize {
80    self.heap.len()
81  }
82
83  pub fn update(&mut self, node: Node) {
84    self.cache(node);
85  }
86
87  pub fn get_node(&self, x: i32, y: i32) -> Option<&Node> {
88    match self.cache.get(&y) {
89      None => None,
90      Some(inner_hash) => inner_hash.get(&x),
91    }
92  }
93
94  pub fn is_pathing(&self) -> bool {
95    self.dest.is_some()
96  }
97
98  pub fn coordinate_to_node(&self, parent: Option<&Node>, x: i32, y: i32, cost: i32) -> Node {
99    match self.get_node(x, y) {
100      Some(&node) => node,
101      None => {
102        let distance = match !self.is_pathing() {
103          true => 1,
104          false => {
105            let dest = self.dest.unwrap();
106            get_distance(x, y, dest.x, dest.y)
107          }
108        };
109
110        Node::new(
111          parent,
112          x,
113          y,
114          match parent {
115            None => cost,
116            Some(parent) => parent.cost + cost,
117          },
118          distance,
119        )
120      }
121    }
122  }
123
124  pub fn check_adjacent_node(&mut self, grid: &Grid, source_node: &Node, x: i32, y: i32) {
125    let adjacent_x = source_node.x + x;
126    let adjacent_y = source_node.y + y;
127    let adjacent_cost = grid.get_coord_cost(adjacent_x, adjacent_y);
128
129    if grid.is_coord_walkable(adjacent_x, adjacent_y)
130      & can_afford(
131        source_node,
132        adjacent_cost,
133        match self.opts.path_to_threshold {
134          true => None,
135          _ => self.opts.cost_threshold,
136        },
137      )
138    {
139      let mut adjacent_node =
140        self.coordinate_to_node(Some(source_node), adjacent_x, adjacent_y, adjacent_cost);
141
142      if !adjacent_node.visited {
143        self.push(adjacent_node);
144      } else if (source_node.cost + adjacent_cost) < adjacent_node.cost {
145        adjacent_node.cost = source_node.cost + adjacent_cost;
146        adjacent_node.parent = Some(Coord::new(source_node.x, source_node.y));
147        self.update(adjacent_node);
148      }
149    }
150  }
151
152  pub fn traversed_nodes(&self) -> Vec<&Node> {
153    let nodes = &mut vec![];
154    for list in self.cache.values() {
155      nodes.extend(list.values());
156    }
157    nodes.to_vec()
158  }
159}
160
161fn can_afford(node: &Node, cost: i32, cost_threshold: Option<i32>) -> bool {
162  match cost_threshold {
163    None => true,
164    Some(cost_threshold) => node.cost + cost <= cost_threshold,
165  }
166}
167
168fn get_distance(x1: i32, y1: i32, x2: i32, y2: i32) -> i32 {
169  let dx = (x1 - x2).abs();
170  let dy = (y1 - y2).abs();
171  dx + dy
172}
basic_pathfinding/search.rs

basic_pathfinding/
search.rs
