bracket_pathfinding/field_of_view/
mod.rs

1use bracket_algorithm_traits::prelude::Algorithm2D;
2use bracket_geometry::prelude::Point;
3
4use std::collections::HashSet;
5
6mod recursive_shadowcasting;
7// Default algorithm / backwards compatibility
8pub use recursive_shadowcasting::{field_of_view, field_of_view_set};
9mod symmetric_shadowcasting;
10
11/// Enumeration of available FOV algorithms
12#[derive(Clone, Copy)]
13#[non_exhaustive] // Other algorithms may be added in the future
14pub enum FieldOfViewAlg {
15    RecursiveShadowcasting,
16    SymmetricShadowcasting,
17}
18
19impl FieldOfViewAlg {
20    pub fn field_of_view_set(
21        self,
22        center: Point,
23        range: i32,
24        fov_check: &dyn Algorithm2D,
25    ) -> HashSet<Point> {
26        match self {
27            FieldOfViewAlg::RecursiveShadowcasting => {
28                recursive_shadowcasting::field_of_view_set(center, range, fov_check)
29            }
30            FieldOfViewAlg::SymmetricShadowcasting => {
31                symmetric_shadowcasting::field_of_view_set(center, range, fov_check)
32            }
33        }
34    }
35    pub fn field_of_view(
36        self,
37        start: Point,
38        range: i32,
39        fov_check: &dyn Algorithm2D,
40    ) -> Vec<Point> {
41        match self {
42            FieldOfViewAlg::RecursiveShadowcasting => {
43                recursive_shadowcasting::field_of_view(start, range, fov_check)
44            }
45            FieldOfViewAlg::SymmetricShadowcasting => {
46                symmetric_shadowcasting::field_of_view(start, range, fov_check)
47            }
48        }
49    }
50}
51
52#[cfg(test)]
53mod tests {
54
55    use crate::prelude::FieldOfViewAlg;
56    use bracket_algorithm_traits::prelude::{Algorithm2D, BaseMap};
57    use bracket_geometry::prelude::{BresenhamCircle, Point};
58    use std::cmp::max;
59    use std::collections::HashSet;
60    use std::hash::Hash;
61
62    const TESTMAP_W: usize = 20;
63    const TESTMAP_H: usize = 20;
64    const TESTMAP_TILES: usize = (TESTMAP_W * TESTMAP_H) as usize;
65    const ALGORITHS: [FieldOfViewAlg; 2] = [
66        FieldOfViewAlg::RecursiveShadowcasting,
67        FieldOfViewAlg::SymmetricShadowcasting,
68    ];
69
70    struct Map {
71        pub tiles: Vec<bool>,
72    }
73
74    impl Map {
75        fn new() -> Map {
76            Map {
77                tiles: vec![false; TESTMAP_TILES],
78            }
79        }
80    }
81
82    // The map needs to be see-through for the tests to check FOV
83    impl BaseMap for Map {
84        fn is_opaque(&self, idx: usize) -> bool {
85            self.tiles[idx]
86        }
87    }
88
89    impl Algorithm2D for Map {
90        fn dimensions(&self) -> Point {
91            Point::new(TESTMAP_W, TESTMAP_H)
92        }
93    }
94
95    fn has_unique_elements<T>(iter: T) -> bool
96    where
97        T: IntoIterator,
98        T::Item: Eq + Hash,
99    {
100        let mut uniq = HashSet::new();
101        iter.into_iter().all(move |x| uniq.insert(x))
102    }
103
104    // Tests that we are correctly de-duplicating field of view
105    #[test]
106    fn fov_dupes() {
107        let map = Map::new();
108
109        for alg in ALGORITHS {
110            let visible = alg.field_of_view(Point::new(10, 10), 8, &map);
111
112            assert!(has_unique_elements(&visible));
113        }
114    }
115
116    // Tests that the bounds-checking trait is applying properly to field-of-view checks
117    #[test]
118    fn fov_bounds_check() {
119        let map = Map::new();
120
121        for alg in ALGORITHS {
122            let visible = alg.field_of_view(Point::new(2, 2), 8, &map);
123
124            for t in visible.iter() {
125                assert!(t.x >= 0);
126                assert!(t.x < TESTMAP_W as i32 - 1);
127                assert!(t.y >= 0);
128                assert!(t.y < TESTMAP_H as i32 - 1);
129            }
130        }
131    }
132
133    // Tests that the FOV scan does not miss any interior points
134    #[test]
135    fn fov_inclusive() {
136        for radius in 4..=9 {
137            let map = Map::new();
138            let dimensions = map.dimensions();
139            let c = Point::new(10, 10);
140            for alg in ALGORITHS {
141                let visible = alg.field_of_view(c, radius, &map);
142                // let max_radius_sq: i32 = visible.iter().fold(0, |max_r2, p| {
143                let max_radius_sq: i32 = BresenhamCircle::new(c, radius).fold(0, |max_r2, p| {
144                    let r2 = (p.x - c.x) * (p.x - c.x) + (p.y - c.y) * (p.y - c.y);
145                    max(r2, max_r2)
146                });
147                /*
148                for y in 0..dimensions.y {
149                    let mut s = "".to_string();
150                    for x in 0..dimensions.x {
151                        let point = Point::new(x, y);
152                        let c = if visible.contains(&point) {
153                            '.'
154                        } else {
155                            '#'
156                        };
157                        s.push(c);
158                    }
159                    println!("{}", s);
160                }
161                */
162                for x in 0..dimensions.x {
163                    for y in 0..dimensions.y {
164                        let r2 = (x - c.x) * (x - c.x) + (y - c.y) * (y - c.y);
165                        let point = Point::new(x, y);
166                        assert!(
167                            r2 >= max_radius_sq || visible.contains(&point),
168                            "Interior point ({:?}) not in FOV({})",
169                            point,
170                            radius
171                        );
172                    }
173                }
174            }
175        }
176    }
177
178    #[test]
179    fn fov_corridor() {
180        let mut map = Map::new();
181        let c = Point::new(10, 10);
182        let radius: i32 = 5;
183
184        for i in 0..20 {
185            let idx = 9 * 20 + i;
186            map.tiles[idx] = true;
187            let idx = 11 * 20 + i;
188            map.tiles[idx] = true;
189        }
190
191        for alg in ALGORITHS {
192            let visible = alg.field_of_view(c, radius, &map);
193            for i in 1..radius * 2 - 2 {
194                let pos = Point::new(c.x - radius + i, c.y);
195                assert!(visible.contains(&pos));
196                let pos = Point::new(c.x - radius + i, c.y - 1);
197                assert!(visible.contains(&pos), "{:?} not in result", pos);
198                let pos = Point::new(c.x - radius + i, c.y + 1);
199                assert!(visible.contains(&pos));
200            }
201        }
202    }
203
204    // NOTE: Symmetry applies to FieldOfViewAlg::SymmetricShadowcasting only
205    #[test]
206    fn fov_symmetric() {
207        use bracket_random::prelude::RandomNumberGenerator;
208
209        let mut rng = RandomNumberGenerator::seeded(0);
210        let mut map = Map::new();
211        let c = Point::new(10, 10);
212        let radius: i32 = 8;
213
214        for _ in 0..TESTMAP_TILES / 5 {
215            map.tiles[rng.range(0, TESTMAP_TILES)] = true;
216        }
217        map.tiles[c.to_index(TESTMAP_W)] = false;
218
219        for point in FieldOfViewAlg::SymmetricShadowcasting.field_of_view_set(c, radius, &map) {
220            // Symmetry only holds for transparent tiles
221            if !map.tiles[point.to_index(TESTMAP_W)] {
222                assert!(FieldOfViewAlg::SymmetricShadowcasting
223                    .field_of_view_set(point, radius, &map)
224                    .contains(&c));
225            }
226        }
227    }
228}
bracket_pathfinding/field_of_view/mod.rs

bracket_pathfinding/field_of_view/
mod.rs
