Add testcases for a_star algorithm to avoid expensive shortcuts
@@ -174,3 +174,88 @@ impl AStar {
result
}
}
+
+#[cfg(test)]
+mod test {
+ use bracket_algorithm_traits::prelude::BaseMap;
+ use smallvec::smallvec;
+
+ use super::a_star_search;
+
+ /// A triangular graph with unidirectional edges.
+ /// 1
+ /// /\
+ /// 1.0 / \ 1.0
+ /// / \
+ /// 0 /______\ 2
+ /// 3.0
+ struct TriangleMap;
+
+ impl BaseMap for TriangleMap {
+ fn get_available_exits(&self, idx: usize) -> smallvec::SmallVec<[(usize, f32); 10]> {
+ match idx {
+ 0 => smallvec![(1, 1.0), (2, 3.0)],
+ 1 => smallvec![(2, 1.0)],
+ _ => smallvec![],
+ }
+ }
+
+ fn get_pathing_distance(&self, idx1: usize, idx2: usize) -> f32 {
+ match (idx1, idx2) {
+ (0, 1) | (1, 2) => 1.0,
+ (0, 2) => 3.0,
+ (2, 2) => 0.0,
+ x => panic!("This distance should never be requested: {:?}", x),
+ }
+ }
+ }
+
+ #[test]
+ fn avoid_expensive_shortcut_on_triangle() {
+ let map = TriangleMap;
+ let path = a_star_search(0, 2, &map);
+ println!("{:?}", path.steps);
+ assert_eq!(path.steps, [0, 1, 2]);
+ }
+
+ /// A simple graph with `len` nodes. Same concept as the `TriangleMap`, but with more nodes in
+ /// the indirect path.
+ /// Each node is connected to it's successor but the first node also connects to the last this
+ /// "shortcut" has slightly higher cost than walking all the other nodes
+ struct ExpensiveShortcutMap {
+ len: usize,
+ }
+
+ impl BaseMap for ExpensiveShortcutMap {
+ fn get_available_exits(&self, idx: usize) -> smallvec::SmallVec<[(usize, f32); 10]> {
+ let mut exits = smallvec::SmallVec::new();
+
+ // shortcut to the end with slightly higher cost
+ if idx == 0 {
+ exits.push((self.len - 1, self.len as f32))
+ }
+ // step to next node
+ if idx <= self.len - 1 {
+ exits.push((idx + 1, 1.0));
+ }
+
+ exits
+ }
+
+ fn get_pathing_distance(&self, idx1: usize, idx2: usize) -> f32 {
+ if idx1 == 0 && idx2 == self.len {
+ return self.len as f32;
+ }
+ (idx1.abs_diff(idx2)) as f32
+ }
+ }
+
+ #[test]
+ fn avoid_expensive_shortcut() {
+ let len = 15;
+ let map = ExpensiveShortcutMap { len };
+ let path = a_star_search(0, len - 1, &map);
+ println!("{:?}", path.steps);
+ assert_eq!(path.steps, (0..len).collect::<Vec<_>>());
+ }
+}
