big_space/hash/
mod.rs

1//! Spatial hashing acceleration structure. See [`CellHashingPlugin`].
2
3use core::marker::PhantomData;
4
5use crate::prelude::*;
6use bevy_app::prelude::*;
7use bevy_ecs::entity::EntityHashSet;
8use bevy_ecs::{prelude::*, query::QueryFilter};
9
10pub mod component;
11pub mod map;
12pub mod partition;
13
14/// Add spatial hashing acceleration to `big_space`, accessible through the [`CellLookup`] resource,
15/// and [`CellId`] components.
16///
17/// You can optionally add a [`SpatialHashFilter`] to this plugin, to only run the spatial hashing on
18/// entities that match the query filter. This is useful if you only want to, say, compute hashes
19/// and insert in the [`CellLookup`] for `Player` entities.
20///
21/// If you are adding multiple copies of this plugin with different filters, there are optimizations
22/// in place to avoid duplicating work. However, you should still take care to avoid excessively
23/// overlapping filters.
24pub struct CellHashingPlugin<F = ()>(PhantomData<F>)
25where
26    F: SpatialHashFilter;
27
28impl<F> CellHashingPlugin<F>
29where
30    F: SpatialHashFilter,
31{
32    /// Create a new instance of [`CellHashingPlugin`].
33    pub fn new() -> Self {
34        Self(PhantomData)
35    }
36}
37
38impl<F> Plugin for CellHashingPlugin<F>
39where
40    F: SpatialHashFilter,
41{
42    fn build(&self, app: &mut App) {
43        app.init_resource::<CellLookup<F>>()
44            .init_resource::<ChangedCells<F>>()
45            .register_type::<CellId>()
46            .add_systems(
47                PostUpdate,
48                (
49                    CellId::update::<F>
50                        .in_set(SpatialHashSystems::UpdateCellHashes)
51                        .after(BigSpaceSystems::RecenterLargeTransforms),
52                    CellLookup::<F>::update
53                        .in_set(SpatialHashSystems::UpdateCellLookup)
54                        .after(SpatialHashSystems::UpdateCellHashes),
55                ),
56            );
57    }
58}
59
60impl Default for CellHashingPlugin<()> {
61    fn default() -> Self {
62        Self(PhantomData)
63    }
64}
65
66/// System sets for [`CellHashingPlugin`].
67#[derive(SystemSet, Hash, Debug, PartialEq, Eq, Clone)]
68pub enum SpatialHashSystems {
69    /// [`CellId`] and [`CellHash`] updated.
70    UpdateCellHashes,
71    /// [`CellLookup`] updated.
72    UpdateCellLookup,
73    /// [`PartitionLookup`] updated.
74    UpdatePartitionLookup,
75}
76
77/// Used as a [`QueryFilter`] to include or exclude certain types of entities from spatial
78/// hashing.The trait is automatically implemented for all compatible types, like [`With`] or
79/// [`Without`].
80///
81/// By default, this is `()`, but it can be overridden when adding the [`CellHashingPlugin`] and
82/// [`CellLookup`]. For example, if you use `With<Players>` as your filter, only `Player`s would be
83/// considered when building spatial hash maps. This is useful when you only care about querying
84/// certain entities and want to avoid the plugin doing bookkeeping work for entities you don't
85/// care about.
86pub trait SpatialHashFilter: QueryFilter + Send + Sync + 'static {}
87impl<T: QueryFilter + Send + Sync + 'static> SpatialHashFilter for T {}
88
89/// Resource to manually track entities that have moved between cells, for optimization purposes.
90///
91/// Updated every frame in [`CellId::update`] in [`SpatialHashSystems::UpdateCellHashes`].
92///
93/// We use a manual collection instead of a `Changed` query because a query that uses `Changed`
94/// still has to iterate over every single entity. By making a shortlist of changed entities
95/// ourselves, we can make this 1000x faster.
96///
97/// Note that this is optimized for *sparse* updates, this may perform worse if you are updating
98/// every entity. The observation here is that usually entities are not moving between grid cells,
99/// and thus their spatial hash is not changing. On top of that, many entities are completely
100/// static.
101///
102/// It may be possible to remove this if bevy gets archetype change detection, or observers that can
103/// react to a component being mutated. For now, this performs well enough.
104#[derive(Resource)]
105pub struct ChangedCells<F: SpatialHashFilter> {
106    updated: EntityHashSet,
107    spooky: PhantomData<F>,
108}
109
110impl<F: SpatialHashFilter> Default for ChangedCells<F> {
111    fn default() -> Self {
112        Self {
113            updated: Default::default(),
114            spooky: PhantomData,
115        }
116    }
117}
118
119impl<F: SpatialHashFilter> ChangedCells<F> {
120    /// Iterate over all entities that have moved between cells.
121    pub fn iter(&self) -> impl Iterator<Item = &Entity> {
122        self.updated.iter()
123    }
124}
125
126// TODO:
127//
128// - When an entity is re-parented, is is removed/updated in the spatial map?
129// - Entities are hashed with their parent - what happens if an entity is moved to the root? Is the
130//   hash ever recomputed? Is it removed? Is the spatial map updated?
131#[cfg(test)]
132mod tests {
133    use crate::plugin::BigSpaceMinimalPlugins;
134    use crate::{hash::map::SpatialEntryToEntities, prelude::*};
135    use bevy_ecs::entity::EntityHashSet;
136    use bevy_platform::sync::OnceLock;
137
138    #[test]
139    fn entity_despawn() {
140        use bevy::prelude::*;
141
142        static ENTITY: OnceLock<Entity> = OnceLock::new();
143
144        let setup = |mut commands: Commands| {
145            commands.spawn_big_space_default(|root| {
146                let entity = root.spawn_spatial(CellCoord::ZERO).id();
147                ENTITY.set(entity).ok();
148            });
149        };
150
151        let mut app = App::new();
152        app.add_plugins(CellHashingPlugin::default())
153            .add_systems(Update, setup)
154            .update();
155
156        let hash = *app
157            .world()
158            .entity(*ENTITY.get().unwrap())
159            .get::<CellId>()
160            .unwrap();
161
162        assert!(app.world().resource::<CellLookup>().get(&hash).is_some());
163
164        app.world_mut().despawn(*ENTITY.get().unwrap());
165
166        app.update();
167
168        assert!(app.world().resource::<CellLookup>().get(&hash).is_none());
169    }
170
171    #[test]
172    fn get_hash() {
173        use bevy::prelude::*;
174
175        #[derive(Resource, Clone)]
176        struct ParentSet {
177            a: Entity,
178            b: Entity,
179            c: Entity,
180        }
181
182        #[derive(Resource, Clone)]
183        struct ChildSet {
184            x: Entity,
185            y: Entity,
186            z: Entity,
187        }
188
189        let setup = |mut commands: Commands| {
190            commands.spawn_big_space_default(|root| {
191                let a = root.spawn_spatial(CellCoord::new(0, 1, 2)).id();
192                let b = root.spawn_spatial(CellCoord::new(0, 1, 2)).id();
193                let c = root.spawn_spatial(CellCoord::new(5, 5, 5)).id();
194
195                root.commands().insert_resource(ParentSet { a, b, c });
196
197                root.with_grid_default(|grid| {
198                    let x = grid.spawn_spatial(CellCoord::new(0, 1, 2)).id();
199                    let y = grid.spawn_spatial(CellCoord::new(0, 1, 2)).id();
200                    let z = grid.spawn_spatial(CellCoord::new(5, 5, 5)).id();
201                    grid.commands().insert_resource(ChildSet { x, y, z });
202                });
203            });
204        };
205
206        let mut app = App::new();
207        app.add_plugins(CellHashingPlugin::default())
208            .add_systems(Update, setup);
209
210        app.update();
211
212        let mut spatial_hashes = app.world_mut().query::<&CellId>();
213
214        let parent = app.world().resource::<ParentSet>().clone();
215        let child = app.world().resource::<ChildSet>().clone();
216
217        assert_eq!(
218            spatial_hashes.get(app.world(), parent.a).unwrap(),
219            spatial_hashes.get(app.world(), parent.b).unwrap(),
220            "Same parent, same cell"
221        );
222
223        assert_ne!(
224            spatial_hashes.get(app.world(), parent.a).unwrap(),
225            spatial_hashes.get(app.world(), parent.c).unwrap(),
226            "Same parent, different cell"
227        );
228
229        assert_eq!(
230            spatial_hashes.get(app.world(), child.x).unwrap(),
231            spatial_hashes.get(app.world(), child.y).unwrap(),
232            "Same parent, same cell"
233        );
234
235        assert_ne!(
236            spatial_hashes.get(app.world(), child.x).unwrap(),
237            spatial_hashes.get(app.world(), child.z).unwrap(),
238            "Same parent, different cell"
239        );
240
241        assert_ne!(
242            spatial_hashes.get(app.world(), parent.a).unwrap(),
243            spatial_hashes.get(app.world(), child.x).unwrap(),
244            "Same cell, different parent"
245        );
246
247        let entities = &app
248            .world()
249            .resource::<CellLookup>()
250            .get(spatial_hashes.get(app.world(), parent.a).unwrap())
251            .unwrap()
252            .entities;
253
254        assert!(entities.contains(&parent.a));
255        assert!(entities.contains(&parent.b));
256        assert!(!entities.contains(&parent.c));
257        assert!(!entities.contains(&child.x));
258        assert!(!entities.contains(&child.y));
259        assert!(!entities.contains(&child.z));
260    }
261
262    #[test]
263    fn neighbors() {
264        use bevy::prelude::*;
265
266        #[derive(Resource, Clone)]
267        struct Entities {
268            a: Entity,
269            b: Entity,
270            c: Entity,
271        }
272
273        let setup = |mut commands: Commands| {
274            commands.spawn_big_space_default(|root| {
275                let a = root.spawn_spatial(CellCoord::new(0, 0, 0)).id();
276                let b = root.spawn_spatial(CellCoord::new(1, 1, 1)).id();
277                let c = root.spawn_spatial(CellCoord::new(2, 2, 2)).id();
278
279                root.commands().insert_resource(Entities { a, b, c });
280            });
281        };
282
283        let mut app = App::new();
284        app.add_plugins(CellHashingPlugin::default())
285            .add_systems(Startup, setup);
286
287        app.update();
288
289        let entities = app.world().resource::<Entities>().clone();
290        let parent = app
291            .world_mut()
292            .query::<&ChildOf>()
293            .get(app.world(), entities.a)
294            .unwrap();
295
296        let map = app.world().resource::<CellLookup>();
297        let entry = map.get(&CellId::new(parent, &CellCoord::ZERO)).unwrap();
298        let neighbors: EntityHashSet = map.nearby(entry).entities().collect();
299
300        assert!(neighbors.contains(&entities.a));
301        assert!(neighbors.contains(&entities.b));
302        assert!(!neighbors.contains(&entities.c));
303
304        let flooded: EntityHashSet = map
305            .flood(&CellId::new(parent, &CellCoord::ZERO), None)
306            .entities()
307            .collect();
308
309        assert!(flooded.contains(&entities.a));
310        assert!(flooded.contains(&entities.b));
311        assert!(flooded.contains(&entities.c));
312    }
313
314    #[test]
315    fn query_filters() {
316        use bevy::prelude::*;
317
318        #[derive(Component)]
319        struct Player;
320
321        static ROOT: OnceLock<Entity> = OnceLock::new();
322
323        let setup = |mut commands: Commands| {
324            commands.spawn_big_space_default(|root| {
325                root.spawn_spatial((CellCoord::ZERO, Player));
326                root.spawn_spatial(CellCoord::ZERO);
327                root.spawn_spatial(CellCoord::ZERO);
328                ROOT.set(root.id()).ok();
329            });
330        };
331
332        let mut app = App::new();
333        app.add_plugins((
334            CellHashingPlugin::default(),
335            CellHashingPlugin::<With<Player>>::new(),
336            CellHashingPlugin::<Without<Player>>::new(),
337        ))
338        .add_systems(Startup, setup)
339        .update();
340
341        let zero_hash = CellId::from_parent(*ROOT.get().unwrap(), &CellCoord::ZERO);
342
343        let map = app.world().resource::<CellLookup>();
344        assert_eq!(
345            map.get(&zero_hash).unwrap().entities.iter().count(),
346            3,
347            "There are a total of 3 spatial entities"
348        );
349
350        let map = app.world().resource::<CellLookup<With<Player>>>();
351        assert_eq!(
352            map.get(&zero_hash).unwrap().entities.iter().count(),
353            1,
354            "There is only one entity with the Player component"
355        );
356
357        let map = app.world().resource::<CellLookup<Without<Player>>>();
358        assert_eq!(
359            map.get(&zero_hash).unwrap().entities.iter().count(),
360            2,
361            "There are two entities without the player component"
362        );
363    }
364
365    /// Verify that [`CellLookup::newly_emptied`] and [`CellLookup::newly_occupied`] work correctly when
366    /// entities are spawned and move between cells.
367    #[test]
368    fn spatial_map_changed_cell_tracking() {
369        use bevy::prelude::*;
370
371        #[derive(Resource, Clone)]
372        struct Entities {
373            a: Entity,
374            b: Entity,
375            c: Entity,
376        }
377
378        let setup = |mut commands: Commands| {
379            commands.spawn_big_space_default(|root| {
380                let a = root.spawn_spatial(CellCoord::new(0, 0, 0)).id();
381                let b = root.spawn_spatial(CellCoord::new(1, 1, 1)).id();
382                let c = root.spawn_spatial(CellCoord::new(2, 2, 2)).id();
383
384                root.commands().insert_resource(Entities { a, b, c });
385            });
386        };
387
388        let mut app = App::new();
389        app.add_plugins((BigSpaceMinimalPlugins, CellHashingPlugin::default()))
390            .add_systems(Startup, setup);
391
392        app.update();
393
394        let entities = app.world().resource::<Entities>().clone();
395        let get_hash = |app: &mut App, entity| {
396            *app.world_mut()
397                .query::<&CellId>()
398                .get(app.world(), entity)
399                .unwrap()
400        };
401
402        let a_hash_t0 = get_hash(&mut app, entities.a);
403        let b_hash_t0 = get_hash(&mut app, entities.b);
404        let c_hash_t0 = get_hash(&mut app, entities.c);
405        let map = app.world().resource::<CellLookup>();
406        assert!(map.newly_occupied().contains(&a_hash_t0));
407        assert!(map.newly_occupied().contains(&b_hash_t0));
408        assert!(map.newly_occupied().contains(&c_hash_t0));
409
410        // Move entities and run an update
411        app.world_mut()
412            .entity_mut(entities.a)
413            .get_mut::<CellCoord>()
414            .unwrap()
415            .z += 1;
416        app.world_mut()
417            .entity_mut(entities.b)
418            .get_mut::<Transform>()
419            .unwrap()
420            .translation
421            .z += 1e10;
422        app.update();
423
424        let a_hash_t1 = get_hash(&mut app, entities.a);
425        let b_hash_t1 = get_hash(&mut app, entities.b);
426        let c_hash_t1 = get_hash(&mut app, entities.c);
427        let map = app.world().resource::<CellLookup>();
428
429        // Last grid
430        assert!(map.newly_emptied().contains(&a_hash_t0)); // Moved cell
431        assert!(map.newly_emptied().contains(&b_hash_t0)); // Moved cell via transform
432        assert!(!map.newly_emptied().contains(&c_hash_t0)); // Did not move
433
434        // Current grid
435        assert!(map.newly_occupied().contains(&a_hash_t1)); // Moved cell
436        assert!(map.newly_occupied().contains(&b_hash_t1)); // Moved cell via transform
437        assert!(!map.newly_occupied().contains(&c_hash_t1)); // Did not move
438    }
439}
big_space/hash/mod.rs

big_space/hash/
mod.rs
