veloren_common/util/
spatial_grid.rs

1use super::GridHasher;
2use vek::*;
3
4#[derive(Debug)]
5pub struct SpatialGrid {
6    // Uses two scales of grids so that we can have a hard limit on how far to search in the
7    // smaller grid
8    grid: hashbrown::HashMap<Vec2<i32>, Vec<specs::Entity>, GridHasher>,
9    large_grid: hashbrown::HashMap<Vec2<i32>, Vec<specs::Entity>, GridHasher>,
10    // Log base 2 of the cell size of the spatial grid
11    lg2_cell_size: usize,
12    // Log base 2 of the cell size of the large spatial grid
13    lg2_large_cell_size: usize,
14    // Entities with a radius over this value are store in the coarser large_grid
15    // This is the amount of buffer space we need to add when finding the intersections with cells
16    // in the regular grid
17    radius_cutoff: u32,
18    // Stores the largest radius of the entities in the large_grid
19    // This is the amount of buffer space we need to add when finding the intersections with cells
20    // in the larger grid
21    // note: could explore some distance field type thing for querying whether there are large
22    // entities nearby that necessitate expanding the cells searched for collision (and querying
23    // how much it needs to be expanded)
24    // TODO: log this to metrics?
25    largest_large_radius: u32,
26}
27
28impl SpatialGrid {
29    pub fn new(lg2_cell_size: usize, lg2_large_cell_size: usize, radius_cutoff: u32) -> Self {
30        Self {
31            grid: Default::default(),
32            large_grid: Default::default(),
33            lg2_cell_size,
34            lg2_large_cell_size,
35            radius_cutoff,
36            largest_large_radius: radius_cutoff,
37        }
38    }
39
40    /// Add an entity at the provided 2d pos into the spatial grid
41    pub fn insert(&mut self, pos: Vec2<i32>, radius: u32, entity: specs::Entity) {
42        if radius <= self.radius_cutoff {
43            let cell = pos.map(|e| e >> self.lg2_cell_size);
44            self.grid.entry(cell).or_default().push(entity);
45        } else {
46            let cell = pos.map(|e| e >> self.lg2_large_cell_size);
47            self.large_grid.entry(cell).or_default().push(entity);
48            self.largest_large_radius = self.largest_large_radius.max(radius);
49        }
50    }
51
52    /// Get an iterator over the entities overlapping the provided axis aligned
53    /// bounding region.
54    /// NOTE: for best optimization of the iterator use
55    /// `for_each` rather than a for loop.
56    pub fn in_aabr<'a>(&'a self, aabr: Aabr<i32>) -> impl Iterator<Item = specs::Entity> + 'a {
57        let iter = |max_entity_radius, grid: &'a hashbrown::HashMap<_, _, _>, lg2_cell_size| {
58            // Add buffer for other entity radius
59            let min = aabr.min - max_entity_radius as i32;
60            let max = aabr.max + max_entity_radius as i32;
61            // Convert to cells
62            let min = min.map(|e| e >> lg2_cell_size);
63            let max = max.map(|e| (e + (1 << lg2_cell_size) - 1) >> lg2_cell_size);
64
65            (min.x..=max.x)
66                .flat_map(move |x| (min.y..=max.y).map(move |y| Vec2::new(x, y)))
67                .flat_map(move |cell| grid.get(&cell).into_iter().flatten())
68                .copied()
69        };
70
71        iter(self.radius_cutoff, &self.grid, self.lg2_cell_size).chain(iter(
72            self.largest_large_radius,
73            &self.large_grid,
74            self.lg2_large_cell_size,
75        ))
76    }
77
78    /// Get an iterator over the entities overlapping the
79    /// axis aligned bounding region that contains the provided circle
80    /// NOTE: for best optimization of the iterator use `for_each` rather than a
81    /// for loop
82    // TODO: using the circle directly would be tighter (how efficient would it be
83    // to query the cells intersecting a circle?) (note: if doing this rename
84    // the function)
85    pub fn in_circle_aabr(
86        &self,
87        center: Vec2<f32>,
88        radius: f32,
89    ) -> impl Iterator<Item = specs::Entity> + '_ {
90        let center = center.map(|e| e as i32);
91        let radius = radius.ceil() as i32;
92        // From conversion of center above
93        const CENTER_TRUNCATION_ERROR: i32 = 1;
94        let max_dist = radius + CENTER_TRUNCATION_ERROR;
95
96        let aabr = Aabr {
97            min: center - max_dist,
98            max: center + max_dist,
99        };
100
101        self.in_aabr(aabr)
102    }
103
104    pub fn clear(&mut self) {
105        self.grid.clear();
106        self.large_grid.clear();
107        self.largest_large_radius = self.radius_cutoff;
108    }
109}
veloren_common/util/spatial_grid.rs

veloren_common/util/
spatial_grid.rs
