Optimizing basic code

[EpoxTime]

This is code for fluid sim project. The basic idea is it makes a grid of balls or “particles” and then every run step it goes to the first particle, finds the distance of all the other particles from it, and moves away from the closest particle.

I’m looking for ways to make this code optimized. Specifically how can I make it so it doesn’t have to loop through each particle each time, and instead only the particles near the current particle. Any ideas? Because why look for every particle if they wont even meet the distance requirement.

Code:

Size = {8,8,8}
PreviousPosition = Vector3.new(0,0,0)--Also effects starting position
ParticleNumber = 0

for i = 1,Size[3],1 do
	for i = 1,Size[2],1 do
		for i = 1,Size[1],1 do
			--make particle
			Particle = Instance.new("Part")
			Particle.Shape = "Ball"
			Particle.Size = Vector3.new(1,1,1)
			Particle.Anchored = false
			Particle.Position = Vector3.new(PreviousPosition.X + 1, PreviousPosition.Y, PreviousPosition.Z)
			Particle.Parent = game.Workspace.Simulation.Particles
			
			--Name Particle
			Particle.Name = tostring(ParticleNumber)
			ParticleNumber += 1
			
			--Make attachment
			Attachment = Instance.new("Attachment")
			Attachment.Parent = Particle
			
			--Make vector force
			VectorForce = Instance.new("VectorForce")
			VectorForce.Force = Vector3.new(0,0,0)
			VectorForce.Name = "Force"
			VectorForce.RelativeTo = "World"
			VectorForce.Attachment0 = Attachment
			VectorForce.Visible = true
			VectorForce.Parent = Particle
			
			--Adjust position
			PreviousPosition = Particle.Position
		end
		PreviousPosition += Vector3.new(0,1,0)
		PreviousPosition = Vector3.new(0,PreviousPosition.Y,PreviousPosition.Z)
	end
	PreviousPosition += Vector3.new(0,0,1)
	PreviousPosition = Vector3.new(PreviousPosition.X,0,PreviousPosition.Z)
end

Particles = game.Workspace.Simulation.Particles:GetChildren()

local RunService = game:GetService("RunService")
RunService.Stepped:Connect(function()
	for i,v in pairs(Particles) do
		local CurrentName = v.Name
		
		for i,j in pairs(Particles ) do
			if v == j then continue end
			local PositionOne = v.Position
			local PositionTwo = j.Position

			local X1 = PositionOne.X
			local Y1 = PositionOne.Y
			local Z1 = PositionOne.Z

			local X2 = PositionTwo.X
			local Y2 = PositionTwo.Y
			local Z2 = PositionTwo.Z

			local Distance = math.round(math.sqrt((X2-X1)^2 + (Y2-Y1)^2 + (Z2-Z1)^2) * 100) /100 

			if Distance <5 then	

				local Constant = 200
				local Factor = 1

				local Multiplier = Constant*Distance^-Factor
				local LookAt = (PositionOne - PositionTwo).Unit
				local PushValue = LookAt * Multiplier

				v:FindFirstChild("Force").Force = PushValue
			end
		end
	end
end)

Thanks!

[LuffyReformed (Luffy)]

If you really feel like you needed to optimize, then the best place to start would be to introduce some sort of spatial partitioning data structure for storing your objects in. By doing this, if all works out and you use the right data structure, you should be able to decrease the number of objects needed to loop through to find the closest object to another. Here is a wikipedia page that contains various spatial partitioning data structures you could use ( I would recommend using quad-trees for something like this )

Link: Space partitioning - Wikipedia

[EpoxTime]

I will look into this, thanks!

[Katrist]

By the way, you can do space partitioning really easily by using :GetPartsInPart, with an argument of a part that fits the space you want to search.

[EpoxTime]

I did do that using get parts in parts and a hitbox, but since it searches once every step it actually added more lag since it has to search all parts anyways to find that

[Katrist]

@FlawedFunction

it actually added more lag

How would it have added more lag if you were searching for fewer instances each time? You were either implementing it wrong or not benchmarking it properly.

Like for example, your initial code would do O(n^2), meaning it would have to loop over every parts, for every part in your table. Instead of looping over every part twice, you would have to loop over only the parts closest, for every part in your table.

At the least, it shouldn’t create more lag.

[EpoxTime]

I was probably implementing it wrong. How should I? This is the way I did it:

First I made a larger hitbox ball welded to the particle:

			--[[
			Hitbox = Instance.new("Part")
			Hitbox.Shape = "Ball"
			Hitbox.Size = Vector3.new(8,8,8)
			Hitbox.Anchored = false
			Hitbox.CanCollide = false
			Hitbox.Position = Particle.Position
			Hitbox.Transparency = 0.999
			Hitbox.Massless = false
			Hitbox.Name = "Hitbox"
			Hitbox.Parent = Particle
			
			--make hitbox
			
			
			--make weld
			Weld = Instance.new("Weld")
			Weld.Parent = Particle
			Weld.Part0 = Particle
			Weld.Part1 = Hitbox
			
			]]

Then I found parts in part of that

		--local RelevantParticles = workspace:GetPartsInPart(v.Hitbox)

then I used the found parts and looped through only those. I’m sure there is a better or correct way but this is y first time using get parts in part.

[LuffyReformed (Luffy)]

The approach you mentioned is still O(n^2). In fact, it also has the same least case time complexity, just the average case time complexity has changed. While there may be many reasons why it might cause more lag, it could just be the fact that he is just introducing more parts, which are unanchored and welded, that the physics engine etc have to account for. So to still use that same approach but avoid creating the parts/welds, perhaps you could use Region3?

[Katrist]

Yeah sorry, I was talking about the average time complexity. Region3 would also work, but as I’ve heard, GetPartsInParts was supposed to supersede Region3, so I’m not sure if the speed difference is worth it.

You could also use workspace:GetPartBoundsInBox too:

WorldRoot | Documentation - Roblox Creator Hub

If this doesn’t work though, the last solution would be to create a custom octree for your parts.

@FlawedFunction