Spatial

Quickly finds the game objects near a point or within a box.

Commands

Import blitz.spatial As Sp gives your program these, with Sp. in front. Each name leads to its part of the reference.

Functions

• CreateSpatial:SpatialIndex(cellSize:Float = 4, dimensions:Int = SpatialDimensions.XYZ)
• IndexPoint(index:SpatialIndex, id:Long, x:Float, y:Float, z:Float)
• IndexBounds(index:SpatialIndex, id:Long, bounds:Bounds)
• RemoveSpatial:Int(index:SpatialIndex, id:Long)
• QuerySphere(index:SpatialIndex, x:Float, y:Float, z:Float, radius:Float, output:Long List)
• QueryBounds(index:SpatialIndex, bounds:Bounds, output:Long List)
• NearestSpatial:Long(index:SpatialIndex, x:Float, y:Float, z:Float, maximumDistance:Float)

Types

• Bounds
  Fields minimumX:Float, minimumY:Float, minimumZ:Float, maximumX:Float, maximumY:Float, maximumZ:Float
• SpatialIndex

Enums

• SpatialDimensions
  Values XZ, XYZ

Guide

Spatial answers the question "what's near here?", quickly, even when your game has thousands of things in it. Which enemies can hear the player, which coins the magnet pulls in, which units are inside the box the player dragged. You tell it where each thing is, by a number of your own, and ask about a circle, a box, or just the nearest one. It gives you back the numbers, and your game does the rest.

Try it

Open nearby.bb and run it. Move the mouse among the drifting dots: the ones inside the circle light up green, and the nearest one turns yellow. Turn the mouse wheel to make the circle bigger or smaller.

; Hundreds of dots drift about. The ones near the mouse light up, and the
; nearest one turns yellow. Turn the mouse wheel to change the circle's size.
Dialect "modern"
Import blitz.spatial As Sp

Const DOTS:Int = 400
Graphics 640, 480, 0, 2
SetBuffer BackBuffer()
ClsColor 18, 52, 79

; Our own dots. Each dot's number, from 1 to 400, is its ID in the index.
Dim dotX:Float(DOTS)
Dim dotY:Float(DOTS)
Dim speedX:Float(DOTS)
Dim speedY:Float(DOTS)
Local dot:Int
For dot = 1 To DOTS
    dotX(dot) = Rnd(640)
    dotY(dot) = Rnd(480)
    speedX(dot) = Rnd(-30, 30)
    speedY(dot) = Rnd(-30, 30)
Next

; A flat index in 64-pixel cells. Flat (XZ) means it ignores height, as for
; things on the ground in a 3D game, so the screen's y goes where z would.
Local index:Sp.SpatialIndex = Sp.CreateSpatial(64, Sp.SpatialDimensions.XZ)
Local nearby:Long List = New List ; The index fills this with IDs.
Local radius:Float = 80
Local previous:Int = MilliSecs()

While Not KeyDown(1)
    Local now:Int = MilliSecs()
    Local seconds:Float = Float(now - previous) / 1000
    previous = now
    radius = radius + MouseZSpeed() * 10
    If radius < 10 Then radius = 10

    ; Move every dot, then tell the index where it is now.
    For dot = 1 To DOTS
        dotX(dot) = (dotX(dot) + speedX(dot) * seconds + 640) Mod 640
        dotY(dot) = (dotY(dot) + speedY(dot) * seconds + 480) Mod 480
        Sp.IndexPoint index, dot, dotX(dot), 0, dotY(dot)
    Next

    ; Which dots are inside the circle, and which one is nearest?
    Sp.QuerySphere index, MouseX(), 0, MouseY(), radius, nearby
    Local nearest:Int = Int(Sp.NearestSpatial(index, MouseX(), 0, MouseY(), radius))

    Cls
    Color 70, 120, 170
    For dot = 1 To DOTS
        Oval dotX(dot) - 2, dotY(dot) - 2, 5, 5
    Next
    Color 110, 250, 150
    Local slot:Int
    For slot = 0 To nearby.Count() - 1
        dot = Int(nearby[slot])
        Oval dotX(dot) - 3, dotY(dot) - 3, 7, 7
    Next
    Color 255, 255, 255
    Oval MouseX() - radius, MouseY() - radius, radius * 2, radius * 2, False
    If nearest > 0 ; 0 means there's nothing in the circle.
        Line MouseX(), MouseY(), dotX(nearest), dotY(nearest)
        Color 255, 220, 0
        Oval dotX(nearest) - 5, dotY(nearest) - 5, 11, 11
    EndIf
    Color 255, 255, 255
    Text 10, 10, nearby.Count() + " dots in the circle"
    Flip
Wend
Delete nearby
Delete index
End

Each frame, the program moves its dots and then tells the index where each one is now. Then it asks two questions: which dots are inside the circle, which QuerySphere answers by filling the list with their numbers, and which one is nearest, which NearestSpatial answers. The index keeps the dots sorted into cells, like squares on a map, so it only has to look in the cells near the mouse rather than check every dot.

How do I...

Find enemies near the player in a 3D game?

Things on the ground only need a flat index, like the one above. Give it each thing's x and z, and 0 for its y. Number your things yourself, from 1 up.

Local enemies:Sp.SpatialIndex = Sp.CreateSpatial(10, Sp.SpatialDimensions.XZ)
Sp.IndexPoint enemies, 7, EntityX(orc), 0, EntityZ(orc) ; The orc is enemy 7.
Sp.QuerySphere enemies, EntityX(player), 0, EntityZ(player), 15, nearby

For birds, fish or spaceships, where height matters, make the index with Sp.SpatialDimensions.XYZ and give it the y as well.

Take something out, such as a defeated enemy?

Sp.RemoveSpatial enemies, 7

It returns False if that number wasn't in the index. It never frees the orc itself: that's up to your game.

Find the nearest one?

Local target:Long = Sp.NearestSpatial(enemies, EntityX(player), 0, EntityZ(player), 30)
If target = 0 Then Print "No enemy within 30 units"

It only looks as far as the distance you give it. When two are exactly as near, it picks the lower number.

Select everything in a box, as in a strategy game?

Fill in a Bounds with the box's smallest and largest x and z, and ask QueryBounds. In the program above, z is the screen's y:

Local box:Sp.Bounds = New Sp.Bounds
box.minimumX = 100
box.maximumX = 300
box.minimumZ = 50
box.maximumZ = 200
Sp.QueryBounds index, box, nearby
Delete box

Add something big, such as a building or a trap?

Give it a box instead of a point, with IndexBounds. Distances are measured to the nearest edge of the box, so a long wall is found when you're near any part of it, not just its middle.

Local traps:Sp.SpatialIndex = Sp.CreateSpatial(10, Sp.SpatialDimensions.XZ)
Local area:Sp.Bounds = New Sp.Bounds
area.minimumX = -40
area.maximumX = 40
area.minimumZ = 20
area.maximumZ = 24
Sp.IndexBounds traps, 1, area ; A long, thin trap, number 1.
Delete area ; The index keeps its own copy.

Choose a cell size?

Make the cells about as big as the distance you usually search, or as your ordinary things. Any size gives the right answers: the size only changes how quickly they come.

Blip's tip

Moving something in your game doesn't move it in the index. After you move it, call IndexPoint again with its number, as the program above does every frame. Otherwise the index answers with where things used to be.

Good to know

• The numbers are your own. Use any whole number above 0: 0 or less stops the program. The index only remembers numbers and places, never your entities, so deleting it leaves your things alone.
• Answers come lowest number first, not nearest first, and each number only once. Ask NearestSpatial for the nearest.
• Touching counts. Something exactly on the edge of the circle or box is inside it.
• The answer list is yours. Make it once and use it for every question: each one empties the list and fills it again. Delete it when you've finished.

More examples

Three more complete programs come with the module:

• quick_start.bb puts three beacons in a row. Click near one, and it shows the nearest beacon within 60 pixels, and how many are in reach.
• crowd.bb moves a crowd of 180 dots across the screen. Click to move the circle: the dots inside it turn green and the nearest one yellow. Space pauses, N adds a dot and R removes the one nearest the circle's middle.
• large_bounds.bb has a strip that reaches 10,000 units off the screen, found wherever the circle touches it. Click to move the circle, press Left and Right to change its size, Space to search with a box instead, and M to move the strip.

The reference below has every function and rule.

Reference

Needs

No other modules

Examples

crowd.bb, large_bounds.bb, quick_start.bb

0.1.0 unpublished source preview. A uniform spatial hash for point and axis-aligned bounds queries. No package dependencies, assets or hidden game loop. Requires Extended object-lifecycle-v1 (runtime 1114 / module ABI 5 or later).

Blitz3D+ comes with this module, so any Extended program can Import blitz.spatial:

Dialect "modern"
Import blitz.spatial
Local index:Spatial.SpatialIndex = Spatial.CreateSpatial(4, Spatial.SpatialDimensions.XZ)
Local nearby:Long List = New List
Spatial.IndexPoint index, 42L, -2, 0, 5
Spatial.QuerySphere index, 0, 0, 5, 3, nearby
Print nearby[0] ; 42
Print Spatial.NearestSpatial(index, 0, 0, 5, 3) ; 42
Delete index
Delete nearby
End

The index stores positive Long IDs chosen by your game. Moving a game object does not update its ID's position: call IndexPoint or IndexBounds after movement, before queries. Insert and update use the same call. Rendering, physics, time, callbacks and game-object ownership stay with the application.

API and ownership

Both output queries borrow a live caller-owned Long List, validate all arguments before clearing it, then replace it with unique ascending IDs. Results remain valid after updates, removals or index destruction. No returned reference points at index storage. Keep/remove game objects independently; two indexes can contain the same IDs without sharing any owned state.

Local trigger:Spatial.Bounds = New Spatial.Bounds
trigger.minimumX = -10000
trigger.maximumX = 10
trigger.minimumY = -1
trigger.maximumY = 1
trigger.minimumZ = -1
trigger.maximumZ = 1
Spatial.IndexBounds index, 100L, trigger
Delete trigger ; geometry was copied
Spatial.QuerySphere index, 12, 0, 0, 2, nearby ; touches ID 100's near face

Use explicit Delete. Scope exit and assignment to Null do not invoke user destructors. Deleting a List releases references, not objects stored in it; the index destructor explicitly deletes its owned records and nested Lists. Repeated deletion of a typed Null/deleted index is harmless. Stop/Cancel/Save/ Commit are not spatial operations; deletion neither saves nor commits gameplay.

Validation, determinism and cost

Programming errors raise contextual RuntimeError: Null/deleted index or Bounds, non-positive IDs, invalid dimensions/cell size, non-finite active coordinates, reversed active bounds, negative/non-finite distances, and Null/deleted output Lists. Missing IDs, empty queries and an absent nearest target are normal results. There are no recoverable I/O failures and no redundant LastError API. For example, Spatial.CreateSpatial(0) fails before allocating any index storage.

All finite Float X/Y/Z values and all positive finite Float cell sizes are supported; extreme ratios use oversize/scan paths. Distance arithmetic promotes to Double before subtraction and squaring, avoiding Float overflow. Bounds and radii remain Float at the API boundary. Sorting and tie-breaking compare Long values directly, including IDs above 2^53 and up to 9223372036854775807. Map iteration order never determines results. The module reads no clock or RNG.

Operations are synchronous main-thread calls with no callbacks or yields. Public mutation cannot interleave with a query; there is no callback/reentrancy interface to implement. Update order is explicit: capture input, move gameplay objects, reindex, query, draw. Worker adapters are deferred.

The first-release algorithm is:

1. Floor each active coordinate divided by cell size with FloorD, including negatives. Include the maximum cell: touching boundaries count. Store one entry per ID in a Long-keyed Map and its occupied cell range.
2. Hash signed cell coordinates into a Long, then compare the full signed coordinate triple in a collision chain. Equal hashes are not equal cells. Each bucket wrapper owns a Long List. Updates change only memberships in the old/new range's symmetric difference and immediately delete empty buckets.
3. An entry touching more than 256 cells, or having a cell coordinate outside [-2147483647,2147483646], uses an oversize List instead. It is always considered by local queries. Swap-removal keeps this List's removal O(1). Extreme geometry remains exact; integer conversion is skipped.
4. Query up to 4096 cells; larger/out-of-range regions scan all entries. Reuse an entry-reference candidate List and per-entry generation stamps for deduplication. Reset stamps on generation rollover. Apply exact geometry and sort matches with in-place heapsort (O(k log k), no recursive stack).
5. Candidate references are cleared after each query while capacity is retained. Repeated queries within warmed capacity create no new module objects, containers or string keys. Collection growth may allocate on a new high-water workload; runtime iteration/debug instrumentation may have its own overhead.

Insertion/removal costs O(occupied cells plus bucket occupancy), capped at 256 cells per ordinary entry. Overlap updates retain existing bucket storage. Query cost is visited cells + candidate memberships + exact filtering + result sorting. Nearest uses filtering without sorting. Dense cells and many oversize objects can make scans faster. Cell size should be near ordinary neighbour distance and object size. No automatic tuning or quadtree is present.

Complete examples and scope

• Quick start: click to select a nearby generated beacon; Escape exits. --verify checks two distinct selections.
• Crowd: moving generated objects with click selection and nearest highlighting; Space pauses, N spawns, R removes nearest, Escape exits. Its 30-frame --verify exercises spawn/remove/pause/movement and compares both selected IDs and nearest target with a direct gameplay-object scan.
• Large bounds: a trigger extending far offscreen, exact sphere/AABB filtering and live updates. Click places the query, arrows change radius, Space changes query shape, M moves the trigger, Escape exits. Its six-frame --verify checks touching and moved oversize bounds in both shapes.

The steering module's optional blitz.steering.spatial part uses this index; the spatial core has no dependency on it. Quadtree remains deferred until clustered-2D benchmarks justify its root growth, spanning, removal and collapse design. See provenance.