How can i implement quad trees?

Help and Feedback Scripting Support
#1

Hello, quick question, do anyone have idea how to implement quad trees into roblox studio? i’m simply curious bc they aren’t that usefull or at least they are in very rare cases, any idea?

#2

if you mean octree (used for 3d spaces) then it already exists

you can probably modify it to create a quadtree

edit: and you can look up implementations in other languages and copy to lua

#3

This is not what he’s asking, He’s asking how can he Implement it, Yes you’ve given the resource but not to the Problem.

Secondly Quadtrees ARE NOT Octrees, though they are quite similar, they are used for certain situations (2D &3D).
Quadtree and an Octree

You can watch this video to understand more.

Secondly, Why would you need an QuadTree for roblox? You’ve put this under scripting support but you’ve not given a problem to what you need this for.

Here are some sources that may help you.

Video 1

Video 2

Video 3

1 Like
#4

Thx, i forget about this post and started working, after some try and error + math experiments i found out how to implement them at very basic level that i can use later to make optimized version of them, here is short video:

My entire methood depends on checking min and max points which are calculated based off size (we can determine size of subdivision by:

return OriginalSize / 2 ^ Iteration --/ where iteration starts from 0

and calculating max point:

return Minimal.X + SubdividedSize, Minimal.Z + SubdividedSize

Later we can determine if point is within given tile by using:

if Minimal.X > Target.X and Minimal.Z > Target.Z then return end
if Maximal.X < Target.X and Maximal.Z < Target.Z then return end

return true

And last thing is that to get Min/Max we need to multiply our size by row, which we get from:

local row = index % 2 ^ Counter
local collumn = math.floor(index / 2 ^ Counter)
--! Counter must start from 0 and be 1 at the first iteration moment

The rest is hardcoded part instancing to show how the tree looks, it helped debugging a lot
Anyways thx for help

EDIT: I forget to mention that idk how to overwrite current tree without re-generating it, but i think for static objects it would be good enough

1 Like
#5

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.