bracket_pathfinding/
dijkstra.rs

1use bracket_algorithm_traits::prelude::BaseMap;
2#[cfg(feature = "threaded")]
3use rayon::prelude::*;
4#[allow(unused_imports)]
5use smallvec::SmallVec;
6use std::collections::VecDeque;
7use std::convert::TryInto;
8use std::f32::MAX;
9
10/// Representation of a Dijkstra flow map.
11/// map is a vector of floats, having a size equal to size_x * size_y (one per tile).
12/// size_x and size_y are stored for overflow avoidance.
13/// max_depth is the maximum number of iterations this search shall support.
14pub struct DijkstraMap {
15    pub map: Vec<f32>,
16    size_x: usize,
17    size_y: usize,
18    max_depth: f32,
19}
20
21/// Used internally when constructing maps in parallel
22#[cfg(feature = "threaded")]
23struct ParallelDm {
24    map: Vec<f32>,
25    max_depth: f32,
26    starts: Vec<usize>,
27}
28
29// This is chosen arbitrarily. Whether it's better to
30// run threaded or not would depend on map structure,
31// map size, number of starts, and probably several
32// other parameters. Might want to make this choice
33// an explicit part of the API?
34#[allow(dead_code)]
35const THREADED_REQUIRED_STARTS: usize = 4;
36
37#[derive(PartialEq)]
38enum RunThreaded {
39    True,
40    False,
41}
42
43#[allow(dead_code)]
44impl DijkstraMap {
45    /// Construct a new Dijkstra map, ready to run. You must specify the map size, and link to an implementation
46    /// of a BaseMap trait that can generate exits lists. It then builds the map, giving you a result.
47    pub fn new<T>(
48        size_x: T,
49        size_y: T,
50        starts: &[usize],
51        map: &dyn BaseMap,
52        max_depth: f32,
53    ) -> DijkstraMap
54    where
55        T: TryInto<usize>,
56    {
57        let sz_x: usize = size_x.try_into().ok().unwrap();
58        let sz_y: usize = size_y.try_into().ok().unwrap();
59        let result: Vec<f32> = vec![MAX; sz_x * sz_y];
60        let mut d = DijkstraMap {
61            map: result,
62            size_x: sz_x,
63            size_y: sz_y,
64            max_depth,
65        };
66        DijkstraMap::build(&mut d, starts, map);
67        d
68    }
69
70    /// Construct a new Dijkstra map, ready to run. You must specify the map size, and link to an implementation
71    /// of a BaseMap trait that can generate exits lists. It then builds the map, giving you a result.
72    /// Starts is provided as a set of tuples, two per tile. The first is the tile index, the second the starting
73    /// weight (defaults to 0.0 on new)
74    pub fn new_weighted<T>(
75        size_x: T,
76        size_y: T,
77        starts: &[(usize, f32)],
78        map: &dyn BaseMap,
79        max_depth: f32,
80    ) -> DijkstraMap
81    where
82        T: TryInto<usize>,
83    {
84        let sz_x: usize = size_x.try_into().ok().unwrap();
85        let sz_y: usize = size_y.try_into().ok().unwrap();
86        let result: Vec<f32> = vec![MAX; sz_x * sz_y];
87        let mut d = DijkstraMap {
88            map: result,
89            size_x: sz_x,
90            size_y: sz_y,
91            max_depth,
92        };
93        DijkstraMap::build_weighted(&mut d, starts, map);
94        d
95    }
96
97    /// Creates an empty Dijkstra map node.
98    pub fn new_empty<T>(size_x: T, size_y: T, max_depth: f32) -> DijkstraMap
99    where
100        T: TryInto<usize>,
101    {
102        let sz_x: usize = size_x.try_into().ok().unwrap();
103        let sz_y: usize = size_y.try_into().ok().unwrap();
104        let result: Vec<f32> = vec![MAX; sz_x * sz_y];
105        DijkstraMap {
106            map: result,
107            size_x: sz_x,
108            size_y: sz_y,
109            max_depth,
110        }
111    }
112
113    /// Clears the Dijkstra map. Uses a parallel for each for performance.
114    #[cfg(feature = "threaded")]
115    pub fn clear(dm: &mut DijkstraMap) {
116        dm.map.par_iter_mut().for_each(|x| *x = MAX);
117    }
118
119    #[cfg(not(feature = "threaded"))]
120    pub fn clear(dm: &mut DijkstraMap) {
121        dm.map.iter_mut().for_each(|x| *x = MAX);
122    }
123
124    #[cfg(feature = "threaded")]
125    fn build_helper(dm: &mut DijkstraMap, starts: &[usize], map: &dyn BaseMap) -> RunThreaded {
126        if starts.len() >= THREADED_REQUIRED_STARTS {
127            DijkstraMap::build_parallel(dm, starts, map);
128            return RunThreaded::True;
129        }
130        RunThreaded::False
131    }
132
133    #[cfg(not(feature = "threaded"))]
134    fn build_helper(_dm: &mut DijkstraMap, _starts: &[usize], _map: &dyn BaseMap) -> RunThreaded {
135        RunThreaded::False
136    }
137
138    /// Builds the Dijkstra map: iterate from each starting point, to each exit provided by BaseMap's
139    /// exits implementation. Each step adds cost to the current depth, and is discarded if the new
140    /// depth is further than the current depth.
141    /// WARNING: Will give incorrect results when used with non-uniform exit costs. Much slower
142    /// algorithm required to support that.
143    /// Automatically branches to a parallel version if you provide more than 4 starting points
144    pub fn build(dm: &mut DijkstraMap, starts: &[usize], map: &dyn BaseMap) {
145        let threaded = DijkstraMap::build_helper(dm, starts, map);
146        if threaded == RunThreaded::True {
147            return;
148        }
149        let mapsize: usize = (dm.size_x * dm.size_y) as usize;
150        let mut open_list: VecDeque<(usize, f32)> = VecDeque::with_capacity(mapsize);
151
152        for start in starts {
153            open_list.push_back((*start, 0.0));
154        }
155
156        while let Some((tile_idx, depth)) = open_list.pop_front() {
157            let exits = map.get_available_exits(tile_idx);
158            for (new_idx, add_depth) in exits {
159                let new_depth = depth + add_depth;
160                let prev_depth = dm.map[new_idx];
161                if new_depth >= prev_depth {
162                    continue;
163                }
164                if new_depth >= dm.max_depth {
165                    continue;
166                }
167                dm.map[new_idx] = new_depth;
168                open_list.push_back((new_idx, new_depth));
169            }
170        }
171    }
172
173    /// Builds the Dijkstra map: iterate from each starting point, to each exit provided by BaseMap's
174    /// exits implementation. Each step adds cost to the current depth, and is discarded if the new
175    /// depth is further than the current depth.
176    /// WARNING: Will give incorrect results when used with non-uniform exit costs. Much slower
177    /// algorithm required to support that.
178    /// Automatically branches to a parallel version if you provide more than 4 starting points
179    pub fn build_weighted(dm: &mut DijkstraMap, starts: &[(usize, f32)], map: &dyn BaseMap) {
180        let mapsize: usize = (dm.size_x * dm.size_y) as usize;
181        let mut open_list: VecDeque<(usize, f32)> = VecDeque::with_capacity(mapsize);
182
183        for start in starts {
184            open_list.push_back(*start);
185        }
186
187        while let Some((tile_idx, depth)) = open_list.pop_front() {
188            let exits = map.get_available_exits(tile_idx);
189            for (new_idx, add_depth) in exits {
190                let new_depth = depth + add_depth;
191                let prev_depth = dm.map[new_idx];
192                if new_depth >= prev_depth {
193                    continue;
194                }
195                if new_depth >= dm.max_depth {
196                    continue;
197                }
198                dm.map[new_idx] = new_depth;
199                open_list.push_back((new_idx, new_depth));
200            }
201        }
202    }
203
204    /// Implementation of Parallel Dijkstra.
205    #[cfg(feature = "threaded")]
206    fn build_parallel(dm: &mut DijkstraMap, starts: &[usize], map: &dyn BaseMap) {
207        let mapsize: usize = (dm.size_x * dm.size_y) as usize;
208        let mut layers: Vec<ParallelDm> = Vec::with_capacity(starts.len());
209        for start_chunk in starts.chunks(rayon::current_num_threads()) {
210            let mut layer = ParallelDm {
211                map: vec![MAX; mapsize],
212                max_depth: dm.max_depth,
213                starts: Vec::new(),
214            };
215            layer
216                .starts
217                .extend(start_chunk.iter().copied().map(|x| x as usize));
218            layers.push(layer);
219        }
220
221        let exits: Vec<SmallVec<[(usize, f32); 10]>> = (0..mapsize)
222            .map(|idx| map.get_available_exits(idx))
223            .collect();
224
225        // Run each map in parallel
226        layers.par_iter_mut().for_each(|l| {
227            let mut open_list: VecDeque<(usize, f32)> = VecDeque::with_capacity(mapsize);
228
229            for start in l.starts.iter().copied() {
230                open_list.push_back((start, 0.0));
231            }
232
233            while let Some((tile_idx, depth)) = open_list.pop_front() {
234                let exits = &exits[tile_idx];
235                for (new_idx, add_depth) in exits {
236                    let new_idx = *new_idx;
237                    let new_depth = depth + add_depth;
238                    let prev_depth = l.map[new_idx];
239                    if new_depth >= prev_depth {
240                        continue;
241                    }
242                    if new_depth >= l.max_depth {
243                        continue;
244                    }
245                    l.map[new_idx] = new_depth;
246                    open_list.push_back((new_idx, new_depth));
247                }
248            }
249        });
250
251        // Recombine down to a single result
252        for l in layers {
253            for i in 0..mapsize {
254                dm.map[i] = f32::min(dm.map[i], l.map[i]);
255            }
256        }
257    }
258
259    /// Helper for traversing maps as path-finding. Provides the index of the lowest available
260    /// exit from the specified position index, or None if there isn't one.
261    /// You would use this for pathing TOWARDS a starting node.
262    #[cfg(feature = "threaded")]
263    pub fn find_lowest_exit(dm: &DijkstraMap, position: usize, map: &dyn BaseMap) -> Option<usize> {
264        let mut exits = map.get_available_exits(position);
265
266        if exits.is_empty() {
267            return None;
268        }
269
270        exits.par_sort_by(|a, b| {
271            dm.map[a.0 as usize]
272                .partial_cmp(&dm.map[b.0 as usize])
273                .unwrap()
274        });
275
276        Some(exits[0].0)
277    }
278
279    #[cfg(not(feature = "threaded"))]
280    pub fn find_lowest_exit(dm: &DijkstraMap, position: usize, map: &dyn BaseMap) -> Option<usize> {
281        let mut exits = map.get_available_exits(position);
282
283        if exits.is_empty() {
284            return None;
285        }
286
287        exits.sort_by(|a, b| {
288            dm.map[a.0 as usize]
289                .partial_cmp(&dm.map[b.0 as usize])
290                .unwrap()
291        });
292
293        Some(exits[0].0)
294    }
295
296    /// Helper for traversing maps as path-finding. Provides the index of the highest available
297    /// exit from the specified position index, or None if there isn't one.
298    /// You would use this for pathing AWAY from a starting node, for example if you are running
299    /// away.
300    #[cfg(feature = "threaded")]
301    pub fn find_highest_exit(
302        dm: &DijkstraMap,
303        position: usize,
304        map: &dyn BaseMap,
305    ) -> Option<usize> {
306        let mut exits = map.get_available_exits(position);
307
308        if exits.is_empty() {
309            return None;
310        }
311
312        exits.par_sort_by(|a, b| {
313            dm.map[b.0 as usize]
314                .partial_cmp(&dm.map[a.0 as usize])
315                .unwrap()
316        });
317
318        Some(exits[0].0)
319    }
320
321    #[cfg(not(feature = "threaded"))]
322    pub fn find_highest_exit(
323        dm: &DijkstraMap,
324        position: usize,
325        map: &dyn BaseMap,
326    ) -> Option<usize> {
327        let mut exits = map.get_available_exits(position);
328
329        if exits.is_empty() {
330            return None;
331        }
332
333        exits.sort_by(|a, b| {
334            dm.map[b.0 as usize]
335                .partial_cmp(&dm.map[a.0 as usize])
336                .unwrap()
337        });
338
339        Some(exits[0].0)
340    }
341}
342
343#[cfg(test)]
344mod test {
345    use crate::prelude::*;
346    use bracket_algorithm_traits::prelude::*;
347    // 1 by 3 stripe of tiles
348    struct MiniMap;
349    impl BaseMap for MiniMap {
350        fn get_available_exits(&self, idx: usize) -> SmallVec<[(usize, f32); 10]> {
351            match idx {
352                0 => smallvec![(1, 1.)],
353                2 => smallvec![(1, 1.)],
354                _ => smallvec![(idx - 1, 1.), (idx + 1, 2.)],
355            }
356        }
357    }
358    #[test]
359    fn test_highest_exit() {
360        let map = MiniMap {};
361        let exits_map = DijkstraMap::new(3, 1, &[0], &map, 10.);
362        let target = DijkstraMap::find_highest_exit(&exits_map, 0, &map);
363        assert_eq!(target, Some(1));
364        let target = DijkstraMap::find_highest_exit(&exits_map, 1, &map);
365        assert_eq!(target, Some(2));
366    }
367}
bracket_pathfinding/dijkstra.rs

bracket_pathfinding/
dijkstra.rs
