Math and Space

Octree

A spatial index for points in 3D. Find everything within a radius, inside a box, along a ray or nearest to a position, fast.

PackageShared

Getting it

local Octree = Engine:GetPackage("Octree")

Checking every object against every other object gets slow quickly. An octree splits space into nested boxes so a query only looks at the boxes near the area you ask about. Use it for "which pickups are near this player", "which enemies are inside the explosion" or "the five closest spawn points".

Items can be anything (parts, tables, ids); you give each one a position.

local Octree = Engine:GetPackage("Octree")

local pickups = Octree.new({
	Min = Vector3.new(-1024, -64, -1024),
	Max = Vector3.new(1024, 512, 1024),
})

for _, coin in workspace.Coins:GetChildren() do
	pickups:Insert(coin, coin.Position)
end

RunService.Heartbeat:Connect(function()
	for _, player in Players:GetPlayers() do
		local root = player.Character and player.Character:FindFirstChild("HumanoidRootPart")
		if root then
			for _, coin in pickups:QueryRadius(root.Position, 6) do
				pickups:Remove(coin)
				collect(player, coin)
			end
		end
	end
end)

For whole parts and models with size, or for zones and volumes, see SpatialService, which builds on the same idea.

Constructor

new

Octree.new(bounds: { Min: Vector3, Max: Vector3 }, config: { maxDepth: number?, maxItems: number? }?): Octree

An empty octree covering bounds. A box splits into eight once it holds more than maxItems items, up to maxDepth levels deep. Positions outside the bounds are clamped onto the edge, so make the bounds cover your whole play area.

Members

Member	Description
`Size: number`, `IsEmpty: boolean`	Number of items.
`Bounds`, `MaxDepth`, `MaxItems`	The settings it was created with.
`:Insert(item, position)`	Adds an item.
`:Move(item, position): boolean`	Updates an item's position. `false` if the item is not in the tree.
`:Remove(item): boolean`	Removes an item.
`:Contains(item): boolean`	Whether the item is in the tree.
`:GetPosition(item): Vector3?`	The position it was stored at.
`:ForEach(callback)`	Calls `callback(item, position)` for every item.
`:GetAllItems(): { any }`	Every item.
`:Clear()`	Removes everything.

Queries

Method	Returns
`:QueryRadius(position, radius)`	Items within `radius` studs of `position`.
`:CountInRadius(position, radius)`	How many there are, without building a list.
`:QueryBox(cframe, size)`	Items inside a rotated box.
`:QueryAABB(min, max)`	Items inside an axis-aligned box.
`:QueryRay(origin, direction, radius?)`	Items within `radius` of the ray segment from `origin` to `origin + direction`.
`:Nearest(position, k)`	The `k` items closest to `position`, nearest first.

Configuration

Defaults from DefaultConfiguration/Packages/Octree3 settings

Setting	Default	What it does
DefaultMaxDepth	8	Subdivision depth an Octree.new() allows when config.maxDepth is omitted.
DefaultMaxItems	8	Items a node holds before splitting when config.maxItems is omitted.
DefaultQueryRayRadius	1	Radius :QueryRay() searches around the ray when none is passed.

Types

export type Bounds = { Min: Vector3, Max: Vector3 }
export type OctreeConfig = { maxDepth: number?, maxItems: number? }
export type Octree