path_finding/search/
a_star.rs

1#[cfg(test)]
2use std::collections::HashMap;
3
4use crate::{graph::Graph, path::PathFinding};
5#[cfg(test)]
6use crate::graph::Edge;
7use crate::grid::{Direction, Grid};
8use crate::node::{Node, Vec3};
9use crate::search::{dijkstra, dijkstra_grid};
10
11pub fn euclidean_distance(src: &Vec3, dest: &Vec3) -> f32 {
12    return src.euclidean_dist(dest);
13}
14
15pub fn manhattan_distance(src: &Vec3, dest: &Vec3) -> f32 {
16    return src.manhattan_dist(dest);
17}
18
19pub struct AStar {
20    pub heuristic: Box<dyn Fn(&Vec3, &Vec3) -> f32>,
21}
22
23impl PathFinding for AStar {
24    fn graph(&self, source: Node, target: Node, graph: &Graph) -> Graph {
25        graph.verify_positions();
26        return dijkstra(source, target, graph, &self.heuristic);
27    }
28
29    fn grid(&self, source: (usize, usize), target: (usize, usize), grid: &Grid, directions: &[Direction]) -> Graph {
30        return dijkstra_grid(source, target, grid, directions, &self.heuristic);
31    }
32}
33
34
35#[test]
36#[should_panic(expected = "You must offer node positions to the graph before using this heuristic.")]
37fn missing_node_positions_should_cause_panic() {
38    Graph::from(Vec::from([
39        Edge::from(0, 0, 1, 4.0)
40    ])).get_position(&1);
41}
42
43#[test]
44#[should_panic(expected = "Node position missing for given node id: 1")]
45fn missing_node_position_should_cause_panic() {
46    let mut graph = Graph::from(Vec::from([
47        Edge::from(0, 0, 1, 4.0)
48    ]));
49
50    graph.offer_positions(HashMap::from([(0, Vec3::from(0.0, 0.0, 0.0))]));
51
52    graph.get_position(&1);
53}
54
55#[test]
56fn node_position_should_be_returned() {
57    let mut graph = Graph::from(Vec::from([
58        Edge::from(0, 0, 1, 4.0)
59    ]));
60
61    graph.offer_positions(HashMap::from([(1, Vec3::from(0.1, 0.2, 0.3))]));
62    let pos = graph.get_position(&1);
63
64    assert_eq!(0.1, pos.x);
65    assert_eq!(0.2, pos.y);
66    assert_eq!(0.3, pos.z);
67}
68
69#[test]
70fn euclidean_heuristic_should_return_dist() {
71    let mut graph = Graph::from(Vec::from([
72        Edge::from(0, 0, 1, 4.0)
73    ]));
74
75    graph.offer_positions(HashMap::from([
76        (0, Vec3::from(20.0, 30.0, 90.0)),
77        (1, Vec3::from(80.0, 44.0, 40.0))
78    ]));
79
80    assert_eq!(79.347336, euclidean_distance(graph.get_position(&0), graph.get_position(&1)));
81}
82
83#[test]
84fn manhattan_heuristic_should_return_dist() {
85    let mut graph = Graph::from(Vec::from([
86        Edge::from(0, 0, 1, 4.0)
87    ]));
88
89    graph.offer_positions(HashMap::from([
90        (0, Vec3::from(2.0, 9.0, 0.0)),
91        (1, Vec3::from(3.0, 5.0, 0.0))
92    ]));
93
94    assert_eq!(5.0, manhattan_distance(graph.get_position(&0), graph.get_position(&1)));
95}
path_finding/search/a_star.rs

path_finding/search/
a_star.rs
