How to search for targets more efficiently?

[Riamble]

Below here I have a function for my turret script that searches for the nearest zombie to shoot. My problem is that there are multiple turrets and hundreds of zombies to find which causes a bad lag spike.

Is there any way I can actually optimize this?

function findTarget()
	local possibleTargets = CollectionService:GetTagged("Zombie") --This is the laggy part. You are basically looking through the zombies in the whole server and finding the nearest one (not very efficient)

	for i, v in pairs(possibleTargets) do --looks through the possible targets that are tagged "enemy" and checks if they are near and not dead
		if (turret.PrimaryPart.Position - v.PrimaryPart.Position).Magnitude < range and v.Humanoid.Health > 0 then
			Target = v
		end
	end
end

[wafflechad]

A good (probably only) option is to use some kind of spatial data structuring and querying.

If the density of roblox parts isn’t too high and the range isn’t insanely large, using the Roblox provided querying functions such as Workspace:GetPartsBoundsInBox() or Workspace:GetPartsBoundInRadius() is a good idea. IIRC, using the ignore list won’t improve the performance of these functions besides possible benefits from having the filtering done on the engine side instead of in luau. You might get a performance benefit from using physics groups and having one dedicated to zombie primary parts and using that in the query filters.

If that is not good enough, you could implement the data structure and querying yourself on the luau side for more manual control. An easy method is to just make a 2d/3d grid, with which you can tune the extents and density of cells to your pleasing. Then you can just track what zombies are in which cell by inserting and removing references in each cell. Then you can do spherical, rectangular or even conular queries around the various turrets to narrow down the number of zombies you need to check for each turret.

In both cases, you are reducing an O(A*B) time complexity situation into a O(A) time complexity (A: #turrets, B: # zombies) assuming a homogenous zombie density. This does not necessarily mean though that it will be faster than just checking every zombie against each turret, especially if the turrets and zombies are organized very densely.

[Riamble]

Seems plausible, will definitely read into this!