I am making a interact system but more interactables = slower check for nearest interactable

Help and Feedback Scripting Support
1

Right now how im doing it is i just check the position of each part and then check which part is closest to the players hrp but with a few interactable parts the code ran pretty fast like (0.07ms) but when i tested it and added a bunch more (536) the code run time jumped up to (.25ms) and i run this function every .1s in a while loop making it pretty expensive now does anyone have a better approach of checking what part in a table of parts is the closest to the player cheaply?

local collectionService = game:GetService("CollectionService")

local effectsManagerModule = require(script.Parent.EffectsManager)

local player = game.Players.LocalPlayer
local character = player.Character or player.CharacterAdded:Wait()
local humanoidRootPart = character:WaitForChild("HumanoidRootPart")

local RANGE_SQUARED = 64 --that means the range is 8 studs (8*8=64)

local interactables = {}
local currentInteractable

player.CharacterAdded:Connect(function(newCharacter)
	character = newCharacter
	humanoidRootPart = newCharacter:WaitForChild("HumanoidRootPart")
	currentInteractable = nil
end)

for _, interactable in pairs(collectionService:GetTagged("Interactable")) do
	interactables[interactable] = true
end

collectionService:GetInstanceAddedSignal("Interactable"):Connect(function(interactable)
	interactables[interactable] = true
end)

collectionService:GetInstanceRemovedSignal("Interactable"):Connect(function(interactable)
	interactables[interactable] = nil
	
	if currentInteractable == interactable then
		currentInteractable = nil
		effectsManagerModule.removeEffects()
	end
end)

return function()
	if not (humanoidRootPart and next(interactables)) then
		return
	end
	
	local humanoidRootPartPosition = humanoidRootPart.Position

	local closestDistSq = RANGE_SQUARED
	local closestInteractable = nil

	for interactable in interactables do
		if not interactable then
			continue
		end
		
		local difference = humanoidRootPartPosition - interactable.Position
		local distSq = difference:Dot(difference)
		
		if distSq >= closestDistSq then
			continue
		end
		
		closestDistSq = distSq
		closestInteractable = interactable

		if distSq == 0 then
			break
		end
	end
	
	if closestInteractable == currentInteractable then
		return currentInteractable
	end
	effectsManagerModule.removeEffects()

	currentInteractable = closestInteractable
	
	effectsManagerModule.applyEffects(currentInteractable)

	return currentInteractable
end
3 Likes
2

Did you actually measure it at 0.25 ms or 25 ms? There’s a big difference between the two. If it’s 0.25 ms then don’t touch it at all, that’s completely normal

2 Likes
3

Try workspace:GetPartsInRadius with the OverlapParams’ whitelist set to the interactables

2 Likes
4

Why exactly are you measuring distance with :Dot product, instead of just simple magnitude? You could replace it with:

vector.magnitude(hrp.Position-Interactable.Position)

Also regarding the table, you could change it to an array, instead of a dict, and instead of doing:

next(interactable)

You just:

#interactables > 0
1 Like
5

I don’t think # will work as its a dict
The real question is why is it a dict, but yes the squaring is odd. I personally would do

(hrp.Position-interactable.Position).Magnitude

6

He is completely correct and this is the right decision to use a squared distance. A magnitude does a square root operation, which is unnecessary for simply comparing distance and expensive at his scale and is the proper optimization when you’re comparing many objects like this.

1 Like
7

Feel free to run the benchmark yourself.

task.wait(2)

local start = os.clock()

for i = 1, 10_000_000 do
	local diff = workspace.Part.Position-workspace.Part2.Position
	local distSq = diff:Dot(diff)
end

print("dot", os.clock()-start)

task.wait(1)

local start = os.clock()

for i = 1, 10_000_000 do
	local dist = vector.magnitude(workspace.Part.Position-workspace.Part2.Position)
	local squared = dist*dist
end

print("magnitude", os.clock()-start)

results, 10 mil sample

dot 3.890899800000625
magnitude 3.727897800001301

it’s faster even if you square the magnitude itself

EDIT:
Not to mention that if you’ll need non-squared magnitude it’ll take even more time

task.wait(2)

local start = os.clock()

for i = 1, 10_000_000 do
	local diff = workspace.Part.Position-workspace.Part2.Position
	local distSq = diff:Dot(diff)
	local squareRoot = math.sqrt(distSq)
end

print("dot", os.clock()-start)

task.wait(1)

local start = os.clock()

for i = 1, 10_000_000 do
	local dist = vector.magnitude(workspace.Part.Position-workspace.Part2.Position)
	local squared = dist*dist
end

print("magnitude", os.clock()-start)

dot 4.0481199999994715
magnitude 3.6420749999997497

around ~11% difference for the vector.magnitude being faster

8

Try vector.dot, not the Dot function on the vector3 itself. Second run these separately, you’re warming up the interpreter after the first bench

9

Well I’m not sure, they beat eachother 50/50:

local Iterations = 10_000_000
local Diff = vector.create(123.45, 678.9, -321.12)

-- Warmup
for i = 1, 100_000 do
	vector.dot(Diff, Diff)
	vector.magnitude(Diff)
end

task.wait(1)

local Sink = 0
local Start = os.clock()

for i = 1, Iterations do
	Sink += vector.magnitude(Diff)
end

print("vector.magnitude:", os.clock() - Start, Sink)

task.wait(1)

Sink = 0
Start = os.clock()

for i = 1, Iterations do
	Sink += vector.dot(Diff, Diff)
end

print("vector.dot:", os.clock() - Start, Sink)

So neither of us are wrong
Regardless his optimization concern isn’t true then if he’s actually measuring 0.25ms, the frame budget for 60 FPS is ~16.67 ms, 0.25ms is far below. 25 ms would actually mean he’s exceeding the budget, but I don’t know

10 
task.wait(1)

local start = os.clock()

for i = 1, 10_000_000 do
	local diff = workspace.Part.Position-workspace.Part2.Position
	local distSq = vector.dot(diff, diff)
	local squareRoot = math.sqrt(distSq)
end

print("dot", os.clock()-start)

dot 3.837357799999154

task.wait(1)

local start = os.clock()

for i = 1, 10_000_000 do
	local dist = vector.magnitude(workspace.Part.Position-workspace.Part2.Position)
	local squared = dist*dist
end

print("magnitude", os.clock()-start)

magnitude 3.627147999999579

Ran separately. Depending on the specific benchmark, the margin varies, but leans towards magnitude on the same result (both squared + square root values)

1 Like
11

My original bench was flawed, Luau is folding that into a precomputed constant. The ratio is around 50/50 (see console below)
Magnitude First

local SAMPLE_COUNT = 10_000
local REPEATS = 1_000

local RandomGenerator = Random.new()
local Samples = table.create(SAMPLE_COUNT)

for i = 1, SAMPLE_COUNT do
	Samples[i] = vector.create(
		RandomGenerator:NextNumber(-1000, 1000),
		RandomGenerator:NextNumber(-1000, 1000),
		RandomGenerator:NextNumber(-1000, 1000)
	)
end

-- Warmup
for i = 1, SAMPLE_COUNT do
	local Diff = Samples[i]

	vector.dot(Diff, Diff)
	vector.magnitude(Diff)
end

task.wait(1)

local Sink = 0
local Start = os.clock()

for _ = 1, REPEATS do
	for i = 1, SAMPLE_COUNT do
		local Diff = Samples[i]
		Sink += vector.magnitude(Diff)
	end
end

print("vector.magnitude:", os.clock() - Start, Sink)

task.wait(1)

Sink = 0
Start = os.clock()

for _ = 1, REPEATS do
	for i = 1, SAMPLE_COUNT do
		local Diff = Samples[i]
		Sink += vector.dot(Diff, Diff)
	end
end

print("vector.dot:", os.clock() - Start, Sink)

Magnitude Second

local SAMPLE_COUNT = 10_000
local REPEATS = 1_000

local RandomGenerator = Random.new()
local Samples = table.create(SAMPLE_COUNT)

for i = 1, SAMPLE_COUNT do
	Samples[i] = vector.create(
		RandomGenerator:NextNumber(-1000, 1000),
		RandomGenerator:NextNumber(-1000, 1000),
		RandomGenerator:NextNumber(-1000, 1000)
	)
end

-- Warmup
for i = 1, SAMPLE_COUNT do
	local Diff = Samples[i]

	vector.dot(Diff, Diff)
	vector.magnitude(Diff)
end

task.wait(1)

local Sink = 0
local Start = os.clock()

for _ = 1, REPEATS do
	for i = 1, SAMPLE_COUNT do
		local Diff = Samples[i]
		Sink += vector.dot(Diff, Diff)
	end
end

print("vector.dot:", os.clock() - Start, Sink)

task.wait(1)

Sink = 0
Start = os.clock()

for _ = 1, REPEATS do
	for i = 1, SAMPLE_COUNT do
		local Diff = Samples[i]
		Sink += vector.magnitude(Diff)
	end
end

print("vector.magnitude:", os.clock() - Start, Sink)

Console (Magnitude First)

vector.magnitude: 0.369303100000252 9592398629.608154
vector.dot: 0.32162050000079034 9965405616369.14 🏆

vector.magnitude: 0.3543900000004214 9578991131.946564
vector.dot: 0.29888560000108555 9966916522395.166 🏆

vector.magnitude: 0.36467760000050475 9623123502.132416 🏆
vector.dot: 0.3855968000007124 10031748552651.965

Console (Magnitude Second)

vector.dot: 0.3886280999995506 9945065626874.227
vector.magnitude: 0.34644699999989825 9573537724.67041 🏆

vector.dot: 0.3499550000015006 10048411675588.984 🏆
vector.magnitude: 0.3617503999994369 9630961109.214783

vector.dot: 0.36203930000010587 10020959904113.227
vector.magnitude: 0.33096329999898444 9608771380.844116 🏆

Dot: 3 :trophy:
Magnitude: 3 :trophy:
Anyway this is kinda off topic, for @kubiktrierjebubu if it’s 0.25ms no worries, if it’s 25ms then yes a need for optimization is there

12

Wouldn’t it be better to just make character check what is near it by hit detection? Or you can use chunk system like Minecraft.

13

A spatial query is slower than just comparing distances, unless you have like 10,000 objects, then it would make sense to spatial query but for 500+ nah

14

What about node based query? like real life addresses you start with major nodes for example 500 studs far away there is a interactable but also there a lot of interactables surrounding, in radius 200 studs maybe, you could check that main center interactable.

1 Like
15

Not sure, honestly his approach is completely fine

16

If you’re concerned about checking the distance from interactables to the player, (including super faraway interactables that have a higher magnitude = more performance cost) I’d look into using Octree. This assumes the interactables don’t move from the position they were in initially.

I used this for a system where there was spinning coins and I needed to disable the effects of the coins because there was heavy usage of them across the map. I found that by rotating the coins with a Bone and using Octree to decide if effects should process, performance was better.

1 Like
17

Worth settling the budget question before optimising anything, because it decides whether the rest of this matters. 0.25ms is about 1.5% of a single frame at 60 FPS (16.67ms), and you are running the check every 0.1s, so that cost lands on one frame in six and comes to roughly 2.5ms per second of wall clock. Kasuraa is right. At 536 interactables a squared-distance loop is a reasonable thing to be doing, and I would not restructure it on these numbers.

Two notes if you go the spatial query route anyway, since it has been suggested twice above.

The method name is GetPartBoundsInRadius, not GetPartsInRadius. The latter does not exist. I checked against the current API dump (version-ff6341faef444107) and GetPartBoundsInRadius is the only InRadius method there is. It lives on WorldRoot, which Workspace inherits from, so the call is workspace:GetPartBoundsInRadius(hrp.Position, 8, params).

The one that will actually bite you is MaxParts on OverlapParams. It caps how many parts the query returns, and it is a cap, not a “give me the nearest N”. If enough of your 536 interactables fall inside the 8 stud radius at once and you hit that cap, you get back a subset with no distance guarantee, and your code then picks a confident “closest” out of an incomplete list. That only misbehaves in your densest room, which is the worst possible place to be debugging it. Set MaxParts explicitly rather than leaving it at whatever the default happens to be.

The thing that actually scales here is not the query, it is how often you rebuild the candidate set. Your tagged list barely changes between ticks. Bucket the tagged parts into a coarse grid by position once at load, keep the grid in sync with CollectionService GetInstanceAddedSignal and GetInstanceRemovedSignal, then each tick test only the buckets adjacent to the player’s cell. That is ROXAR0’s chunk suggestion, and the reason it is cheap is the same reason a per-tick radius query is not: the expensive work happens once instead of ten times a second.