Every picture in this README is drawn from what the package returns for the call beside it.
- Generic – any comparable key, any
geometrynumber 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.
go get github.com/gravitton/spatialimport "github.com/gravitton/spatial"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)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)
}
}The figures below store these boxes, one key each in the order given, in cells of 32:
index := spatial.NewHash[int](32.0)
for key, box := range []geom.Box[float64]{
geom.BoxFromMin(geom.Pt(6.0, 8.0), geom.Sz(20.0, 16.0)),
geom.BoxFromMin(geom.Pt(38.0, 10.0), geom.Sz(24.0, 12.0)),
geom.BoxFromMin(geom.Pt(52.0, 30.0), geom.Sz(14.0, 30.0)),
geom.BoxFromMin(geom.Pt(76.0, 6.0), geom.Sz(28.0, 18.0)),
geom.BoxFromMin(geom.Pt(114.0, 14.0), geom.Sz(12.0, 12.0)),
geom.BoxFromMin(geom.Pt(140.0, 8.0), geom.Sz(30.0, 22.0)),
geom.BoxFromMin(geom.Pt(8.0, 44.0), geom.Sz(16.0, 24.0)),
geom.BoxFromMin(geom.Pt(30.0, 70.0), geom.Sz(26.0, 18.0)),
geom.BoxFromMin(geom.Pt(80.0, 48.0), geom.Sz(32.0, 24.0)),
geom.BoxFromMin(geom.Pt(98.0, 76.0), geom.Sz(12.0, 14.0)),
geom.BoxFromMin(geom.Pt(130.0, 50.0), geom.Sz(22.0, 28.0)),
geom.BoxFromMin(geom.Pt(162.0, 56.0), geom.Sz(22.0, 16.0)),
geom.BoxFromMin(geom.Pt(150.0, 76.0), geom.Sz(10.0, 12.0)),
geom.BoxFromMin(geom.Pt(176.0, 8.0), geom.Sz(10.0, 20.0)),
} {
index.Set(key, box)
}
camera := geom.BoxFromMin(geom.Pt(44.0, 18.0), geom.Sz(68.0, 50.0))
cursor := geom.Pt(92.0, 60.0)
var keys []int
keys = index.AppendQueryBox(keys[:0], camera) // what to draw
keys = index.AppendQueryPoint(keys[:0], cursor) // what is under the cursor
guard, target := geom.Pt(4.0, 90.0), geom.Pt(188.0, 40.0)
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.
The MIT License (MIT). Please see License File for more information.