Most efficient way to compare hundreds (potentially thousands) of positions while keeping script activity low?

[Pa_roy0]

Hello, my game has a grid system, where the entire map is split into 5 by 5 stud blocks (with no unique identifiers), and I also have npcs that move around said grids using lerp (although I do plan to find a different way to do so in the future), and it works well enough

however, the problem for me is that I want to know which grid the npc is currently above pretty much at all times. I haven’t tried spatial queries, because I’ve heard that raycasts are more efficient performance wise, and I haven’t used region3 because it’s deprecated

-I have used short (1-2 stud) downcasts, however, with them, updating 200 npcs hiked script activity to ~20% as well as with frequent frame drops

-so I have moved on to storing the positions of all of the grids on the map (~1300) in a table and comparing the position of the npc to that, however, after playing around with it for a few days I couldn’t get the script activity lower than 11% for every 200 npcs it has to update, although I haven’t noticed nearly as many frame drops with it

here is the current setup I am using

local tabletoinclude = {}
for i, v in ipairs(workspace.CloseUpGrids:GetDescendants()) do
	if v.Name == "Grid" then
		table.insert(tabletoinclude, v)
	end
end
local postable = {}
for i, v in ipairs(tabletoinclude) do
	postable[v.Position] = v
end

while wait(.1) do
	for i, folder in ipairs(workspace.People:GetChildren()) do
		for j, workermodel in ipairs(folder:GetChildren()) do
			if workermodel:IsA('ObjectValue') then continue end
			local humanoidpos = workermodel.HumanoidRootPart.Position
			local closest = 99999 --didn't use math.huge because i am unsure of how performance heavy getting/operating with the constant assigned to it is
			local chosenpos
			for position, v in pairs(postable) do
				local distance = (humanoidpos - position).Magnitude
				if distance < closest then
					closest = distance
					chosenpos = position
				end
			end
			game.ReplicatedStorage.Workers:FindFirstChild(workermodel.ID.Value, true).CurrentGrid.Value = postable[chosenpos]
		end
	end
end

any advice?

[Pa_roy0]

update: I tried running the script using native code generation since I’ve heard it deals with math better but even if it did improve the script activity it was not noticeable at all, so it still sat at 11-12% for the 200 npcs I was testing it on

[bestruaridh12 (ruaridh)]

I think you could try multithreading while comparing the positions, but not while setting any values

[2112Jay]

This can get complicated. How deep do you want to go …
Research: Spatial hash grid indexing or Spatial quadtrees indexing.
I’ve never tried that in Roblox.

[Pa_roy0]

yeah I have a slight suspicion that multithreading might not be… the go to method in this situation…
thanks though, I’ll look into what you suggested

[savio14562 (savio14563)]

You should try storing your grids in a 2D or 3D table, so you can just do

local gridSize = 5 
characterGrid = grid[math.floor(pos.X/gridSize), math.floor(pos.Z/gridSize)]

[2112Jay]

@Pa_roy0

multithreading

I’m not sure I’d call that multithreading, more of concurrent processing.
Roblox does not support true multithreading …

[bestruaridh12 (ruaridh)]

When i said using multithreading i meant putting the script under an Actor and then calling task.desynchronize() before computations, then calling task.synchronize() before setting any values

[2112Jay]

I was just reading about that … a similar effect to multithreading. Do you have an example of that?

[bestruaridh12 (ruaridh)]

I was making a magnet system for fun and for each magnet it would go through all other magnets to calculate the coulombic force. Since i didn’t have to set anything, I can call task.desynchronize() before the calculations, then call task.synchronize() when im ready to set the final force for the part. Ig this would allow me to make ten thousand magnets if i really wanted to

[2112Jay]

I wonder if that could just be added… Guess not

[SpikyTexasCactus]

You could split up the grid into large chunks, so that you’ll find which chunk the npc is in first, then go through each individual grid inside the chunk.
It should cut out unnecessary calculation on grids that are way to far from the npc.

[Prototrode (Vernumerator)]

@2112Jay

I wonder if that could just be added…

That’s not how it works, each parallel thread can only be declared when in a separate script parented under a separate Actor. If you just desynchronize the main script you are effectively still running in serial. You need to branch out the work among multiple Actors and then consolidate the calculation results. I suggest you read more about Parallel Luau in the Roblox docs.

And for the OP, theres numerous optimizations (even microoptimizations) that could be done to save performance. But before doing those, you should profile your script to see exactly where the performance loss is going to.

Using MicroProfiler | Documentation - Roblox Creator Hub

@Pa_roy0

	for i, folder in ipairs(workspace.People:GetChildren()) do
		for j, workermodel in ipairs(folder:GetChildren()) do

You can simplify the nested loop into a single :GetDescendants() loop to avoid calling :GetChildren() multiple times. Just make sure you are filtering the instances correctly in the loop.

@Pa_roy0

for position, v in pairs(postable) do

The pairs function is unnecessary in Luau because of generalized iteration. You can save performance by omitting it since pairs() is a function call while generalized iteration is a syntax. It can be simplified into for position, v in postable do

@Pa_roy0

game.ReplicatedStorage.Workers:FindFirstChild(workermodel.ID.Value, true).CurrentGrid.Value = postable[chosenpos]

Not only is this line error-prone (you are using FindFirstChild which DOES NOT guarantee finding the instance), you can do one of the most trivial optimization here: Aliasing the Workers instance by storing it in a variable outside of the loop and then using the variable instead. When you write out the path of the instance, the game has to reevaluate the hierarchy to find the instance, which can impact performance if done frequently enough.

Also, a suggestion regarding native codegen, you can make the actual math stuff a separate function and only mark that as native (using Luau function attributes) instead of the whole script. Native codegen does well with math-related workloads, but poorly with frontend tasks.

@native local function closest(at: Vector3): Vector3
	local closest: number = math.huge
	local closestPos: Vector3 = Vector3.zero
	for pos in postable do
		local dist: number = (at - pos).Magnitude
		if dist < closest then
			closest = dist
			closestPos = pos
		end
	end
	return closestPos
end

[Starlight_Salvatore (Salvatore)]

Looping through all the cells and comparing their positions to your NPC’s position would be a bad idea since cells are only used to represent regions, so they are indexed with a key representing their position.

For most games storing cells would work by labelling them as a Vector3 whose integers mark the position of the cell relative to the size of the cell. This is because the only real benefit of using cells is for position querying of objects. So the cell of size 100 labelled as 0,1,0 would be at the position 0,100,0 and would represent the cell above the origin cell assuming that the origin cell would be at the position 0,0,0. This is the easiest way to represent regions as the name of the cell directly correlates to the cell’s position. It also helps us use algebra to identify cells around an object. If you are in cell 10,15,41 the cell under your current cell would be 10,14,41.

So why is it done that way, well to find the cell an object is in you can round the position of the object by the cell size to get the name of the cell the object is in. So rather than comparing the position of the object to the position of every cell you could just round the position and get the cell. If you have information attributed to cells then you’d store the cell in a dictionary where the key is the position, much like what you are already doing.

local origin = Vector3.new(0,0,0) -- Position of the origin cell or central cell (center of the map)
local position = Vector3.new(1,41,20) - position of the object you are checking
local cellSize = 5 -- Size of all cells
print(
Vector3.new(math.floor((position.X + cellSize / 2) / cellSize),
math.floor((position.Y + cellSize / 2) / cellSize),
math.floor((position.Z + cellSize / 2) / cellSize))
)
--> 0, 8, 4 -- The cell

Since the point of using cells in the first place is position querying can I ask, why do you want to know the cell that an NPC is in at all times? What are you doing with that information? If you store cells this way you can quickly get the cell an NPC is in using their position, but how does knowing that cell constantly benefit you?

If you let me know that it would help me help you.

[Glitchifyed]

From what I’ve read, I believe it is true multithreading. As far as I know, the render thread still depends on the other threads for whatever reason, which is why you can still experience stutters even while using parallel luau on the client.
My presumption could be completely wrong, but that is what it looks like and how it has behaved during my testing of the feature.

[2112Jay]

I figured 小蜜梨 knew what to do other than tell us we are wrong. I was just testing because I really don’t know. That about all I could find on it. People saying it can be done no examples …

[Juicy_Fruit]

i dont see a concrete use case on how you are implementing this but;

do all npcs need to know or have magnitudes of everyone on the map truly at all times? if not explore spatial partitioning

potentially use physics calculations to determine the theoretical time before a worker npc is expected to breach and change grid (would be more beneficial with larger grid blocks).

the above is quite the demanding task though.

[Pa_roy0]

hello again everyone, thanks for the feedback, and special thanks to @Prototrode for all of the optimization tips, I am genuinely flabbergasted at the amount of engine knowledge this man has.

I got a setup that I am happy with, expanding on @savio14562 and @Starlight_Salvatore’s concepts.

I looked into quadtrees and spacial hashes as per @2112Jay ‘s suggestion, but I dont think either are particularly useful in my case, quadtrees because I don’t deal with particularly complex geometry while pathfinding and spacial hashes because I couldn’t think of a way to solve the initial problem of comparing the npcs’ positions.

By the way, I did analyze the game using MicroProfiler and unsurprisingly the loop for choosing the closest position took up 90% of the calculation time

some notes in case it still matters:

@Starlight_Salvatore

but how does knowing that cell constantly benefit you?

-a lot of functionality in my game depends on the amount of workers allocated to a certain building and whatnot, and it’s also used in estimation math as a reliable “last seen” position before the npc stops getting rendered (under certain conditions) so that a bunch of estimation math can be ran instead

@Juicy_Fruit

potentially use physics calculations to determine the theoretical time before a worker npc is expected to breach and change grid (would be more beneficial with larger grid blocks).

-I thought of that but ultimately decided against it due to the potential difficulty in maintaining a script like this in case the npc classes I add in the future differ substantially from the current workers

@Prototrode

You can simplify the nested loop into a single :GetDescendants() loop to avoid calling :GetChildren() multiple times. Just make sure you are filtering the instances correctly in the loop.

-in my case that will return a bunch of stuff like constraints and welds that I don’t really want to have in the loop

@Prototrode

Not only is this line error-prone (you are using FindFirstChild which DOES NOT guarantee finding the instance)

-I have 50 or so lines of checks dictating what goes into the worker folder, as well as when it gets removed, so in my case its genuinely better if it errors if something goes wrong than silently being ignored, to simplify debugging

in the end, this is the final script:

local workersrepfolder = game.ReplicatedStorage.Workers

local tabletoinclude = {}
for i, v in ipairs(workspace.CloseUpGrids:GetDescendants()) do
	if v.Name == "Grid" then
		table.insert(tabletoinclude, v)
	end
end
local postable = {}
for i, v in ipairs(tabletoinclude) do
	postable[tostring(v.Position.X) .. tostring(v.Position.Z)] = v
end

@native function getgridpos(number, offset)
	return math.floor((math.floor(((number - offset) / 5) + 0.5) * 5) + offset)
end


while wait(.1) do
	for i, folder in ipairs(workspace.People:GetChildren()) do
		for j, workermodel in ipairs(folder:GetChildren()) do
			if workermodel:IsA('ObjectValue') then continue end
			local humanoidpos = workermodel.HumanoidRootPart.Position
			local finalstring = tostring(getgridpos(math.round(humanoidpos.X), 1)) .. tostring(getgridpos(math.round(humanoidpos.Z), 1)) --I am not too sure about this usage of tostring and .., please correct me if there's something wrong with it
			workersrepfolder:FindFirstChild(workermodel.ID.Value, true).CurrentGrid.Value = postable[finalstring]
		end
	end
end

(the offset in the getgridpos function is because my grids arent located at positions which are multiples of 5 despite being 5 studs long, I know, bad practice, but honestly I don’t want to bother with it right now)

In the end it handles 1000 npcs at 10% script activity and no stutters, and I can honestly deal with that, but just in case, @Prototrode , could you please explain how to call a function (in this case the getgridpos function) from a different script parented to an actor? (I’ve never touched them before)

Thank you.

[Prototrode (Vernumerator)]

Parallelization is a REALLY complicated topic to developers who have never heard of it before. What I’m about to explain will make no sense.

@Pa_roy0

could you please explain how to call a function (in this case the getgridpos function) from a different script parented to an actor?

You don’t. Each Actor is a separate Luau VM that runs in an isolated environment. It’s impossible for Actor scripts to directly access other script’s contents, and this includes Modulescripts. When you require a Modulescript from an Actor script, it actually clones the module so it remains isolated; any changes made to the module from the Actor script will not propagate, and likewise any changes made to the module from the main environment will not replicate to Actors.

The ideal setup that I know of for Parallel Luau is you putting all the functions directly inside the Actor script. To command the Actor to perform work, you send a BindableEvent or an Actor message (Actor:SendMessage()) with your own instructions. The Actor script reads the instructions, does the task it’s asked, and then (if necessary) relays the results back to the main script using the same technique or with SharedTables. Otherwise, the Actor script will enter serial execution and process the results itself and do thread-unsafe operations in situ.

Below is a schematic of what the described processes can look like:

Below is a screenshot from one of my projects that used parallelization. This is what the frametime can look like:

And here’s what a typical parallel system could look like in your game:

--marshaller
local function sendTask(instructionTable)
    for _, actor in actorTable do
        actor:SendMessage('Instruction', instructionTable)
    end
end

returnSignal.Event:Connect(function(result)
    print(result)
    serialWork(result)
end)

--each Actor script
script.Parent:BindToMessageParallel('Instruction', @native function(instruction)
    parallelWork()
    task.synchronize()
    serialWork()
    returnSignal:Fire(results)
end)

[Glitchifyed]

From my testing it is to be used more like multithreading in other applications of computer science; like for example a Unity game using the Jobs system.