Detect proximity of hundreds of vectors efficiently

Help and Feedback Scripting Support
#1

My game has two modules for abilities, client and server. Client has visuals only, no raycast checks nothing, the server is the one that handles all the collision checks and only uses number/data to keep track of where the projectile is. This is all fine and it’s pretty standard, however the issue lies in how different abilities interact with EACHOTHER.

For the experiment I’ve tried to test it to see if it can perform magnitude checks of 200 vector3 positions. At 60fps it takes up 8% script usage which is a bit too much. I do understand 200 projectiles will never really be in my game at once but I need to know how to optimize it to it’s maximum capacity to lower server load.


local invisibleProjectiles = {}
for i = 1,200 do 
	invisibleProjectiles[i] = {p = Vector3.new(math.random(1,200), math.random(1,200), math.random(1,200)), s=Vector3.new(math.random(1,5), math.random(1,5), math.random(1,5)), priority = math.random(1,8)}
end


local function check(id)
	if not invisibleProjectiles[id] then
		return
	end
	local cp = invisibleProjectiles[id].p
	local cs = invisibleProjectiles[id].s
	
	for iid, t in invisibleProjectiles do 
		if iid == id or invisibleProjectiles[id].priority > t.priority then
			continue
		end    
		local magDifference = (t.p-cs).Magnitude
	end
end

game:GetService('RunService').PreRender:Connect(function()
	for id,_ in invisibleProjectiles do 
		check(id)
	end
end)
#2

Have you considered looking at an algorithm like octrees for collision detection?

2 Likes
#3

Aren’t those meant for static objects? These projectiles will be constantly moving

#4

They also would create unwanted behaviour in your application: if two points are close enough to collide, but are right on the border between two octants and thus in different octants, they will not collide.

image
image1100×752 26.6 KB

For example, if the collission tolerance is the distance between these two points, then these points should collide. But they won’t, because they’re in different octants.

Anyways, I wrote a script for you. It’ll generate a bunch of points, then check if any points are in the same octant. If they are, they’ll be made red.

image
image972×860 31 KB 

local function isPointWithinBounds(point, minBound, maxBound)
	return point.X >= minBound.X and point.X <= maxBound.X  
		and point.Y >= minBound.Y and point.Y <= maxBound.Y
		and point.Z >= minBound.Z and point.Z <= maxBound.Z
end

local function divideVolumeInEights(minBound, maxBound)
	local subdivisions = {}
	local halfSize = (maxBound - minBound) / 2
	local center = minBound + halfSize

	for x = 0, 1 do
		for y = 0, 1 do
			for z = 0, 1 do
				local offset = Vector3.new(x, y, z) * halfSize
				local newMinBound = minBound + offset
				local newMaxBound = newMinBound + halfSize
				table.insert(subdivisions, {newMinBound, newMaxBound})
			end
		end
	end
	return subdivisions
end

local function visualizeDivision(minBound, maxBound)
	local part = Instance.new("Part")
	part.Size = maxBound - minBound
	part.Position = minBound + part.Size / 2
	part.Anchored = true
	part.CanCollide = false
	part.Color = Color3.new(1, 0, 0)
	part.Transparency = 0.9
	part.Parent = workspace
	return part
end

local function octree(points, minBound, maxBound, visualize, depth)
	depth = depth or 1
	if #points <= 1 or depth > 3 then
		-- Terminal condition: either only one point or max depth reached.
		if visualize and #points > 1 then
			for _, entry in ipairs(points) do
				if entry[2] then
					entry[2].Color = Color3.new(1, 0, 0)
				end
			end
		end
		return
	end

	local subdivisions = divideVolumeInEights(minBound, maxBound)

	for _, bounds in ipairs(subdivisions) do
		local subMin, subMax = bounds[1], bounds[2]
		local pointsInDivision = {}

		if visualize then
			visualizeDivision(subMin, subMax)
		end

		for _, entry in ipairs(points) do
			local point, part = entry[1], entry[2]
			if isPointWithinBounds(point, subMin, subMax) then
				table.insert(pointsInDivision, {point, part})
			end
		end

		if #pointsInDivision > 0 then
			octree(pointsInDivision, subMin, subMax, visualize, depth + 1)
		end
	end
end

local function generateRandomPointsInVolume(minBound, maxBound, quantity, visualize)
	local points = {}
	for i = 1, quantity or 100 do
		local x = math.random(minBound.X, maxBound.X)
		local y = math.random(minBound.Y, maxBound.Y)
		local z = math.random(minBound.Z, maxBound.Z)
		local point = Vector3.new(x, y, z)

		local part
		if visualize then
			part = Instance.new("Part")
			part.Size = Vector3.new(0.4, 0.4, 0.4)
			part.Position = point
			part.Anchored = true
			part.CanCollide = false
			part.Color = Color3.new(0, 1, 0)
			part.Transparency = 0
			part.Parent = workspace
		end

		table.insert(points, {point, part})
	end
	return points
end

-- Test setup
local minBound, maxBound = Vector3.zero, Vector3.new(50, 50, 50)
local points = generateRandomPointsInVolume(minBound, maxBound, 100, true)
octree(points, minBound, maxBound, true)
#5

Octrees don’t compare their origin so that issue doesn’t exist. When octrees attempt to query in a radius, they check the bounding boxes, meaning that the two dots will query in your example.

#6

Then I guess I’m not implementing them properly.

In any case, we can even get around the issue with my implementation by doing the operation twice, once offset by 0.5*octant size

#7

trying to implement the octree with this implementation right now, I tried an open source one but it was quite bad hehe

#8

Use client for hitboxes, it's much more performant, security checks can be done to make sure player isn’t cheating, remember that most of cheats that you want to prevent are impossible due to how replication works

#9

It’s still pretty performant on server, it’s only maths, no parts being altered. It’s running at 30fps only since its the server too

#10

still doing math on client is more performant, you can consider multi-threading

#11

Okay, I considered what you said and I understand. Instead of considering points, I’ll consider cubes and allow them to be registered under multiple octants.