What I am doing
I am working on a script that pushes characters apart when they are overlapping with each over. I have an array of cframes for each of the character. The problem
I did manage tp cpde this, however the code is VERY slow. Because the number of pairs in the array would be
nC2 (math combination formula)
The code has a significant performace hit as the array size increases.
How can I reduce the number of calculations?
My code
for i: number, cframe: CFrame in ipairs(self.cframes) do
for j: number = i + 1, #self.cframes do
local diff: Vector3 = (cframe.Position - self.cframes[j].Position) * Vector3.new(1, 0, 1)
local mag: number = diff.Magnitude
if mag < characterRadius * 2 then
self.cframes[i] += (diff / mag) * (characterRadius - mag / 2) / 2
self.cframes[j] -= (diff / mag) * (characterRadius - mag / 2) / 2
end
end
end
Is it necessary to iterate over the entire table to find nearby parts that need to be pushed? Perhaps you can instead create a hitbox around the target and process only the parts that are touching the hitbox to lower the amount of processing.
I am pretty sure there’s some very specific and well-optimized algorithm for the kind of task you’re doing here. Try digging around the internet for that.
In addition to that, the most obvious solution to reducing lag would be to optimize your code (shocking, I know). Wherever you see repetition, it can be simplified to reduce the number of operations. There are a few examples inside your code:
You’re creating a new Vector3 (Vector3.new(1, 0, 1)) for each calculation. This is really redundant since you can just store it in a variable outside of the nested loop and use it as is.
You seem to have repeated an expensive calculation here. The expression (diff / mag) * (characterRadius - mag / 2) / 2 can be stored so that it only needs to be calculated once instead of twice.
Also, you are apparently using OOP via the self variables? I don’t really see a reason for that, it just doesn’t seem right to be using that for something this expensive and repetitive; likewise, unless it’s absolutely necessary to store everything in a table, I would just take the result and use it immediately.
Thanks for the detailed answer!
I got a couple of questions
First, I dont’t really understand how this is faster. Finding parts that are nearby seems reasolable, however to find those parts, ins’t roblox engine doing the same thing, comparing object positions anywhay?
Anothers is that, is this still the case? Roblox announsed Vector as primitive a while ago. My understanding was that vectors are no longer created, but just a value like numbers are.
That somehow didnt cross my mind at all. Thanks
I am doing a “Semi-OOP”. I just recently learned that metatables are slow, so I am not using them. Functions are just stored inside the table. As for why Im stuffing everything in the table is because I am grouping numbers of entities together and moveing them with workspace:BulkMove()
Could you not just create some new collision groups. Put a “personal bubble” on each character. Then make it so the bubbles can only collide with other bubbles. Then the physics engine would handle all this for you.
Although I don’t know much about the internals of the roblox engine, I suspect that there are well-optimized querying algorithms for 3D space, that most likely do not require iteration over every single part like what you did with your code. An example would be k-d trees whose operations usually have a time complexity of O(log n), however once again I have no idea what roblox is using internally.
Based on my understanding:
You’re still repetitively calling the Vector3.new function. Unless roblox explicitly optimized this specific function in the internals of Luau (which is super unlikely), it’s still going to perform worse because it’s doing thousands of function calls.
Also, the Vector3 primitives you’re referring to sounds a lot like the upcoming “static values”:
In which case it would be suitable for the job since they are simply just stored Vector3 values which is exactly what you should be using.
Understandable, but I noticed a warning on the API reference discouraging you from using this function unless you’re sure that part translation is the bottleneck in your code. So this makes me wonder, have you performed a proper benchmark of your code to see which process/calculation is the most demanding? If part translation isn’t the problem then the insane table creations wouldn’t be necessary, which allows you to simplify the code even further.
PS, that k-d tree thing might be exactly what you’re looking for.
