by Plasma_Node
This module expands Quenty’s Octree module and makes it easy to track dynamic, moving objects. According to Quenty, Octrees work best for static objects (objects that are staying still), however they can still be used with moving objects.
This module is actually pretty simple! It lets you register objects to the Octree, so that when you update them it automatically removes the node at it’s old position.
Disclaimer: This is a module I made for myself, and while I will be updating it, it’s in my “as-is” open-source code repository, meaning I make no promises.
TL;DR: Octrees = Efficient chunk system, my module takes an existing Octree module and makes it work with moving objects.
What are Octrees?
In essence, an Octree is sort of like a recursive chunk system.
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants.
Basically, it’s useful because if you have a huge area, instead of filling it with a ton of small, precise chunks and sacrificing performance, or a few big chunks and sacrificing fidelity, you can create an Octree and it will automatically subdivide! Better yet, if nothing exists in a particular area… there won’t be any grid sections there! Saves memory!
What this looks like in Roblox
Here’s a visualization I threw together. I am working on updating the Draw module included (made by Quenty), so we can visualize Dynamic Octrees in real time, and in a way that looks prettier and easier to see.
Why use Octrees?
Octrees are a very fast way to handle searching for nearby objects. For example, if you need to compute collisions, instead of first checking the distance between every object and the player, you first see what objects are within a certain radius using Octree:RadiusSearch(Pos, Dist), to get nearby objects. It’s pretty sweet!
Source
Github
Github removed, use this instead
DynamicOctreeSystem.m.rbxm (12.5 KB)
API
Expand to view
API details
Creating a grid:
Calling DOS.New returns a “Grid”.
It’s structure is:
Name = string
Tree = Octree
Update = boolean (Enables/disables tracked entry updates)
Entires = table
Tracked = table
local Grid = DOS.New("Name", 4, 512); -- Name, Depth (default 4), Size (default 512)
Adding entry:
Entries can be any data type that Quenty’s octree module supports.
Grid:Add(SomeInstance, Vector3.zero); -- Item, Position
You can also add static entries, that is items which will not be destroyed or moved within the lifespan of the DOS grid.
Grid:AddStatic(Item, Position)
Update entry:
When an entry moves, you can update it by calling the Grid:UpdateFor function and sending a new position plus the item itself:
Grid:UpdateFor(Item, Position);
Auto update entry:
WARNING! This is mainly for convenience, and should not be relied on or used for a large number of entries. It’s useful because you can give it an instance,
including a model (so long as it has a primary part) and a set interval at how often it should update. For a large number of dynamic entries,
it is best to implement your own update solution.
local tracked = Grid:Track(SomeInstance, 0.1); -- Instance, Update Frequency (Default: 0.1s)
You can destroy the entry by calling tracked:Destroy();
Searching:
For full documentation on Octree system, see here. You can access the Octree with Grid.Tree.
Grid:RadiusSearch(Position, Radius);
Grid:GetAllNodes();
Cleanup:
Grid:Destroy();
Example Usage
local DOS = require(pathToDOSModule);
local Grid = DOS.New("Players", 4, 100);
game.Players.PlayerAdded:Connect(function (Player)
local tracker;
Player.CharacterAdded:Connect(function (Character)
tracker = Grid:Track(Character.HumanoidRootPart, 0.1); -- Remember that using Grid:Track is not ideal for a large amount of objects. Better in this case to make a big loop to update for all players, or update only when movement events are fired.
end);
Player.CharacterRemoving:Connect(function (Character)
if (tracker) then
tracker:Destroy();
end
end);
end);
while true do
task.wait(1);
local nearby = Grid:RadiusSearch(Vector3.zero, 50);
print("Nearby entities: ", nearby)
end
Future Plans
This is a pretty straightforward module. However, I plan on adding a robust visualization system to let you see a real-time display of the Octree. I also plan on finding ways to optimize the code and make it more versatile.
About me
I’m Plasma_Node, a 20 year old programmer. I love cool technology, space, and programming.
If you enjoy my work please consider subscribing to my YouTube or my Twitter, where I post my work. I consider my YouTube as my current portfolio, though I should really make a real one, lol.
