OctoTree

Octree implementation for Roblox game development. Octrees are useful data structure for performing fast spatial queries for objects within a 3D space.

Roblox also provides some generalized spatial query methods, such as GetPartBoundsInRadius. These methods are useful for general purposes, but a special Octree can still be much faster for specific use-cases. For instance, having a bunch of collectables in the world.

Types

``ts
interface Node {
readonly Position: Vector3;
readonly Object: T;
}
`

Constructor

`ts
Octree.new();
Octree.new(topRegionSize: number);
`
In most cases, it is preferred to leave out the topRegionSize and use the default. The topRegionSize represents the cubic size of the top-level regions. By default, this is set to 512, which means the top-level regions have a 3D size of 512x512x512. Type T represents the arbitrary object that is held within each node.

Methods

$3

`ts
CreateNode(position: Vector3, object: T): Node;

const node = octree.CreateNode(someVector3, someObject);
`
Creates a Node within the octree at the given position. An arbitrary object can be given to the node as well.

$3


`ts
RemoveNode(node: Node): void;

octree.RemoveNode(node);
`
Removes the node from the octree. If the desire is to remove all nodes from the octree, use ClearAllNodes() instead.

$3


`ts
ChangeNodePosition(node: Node, position: Vector3): void;

octree.ChangeNodePosition(node, someNewVector3);
print(node.Position);
`
Change the position of the given node to the new position. Due to the internal workings of the octree, this is can be a fairly expensive operation. It is usually beneficial to keep most nodes as static as possible. Only change the position if necessary. Note: This is still faster than removing the node and creating a new one at a different position.

$3


`ts
GetAllNodes(): Array>;

const nodes = octree.GetAllNodes();
for (const node of nodes) {}
`
Get an array of all the nodes in the octree. This can be an expensive operation, as all regions and subregions in the octree must be traversed.

$3


`ts
ForEachNode(): IterableFunction>;

for (const node of octree.ForEachNode()) {}
`
Iterate over each node in the octree. This is useful if the desire is to scan through each node, but perhaps have a break within the loop, which will keep it from having to scan all nodes.

$3


`ts
CountNodes(): number;

const numNodes = octree.CountNodes();
`
Count the number of nodes in the octree. Similar to GetAllNodes(), this can be an expensive operation.

$3


`ts
ClearAllNodes(): void;

octree.ClearAllNodes();
`
Removes all nodes from the octree. This is a very quick operation and should be used instead of calling RemoveNode() on all nodes.

$3


`ts
FindFirstNode(object: T): Node | undefined;

const node = octree.FindFirstNode(someObject);
if (node !== undefined) {}
`
Finds the first node in the octree that has the same object. If no object is found, undefined is returned instead.

$3


`ts
SearchRadius(position: Vector3, radius: number): Array>;

const nearbyNodes = octree.SearchRadius(somePosition, 200);
for (const node of nearbyNodes) {}
`
Performs a search for all nodes within the given radius. An array of all the nodes found is returned.

$3


`ts
ForEachInRadius(position: Vector3, radius: number): IterableFunction>;

for (const node of octree.ForEachInRadius(somePosition, 200)) {}
`
Same as SearchRadius, except an iterator function is returned instead of a table. Unless a table of nodes is needed, ForEachInRadius will be faster than SearchRadius (because no table allocations are needed).

$3


`ts
GetNearest(position: Vector3, radius: number, maxNodes?: number): Array>;

const topTenNearest = octree.GetNearest(somePosition, 200, 10);
for (const node of topTenNearest) {}
`
Performs a radius search (same as the SearchRadius() method), but sorts the nodes by distance. If the maxNodes` parameter is used, the amount of nodes returned will be limited to that number.