Get parts closest to an object

Hello everyone,

I’m trying to make a framework that places blocks. Obviously, I need the blocks to not be placed in a position when there is an obvious collision. To do this, I need to make sure the distance between the obstacle is greater than the distance between the corner of the obstacle to the center of the obstacle. (I am aware that this only works with rectangular hitboxes which is what I’m going to be dealing with)
Code:

-- distance from obstacle
local DistFromObstacle = (Obstacle.Position - Obj.Position) .Magnitude

-- get corner position
local CF = Obstacle.CFrame
local HalfSize = Obstacle.Size/2
local Corner = CF.Position + CF.RightVector*HalfSize.X + CF.LookVector*HalfSize.Z + CF.UpVector*HalfSize.Y

-- distance from center to corner
local CornerDist = (Obstacle.Position - Corner).Magnitude

-- colliding if obj is closer than corner
if DistFromObstacle <= CornerDist then print("colliding") ; end

However, I’ve run into an issue where I have to loop through all of workspace’s descendants per frame (since I am doing a preview of what the result will be) in order to get the obstacle that is in the way.

for i, v in pairs(workspace:GetDescendants()) do
    if not v:IsA("BasePart") or not v:IsA("UnionOperation") or not v:IsA("Model") then continue; end
    if (v.Position - Obj.Position).Magnitude < ClosestMag or not Closest then
        v = Closest
        ClosestMag = (v.Position - Obj.Position).Magnitude
    end
end

How can I get the part that is closest to the Object without having to loop through every single part in the entire game? If you have any ideas, please leave them below. Thanks!

2 Likes

Octrees or maybe k-d trees are useful for this sort of thing.

@Quenty wrote an implementation here: NevermoreEngine/Octree.lua at version2 · Quenty/NevermoreEngine · GitHub

And @sayhisam1 wrote a stand-alone one here: GitHub - sayhisam1/Octree: Lua implementation of Octree intended for Roblox

Thanks for your help. I’ll look into these resources.