Broad-phase spatial indexes: a spatial hash, its box, point and cast queries, and touching pairs

---

Features

• Generic – any comparable key, any geometry number type for coordinates.
• Broad phase only – an index answers which keys may touch a region; the shapes decide.
• Spatial hash – Hash, a uniform grid of cells over an unbounded plane.

The rules behind them are in the package documentation.

Installation

go get github.com/gravitton/spatial

import "github.com/gravitton/spatial"

Usage

An index holds a key and a box per entity, and answers which keys may touch a region. The shapes decide the rest.

index := spatial.NewHash[Entity](64.0) // cells about the size of a typical entity

index.Set(player, shapes[player].Bounds()) // insert, or move after the entity moved
index.Delete(bullet)

Collisions

var pairs []spatial.Pair[Entity] // reused every frame, so the broad phase allocates nothing

pairs = index.AppendPairs(pairs[:0])
for _, pair := range pairs {
	if contact, ok := geom.Collide(shapes[pair.A], shapes[pair.B]); ok {
		resolve(pair.A, pair.B, contact)
	}
}

Queries

var keys []Entity

keys = index.AppendQueryBox(keys[:0], camera)    // what to draw
keys = index.AppendQueryPoint(keys[:0], cursor)  // what is under the cursor

sight := geom.Seg(guard, target)
for key := range index.QuerySegment(sight) { // line of sight, stopping at the first wall
	if geom.Intersects(shapes[key], sight) {
		break
	}
}

Full reference: pkg.go.dev.

Credits

• Tomáš Novotný
• All Contributors

License

The MIT License (MIT). Please see License File for more information.