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.
4 Likes
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
1 Like
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)]
3 Likes
I’m not sure I’d call that multithreading, more of concurrent processing.
Roblox does not support true multithreading …
2 Likes
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
1 Like
I was just reading about that … a similar effect to multithreading. Do you have an example of that?
1 Like
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
1 Like
I wonder if that could just be added… Guess not
2 Likes
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.
2 Likes
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.
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.
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
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
1 Like
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.
1 Like
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.
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 …
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.
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:
-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
-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
-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
-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.
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.
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)
2 Likes
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.
1 Like
this is actually insane, combined script activity of the npc script and the actor script never goes higher than half a percent for 1000 rendered npcs, thank you
I have a thread discussing about measuring the number of parallel threads that can be utilized by a player’s device:
A parallelized raycast minimap project:
And a Roblox game that actively uses parallelization for gameplay:
You can try out the game and see the parallel work in action via the microprofiler!
2 Likes
This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.