bracket_pathfinding/field_of_view/
recursive_shadowcasting.rs

1use bracket_algorithm_traits::prelude::Algorithm2D;
2// use bracket_geometry::prelude::{BresenhamCircleNoDiag, Point, VectorLine};
3use bracket_geometry::prelude::Point;
4use std::collections::HashSet;
5
6struct ScanFovData<'a> {
7    center: Point,
8    dimensions: Point,
9    range_2: i32,
10    fov_check: &'a dyn Algorithm2D,
11    visible_points: &'a mut HashSet<Point>,
12}
13
14#[allow(non_snake_case)]
15impl ScanFovData<'_> {
16    fn is_transparent(&self, idx: usize, point: Point) -> bool {
17        if self.fov_check.in_bounds(point) {
18            !self.fov_check.is_opaque(idx)
19        } else {
20            false
21        }
22    }
23
24    fn distance_to_center(&self, point: Point) -> f32 {
25        let dx = i32::abs(point.x - self.center.x) as f32 - 0.5;
26        let dy = i32::abs(point.y - self.center.y) as f32 - 0.5;
27        dx * dx + dy * dy
28    }
29
30    fn insert_visible_for_vertical(&mut self, point: Point) -> bool {
31        let idx = self.fov_check.point2d_to_index(point);
32        let mut is_visible = self.is_transparent(idx, point);
33
34        if self.distance_to_center(point) <= self.range_2 as f32 {
35            if point.x != self.center.x {
36                self.visible_points.insert(point);
37            }
38        } else {
39            is_visible = false;
40        }
41        is_visible
42    }
43
44    fn insert_visible_for_horizontal(&mut self, point: Point) -> bool {
45        let idx = self.fov_check.point2d_to_index(point);
46        let mut is_visible = self.is_transparent(idx, point);
47
48        if self.distance_to_center(point) <= self.range_2 as f32 {
49            if self.center.y != point.y {
50                self.visible_points.insert(point);
51            }
52        } else {
53            is_visible = false;
54        }
55        is_visible
56    }
57
58    fn scan_N2NE(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
59        let mut start_slope = start_slope;
60
61        if distance * distance > self.range_2 {
62            return;
63        }
64
65        let mut current = Point::new(0, self.center.y - distance);
66        if current.y < 0 {
67            return;
68        }
69
70        current.x = self.center.x + (start_slope * distance as f32 + 0.5) as i32;
71        if current.x >= self.dimensions.x {
72            return;
73        }
74
75        let mut end_x = self.center.x + (end_slope * distance as f32 + 0.5) as i32;
76        if end_x >= self.dimensions.x {
77            end_x = self.dimensions.x - 1;
78        }
79
80        let idx = self.fov_check.point2d_to_index(current);
81        let mut last_visible = self.is_transparent(idx, current);
82        for current_x in current.x..=end_x {
83            current.x = current_x;
84
85            let is_visible = self.insert_visible_for_vertical(current);
86
87            if last_visible && !is_visible {
88                self.scan_N2NE(
89                    distance + 1,
90                    start_slope,
91                    ((current.x - self.center.x) as f32 - 0.5) / (distance as f32 + 0.5),
92                );
93            } else if !last_visible && is_visible {
94                start_slope = ((current.x - self.center.x) as f32 - 0.5) / (distance as f32 - 0.5);
95            }
96            last_visible = is_visible;
97        }
98        if last_visible {
99            self.scan_N2NE(distance + 1, start_slope, end_slope);
100        }
101    }
102
103    fn scan_N2NW(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
104        let mut start_slope = start_slope;
105
106        if distance * distance > self.range_2 {
107            return;
108        }
109
110        let mut current = Point::new(0, self.center.y - distance);
111        if current.y < 0 {
112            return;
113        }
114
115        current.x = self.center.x - (start_slope * distance as f32 + 0.5) as i32;
116        if current.x < 0 {
117            return;
118        }
119
120        let mut end_x = self.center.x - (end_slope * distance as f32 + 0.5) as i32;
121        if end_x < 0 {
122            end_x = 0;
123        }
124
125        let idx = self.fov_check.point2d_to_index(current);
126        let mut last_visible = self.is_transparent(idx, current);
127        while current.x >= end_x {
128            let is_visible = self.insert_visible_for_vertical(current);
129
130            if last_visible && !is_visible {
131                self.scan_N2NW(
132                    distance + 1,
133                    start_slope,
134                    ((self.center.x - current.x) as f32 - 0.5) / (distance as f32 + 0.5),
135                );
136            } else if !last_visible && is_visible {
137                start_slope = ((self.center.x - current.x) as f32 - 0.5) / (distance as f32 - 0.5);
138            }
139            last_visible = is_visible;
140            current.x -= 1;
141        }
142        if last_visible {
143            self.scan_N2NW(distance + 1, start_slope, end_slope);
144        }
145    }
146
147    fn scan_S2SE(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
148        let mut start_slope = start_slope;
149
150        if distance * distance > self.range_2 {
151            return;
152        }
153
154        let mut current = Point::new(0, self.center.y + distance);
155        if current.y >= self.dimensions.y {
156            return;
157        }
158
159        current.x = self.center.x + (start_slope * distance as f32 + 0.5) as i32;
160        if current.x >= self.dimensions.x {
161            return;
162        }
163
164        let mut end_x = self.center.x + (end_slope * distance as f32 + 0.5) as i32;
165        if end_x >= self.dimensions.x {
166            end_x = self.dimensions.x - 1;
167        }
168
169        let idx = self.fov_check.point2d_to_index(current);
170        let mut last_visible = self.is_transparent(idx, current);
171        for current_x in current.x..=end_x {
172            current.x = current_x;
173
174            let is_visible = self.insert_visible_for_vertical(current);
175
176            if last_visible && !is_visible {
177                self.scan_S2SE(
178                    distance + 1,
179                    start_slope,
180                    ((current.x - self.center.x) as f32 - 0.5) / (distance as f32 + 0.5),
181                );
182            } else if !last_visible && is_visible {
183                start_slope = ((current.x - self.center.x) as f32 - 0.5) / (distance as f32 - 0.5);
184            }
185            last_visible = is_visible;
186        }
187        if last_visible {
188            self.scan_S2SE(distance + 1, start_slope, end_slope);
189        }
190    }
191
192    fn scan_S2SW(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
193        let mut start_slope = start_slope;
194
195        if distance * distance > self.range_2 {
196            return;
197        }
198
199        let mut current = Point::new(0, self.center.y + distance);
200        if current.y >= self.dimensions.y {
201            return;
202        }
203
204        current.x = self.center.x - (start_slope * distance as f32 + 0.5) as i32;
205        if current.x < 0 {
206            return;
207        }
208
209        let mut end_x = self.center.x - (end_slope * distance as f32 + 0.5) as i32;
210        if end_x < 0 {
211            end_x = 0;
212        }
213
214        let idx = self.fov_check.point2d_to_index(current);
215        let mut last_visible = self.is_transparent(idx, current);
216        while current.x >= end_x {
217            let is_visible = self.insert_visible_for_vertical(current);
218
219            if last_visible && !is_visible {
220                self.scan_S2SW(
221                    distance + 1,
222                    start_slope,
223                    ((self.center.x - current.x) as f32 - 0.5) / (distance as f32 + 0.5),
224                );
225            } else if !last_visible && is_visible {
226                start_slope = ((self.center.x - current.x) as f32 - 0.5) / (distance as f32 - 0.5);
227            }
228            last_visible = is_visible;
229            current.x -= 1;
230        }
231        if last_visible {
232            self.scan_S2SW(distance + 1, start_slope, end_slope);
233        }
234    }
235
236    fn scan_E2SE(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
237        let mut start_slope = start_slope;
238
239        if distance * distance > self.range_2 {
240            return;
241        }
242
243        let mut current = Point::new(self.center.x + distance, 0);
244        if current.x >= self.dimensions.x {
245            return;
246        }
247
248        current.y = self.center.y + (start_slope * distance as f32 + 0.5) as i32;
249        if current.y >= self.dimensions.y {
250            return;
251        }
252
253        let mut end_y = self.center.y + (end_slope * distance as f32 + 0.5) as i32;
254        if end_y >= self.dimensions.y {
255            end_y = self.dimensions.y - 1;
256        }
257
258        let idx = self.fov_check.point2d_to_index(current);
259        let mut last_visible = self.is_transparent(idx, current);
260        for current_y in current.y..=end_y {
261            current.y = current_y;
262
263            let is_visible = self.insert_visible_for_horizontal(current);
264
265            if last_visible && !is_visible {
266                self.scan_E2SE(
267                    distance + 1,
268                    start_slope,
269                    ((current.y - self.center.y) as f32 - 0.5) / (distance as f32 + 0.5),
270                );
271            } else if !last_visible && is_visible {
272                start_slope = ((current.y - self.center.y) as f32 - 0.5) / (distance as f32 - 0.5);
273            }
274            last_visible = is_visible;
275        }
276        if last_visible {
277            self.scan_E2SE(distance + 1, start_slope, end_slope);
278        }
279    }
280
281    fn scan_E2NE(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
282        let mut start_slope = start_slope;
283
284        if distance * distance > self.range_2 {
285            return;
286        }
287
288        let mut current = Point::new(self.center.x + distance, 0);
289        if current.x >= self.dimensions.x {
290            return;
291        }
292
293        current.y = self.center.y - (start_slope * distance as f32 + 0.5) as i32;
294        if current.y < 0 {
295            return;
296        }
297
298        let mut end_y = self.center.y - (end_slope * distance as f32 + 0.5) as i32;
299        if end_y < 0 {
300            end_y = 0;
301        }
302
303        let idx = self.fov_check.point2d_to_index(current);
304        let mut last_visible = self.is_transparent(idx, current);
305        while current.y >= end_y {
306            let is_visible = self.insert_visible_for_horizontal(current);
307
308            if last_visible && !is_visible {
309                self.scan_E2NE(
310                    distance + 1,
311                    start_slope,
312                    ((self.center.y - current.y) as f32 - 0.5) / (distance as f32 + 0.5),
313                );
314            } else if !last_visible && is_visible {
315                start_slope = ((self.center.y - current.y) as f32 - 0.5) / (distance as f32 - 0.5);
316            }
317            last_visible = is_visible;
318            current.y -= 1;
319        }
320        if last_visible {
321            self.scan_E2NE(distance + 1, start_slope, end_slope);
322        }
323    }
324
325    fn scan_W2SW(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
326        let mut start_slope = start_slope;
327
328        if distance * distance > self.range_2 {
329            return;
330        }
331
332        let mut current = Point::new(self.center.x - distance, 0);
333        if current.x < 0 {
334            return;
335        }
336
337        current.y = self.center.y + (start_slope * distance as f32 + 0.5) as i32;
338        if current.y >= self.dimensions.y {
339            return;
340        }
341
342        let mut end_y = self.center.y + (end_slope * distance as f32 + 0.5) as i32;
343        if end_y >= self.dimensions.y {
344            end_y = self.dimensions.y - 1;
345        }
346
347        let idx = self.fov_check.point2d_to_index(current);
348        let mut last_visible = self.is_transparent(idx, current);
349        for current_y in current.y..=end_y {
350            current.y = current_y;
351
352            let is_visible = self.insert_visible_for_horizontal(current);
353
354            if last_visible && !is_visible {
355                self.scan_W2SW(
356                    distance + 1,
357                    start_slope,
358                    ((current.y - self.center.y) as f32 - 0.5) / (distance as f32 + 0.5),
359                );
360            } else if !last_visible && is_visible {
361                start_slope = ((current.y - self.center.y) as f32 - 0.5) / (distance as f32 - 0.5);
362            }
363            last_visible = is_visible;
364        }
365        if last_visible {
366            self.scan_W2SW(distance + 1, start_slope, end_slope);
367        }
368    }
369
370    fn scan_W2NW(&mut self, distance: i32, start_slope: f32, end_slope: f32) {
371        let mut start_slope = start_slope;
372
373        if distance * distance > self.range_2 {
374            return;
375        }
376
377        let mut current = Point::new(self.center.x - distance, 0);
378        if current.x < 0 {
379            return;
380        }
381
382        current.y = self.center.y - (start_slope * distance as f32 + 0.5) as i32;
383        if current.y < 0 {
384            return;
385        }
386
387        let mut end_y = self.center.y - (end_slope * distance as f32 + 0.5) as i32;
388        if end_y < 0 {
389            end_y = 0;
390        }
391
392        let idx = self.fov_check.point2d_to_index(current);
393        let mut last_visible = self.is_transparent(idx, current);
394        while current.y >= end_y {
395            let is_visible = self.insert_visible_for_horizontal(current);
396
397            if last_visible && !is_visible {
398                self.scan_W2NW(
399                    distance + 1,
400                    start_slope,
401                    ((self.center.y - current.y) as f32 - 0.5) / (distance as f32 + 0.5),
402                );
403            } else if !last_visible && is_visible {
404                start_slope = ((self.center.y - current.y) as f32 - 0.5) / (distance as f32 - 0.5);
405            }
406            last_visible = is_visible;
407            current.y -= 1;
408        }
409        if last_visible {
410            self.scan_W2NW(distance + 1, start_slope, end_slope);
411        }
412    }
413}
414
415/// Calculates field-of-view for a map that supports Algorithm2D, returning a HashSet. This is a bit faster
416/// than coercing the results into a vector, since internally it uses the set for de-duplication.
417#[rustfmt::skip]
418pub fn field_of_view_set(center: Point, range: i32, fov_check: &dyn Algorithm2D) -> HashSet<Point> {
419    let mut visible_points: HashSet<Point> =
420        HashSet::with_capacity(((range * 2) * (range * 2)) as usize);
421
422    visible_points.insert(center);
423
424    /* N, NE, E, SE, S, SW, W, NW */
425    const SECTORS: [(i32, i32); 8] = [ (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), ];
426
427    let r2 = range * range;
428    let dimensions = fov_check.dimensions();
429
430    // Add visibility for every 45 degree line:
431    let mut visibility_per_sector = [false; 8];
432    for (i, (dx, dy)) in SECTORS.iter().enumerate() {
433        let mut current = center;
434        loop {
435            current = Point::new(current.x + dx, current.y + dy);
436            if current.x < 0 || current.x >= dimensions.x
437                || current.y < 0 || current.y >= dimensions.y
438            {
439                break;
440            }
441            let x2 = current.x - center.x;
442            let x2 = x2 * x2;
443            let y2 = current.y - center.y;
444            let y2 = y2 * y2;
445            if x2 + y2 > r2 {
446                break;
447            }
448
449            let idx = fov_check.point2d_to_index(current);
450            visible_points.insert(current);
451            if fov_check.is_opaque(idx) {
452                break;
453            }
454            visibility_per_sector[i] = true;
455        }
456    }
457
458    let mut scanner = ScanFovData {
459        center,
460        dimensions,
461        range_2: r2,
462        fov_check,
463        visible_points: &mut visible_points,
464    };
465    if visibility_per_sector[0] {
466        scanner.scan_N2NW(1, 0., 1.);
467        scanner.scan_N2NE(1, 0., 1.);
468    }
469
470    if visibility_per_sector[2] {
471        scanner.scan_E2NE(1, 0., 1.);
472        scanner.scan_E2SE(1, 0., 1.);
473    }
474
475    if visibility_per_sector[4] {
476        scanner.scan_S2SE(1, 0., 1.);
477        scanner.scan_S2SW(1, 0., 1.);
478    }
479
480    if visibility_per_sector[6] {
481        scanner.scan_W2SW(1, 0., 1.);
482        scanner.scan_W2NW(1, 0., 1.);
483    }
484
485    visible_points
486        .iter()
487        .copied()
488        .filter(|p| fov_check.in_bounds(*p))
489        .collect()
490}
491
492/// Calculates field-of-view for a map that supports Algorithm2D.
493pub fn field_of_view(start: Point, range: i32, fov_check: &dyn Algorithm2D) -> Vec<Point> {
494    field_of_view_set(start, range, fov_check)
495        .into_iter()
496        .collect()
497}
bracket_pathfinding/field_of_view/recursive_shadowcasting.rs

bracket_pathfinding/field_of_view/
recursive_shadowcasting.rs
