spatial/grid

Hash Grid spatial partitioning data structure.

Uses Erlang maps (HAMT with branching factor 32) providing O(log₃₂ n) operations, which is effectively O(1) in practice. At 1 million cells, operations take only ~5 steps. Excellent for uniformly distributed objects like particles or crowds.

Types

Grid

opaque </>

Hash Grid for fast spatial queries with uniform distributions.

Uses Erlang maps (32-way HAMT) for O(log₃₂ n) insertion/removal, effectively O(1) in practice. n is the number of occupied cells.

pub opaque type Grid(a)

Values

bounds

</>

pub fn bounds(grid: Grid(a)) -> collider.Collider

Get the bounds of the grid.

cell_count

</>

pub fn cell_count(grid: Grid(a)) -> Int

Get the number of non-empty cells.

cell_size

</>

pub fn cell_size(grid: Grid(a)) -> Float

Get the cell size of the grid.

count

</>

pub fn count(grid: Grid(a)) -> Int

Count total items in the grid.

Time Complexity: O(m) where m is the number of occupied cells.

insert

</>

pub fn insert(
  grid: Grid(a),
  position: vec3.Vec3(Float),
  item: a,
) -> Grid(a)

Insert an item at a position into the grid.

Time Complexity: O(log₃₂ n) where n is the number of occupied cells, effectively O(1) in practice. Faster than octree for uniform distributions.

new

</>

pub fn new(
  cell_size cell_size: Float,
  bounds bounds: collider.Collider,
) -> Grid(a)

Create a new empty hash grid.

Parameters

cell_size: Size of each grid cell (should match typical object size)
bounds: The spatial region this grid covers

Example

let bounds = collider.box(
  min: vec3.Vec3(-100.0, -100.0, -100.0),
  max: vec3.Vec3(100.0, 100.0, 100.0),
)
let grid = grid.new(cell_size: 10.0, bounds: bounds)

query

</>

pub fn query(
  grid: Grid(a),
  query_bounds: collider.Collider,
) -> List(#(vec3.Vec3(Float), a))

Query all items within a collider region.

More efficient than octree for uniform distributions.

Time Complexity: O(c·log₃₂ m + k) where c is cells checked, m is occupied cells, and k is results. Effectively O(c + k) in practice.

query_all

</>

pub fn query_all(grid: Grid(a)) -> List(#(vec3.Vec3(Float), a))

Query all items in the grid (useful for iteration).

Time Complexity: O(n) where n is the total number of items.

query_radius

</>

pub fn query_radius(
  grid: Grid(a),
  center: vec3.Vec3(Float),
  radius: Float,
) -> List(#(vec3.Vec3(Float), a))

Query all items within a radius of a point.

Extremely fast for uniform distributions - only checks nearby cells.

Time Complexity: O(c·log₃₂ m + k) where c is cells checked, m is occupied cells, and k is results. Effectively O(c + k) in practice.

remove

</>

pub fn remove(
  grid: Grid(a),
  position: vec3.Vec3(Float),
  predicate: fn(a) -> Bool,
) -> Grid(a)

Remove an item from the grid.

Time Complexity: O(log₃₂ n) cell lookup + O(k) filtering where n is the number of occupied cells and k is items in that cell. Effectively O(k) in practice.