Spatial

Spatial is a flat spatial-hash index: register any id at a world position, then ask what is near a point without touching the DataModel or walking a whole roster. It is the broad phase in front of expensive exact tests (sensor cones, projectile capsules, interest scans): query the index first and spend engine raycasts only on what it returns. SpatialKit is the query language built on top of it, with oriented boxes, 3D cones, capsules and population filters.

There is no tree and no per-node allocation. Every id lives in three flat tables (cell membership, current cell key, current position), and a move within the same cell is one position write.

Mental model

The grid

Space is divided into cubes of CellSize studs (default 8; Spatial.new asserts a finite positive size). A position hashes to a cell by flooring each axis to a cell coordinate and packing the three into one integer key:

local function packKey(cellSize: number, position: Vector3): number
  local X = math.clamp(math.floor(position.X / cellSize) + 65536, 0, 131071)
  local Y = math.clamp(math.floor(position.Y / cellSize) + 65536, 0, 131071)
  local Z = math.clamp(math.floor(position.Z / cellSize) + 65536, 0, 131071)
  return (X * 131072 + Y) * 131072 + Z
end

Each cell coordinate is offset by 65,536 and clamped to 0..131,071, a 17-bit field, and the three fields pack into one number below 2^51. That is inside a double’s 53-bit exact integer range, so the key behaves like an integer hash. Cell coordinates clamp to -65,536..65,535, which is about 524,288 studs each way at the default CellSize. Positions beyond that are still indexed; they share the boundary cells.

Cells maps a key to a set of ids, IdCell maps an id to its key, and IdPosition holds the exact, unclamped position. Exact filters always use IdPosition, so distance and bounds checks stay exact even past the clamp.

set() is cheap when the cell does not change

set(id, position) is the only write and also the move. If the new position hashes to the id’s current key, the call writes IdPosition[id] and returns. Otherwise it removes the id from its old cell (deleting the cell once empty, so dead cells do not accumulate), inserts it in the new one and updates both maps. set is an upsert; there is no separate insert and move.

A position with a NaN coordinate cannot key a cell, so set removes the id instead of indexing it. A NaN root on one character therefore drops that character from the index and leaves every other id untouched.

Queries: broad phase by cell, then exact filter

Every shape shares one walk. Given a world-space box, it converts the box to a cell range (clamped to the grid’s span, so an out-of-range query visits each boundary cell once) and tests every id in those cells against the shape’s exact filter. Cell membership decides which ids are checked, never which are returned, so every result is exact.

When the cell range holds more cells than there are ids in the index, the walk skips the cells and scans every registered id instead. A 512-stud radius at 8-stud cells covers about 2.1 million cells; a server with 30 players has 30 ids, and the scan is the cheaper path. Result order is not defined either way.

The exact filters compare squared distances and read their parameters from module-level slots, so a query allocates no closure. The walk never yields, so the slots cannot be overwritten mid-query.

Query shapes

radius

local Ids = Index:radius(position, radius)

Keeps ids whose distance to position is at most radius, inclusive. A negative radius matches nothing.

box

local Ids = Index:box(min, max)

Keeps ids whose position is between min and max on every axis, inclusive. A box whose min exceeds max on any axis returns nothing.

cone

local Ids = Index:cone(origin, direction, range, fovDegrees)

A horizontal field of view: a range test in 3D, then an angle test on the X/Z plane. fovDegrees >= 360, or a direction with no horizontal component (magnitude of its X/Z part at most 1e-3), degrades to radius(origin, range). Otherwise, for each candidate:

1. Reject when the full 3D distance exceeds range.
2. Accept when the candidate sits directly above or below the origin (no horizontal offset), since there is no horizontal angle to test.
3. Accept when the angle between the flattened facing and the flattened offset is within fovDegrees / 2.

Pitch never enters the test. SpatialKit’s cone is the true 3D alternative.

nearest

local Id, Distance = Index:nearest(position, maxRadius)

An expanding search: a radius query at CellSize, then twice that, doubling until a probe finds at least one id or reaches maxRadius (default 512). The last probe is exactly maxRadius, so a target at the limit is not skipped by a doubling that overshoots. Each probe is a full query from the origin, and the first probe with results is scanned for the closest id. Nothing within maxRadius, a negative or NaN maxRadius, or an empty index returns nil, nil.

Allocation-free queries: the Into variants

radiusInto, boxInto and coneInto append to a table you pass instead of allocating one; radius, box and cone call them with a fresh {}. For per-tick queries (a projectile step, an NPC target scan) pair them with a TablePool scratch table: acquire, query into it, read, release.

local Scratch = TablePool.acquire()
Index:radiusInto(Origin, 30, Scratch)
for _, Id in Scratch do
  -- exact tests on the survivors
end
TablePool.release(Scratch)

Character index: Spatial.characters(kernel)

local Characters = Spatial.characters(kernel, { CellSize = 8, Hz = 10 })

Builds an index of player character roots, keyed by Player, that maintains itself from events:

• PlayerAdded and PlayerRemoving add and forget players; players already in the game are watched at construction.
• CharacterAdded finds the character’s HumanoidRootPart and starts tracking it. A root that arrives after CharacterAdded (streaming, custom rigs) is caught through the character’s ChildAdded.
• CharacterRemoving drops the player at once; a characterless player is never in the index.
• While at least one root is tracked, a Scheduler job samples every tracked root Hz times per second (default 10) at kernel.Priority.Low. It cancels itself when no root is tracked, so an empty server has no job. A root whose Parent became nil is dropped and the player’s current character is watched again.

The result is a normal index, keyed by Player, plus Index:destroy(), which disconnects every event, cancels the job and clears the index. Call it when the owning service stops.

Arbitrary ids: insert, remove, move

id can be anything: strings, numbers, Instances, npc handles.

Call	Effect
Index:set(id, position)	Insert or move; safe to repeat. A NaN position removes the id
Index:remove(id)	Drop an id; no-op when it is not indexed
Index:position(id)	Current stored position, or nil
Index:count()	Number of indexed ids
Index:clear()	Drop every id and cell

Wired consumers

• Projectiles takes Spatial = Characters (a Spatial.characters index) and queries capsule-mode candidates per shot instead of scanning every player each tick.
• Sweeps takes a Spatial.characters index and queries candidates within each attack’s Reach of the rig’s root.
• SpatialKit broad-phases its players() population through a Spatial.characters index.
• NPCKit takes a Spatial index and broad-phases target scans through it. By default its update() refreshes the index from its own target roster and removes ids that are not in it. When several systems share one index that the game maintains, pass false as the second argument (Npcs:update(nil, false)) so NPCKit leaves it alone.
• Zones keeps a private Spatial index of occupant bounds in its Bounds detection mode.

Build one character index and hand the same instance to every consumer that needs “which players are near here”. One set of samples then backs every broad phase.

Usage

src/Server/Game/Services/ArenaService.luau

--!strict
-- ArenaService: owns the shared character index and answers "who is near".

local ReplicatedStorage = game:GetService("ReplicatedStorage")

local Spatial = require(ReplicatedStorage.ChloeKernel.Spatial)

local ArenaService = {
  Name = "ArenaService",
}

function ArenaService.init(self: any, kernel: any)
  self.Kernel = kernel
end

function ArenaService.start(self: any)
  self.Characters = Spatial.characters(self.Kernel, { CellSize = 8, Hz = 10 })
end

function ArenaService.nearestPlayer(self: any, position: Vector3): (Player?, number?)
  return self.Characters:nearest(position, 128)
end

function ArenaService.stop(self: any)
  if self.Characters then
    self.Characters:destroy()
  end
end

return ArenaService

A plain index over props:

local Crates = Spatial.new({ CellSize = 16 })
Crates:set("Crate1", Vector3.new(10, 0, 10))
Crates:set("Crate2", Vector3.new(100, 0, 0))
Crates:set("Crate1", Vector3.new(11, 0, 11)) -- same cell: one position write
local Near = Crates:radius(Vector3.new(10, 0, 10), 5) -- { "Crate1" }
Crates:remove("Crate2")

API reference

Member	Description
Spatial.new(options?) -> index	options: { CellSize? = 8 }; errors on a size that is not finite and positive
Spatial.characters(kernel, options?) -> index	Event-driven index of player roots keyed by Player. options: { CellSize? = 8, Hz? = 10, Players? } (Players injects the player service for specs). Adds index:destroy()
index:set(id, position)	Insert or move; a same-cell move is one position write; a NaN position removes the id
index:remove(id)	Drop id; no-op when absent
index:position(id) -> Vector3?	Stored position, or nil
index:count() -> number	Number of ids
index:clear()	Drop every id and cell
index:radius(position, radius) -> { any }	Ids within radius, inclusive
index:radiusInto(position, radius, out) -> { any }	radius, appending to out
index:box(min, max) -> { any }	Ids inside the axis-aligned box, inclusive on every axis
index:boxInto(min, max, out) -> { any }	box, appending to out
index:cone(origin, direction, range, fovDegrees) -> { any }	Ids within range and within fovDegrees of the horizontal facing; degrades to radius at 360 degrees or a vertical direction
index:coneInto(origin, direction, range, fovDegrees, out) -> { any }	cone, appending to out
index:nearest(position, maxRadius?) -> (any?, number?)	Expanding search from CellSize to maxRadius (default 512); nil, nil when nothing is in range
index:destroy()	Character indexes only: disconnects events, cancels sampling and clears the index

Bus topics

None. Spatial publishes and consumes nothing on the Bus; the systems that query it publish their own events.

Design notes

Caution

Coordinates clamp to about 524,288 studs each way at the default CellSize instead of erroring. An id beyond that is still indexed and still filtered exactly, but it hashes into a boundary cell, so many far-out ids share one cell and the grid stops narrowing them. Results stay correct; the broad phase just stops helping out there.

Caution

nearest(position, maxRadius) defaults maxRadius to 512 studs. A target farther away returns nil, nil unless you pass a larger limit.

Caution

cone is horizontal only. A candidate directly above or below the origin passes the angle test whenever it is in range, whatever the facing or aperture.

Status

Spatial.spec.luau covers same-cell and cross-cell moves, double removal, exact radius filtering across cell boundaries and against a brute-force filter, box bounds, cone ahead and behind, nearest ring expansion and its bounded miss, the far-coordinate clamp, nearest within a radius smaller than half a cell, large sparse queries scanning ids instead of cells, and invalid cell sizes. The core regression runner covers Spatial.characters with player and character doubles (a late root, sampling that stops with no roots, removal on CharacterRemoving) and NaN positions dropping ids.