Feedback on closest part script - efficiency

Standard magnitude checking systems are boring and inefficient, often checking through parts that don’t even need checking, therefor I tried to create the most efficient ‘closest point finder’ system I possibly good, while not compromising on quality.

  • What does the code do and what are you not satisfied with?
    It finds the closest part on the map to the local player
  • What potential improvements have you considered?
    Ive tried everything I could to optimise it as much as possible
  • How (specifically) do you want to improve the code?
    Anything that could make it faster / more efficient.
--[[ Variables ]]--

local RunService = game:GetService("RunService")

local Player = game.Players.LocalPlayer

local MapSize = 600
local BoxSize = 50

local SlowCheck = 1.5
local FastCheck = .1

local HalfSize = MapSize/2
local HalfBox = BoxSize/2
local CheckRate = SlowCheck / FastCheck

local Origin = Vector2.new(0,0)

local Points = {}
local NearPoints = {}

--[[ Actual code ]]--

local function MakePart(Point, Color)
	local Part = Instance.new("Part")
	Part.Anchored = true
	Part.Size = Vector3.new(1,1,1)
	Part.Position = Point
	Part.Parent = game.Workspace
    Part.Color = Color
	return Part
end

local function RoundTo10(Position)
	return Vector2.new((math.floor(Position.X/HalfBox+.5)*HalfBox), (math.floor(Position.Z/HalfBox+.5)*HalfBox))
end


local function DrawGrids()
	local X = MapSize/HalfBox
	local Y = X
	
	local StartPoint = Origin - Vector2.new(HalfSize,HalfSize)
	
	for Xcount = 0, X do
		local Xpos = Xcount * BoxSize
		for Ycount = 0, Y do
			local Ypos = Ycount * BoxSize

			local xpoint = StartPoint.X + Xpos/2
			local ypoint = StartPoint.Y + Ypos/2
			
			Points[(xpoint).. (ypoint)] = {}
		end
	end
end

local function AddObject(Object)
	local MainPoint = Object.PrimaryPart
	local NewPos = RoundTo10(MainPoint.Position)
	local Point = NewPos.X.. NewPos.Y
	local Table = Points[Point]
	
	if Table then
		table.insert(Points[Point], Object)
	end
end

local function ArangeExsistingInteractables()
	for i,v in pairs(game.Workspace.Interactables:GetChildren()) do
		AddObject(v)
	end
end

local function FindNearest()
	local MainPoint = Player.Character.PrimaryPart.Position
	local ClosestLength = 1000
	local ClosestObject = nil
	
	for _, v in pairs(NearPoints) do
		local Mag = (MainPoint - v.PrimaryPart.Position).magnitude
		if Mag < ClosestLength then
			ClosestLength = Mag
			ClosestObject = v
		end
	end
	
	return ClosestObject
end

DrawGrids()
ArangeExsistingInteractables()

game.Players.LocalPlayer.CharacterAdded:Wait()

while RunService.Heartbeat:Wait() do
	local NewPos = RoundTo10(Player.Character.PrimaryPart.Position)
	NearPoints = {}
	
	local PointTable = {
		NewPos.X.. NewPos.Y,
		NewPos.X.. NewPos.Y + HalfBox,
		NewPos.X.. NewPos.Y - HalfBox,
		NewPos.X + HalfBox.. NewPos.Y,
		NewPos.X - HalfBox.. NewPos.Y,
		NewPos.X - HalfBox.. NewPos.Y - HalfBox,
		NewPos.X + HalfBox.. NewPos.Y + HalfBox,
		NewPos.X - HalfBox.. NewPos.Y + HalfBox,
		NewPos.X + HalfBox.. NewPos.Y - HalfBox,
	}
	for _, Point in pairs(PointTable) do
		for _,v in pairs(Points[Point]) do
			table.insert(NearPoints, v)
		end
	end
	
	
	for _ = 1, CheckRate do
		local Closest = FindNearest()
		for i,v in pairs(game.Workspace.Interactables:GetChildren()) do
			v.PrimaryPart.Color = Color3.fromRGB(163, 162, 165)
		end
		if Closest then
			Closest.PrimaryPart.Color = Color3.new(0,0,1)
		end
		wait(FastCheck)
	end
end

3 Likes

Look into quadtrees/octrees, there’s a ton of info on the internet as well as here on the devforums. Using quadtrees, you’ll be able to trade memory usage for speed of computation (so it’s a lot faster to find the nearest part(s), but it uses more memory).

3 Likes

I haven’t used this before, but it could be useful to you.

1 Like

I believe my system is more efficient then region 3 for every single node on the map.

1 Like

I’ve ran a quick benchmark of a few things with a quick implementation I made, given that I’m always skeptical of premature optimizations.

This is no different.

After tinkering around and getting familiar with your code, it appears it performs ~18 checks every 120 frames, taking ~1.7 seconds to do one full cycle and updating your point table. This makes it sluggish when a player can see they’re closer to something, a few frames pass, and then the check is performed. It would also appear that it’s not a maintinable speed. As the benchmark continued, a cycle began to take twice or three times as long. I do not know why. As a technical note, the benchmark excluded any wait calls found within the snippet above.

On the other hand, iterating through every part to be checked performs a check with every frame, taking a thousandth of a second to compute.

Simply iterating through all the children models of Interactables, finding the closest primary part of said child, then updating its color takes around one thousandth of a second, when bound to RunService.Heartbeat fires on the frame, every frame. Its performance was stable no matter how much time had elapsed.

(As a very minor note, your approach makes each garbage collection cycle take roughly a third more time in a place similar to your screenshot)

TL;DR: It is very tempting to many computer scientists to optimize something. To make it more efficent. However, it should only be done once a clear issue arises from performance. The time you take to create optimizations that might work detracts from time used in implementing new features and typically obfuscates code, making it less readable (and terrible to work with).

2 Likes

you dont need to know the actual distance from each part, so instead of this:

local dist = (pos1 - pos2).magnitude
-- which is
local diff = (pos1 - pos2)
local dist = math.sqrt(diff.X^2 + diff.Y^2 + diff.Z^2)

you could do

local diff = (pos1 - pos2)
local dist = (diff.X^2 + diff.Y^2 + diff.Z^2)

this way, you dont need to do an expensive math.sqrt operation every time and you still get the closest part!

1 Like

I believe the .Magnitude is actually faster. Refer to the thread on this sort of optimizations under Discussions. I’m on mobile at the moment, and can’t spare the time to link it myself. I will later if you can’t find it.

I found the post with the benchmark:

https://devforum.roblox.com/t/a-lesson-in-over-optimisation-magnitude-calculation

As it concluded, what would otherwise be a logical optimization is slower than the actual implementation of .Magnitude. Later in that thread; the technical director at Roblox, zeuxcg; confirms that this is the case and why:

In summary, calling the vector’s X, Y, and Z __index that goes to Roblox’s C++ implementation is the main performance issue. Calling Magnitude is only one call which includes an optimized C++ call to compute the magnitude far faster than what’s possible in the Lua VM.

1 Like