grid_search/
dijkstra.rs

1use config::*;
2use direction::*;
3use error::*;
4use grid::*;
5use metadata::*;
6use num_traits::Zero;
7use path;
8use search::*;
9use std::ops::Add;
10
11impl<Cost: Copy + Add<Cost> + PartialOrd<Cost> + Zero> SearchContext<Cost> {
12    pub fn dijkstra<G, V, D>(
13        &mut self,
14        grid: &G,
15        start: Coord,
16        goal: Coord,
17        directions: D,
18        config: SearchConfig,
19        path: &mut Vec<Direction>,
20    ) -> Result<SearchMetadata<Cost>, Error>
21    where
22        G: CostGrid<Cost = Cost>,
23        V: Into<Direction>,
24        D: Copy + IntoIterator<Item = V>,
25    {
26        self.search_general(
27            grid,
28            start,
29            goal,
30            directions,
31            |_, _| Zero::zero(),
32            config,
33            path,
34        )
35    }
36
37    pub fn dijkstra_predicate<G, V, D, F>(
38        &mut self,
39        grid: &G,
40        start: Coord,
41        predicate: F,
42        directions: D,
43        config: SearchConfig,
44        path: &mut Vec<Direction>,
45    ) -> Result<SearchMetadata<Cost>, Error>
46    where
47        G: CostGrid<Cost = Cost>,
48        V: Into<Direction>,
49        D: Copy + IntoIterator<Item = V>,
50        F: Fn(Coord) -> bool,
51    {
52        let initial_entry = match self.init(start, &predicate, grid, config, path) {
53            Ok(initial_entry) => initial_entry,
54            Err(result) => return result,
55        };
56
57        self.priority_queue.push(initial_entry);
58
59        let mut num_nodes_visited = 0;
60
61        while let Some(current_entry) = self.priority_queue.pop() {
62            num_nodes_visited += 1;
63
64            let (current_coord, current_cost) = {
65                let node = &mut self.node_grid[current_entry.node_index];
66
67                if node.visited == self.seq {
68                    continue;
69                }
70                node.visited = self.seq;
71                (node.coord, node.cost)
72            };
73
74            if predicate(current_coord) {
75                path::make_path_all_adjacent(&self.node_grid, current_entry.node_index, path);
76                return Ok(SearchMetadata {
77                    num_nodes_visited,
78                    cost: current_cost,
79                    length: path.len(),
80                });
81            }
82
83            for d in directions {
84                let direction = d.into();
85                let neighbour_coord = current_coord + direction.coord();
86
87                let neighbour_cost =
88                    if let Some(CostCell::Cost(cost)) = grid.cost(neighbour_coord, direction) {
89                        cost
90                    } else {
91                        continue;
92                    };
93
94                let index = self
95                    .node_grid
96                    .index_of_coord(neighbour_coord)
97                    .ok_or(Error::VisitOutsideContext)?;
98
99                let cost = current_cost + neighbour_cost;
100                let node = &mut self.node_grid[index];
101
102                if node.seen != self.seq || node.cost > cost {
103                    node.from_parent = Some(direction);
104                    node.seen = self.seq;
105                    node.cost = cost;
106
107                    let entry = PriorityEntry::new(index, cost);
108                    self.priority_queue.push(entry);
109                }
110            }
111        }
112
113        Err(Error::NoPath)
114    }
115}
grid_search/dijkstra.rs

grid_search/
dijkstra.rs
