reddb_server/storage/engine/pathfinding/
astar_impl.rs

1use super::*;
2
3impl AStar {
4    /// Find shortest path using A* with a custom heuristic
5    ///
6    /// The heuristic function estimates distance from a node to the target.
7    /// Must be admissible (never overestimate) for optimal paths.
8    pub fn shortest_path<H>(
9        graph: &GraphStore,
10        source: &str,
11        target: &str,
12        heuristic: H,
13    ) -> ShortestPathResult
14    where
15        H: Fn(&str, &str) -> f64,
16    {
17        if source == target {
18            return ShortestPathResult {
19                path: Some(Path::start(source)),
20                nodes_visited: 1,
21            };
22        }
23
24        let mut g_costs: HashMap<String, f64> = HashMap::new();
25        let mut heap: BinaryHeap<AStarState> = BinaryHeap::new();
26        let mut nodes_visited = 0;
27
28        let h = heuristic(source, target);
29        g_costs.insert(source.to_string(), 0.0);
30        heap.push(AStarState {
31            node: source.to_string(),
32            g_cost: 0.0,
33            f_cost: h,
34            path: Path::start(source),
35        });
36
37        while let Some(AStarState {
38            node, g_cost, path, ..
39        }) = heap.pop()
40        {
41            nodes_visited += 1;
42
43            if node == target {
44                return ShortestPathResult {
45                    path: Some(path),
46                    nodes_visited,
47                };
48            }
49
50            // Skip if we've found a better path
51            if let Some(&g) = g_costs.get(&node) {
52                if g_cost > g {
53                    continue;
54                }
55            }
56
57            for (edge_type, neighbor, weight) in graph.outgoing_edges(&node) {
58                let new_g = g_cost + weight as f64;
59
60                if !g_costs.contains_key(&neighbor) || new_g < g_costs[&neighbor] {
61                    let h = heuristic(&neighbor, target);
62                    let new_f = new_g + h;
63
64                    g_costs.insert(neighbor.clone(), new_g);
65                    heap.push(AStarState {
66                        node: neighbor.clone(),
67                        g_cost: new_g,
68                        f_cost: new_f,
69                        path: path.extend(&neighbor, edge_type, weight as f64),
70                    });
71                }
72            }
73        }
74
75        ShortestPathResult {
76            path: None,
77            nodes_visited,
78        }
79    }
80
81    /// A* with zero heuristic (equivalent to Dijkstra)
82    pub fn shortest_path_no_heuristic(
83        graph: &GraphStore,
84        source: &str,
85        target: &str,
86    ) -> ShortestPathResult {
87        Self::shortest_path(graph, source, target, |_, _| 0.0)
88    }
89}
reddb_server/storage/engine/pathfinding/astar_impl.rs

reddb_server/storage/engine/pathfinding/
astar_impl.rs
