Help Optimizing a function to find the closest unit

Help and Feedback Scripting Support
1

Hi! I’m currently working on a game where I need a unit to find the closest target. In this function, the unit looks in a radius around itself and detects if there is a target within the radius, if not, it searches the entire group of targets (A table). Problem is, when I’m calling this function for 200 units, it gets VERY resource intensive. Does anyone have any Ideas or insights to make it faster?

function FindClosest(UnitSpecified, UnitPropertiesSpecified)

	local Params = OverlapParams.new()
	
	Params.RespectCanCollide = false

	local UnitPos = UnitSpecified.HumanoidRootPart.Position
	local UnitsClose = workspace:GetPartBoundsInRadius(UnitPos, 10, Params)

	local PotentialTargets = {}
	local UnitParentName = UnitSpecified.Parent.Name

	for _, Object in pairs(UnitsClose) do
		local ObjectParent = Object.Parent
		if Object.Name == "HumanoidRootPart" and ObjectParent:IsA("Folder") then
			if ObjectParent.Humanoid.Health ~= 1 and ObjectParent.Parent.Name ~= UnitParentName then
				table.insert(PotentialTargets, ObjectParent)
			end
		end
	end

	if #PotentialTargets == 0 then
		PotentialTargets = UnitPropertiesSpecified["Attacking"]:GetChildren()
	end

	local closestTarget = nil
	local minDistance = math.huge

	for i, Target in pairs(PotentialTargets) do
		
		local TargetRoot = Target:FindFirstChild("HumanoidRootPart")
		
		if TargetRoot then
			
			local Distance = (UnitPos - TargetRoot.Position).Magnitude
			
			if Distance < minDistance then
				minDistance = Distance
				closestTarget = Target
			end
		end
	end

	return closestTarget, minDistance
end
4 Likes
2

GetPartsBoundsInRadius and any overlap params is usually very recourse intensive, try not using it and opt for some more distance checks with raycasts to verify etc…

3

Instead of just using it once and then searching the entire table, you should do another search but with a larger radius.

4

They aren’t if you don’t overuse them (like using a too large radius or using it every frame)

Raycasts won’t work if the units are obscured by parts.

5

that is technically on purpose. idk why i said it, random recommendation from me xd

6

Use a spatial query approach, like buckets or quadtree/octree. So you trade a bit of memory (and a bit of CPU time) to store where each unit is, for the purpose of saving a lot of CPU time.

This video explains it nicely: https://www.youtube.com/watch?v=OJxEcs0w_kE

7

You can utilize OverlapParams a bit more by putting the character that you want to find in a folder but GetPartBoundsInRadius is very quick for me here is a demo

GetPartBoundsInRadius.rbxl (66.5 KB)

local rootPart = script.Parent:WaitForChild("HumanoidRootPart")
local overlapParams = OverlapParams.new()

-- put all characters that don't have 1 health in the Findable folder
overlapParams.FilterType = Enum.RaycastFilterType.Include
overlapParams.FilterDescendantsInstances = {workspace.Findable}

function FindClosest(position)
	local parts = workspace:GetPartBoundsInRadius(position, 10, overlapParams)
	local closest = nil
	local magnitude = math.huge
	for index, part in parts do
		if part.Name ~= "HumanoidRootPart" then continue end
		local partMagnitude = (position - part.Position).Magnitude
		if partMagnitude >= magnitude then continue end
		closest, magnitude = part, partMagnitude
	end
	return closest, magnitude
end


while true do
	task.wait(1)
	
	local t = os.clock()
	local closest, magnitude = FindClosest(rootPart.Position)
	print(os.clock() - t)
	
	if closest == nil then continue end
	
	closest.Name = "Found"
	closest.Material = Enum.Material.Neon
	closest.Color = Color3.new(1, 0, 0)
	closest.Size = Vector3.one * 4
end

FindClosest takes about 0.00003 seconds to finish
it would take about 0.006 seconds to do 200 FindClosest (200 * 0.00003 = 0.006)
if we consider that 1 frame is about 0.016 seconds
we would have a remaining of 0.010 seconds for the frame
so that means 200 FindClosest uses about 37% of each frames time

image
image218×261 9.34 KB

one option you have is to use a actor for each unit and use FindClosest in parallel for each unit

if this is done on the serverside I’m not 100% sure how many threads Roblox servers have but I think it might scale based on how many players there are

another option you have is to put a invisible ball on the units and use a touch event to detect if something comes in range

another option you have is to do it the other way around where you make each client calculate the closest to there character and report it back to the server in remote events

as I’m not 100% sure what your trying to achieve I cannot really give you more advice for other ways to achieve what your trying to do

Conclusion
Your not going to be able to get faster then GetPartBoundsInRadius because its already very fast

doing 200 finds use about 37% of a frames time this is not acceptable to me

your going to have to find another way to do what you want if you tell me what your trying to do i can maybe help you find a different solution

1 Like