Dynamic Octree System

Dynamic Octree System (DOS) v1.0
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.


image

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

Summary

https://github.com/plasma-node/Various-Personal-Modules/tree/master/src/DynamicOctreeSystem

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.

My YouTube Channel
My Twitter

95 Likes

what do you mean? I don’t follow

1 Like

You didn’t even read their code but looked at their images which look “old”. This is an Octree module, and if you actually read what it does, you’d notice that it doesn’t matter if it uses old or new Roblox code because it is an algorithm thereby only uses vanilla Lua.

15 Likes

I read the code after that, I thought the images are saved from 2010’s and I realized the date for the creation was Feburary 7th 2023 and is an expansion of an old module, and I would use it in flee the mall, Not sure why i’m dumb back at that time

Just letting you know the Github link doesnt work

2 Likes

I’m aware the GitHub went down, I’ll reupload it later

1 Like

Overhauling github system so in the meantime use this. Ripped it from the project im working on so it might error due to a require typo but the system’s dependencies are parented to it I believe. Will have time to check later

DynamicOctreeSystem.m.rbxm (12.5 KB)

5 Likes

hey I downloaded the module script, but it’s trying to require something called Importer, do you know what that is and can I juse get rid of the line?

2 Likes

Really cool tutorial on Octrees, I believe this could be useful in conjunction to reading the OP

2 Likes

this will give an error, cause there is no :RadiusSearch method for Grid.

--output
attempt to call missing method 'RadiusSearch' of table

It’d be great if you fix this and also fix the visualization of the octree, cause “Importer” module is not included in the file and it has been defined as
local Import = require(game.ReplicatedStorage.Importer);

dynamic octree system would really contribute much to the developing community, thank you for this.


Edit: Easy fixes for right now, if you want to use the system:

  1. about the importer module, comment it out and return nil for visualisation function for now so it doesn’t interfere with the actual script, though if you wanna visualize it, then you’d have to wait for @plasma_node’s response.

  2. Most importantly, in the “DynamicOctreeSystem.m” module, you have to add this function:

function Grid:RadiusSearch(pos,radius)
	return self.Tree:RadiusSearch(pos,radius)
end

and there, you’re good to go, please feel free to message/reply me if you’re still having issues with this.

5 Likes

Sorry about this, I was refactoring my GitHub and uploaded a ripped version from my game in a haste. I don’t maintain this anymore unfortunately, but I would recommend @sleitnick 's octotree module. I think it may only be for typescript but I also believe there’s probably a Lua version inside it.

It’s better than mine is.

2 Likes