Skip to content
gravittonPublic

About

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

Topics

Resources

Code of conduct

Contributing

Security policy

Stars

1 star

Watchers

0 watching

Forks

Repository files navigation

Gravitton spatial

Latest Stable Version Build Status Coverage Status Go Dev Reference Go Version Software License

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


The map over the cells of a spatial hash: the keys QueryBox returns for the scout's view of radius 6, the keys QuerySegment returns for the line to the goal, and the pairs of keys that touch
Every picture in this README is drawn from what the package returns for the call beside it.

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

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)
}

Fourteen boxes over the cells of a hash: the cells a camera box touches, shaded, the four boxes QueryBox returns, and the cells around a cursor, shaded, with the one box QueryPoint returns

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

The same boxes with a segment from a guard to a target: the cells it walks, shaded, and the three boxes QuerySegment yields, numbered in the order it yields them

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.

Credits

License

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

About

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

Topics

Resources

Code of conduct

Contributing

Security policy

Stars

1 star

Watchers

0 watching

Forks

Releases

Contributors

Languages