How can i optimize distance checks?

[0786ideal (ideal)]

Soo i want to ask simple question, how do i optimize distance checks for tower defense game? We plan to make game run with few hundred enemies and tens of towers placed, but to accomplish this we need to know how to optimize distance checks

for now it looks like this:

for i, enemy in enemies do
    if (enemy.Position - tower.Position).Magnitude <= distance then 
        -- code
    end
end

[SeargentAUS (Seargent)]

One of the simplest ways to optimise a distance check is to store the position of any stationary objects in a variable, so you don’t access the position using OBJECT.Position each time. (So in this case, store the tower position)

[Pokemoncraft5290 (Based)]

Free ChunkSystem module for easy 2D/3D spatial partitioning

Hello everyone I made a resource today primarily for people that are newer to scripting and want to help optimize certain parts of their game. Have you ever worked on a game and found yourself having to iterate through lots of entities at once? Perhaps you’re making a game with AI entities that don’t move, but for client sided effects(sound,particles,animations, or even logic) you want to only consider entities that are close to your player’s camera. It can be pretty costly to…

Or maybe multithreading, but that’s honestly a headache.

[0786ideal (ideal)]

i think roblox does it automatically for you, also tower.Position is inside table

[drewbluewasabi (Drew)]

A really simple optimization is to use pure math rather than Vector3 object stuff
Here’s the math for a distance check (change a and b to the positions)

local distance = math.sqrt((a.X - b.X)^2 + (a.Y - b.Y)^2 + (a.Z - b.Z)^2)

This itself should make it much faster, but this is just one of many possible optimizations.

[drewbluewasabi (Drew)]

Kinda, but if you catch yourself writing thing.Position a lot, its better to do local pos = thing.Position and just use pos from there. This is a generally good practice anyway

To be clear, everytime you do thing.Position it has to search thing for Position, although it is pretty fast, it still can make a difference

[0786ideal (ideal)]

hmm i would rather consider this micro optimization, the problem is let’s say we have 400 enemies, i need to check 10 times per second for those 400 enemies, soo we perform magnitude checks almost 48000 for 120 towers soo 480000 checks per second, of course magnitude check will be disabled when target was… targetted? and changed to single enemy rather than 400, but still it’s a lot of lag, this is my main problem

[drewbluewasabi (Drew)]

@0786ideal

of course magnitude check will be disabled when target was… targetted?

what do you mean exactly?

[0786ideal (ideal)]

I mean that this system will look like this:

• loop every 10 frames through enemies
• Check x and y distances and if they are smaller or bigger (i want to optimize this)
• If target was found check if it’s in tower’s FOV
• Only check if current target is outside of the FOV
• Repeat process when player changes targetting mode (first, last, strongest ect.)
• Damage enemy

[drewbluewasabi (Drew)]

Here is a list of potential ways to make it run faster

• Use the “native codegen” feature (only works on server). What this does is it compiles your code to make it run faster. It works best with math-heavy code
  “In order to enable native code generation you need to put the --!native directive on top of your script.”
• Try to use as much pure math as possible and minimize using Vector3 operations (Vector3 + Vector3, etc.)
• Try to use a chunking system like @Pokemoncraft5290 mentioned, which speeds up things like distance checks. (Check out what they sent, but you might have to modify it)
• Generally try not to repeat things, use what I said in an earlier reply as an example

Optimizing past simple things can be time consuming and stressful, I suggest you test the waters first and only put much effort into it if you see it causing issues.
I won’t help you past here, but pretty much any response I would give you would probably just be a search here on the devforum

[tyridge77]

this things ancient and I wouldn’t recommend it , use something like an octree instead, there are good ones open source on roblox like quentys

[0786ideal (ideal)]

yk i would use octrees but i need 2D, soo it’s natural that grid is better in this case because it’s lighter*

[tyzone]

If many distance checks are happening at once, consider doing away with the sqrt function.

local distanceSq = (a.X - b.X)^2 + (a.Y - b.Y)^2 + (a.Z - b.Z)^2
if distanceSq <= unit.RangeSq then

Also if elevation is ignored in the range of units,

local distanceSq = (a.X - b.X)^2 + (a.Z - b.Z)^2

[tyzone]

Experimentally, I’m finding anything that isn’t flat-squared-distance to be slower than Vector3.Magnitude.

N = 10e6

local t0 = tick()
for i = 1, N do
	local p1 = Vector3.new(math.random(), math.random(), math.random())
	local p2 = Vector3.new(math.random(), math.random(), math.random())
end
print("Tare:",tick() - t0)
tare = tick() - t0

local t0 = tick()
for i = 1, N do
	local p1 = Vector3.new(math.random(), math.random(), math.random())
	local p2 = Vector3.new(math.random(), math.random(), math.random())
	local m = (p1 - p2).Magnitude
end
print("Vector3 magnitude (minus tare):", tick() - t0 - tare)

local t0 = tick()
for i = 1, N do
	local p1 = Vector3.new(math.random(), math.random(), math.random())
	local p2 = Vector3.new(math.random(), math.random(), math.random())
	local m = math.sqrt((p1.X - p2.X)^2 + (p1.Y - p2.Y)^2 + (p1.Z - p2.Z)^2)
end
print("Magnitude (minus tare):", tick() - t0 - tare)

local t0 = tick()
for i = 1, N do
	local p1 = Vector3.new(math.random(), math.random(), math.random())
	local p2 = Vector3.new(math.random(), math.random(), math.random())
	local mSq = (p1.X - p2.X)^2 + (p1.Y - p2.Y)^2 + (p1.Z - p2.Z)^2 
end
print("Squared magnitude (minus tare):", tick() - t0 - tare)

local t0 = tick()
for i = 1, N do
	local p1 = Vector3.new(math.random(), math.random(), math.random())
	local p2 = Vector3.new(math.random(), math.random(), math.random())
	local mSqFlat = (p1.X - p2.X)^2 + (p1.Z - p2.Z)^2 
end
print("Squared flat magnitude (minus tare):", tick() - t0 - tare)

Tare: 2.2166
Vector3 magnitude (minus tare): 0.2450
Magnitude (minus tare): 0.2939
Squared magnitude (minus tare): 0.2606
Squared flat magnitude (minus tare): 0.1641

[drewbluewasabi (Drew)]

Doing some tests I found that most of the time spent on the manual method is simply just the indexing of the Vector3

--!strict

local ta = {}
local tb = {}

--generate some random vectors
for count = 1, 1000 do
	ta[count] = Vector3.new(math.random(), math.random(), math.random())
	tb[count] = Vector3.new(math.random(), math.random(), math.random())
end
wait(2)

local start = os.clock()
for count = 1, 1000 do
	local a, b = ta[count], tb[count]
	local magnitude = (a - b).Magnitude
end
print(os.clock() - start)

local start = os.clock()
for count = 1, 1000 do
	local a, b = ta[count], tb[count]
--The most expensive part here
	local e = a.X
	local e = b.X
	local e = a.Y
	local e = b.Y
	local e = a.Z
	local e = b.Z
end
print(os.clock() - start)

Here’s the output: (consistently)