sgl_core/collision/
collider_set.rs

1//! The world's colliders plus a uniform broadphase grid over them.
2
3use std::collections::HashMap;
4
5use super::aabb::Aabb;
6use crate::math::IVec2;
7
8/// How a collider behaves during a sweep.
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub struct ColliderFlags {
11    /// Participates in solid collision response. A collider that is not solid
12    /// is skipped entirely by the sweep.
13    pub solid: bool,
14    /// One-way platform: passable except when landing on the face that points
15    /// along the world's up axis.
16    pub one_way: bool,
17    /// Sensor: never blocks, whatever `solid` says. Callers detect sensors by
18    /// querying the set themselves.
19    pub sensor: bool,
20}
21
22impl ColliderFlags {
23    /// A plain solid collider.
24    pub const SOLID: Self = Self {
25        solid: true,
26        one_way: false,
27        sensor: false,
28    };
29
30    /// A one-way platform: solid only against a landing from above.
31    pub const ONE_WAY: Self = Self {
32        solid: true,
33        one_way: true,
34        sensor: false,
35    };
36
37    /// A sensor: reported by [`ColliderSet::query`] but never blocking.
38    pub const SENSOR: Self = Self {
39        solid: false,
40        one_way: false,
41        sensor: true,
42    };
43}
44
45/// One collider in the world: its box and its flags.
46#[derive(Debug, Clone, Copy, PartialEq)]
47pub struct Collider {
48    /// World-space box.
49    pub aabb: Aabb,
50    /// Behavior during a sweep.
51    pub flags: ColliderFlags,
52}
53
54/// The world's colliders, bucketed into a uniform grid for broadphase.
55///
56/// The grid's cell size is the caller's choice: it is a spatial hash bucket,
57/// not a tile size. Cells near the typical collider size keep queries small;
58/// much larger cells simply return more candidates, and much smaller cells make
59/// each collider occupy more buckets. Either way the result is only a candidate
60/// list — [`query`](Self::query) reports colliders whose *cells* meet the
61/// region, not colliders that actually overlap it.
62#[derive(Debug)]
63pub struct ColliderSet {
64    cell_size: f32,
65    colliders: Vec<Collider>,
66    /// Grid cell -> indices of the colliders overlapping that cell.
67    grid: HashMap<IVec2, Vec<usize>>,
68}
69
70impl ColliderSet {
71    /// An empty set bucketed at `cell_size` world units per grid cell.
72    ///
73    /// # Panics
74    /// If `cell_size` is not positive and finite — an authoring error, not a
75    /// runtime condition. A zero, negative, or non-finite cell size cannot
76    /// address a grid at all.
77    #[must_use]
78    pub fn new(cell_size: f32) -> Self {
79        assert!(
80            cell_size > 0.0 && cell_size.is_finite(),
81            "ColliderSet: cell size must be positive and finite, got {cell_size}"
82        );
83        Self {
84            cell_size,
85            colliders: Vec::new(),
86            grid: HashMap::new(),
87        }
88    }
89
90    /// World units per broadphase grid cell.
91    #[must_use]
92    pub fn cell_size(&self) -> f32 {
93        self.cell_size
94    }
95
96    /// Inserts a world-space collider, bucketing it into every grid cell its
97    /// box overlaps, and returns its index.
98    pub fn insert(&mut self, aabb: Aabb, flags: ColliderFlags) -> usize {
99        let index = self.colliders.len();
100        self.colliders.push(Collider { aabb, flags });
101        for cell in cells_for(&aabb, self.cell_size) {
102            self.grid.entry(cell).or_default().push(index);
103        }
104        index
105    }
106
107    /// Borrows a collider by index, as returned by [`query`](Self::query).
108    #[must_use]
109    pub fn get(&self, index: usize) -> Option<&Collider> {
110        self.colliders.get(index)
111    }
112
113    /// Broadphase candidates: the indices of colliders bucketed into any grid
114    /// cell that `region` touches.
115    ///
116    /// Each index appears exactly once, in ascending order, so a caller that
117    /// breaks ties by "first candidate wins" behaves identically run to run.
118    #[must_use]
119    pub fn query(&self, region: &Aabb) -> Vec<usize> {
120        let mut found = Vec::new();
121        for cell in cells_for(region, self.cell_size) {
122            if let Some(bucket) = self.grid.get(&cell) {
123                found.extend_from_slice(bucket);
124            }
125        }
126        found.sort_unstable();
127        found.dedup();
128        found
129    }
130
131    /// Number of colliders in the set.
132    #[must_use]
133    pub fn len(&self) -> usize {
134        self.colliders.len()
135    }
136
137    /// Whether the set holds no colliders.
138    #[must_use]
139    pub fn is_empty(&self) -> bool {
140        self.colliders.is_empty()
141    }
142
143    /// Removes every collider and its grid buckets, keeping the cell size.
144    /// Indices start again from zero.
145    pub fn clear(&mut self) {
146        self.colliders.clear();
147        self.grid.clear();
148    }
149
150    /// Iterates the colliders in insertion order, so position `i` is the
151    /// collider at index `i`.
152    pub fn iter(&self) -> std::slice::Iter<'_, Collider> {
153        self.colliders.iter()
154    }
155}
156
157impl<'a> IntoIterator for &'a ColliderSet {
158    type Item = &'a Collider;
159    type IntoIter = std::slice::Iter<'a, Collider>;
160
161    fn into_iter(self) -> Self::IntoIter {
162        self.iter()
163    }
164}
165
166/// The inclusive range of grid cells a box overlaps.
167fn cells_for(aabb: &Aabb, cell_size: f32) -> impl Iterator<Item = IVec2> {
168    let min = aabb.min();
169    let max = aabb.max();
170    // A non-finite box addresses no cells. Float-to-int casts saturate, so an
171    // infinite bound would otherwise walk the entire `i32` range.
172    let (x0, x1, y0, y1) = if min.is_finite() && max.is_finite() {
173        (
174            cell_of(min.x, cell_size),
175            cell_of(max.x, cell_size),
176            cell_of(min.y, cell_size),
177            cell_of(max.y, cell_size),
178        )
179    } else {
180        (0, -1, 0, -1)
181    };
182    (y0..=y1).flat_map(move |y| (x0..=x1).map(move |x| IVec2::new(x, y)))
183}
184
185/// The grid coordinate a world coordinate falls in.
186// Coordinates beyond the `i32` grid saturate, which is the intended clamp.
187#[allow(clippy::cast_possible_truncation)]
188fn cell_of(value: f32, cell_size: f32) -> i32 {
189    (value / cell_size).floor() as i32
190}
191
192#[cfg(test)]
193mod tests {
194    use super::*;
195    use crate::math::Vec2;
196    use wasm_bindgen_test::wasm_bindgen_test;
197
198    /// #249: the getters report what was configured and inserted.
199    #[wasm_bindgen_test(unsupported = test)]
200    fn getters_report_the_configured_size_and_count() {
201        let mut set = ColliderSet::new(2.5);
202        assert_eq!(set.cell_size().to_bits(), 2.5f32.to_bits());
203        assert!(set.is_empty());
204        assert_eq!(set.len(), 0);
205        set.insert(aabb(0.0, 0.0, 1.0, 1.0), ColliderFlags::SOLID);
206        set.insert(aabb(9.0, 9.0, 1.0, 1.0), ColliderFlags::SENSOR);
207        assert!(!set.is_empty());
208        assert_eq!(set.len(), 2);
209        assert_eq!(set.iter().count(), 2);
210        assert_eq!((&set).into_iter().count(), 2);
211    }
212
213    /// #249: colliders at negative, fractional coordinates with a cell size
214    /// that does not divide them are found by a query in their cells, and a
215    /// non-finite region finds nothing even with a collider at the origin.
216    #[wasm_bindgen_test(unsupported = test)]
217    fn negative_fractional_boxes_are_found_and_non_finite_regions_find_nothing() {
218        let mut set = ColliderSet::new(1.5);
219        let origin = set.insert(aabb(0.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
220        let low = set.insert(aabb(-2.2, -3.7, 0.4, 0.4), ColliderFlags::SOLID);
221        assert_eq!(set.query(&aabb(-2.5, -4.0, 0.2, 0.2)), vec![low]);
222        assert_eq!(set.query(&aabb(-5.0, -5.0, 0.2, 0.2)), Vec::<usize>::new());
223        assert_eq!(set.query(&aabb(0.2, 0.2, 0.1, 0.1)), vec![origin]);
224        assert!(set.query(&aabb(f32::NAN, 0.0, 1.0, 1.0)).is_empty());
225        assert!(set.query(&aabb(0.0, 0.0, f32::INFINITY, 1.0)).is_empty());
226    }
227
228    fn aabb(cx: f32, cy: f32, hx: f32, hy: f32) -> Aabb {
229        Aabb::new(Vec2::new(cx, cy), Vec2::new(hx, hy))
230    }
231
232    /// The configured cell size must drive bucketing. With cells far larger
233    /// than the colliders, two boxes 50 units apart share a cell and both come
234    /// back as candidates; a hard-coded cell size would return only the near
235    /// one.
236    #[wasm_bindgen_test(unsupported = test)]
237    fn configured_cell_size_decides_bucketing() {
238        let mut coarse = ColliderSet::new(100.0);
239        coarse.insert(aabb(0.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
240        coarse.insert(aabb(50.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
241        assert_eq!(coarse.query(&aabb(0.0, 0.0, 1.0, 1.0)), vec![0, 1]);
242
243        let mut fine = ColliderSet::new(1.0);
244        fine.insert(aabb(0.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
245        fine.insert(aabb(50.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
246        assert_eq!(fine.query(&aabb(0.0, 0.0, 1.0, 1.0)), vec![0]);
247    }
248
249    /// A collider wider than one cell must be reachable from every cell it
250    /// covers and still appear exactly once, in ascending index order. At a
251    /// 0.25 cell size the wide floor occupies dozens of buckets, so a missing
252    /// dedupe repeats it and center-only bucketing loses it.
253    #[wasm_bindgen_test(unsupported = test)]
254    fn multi_cell_colliders_are_returned_once_in_index_order() {
255        let mut set = ColliderSet::new(0.25);
256        let floor = set.insert(aabb(0.0, 0.0, 1.0, 0.25), ColliderFlags::SOLID);
257        let far = set.insert(aabb(10.0, 10.0, 0.5, 0.5), ColliderFlags::SOLID);
258        let box_above = set.insert(aabb(0.5, 0.5, 0.3, 0.3), ColliderFlags::SOLID);
259
260        assert_eq!(set.query(&aabb(0.0, 0.0, 1.0, 1.0)), vec![floor, box_above]);
261        // Reachable from a region touching only its right end.
262        assert_eq!(set.query(&aabb(0.9, -0.2, 0.05, 0.02)), vec![floor]);
263        assert_eq!(set.query(&aabb(10.0, 10.0, 0.1, 0.1)), vec![far]);
264    }
265
266    /// Clearing must drop the grid too. Colliders alone would leave buckets
267    /// holding indices that no longer exist, and the next query would hand a
268    /// caller indices past the end of the set.
269    #[wasm_bindgen_test(unsupported = test)]
270    fn clear_drops_the_grid_with_the_colliders() {
271        let mut set = ColliderSet::new(1.0);
272        set.insert(aabb(0.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
273        set.insert(aabb(1.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
274        set.clear();
275
276        assert!(set.is_empty());
277        assert_eq!(set.len(), 0);
278        assert!(set.query(&aabb(0.0, 0.0, 2.0, 2.0)).is_empty());
279
280        let reused = set.insert(aabb(0.0, 0.0, 0.5, 0.5), ColliderFlags::SENSOR);
281        assert_eq!(reused, 0, "indices restart after a clear");
282        assert_eq!(set.query(&aabb(0.0, 0.0, 0.5, 0.5)), vec![0]);
283        assert_eq!(
284            set.iter().next().map(|c| c.flags),
285            Some(ColliderFlags::SENSOR)
286        );
287    }
288
289    /// A non-finite box must address no cells. Saturating casts would otherwise
290    /// turn an infinite bound into a walk over four billion grid cells.
291    #[wasm_bindgen_test(unsupported = test)]
292    fn non_finite_regions_address_no_cells() {
293        let mut set = ColliderSet::new(1.0);
294        set.insert(aabb(0.0, 0.0, 0.5, 0.5), ColliderFlags::SOLID);
295        assert!(
296            set.query(&aabb(0.0, 0.0, f32::INFINITY, 1.0)).is_empty(),
297            "an infinite region must not be walked cell by cell"
298        );
299        assert!(set.query(&aabb(f32::NAN, 0.0, 1.0, 1.0)).is_empty());
300    }
301}
sgl_core/collision/collider_set.rs

sgl_core/collision/
collider_set.rs
