Spatial Systems

Implement efficient spatial queries using voxel grids to find nearby entities

Spatial partitioning is essential for performance in games with many entities. This example shows how to use a voxel grid to efficiently query nearby entities without checking every entity in the world.

Overview

The spatial grid pattern divides the world into fixed-size cells (voxels). Entities are assigned to voxels based on their position, and queries only check entities in relevant voxels.

Benefits

• Performance: Only check entities in nearby voxels instead of the entire world
• Scalability: Handles thousands of entities efficiently
• Flexibility: Works for perception, collision detection, area queries, etc.

Complete Example

This example implements a perception system where a player can detect enemies within range and field of view.

local jecs = require("@jecs")
local pair = jecs.pair
local ChildOf = jecs.ChildOf
local __ = jecs.Wildcard
local Name = jecs.Name
local world = jecs.world()

local Voxel = world:component() :: jecs.Id
local Position = world:component() :: jecs.Id<vector>
local Perception = world:component() :: jecs.Id<{
	range: number,
	fov: number,
	dir: vector,
}>
type part = {
	Position: vector
}
local PrimaryPart = world:component() :: jecs.Id<part>

local local_player = {
	Character = {
		PrimaryPart = {
			Position = vector.create(50, 0, 30)
		}
	}
}
local workspace = {
	CurrentCamera = {
		CFrame = {
			LookVector = vector.create(0, 0, -1)
		}
	}
}

local function distance(a: vector, b: vector)
	return vector.magnitude((b - a))
end

local function is_in_fov(a: vector, b: vector, forward_dir: vector, fov_angle: number)
	local to_target = b - a

	local forward_xz = vector.normalize(vector.create(forward_dir.x, 0, forward_dir.z))
	local to_target_xz = vector.normalize(vector.create(to_target.x, 0, to_target.z))

	local angle_to_target = math.deg(math.atan2(to_target_xz.z, to_target_xz.x))
	local forward_angle = math.deg(math.atan2(forward_xz.z, forward_xz.z))

	local angle_difference = math.abs(forward_angle - angle_to_target)

	if angle_difference > 180 then
		angle_difference = 360 - angle_difference
	end

	return angle_difference <= (fov_angle / 2)
end

local map = {}
local grid = 50

local function add_to_voxel(source: jecs.Entity, position: vector, prev_voxel_id: jecs.Entity?)
	local hash = position // grid
	local voxel_id = map[hash]
	if not voxel_id then
		voxel_id = world:entity()
		world:add(voxel_id, Voxel)
		world:set(voxel_id, Position, hash)
		map[hash] = voxel_id
	end
	if prev_voxel_id ~= nil then
		world:remove(source, pair(ChildOf, prev_voxel_id))
	end
	world:add(source, pair(ChildOf, voxel_id))
end

local function reconcile_client_owned_assembly_to_voxel(dt: number)
	for e, part, position in world:query(PrimaryPart, Position) do
		local p = part.Position
		if p ~= position then
			world:set(e, Position, p)
			local voxel_id = world:target(e, ChildOf, 0)
			if map[p // grid] == voxel_id then
				continue
			end

			add_to_voxel(e, p, voxel_id)
		end
	end
end

local function update_camera_direction(dt: number)
	for _, perception in world:query(Perception) do
		perception.dir = workspace.CurrentCamera.CFrame.LookVector
	end
end

local function perceive_enemies(dt: number)
	local it = world:query(Perception, Position, PrimaryPart):iter()
	-- There is only going to be one entity matching the query
	local e, self_perception, self_position, self_primary_part = it()

	local voxel_id = map[self_primary_part.Position // grid]
	local nearby_entities_query = world:query(Position, pair(ChildOf, voxel_id))

	for enemy, target_position in nearby_entities_query do
		if distance(self_position, target_position) > self_perception.range then
			continue
		end

		if is_in_fov(self_position, target_position, self_perception.dir, self_perception.fov) then
			local p = target_position
			print(`Entity {world:get(e, Name)} can see target {world:get(enemy, Name)} at ({p.x}, {p.y}, {p.z})`)
		end
	end
end

local player = world:entity()
world:set(player, Perception, {
	range = 200,
	fov = 90,
	dir = vector.create(1, 0, 0),
})
world:set(player, Name, "LocalPlayer")
local primary_part = local_player.Character.PrimaryPart
world:set(player, PrimaryPart, primary_part)
world:set(player, Position, vector.zero)

local enemy = world:entity()
world:set(enemy, Name, "Enemy $1")
world:set(enemy, Position, vector.create(50, 0, 20))

add_to_voxel(player, primary_part.Position)
add_to_voxel(enemy, assert(world:get(enemy, Position)))

local dt = 1 / 60
reconcile_client_owned_assembly_to_voxel(dt)
update_camera_direction(dt)
perceive_enemies(dt)

-- Output:
--  LocalPlayer can see target Enemy $1

Breaking It Down

Grid Setup

local map = {}
local grid = 50  -- Voxel size in studs

local Voxel = world:component()

The map table stores voxel entities indexed by their grid position. The grid constant defines the size of each voxel cell.

Adding Entities to Voxels

local function add_to_voxel(source: jecs.Entity, position: vector, prev_voxel_id: jecs.Entity?)
	local hash = position // grid  -- Integer division for grid coordinates
	local voxel_id = map[hash]
	
	-- Create voxel if it doesn't exist
	if not voxel_id then
		voxel_id = world:entity()
		world:add(voxel_id, Voxel)
		world:set(voxel_id, Position, hash)
		map[hash] = voxel_id
	end
	
	-- Remove from previous voxel
	if prev_voxel_id ~= nil then
		world:remove(source, pair(ChildOf, prev_voxel_id))
	end
	
	-- Add to new voxel using ChildOf relationship
	world:add(source, pair(ChildOf, voxel_id))
end

The ChildOf relationship is used to associate entities with their voxel. This allows efficient queries like world:query(Position, pair(ChildOf, voxel_id)) to find all entities in a specific voxel.

Updating Entity Positions

local function reconcile_client_owned_assembly_to_voxel(dt: number)
	for e, part, position in world:query(PrimaryPart, Position) do
		local p = part.Position
		if p ~= position then
			world:set(e, Position, p)
			local voxel_id = world:target(e, ChildOf, 0)
			
			-- Only update voxel if it changed
			if map[p // grid] == voxel_id then
				continue
			end

			add_to_voxel(e, p, voxel_id)
		end
	end
end

This system tracks entities that have moved and updates their voxel assignment only when necessary.

Spatial Query

local function perceive_enemies(dt: number)
	local it = world:query(Perception, Position, PrimaryPart):iter()
	local e, self_perception, self_position, self_primary_part = it()

	-- Find the voxel the player is in
	local voxel_id = map[self_primary_part.Position // grid]
	
	-- Query only entities in that voxel
	local nearby_entities_query = world:query(Position, pair(ChildOf, voxel_id))

	for enemy, target_position in nearby_entities_query do
		if distance(self_position, target_position) > self_perception.range then
			continue
		end

		if is_in_fov(self_position, target_position, self_perception.dir, self_perception.fov) then
			local p = target_position
			print(`Entity {world:get(e, Name)} can see target {world:get(enemy, Name)} at ({p.x}, {p.y}, {p.z})`)
		end
	end
end

Instead of checking every entity in the world, we only query entities in the same voxel as the player. For large perception ranges, you would query multiple nearby voxels.

Performance Characteristics

Without Spatial Grid

• Query all entities in world: O(n)
• For 10,000 entities, check all 10,000

With Spatial Grid

• Query entities in voxel: O(n/v) where v is number of voxels
• For 10,000 entities across 100 voxels, check only ~100 entities

Expanding to Multi-Voxel Queries

For larger perception ranges, query multiple voxels:

local function get_nearby_voxels(center: vector, radius: number)
	local voxels = {}
	local grid_radius = math.ceil(radius / grid)
	local center_grid = center // grid
	
	for x = -grid_radius, grid_radius do
		for y = -grid_radius, grid_radius do
			for z = -grid_radius, grid_radius do
				local offset = vector.create(x, y, z)
				local voxel_id = map[center_grid + offset]
				if voxel_id then
					table.insert(voxels, voxel_id)
				end
			end
		end
	end
	
	return voxels
end

Key Patterns

Using ChildOf for Spatial Relationships

-- Add entity to voxel
world:add(entity, pair(ChildOf, voxel_id))

-- Query entities in voxel
for entity in world:query(pair(ChildOf, voxel_id)) do
	-- Process entity
end

-- Get entity's current voxel
local voxel_id = world:target(entity, ChildOf, 0)

Lazy Voxel Creation

local voxel_id = map[hash]
if not voxel_id then
	voxel_id = world:entity()
	world:add(voxel_id, Voxel)
	map[hash] = voxel_id
end

Voxels are only created when needed, saving memory for sparse worlds.

Use Cases

Collision Detection

Only check collisions between entities in nearby voxels

AI Perception

NPCs search for targets only in their local area

Area Queries

Find all entities in a region (explosions, spells, etc.)

Network Relevancy

Only replicate nearby entities to clients

Next Steps

Basic Usage

Learn the fundamentals of jecs

Networking

Replicate entities across client and server