Spatial partitioning (spatial hash) for 2D top-down (XY coords)

[ember zinc]

This is my current spatial hash implementation used for top-down 2D games (where the z component of a Vec3 is discarded using Vec3::truncate).

What I'm specifically curious about is my addition of a separate variable (entity_positions) to map entities to cell positions. I haven't see this method in many spatial hash pseudocode implementations, but it has worked well for me in respect to improving removal performance.

Finally, I'm aware that the SpatialHash::query_in_range doesn't actually query entities within a "circular range". This is intentional behavior for my use case.

const DEFAULT_CELL_SIZE: f32 = 50.0;

pub struct SpatialHash {
    cells: HashMap<(i32, i32), HashSet<Entity>>,
    entity_positions: HashMap<Entity, (i32, i32)>,
    cell_size: f32,
}

impl Default for SpatialHash {
    fn default() -> Self {
        Self {
            cells: HashMap::new(),
            entity_positions: HashMap::new(),
            cell_size: DEFAULT_CELL_SIZE,
        }
    }
}

impl SpatialHash {
    fn hash(&self, point: Vec2) -> (i32, i32) {
        (
            (point.x / self.cell_size) as i32,
            (point.y / self.cell_size) as i32,
        )
    }

    pub fn insert(&mut self, entity: Entity, position: Vec2) {
        let hash = self.hash(position);
        self.cells.entry(hash).or_default().insert(entity);
        self.entity_positions.insert(entity, hash);
    }

    pub fn remove(&mut self, entity: Entity) {
        if let Some(hash) = self.entity_positions.remove(&entity) {
            if let Some(cell) = self.cells.get_mut(&hash) {
                cell.remove(&entity);
                if cell.is_empty() {
                    self.cells.remove(&hash);
                }
            }
        }
    }

    pub fn update(&mut self, entity: Entity, position: Vec2) {
        self.remove(entity);
        self.insert(entity, position);
    }

    pub fn query_in_range(&self, position: Vec2, range: f32) -> HashSet<Entity> {
        self.query_in_bounds(position - Vec2::splat(range), position + Vec2::splat(range))
    }

    pub fn query_in_bounds(&self, min: Vec2, max: Vec2) -> HashSet<Entity> {
        let mut result = HashSet::new();

        let (min_x, min_y) = self.hash(min);
        let (max_x, max_y) = self.hash(max);

        for x in min_x..=max_x {
            for y in min_y..=max_y {
                if let Some(cell) = self.cells.get(&(x, y)).filter(|cell| !cell.is_empty()) {
                    result.extend(cell.iter());
                }
            }
        }

        result
    }
}

Omitted SpatialHash::new for brevity (and Discord's character limit :D)

Also worth including is an example system that references and uses the spatial hash as a resource. This pattern which uses a custom SystemParam has developed organically:

#[derive(Resource, Default)]
struct InteractablesSpatialHash(SpatialHash);

#[bevy_trait_query::queryable]
pub trait Interactable {
    fn interact(&self);
}

#[derive(SystemParam)]
struct NearbyInteractables<'w, 's> {
    interactables: Query<'w, 's, (&'static Transform, One<&'static dyn Interactable>)>,
    spatial_hash: Res<'w, InteractablesSpatialHash>,
}

impl<'w, 's> NearbyInteractables<'w, 's> {
    fn search(&self, position: Vec2, range: f32) -> Vec<(Entity, Vec2, &dyn Interactable)> {
        let mut interactables = Vec::new();

        let query = self.spatial_hash.0.query_in_range(position, range);

        for entity in query.iter() {
            if let Ok((transform, interactable)) = self.interactables.get(*entity) {
                interactables.push((*entity, transform.translation.truncate(), interactable));
            }
        }

        interactables
    }
}

[fossil bobcat]

Interesting take. For the things I've been using such hash maps for (mostly physics), the cost of rebuilding the entire thing each frame (O(n)) is negligible compared to what I do with map afterwards.

[ember zinc]

Since I sent this message, I've actually ended up refactoring the system a bit. My revised approach has one central spatial hash resource, used for all entities that require spatial partitioning irrespective of their components.

Essentially, I've gone from this:

To this:

This results in a deduplication of efforts for maintaining the hashes.

With a marker component to identify entities that should be spatially partitioned (and tracked), say SpatialHashMarker, I've now got a few discrete systems that ensure the spatial hash's integrity (without needing to establish new systems if I setup a new "kind" of entity that I want to query spatially):

/// Update the positions of entities that are being tracked "spatially" if they moved
fn spatial_entity_moved(query: Query<(Entity, &Transform), (With<SpatialHashMarker>, Changed<Transform>), mut spatial_hash: ResMut<SpatialHash>)

It's also as simple as checking for added/removed of the marker component as a way of inserting/removing entities from the spatial hash.

I might want to eventually take a look at some kind of labelling system within the spatial hash to only look at a subset of entities (i.e. if I'm querying nearby interactables, why do I need to be looking at enemy entities within the spatial hash's internal structure?).