spatial

README

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.

Documentation

Overview

Package spatial holds broad-phase spatial indexes for games. An index stores a key with a geom.Box and answers which keys may touch a region: the broad phase. It never stores a shape and never decides a collision; the caller narrows the candidates with the shapes of github.com/gravitton/geometry.

Types

Hash is a uniform spatial hash: an unbounded plane of square cells, for keys of about the same size. Pick a cell about the size of a typical key; a key much larger than a cell costs every query a test, and a cell much larger than the keys makes a query test many keys it does not touch. Pair is two keys whose boxes touch.

Rules

A key is a candidate exactly when geom says its box touches the region: Box.IntersectsBox for a box, Box.Contains for a point, Segment.IntersectsBox and Ray.IntersectsBox for a cast. The index never disagrees with the narrow phase on a touch, the tolerant one included.

Every query reports a key at most once, and every pair once in either order. Results come in no particular order.

A query never changes the index, so any number may run at once. A change must not run beside a query or another change, and a hash must not change while a query of it is ranged.

A box with a NaN coordinate is kept by Get and All and found by no query, as geom has NaN touch nothing. A box reaching an infinity is found wherever geom says it touches.

Panics

A degenerate value gets an answer; an argument with no meaning gets a panic:

• NewHash for a cell size that is not positive and finite: no cell can be drawn at it, and the panic value is an error that errors.Is matches to ErrInvalidCellSize.

Index

• Variables
• type Hash
  • func NewHash[K comparable, T geom.Number](cellSize T) *Hash[K, T]
  • func (h *Hash[K, T]) All() iter.Seq2[K, geom.Box[T]]
  • func (h *Hash[K, T]) AppendPairs(dst []Pair[K]) []Pair[K]
  • func (h *Hash[K, T]) AppendQueryBox(dst []K, box geom.Box[T]) []K
  • func (h *Hash[K, T]) AppendQueryPoint(dst []K, point geom.Point[T]) []K
  • func (h *Hash[K, T]) AppendQueryRay(dst []K, ray geom.Ray[T]) []K
  • func (h *Hash[K, T]) AppendQuerySegment(dst []K, segment geom.Segment[T]) []K
  • func (h *Hash[K, T]) CellSize() T
  • func (h *Hash[K, T]) Clear()
  • func (h *Hash[K, T]) Delete(key K)
  • func (h *Hash[K, T]) Get(key K) (geom.Box[T], bool)
  • func (h *Hash[K, T]) Len() int
  • func (h *Hash[K, T]) Pairs() []Pair[K]
  • func (h *Hash[K, T]) QueryBox(box geom.Box[T]) []K
  • func (h *Hash[K, T]) QueryPoint(point geom.Point[T]) []K
  • func (h *Hash[K, T]) QueryRay(ray geom.Ray[T]) iter.Seq[K]
  • func (h *Hash[K, T]) QuerySegment(segment geom.Segment[T]) iter.Seq[K]
  • func (h *Hash[K, T]) Set(key K, box geom.Box[T])
• type Pair

Examples

• Hash
• Hash.AppendPairs
• Hash.AppendQueryBox
• Hash.QuerySegment

Variables

var (
	// ErrInvalidCellSize is wrapped by the panic value of a cell size that is not positive and
	// finite.
	ErrInvalidCellSize = errors.New("spatial: invalid cell size")
)

Types

type Hash

type Hash[K comparable, T geom.Number] struct {
	// contains filtered or unexported fields
}

Hash is a uniform spatial hash: keys stored with their boxes in square cells of one size over an unbounded plane.

The zero value is not usable; NewHash builds one.

Example

type entity int

index := NewHash[entity](64.0)
index.Set(1, geom.Bx(geom.Pt(10.0, 10), geom.Pt(40.0, 40)))
index.Set(2, geom.Bx(geom.Pt(30.0, 30), geom.Pt(90.0, 50)))
index.Set(3, geom.Bx(geom.Pt(500.0, 500), geom.Pt(520.0, 520)))

fmt.Println(index.QueryPoint(geom.Pt(35.0, 35)))

for _, pair := range index.Pairs() {
	fmt.Println(min(pair.A, pair.B), max(pair.A, pair.B))
}

for key := range index.QuerySegment(geom.Seg(geom.Pt(400.0, 600), geom.Pt(600.0, 400))) {
	fmt.Println(key)
}

Output:
[1 2]
1 2
3

func NewHash

func NewHash[K comparable, T geom.Number](cellSize T) *Hash[K, T]

NewHash returns an empty hash with square cells of the given size. It panics for a cell size that is not positive and finite.

func (*Hash[K, T]) All

func (h *Hash[K, T]) All() iter.Seq2[K, geom.Box[T]]

All returns every key with its box, in no particular order. The hash must not change while it is ranged.

func (*Hash[K, T]) AppendPairs

func (h *Hash[K, T]) AppendPairs(dst []Pair[K]) []Pair[K]

AppendPairs appends the pairs of Pairs to dst and returns the extended slice.

Example

shapes := map[int]geom.Shape[float64]{
	1: geom.Circ(geom.Pt(10.0, 10), 5),
	2: geom.Circ(geom.Pt(17.0, 10), 5),
	3: geom.Bx(geom.Pt(21.0, 14), geom.Pt(30.0, 30)),
}

index := NewHash[int](16.0)
for key, shape := range shapes {
	index.Set(key, shape.Bounds())
}

var pairs []Pair[int]
pairs = index.AppendPairs(pairs[:0])
for _, pair := range pairs {
	if _, ok := geom.Collide(shapes[pair.A], shapes[pair.B]); ok {
		fmt.Println(min(pair.A, pair.B), max(pair.A, pair.B))
	}
}

Output:
1 2

func (*Hash[K, T]) AppendQueryBox

func (h *Hash[K, T]) AppendQueryBox(dst []K, box geom.Box[T]) []K

AppendQueryBox appends the keys of QueryBox to dst and returns the extended slice.

Example

index := NewHash[int](64.0)
index.Set(1, geom.Bx(geom.Pt(10.0, 10), geom.Pt(40.0, 40)))
index.Set(2, geom.Bx(geom.Pt(100.0, 20), geom.Pt(120.0, 60)))
index.Set(3, geom.Bx(geom.Pt(500.0, 500), geom.Pt(520.0, 520)))

camera := geom.Bx(geom.Pt(0.0, 0), geom.Pt(200.0, 150))
cursor := geom.Pt(110.0, 30)

var keys []int

keys = index.AppendQueryBox(keys[:0], camera)
slices.Sort(keys)
fmt.Println(keys)

keys = index.AppendQueryPoint(keys[:0], cursor)
fmt.Println(keys)

Output:
[1 2]
[2]

func (*Hash[K, T]) AppendQueryPoint

func (h *Hash[K, T]) AppendQueryPoint(dst []K, point geom.Point[T]) []K

AppendQueryPoint appends the keys of QueryPoint to dst and returns the extended slice.

func (*Hash[K, T]) AppendQueryRay

func (h *Hash[K, T]) AppendQueryRay(dst []K, ray geom.Ray[T]) []K

AppendQueryRay appends the keys of QueryRay to dst and returns the extended slice.

func (*Hash[K, T]) AppendQuerySegment

func (h *Hash[K, T]) AppendQuerySegment(dst []K, segment geom.Segment[T]) []K

AppendQuerySegment appends the keys of QuerySegment to dst and returns the extended slice.

func (*Hash[K, T]) CellSize

func (h *Hash[K, T]) CellSize() T

CellSize returns the side of a cell.

func (*Hash[K, T]) Clear

func (h *Hash[K, T]) Clear()

Clear removes every key.

func (*Hash[K, T]) Delete

func (h *Hash[K, T]) Delete(key K)

Delete removes the key; a key not stored is ignored.

func (*Hash[K, T]) Get

func (h *Hash[K, T]) Get(key K) (geom.Box[T], bool)

Get returns the box stored with the key, and false where the key is not stored.

func (*Hash[K, T]) Len

func (h *Hash[K, T]) Len() int

Len returns the number of keys stored.

func (*Hash[K, T]) Pairs

func (h *Hash[K, T]) Pairs() []Pair[K]

Pairs returns every pair of keys whose boxes touch, each pair once in no particular order.

func (*Hash[K, T]) QueryBox

func (h *Hash[K, T]) QueryBox(box geom.Box[T]) []K

QueryBox returns the keys whose box touches the given one, in no particular order.

func (*Hash[K, T]) QueryPoint

func (h *Hash[K, T]) QueryPoint(point geom.Point[T]) []K

QueryPoint returns the keys whose box contains the point, in no particular order.

func (*Hash[K, T]) QueryRay

func (h *Hash[K, T]) QueryRay(ray geom.Ray[T]) iter.Seq[K]

QueryRay returns the keys whose box the ray meets, in no particular order. The hash must not change while it is ranged.

func (*Hash[K, T]) QuerySegment

func (h *Hash[K, T]) QuerySegment(segment geom.Segment[T]) iter.Seq[K]

QuerySegment returns the keys whose box the segment meets, in no particular order. The hash must not change while it is ranged.

Example

walls := map[int]geom.Shape[float64]{
	1: geom.Bx(geom.Pt(40.0, 0), geom.Pt(50.0, 30)),
	2: geom.Circ(geom.Pt(60.0, 60), 5),
}

index := NewHash[int](32.0)
for key, wall := range walls {
	index.Set(key, wall.Bounds())
}

sight := geom.Seg(geom.Pt(0.0, 50), geom.Pt(100.0, 50))
blocked := false
for key := range index.QuerySegment(sight) {
	if geom.Intersects(walls[key], sight) {
		blocked = true
		break
	}
}

fmt.Println(blocked)

Output:
false

func (*Hash[K, T]) Set

func (h *Hash[K, T]) Set(key K, box geom.Box[T])

Set stores the key with the box, replacing the box it had.

type Pair

type Pair[K comparable] struct {
	A K
	B K
}

Pair is two keys whose boxes touch.