Less expensive alternatives for my "gravity well"

My physics simulation “powder game” is a game where every particle interacts with every other particle independently, and each particle is created through one of five classes held in ModuleScripts.

My “gravity-well” particle is part of class “Block” (although this is unimportant). The aim of gravity-well particle is to pull the other particles around it toward it and hold them there, almost floating. This all works well with the code I have wrote; however, I am worried that the game will suffer massive performance issues if too many exist at once. All threads are properly destroyed once a particle expires (25 seconds). It would only be possible for 3 per player to exist at any moment in time.

Maybe I am handling this good enough, but I have concerns about performance:

elseif self.Type == "gravity_well" then
	local m, x = self.SelfMesh.Position - (5 * self.SelfMesh.Size), self.SelfMesh.Position + (5 * self.SelfMesh.Size)

	local R3 = Region3.new(m, x)

	local foundObjects
    local mult = 90
    local hold = .075

	spawn(function() 
		while true do
			sWait(hold)
            mult = mult + hold

			foundObjects = workspace:FindPartsInRegion3(R3, self.SelfMesh, 75)

			for i = 1, #foundObjects do
				if gravity_wellWhitelist[foundObjects[i].Name] and i <= 75 then
					foundObjects[i].CanCollide = false

					foundObjects[i]:ApplyImpulse(((self.SelfMesh.Position - foundObjects[i].Position).unit * mult) * Vector3.new(1,0,1))

					foundObjects[i].CanCollide = true
				end
			end

		end 
	end)
	
	-- More code exists before if statement ends entirely.
    -- All created threads are disconnected/destroyed after 25 seconds.
	
end

All help is appreciated. :slight_smile:

1 Like

Instead of visiting every well for every particle every physics step, you could use the following approach:

Spatially partition your level into cells, e.g. with a square grid. Each cell keeps track of one vector, which describes the sum of the effects of all gravity wells on that cell. When a well is created, destroyed, or moves from one cell to another, update all cells to reflect this change. This way all cells always have an up-to-date “gravity vector”. For every particle every physics step, accelerate the particle according to the gravity vector of whichever cell the particle is in. Each particle only needs to consider one cell.

Before, the runtime of your physics step calculations scaled as O(nParticles * nWells), so having many wells quickly becomes too slow because nParticles tends to be large. With the thing I suggested, each step scales as O(nParticles + nCells * nWellsThatMoved). If your grid is very fine so nCells is large, and if wells tend to move across cell boundaries very often, this can actually be slower than before. There is also an additional calculation for updating all cells when a well is added or removed, but that’s equivalent to handling a well that moved across a cell boundary so it’s not bad.

If it’s acceptable in your case, you can also put a hard limit on the range of wells, so you only have to update the cells in a sphere around each well when they change cells/are created/are destroyed. Another refinement is to use a more complicated spatial partitioning, like a quadtree so that if there’s very few particles in an area, there will be one big cell for that area instead of like a hundred.

2 Likes

Thank you for the incredibly in-depth answer. I’m very excited to start working on this. One thing that went unmentioned in the original thread is that wells are entirely stationary and do not move (which is why I was relatively okay using my original solution), and also because there could never be more than 12-13 wells in existance at any point in time & threads destroy within 25 seconds. Conceptually though, and from a performance standpoint I like this a lot more. The whole goal of this project was to increase my coding knowledge and experience- and taking this on seems like it would continue to accomplish that goal. Thank you :grinning_face_with_smiling_eyes:

1 Like