Struct SpatialHash 

pub struct SpatialHash { /* private fields */ }

Spatial hash for broad phase collision detection.

Divides 2D space into a uniform grid of cells. Entities are mapped to cells based on their AABBs. This enables O(1) insertion/removal and efficient querying of potential collision pairs.

Performance

• Insertion: O(k) where k = number of cells occupied by AABB
• Removal: O(k)
• Query pairs: O(n^2) where n = average entities per cell
• Total query: O(m * n^2) where m = number of occupied cells

Cell Size Selection

The cell size should be roughly equal to the average object size:

• Too small: Objects span many cells, increasing overhead
• Too large: Too many objects per cell, increasing pair checks

For games with mixed object sizes, use the size of the most common objects.

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);

// Insert entities
let player = Entity::new(0, 0);
let enemy = Entity::new(1, 0);

hash.insert(player, Rect::new(0.0, 0.0, 32.0, 32.0));
hash.insert(enemy, Rect::new(50.0, 0.0, 32.0, 32.0));

// Query potential collisions
let pairs = hash.query_pairs();
assert_eq!(pairs.len(), 1);  // Player and enemy are close

Implementations

impl SpatialHash

pub fn query_pairs(&mut self) -> Vec<(Entity, Entity)>

Queries for all potential collision pairs.

Returns a list of entity pairs that share at least one cell. These are candidates for narrow phase collision testing.

Returns

A vector of (Entity, Entity) pairs where the first entity has a lower index than the second (no duplicate pairs).

Performance

O(m * n^2) where m = number of occupied cells, n = average entities per cell.

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);

let e1 = Entity::new(0, 0);
let e2 = Entity::new(1, 0);

hash.insert(e1, Rect::new(0.0, 0.0, 32.0, 32.0));
hash.insert(e2, Rect::new(30.0, 0.0, 32.0, 32.0));

let pairs = hash.query_pairs();
assert_eq!(pairs.len(), 1);  // Overlapping cells

pub fn query_point(&self, point: Vec2) -> Vec<Entity>

Queries for entities near a specific point.

Returns all entities whose AABBs occupy the same cell as the point.

Arguments

• point - The query point

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::{Rect, Vec2};

let mut hash = SpatialHash::new(64.0);
let entity = Entity::new(0, 0);

hash.insert(entity, Rect::new(0.0, 0.0, 32.0, 32.0));

let nearby = hash.query_point(Vec2::new(10.0, 10.0));
assert_eq!(nearby.len(), 1);

pub fn query_aabb(&self, aabb: Rect) -> Vec<Entity>

Queries for entities overlapping an AABB.

Returns all entities whose AABBs occupy any cell overlapped by the query AABB.

Arguments

• aabb - The query AABB

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);
let entity = Entity::new(0, 0);

hash.insert(entity, Rect::new(0.0, 0.0, 32.0, 32.0));

let nearby = hash.query_aabb(Rect::new(-10.0, -10.0, 50.0, 50.0));
assert_eq!(nearby.len(), 1);

pub fn query_circle(&self, center: Vec2, radius: f32) -> Vec<Entity>

Queries for entities overlapping a circle.

Returns all entities in cells that overlap the circle’s bounding square. This is a conservative estimate - narrow phase should verify actual overlap.

Arguments

• center - Circle center position
• radius - Circle radius

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::{Rect, Vec2};

let mut hash = SpatialHash::new(64.0);
let entity = Entity::new(0, 0);

hash.insert(entity, Rect::new(0.0, 0.0, 32.0, 32.0));

let nearby = hash.query_circle(Vec2::new(16.0, 16.0), 20.0);
assert_eq!(nearby.len(), 1);

pub fn cell_size(&self) -> f32

Returns the cell size.

pub fn entity_count(&self) -> usize

Returns the number of entities in the hash.

pub fn cell_count(&self) -> usize

Returns the number of occupied cells.

pub fn is_empty(&self) -> bool

Returns whether the hash is empty.

pub fn contains(&self, entity: Entity) -> bool

Returns whether an entity is in the hash.

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);
let entity = Entity::new(0, 0);

assert!(!hash.contains(entity));
hash.insert(entity, Rect::new(0.0, 0.0, 32.0, 32.0));
assert!(hash.contains(entity));

pub fn get_aabb(&self, entity: Entity) -> Option<Rect>

Returns the AABB for an entity, if present.

pub fn stats(&self) -> &SpatialHashStats

Returns a reference to the current statistics.

impl SpatialHash

pub fn new(cell_size: f32) -> Self

Creates a new spatial hash with the specified cell size.

Arguments

• cell_size - Size of each grid cell in world units (e.g., pixels)

Panics

Panics if cell_size is not positive and finite.

Examples

use goud_engine::ecs::broad_phase::SpatialHash;

// 64-pixel cells (good for medium-sized objects)
let hash = SpatialHash::new(64.0);

// 128-pixel cells (larger objects)
let hash = SpatialHash::new(128.0);

pub fn with_capacity(cell_size: f32, capacity: usize) -> Self

Creates a spatial hash with the specified cell size and initial capacity.

Pre-allocates memory for the specified number of entities, reducing allocations during insertion.

Arguments

• cell_size - Size of each grid cell
• capacity - Expected number of entities

Examples

use goud_engine::ecs::broad_phase::SpatialHash;

// Pre-allocate for 1000 entities
let hash = SpatialHash::with_capacity(64.0, 1000);

pub fn insert(&mut self, entity: Entity, aabb: Rect)

Inserts an entity with its AABB into the spatial hash.

The entity is added to all cells that its AABB overlaps. If the entity was already in the hash, it is first removed before re-insertion.

Arguments

• entity - The entity to insert
• aabb - The entity’s axis-aligned bounding box

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);
let entity = Entity::new(0, 0);
let aabb = Rect::new(0.0, 0.0, 32.0, 32.0);

hash.insert(entity, aabb);
assert!(hash.contains(entity));

pub fn remove(&mut self, entity: Entity) -> bool

Removes an entity from the spatial hash.

Arguments

• entity - The entity to remove

Returns

true if the entity was present and removed, false otherwise.

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);
let entity = Entity::new(0, 0);

hash.insert(entity, Rect::new(0.0, 0.0, 32.0, 32.0));
assert!(hash.remove(entity));
assert!(!hash.contains(entity));

pub fn update(&mut self, entity: Entity, new_aabb: Rect) -> bool

Updates an entity’s AABB in the spatial hash.

This is more efficient than remove + insert when the entity hasn’t moved much, as it can avoid cell changes.

Arguments

• entity - The entity to update
• new_aabb - The entity’s new AABB

Returns

true if the entity was present and updated, false otherwise.

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);
let entity = Entity::new(0, 0);

hash.insert(entity, Rect::new(0.0, 0.0, 32.0, 32.0));
hash.update(entity, Rect::new(10.0, 10.0, 32.0, 32.0));

pub fn clear(&mut self)

Clears all entities from the spatial hash.

Examples

use goud_engine::ecs::broad_phase::SpatialHash;
use goud_engine::ecs::Entity;
use goud_engine::core::math::Rect;

let mut hash = SpatialHash::new(64.0);
hash.insert(Entity::new(0, 0), Rect::new(0.0, 0.0, 32.0, 32.0));

hash.clear();
assert_eq!(hash.entity_count(), 0);

Trait Implementations

impl Clone for SpatialHash

fn clone(&self) -> SpatialHash

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SpatialHash

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for SpatialHash

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.