How to make flood fill/bfs faster?

Help and Feedback Scripting Support
1

Hi guys ive been doing voxel destruction stuff for a long time now but I still can’t figure this out so currently my module took search time for preweld is 436ms ig it a lot it don’t even big map but after preweld it getting 40ms-12ms but I still want a way to optimize it and my search split time is 850ms-750ms on the urban house I already create topic about it but I only get suggest to rewrite which I does but I still can’t figure thing out

the physics code (it so messy don’t worry about it)

local physic = {}

physic.groups = {} -- :(
physic.fallTable = {}
physic.groupLookup = {}

local runService = game:GetService("RunService")
local collectionService = game:GetService("CollectionService")

local blink = require(game.ReplicatedStorage.Blink.Server)
local config = require(script.Parent.Config)
local msConvert = require(script.Parent.MSConvert)
local weldCache = require(script.WeldCache)
local queuer = require(script.Parent.Queue)
local sat = require(script.Parent.SAT)
--local fea = require(script.FEA)
local cache = weldCache.new(10000, 500)

local ingerityRemote = game.ReplicatedStorage.Assets.Remote.Bindable.Server.ingerity
local impactRemote = game.ReplicatedStorage.Assets.Remote.Bindable.Server.impact

--[[
1. Weld Every parts efficiently!!!
]]

local isDebug = false
local debugLog = {}
local visited = {}
local weldQueue = {}
local weldLookup = {}
local ids = {}
local deleteTable = {}
local currentId = 0
local currentGroupId = 0
local groupFolders = {}
local impactLookup = {}

local impactQueue = {}

local function assignId(a: BasePart)
	local id = ids[a]
	
	if not id then
		currentId += 1
		id = currentId
		ids[a] = id
	end
	
	return id
end

local function getKey(a: BasePart, b: BasePart): string
	if a:HasTag("Anchored") and not b:HasTag("Anchored") then
		a, b = b, a
	end
	
	local aKey, bKey = assignId(a), assignId(b)
	
	if aKey < bKey then
		return aKey .. bKey
	else
		return bKey .. aKey
	end
end

local function hasRequiredTag(part)
	return part:HasTag("Anchored") or part:HasTag(config.tag)
end

local function canConnect(a: BasePart, b: BasePart)	
	if hasRequiredTag(a) ~= hasRequiredTag(b) then
		return false
	end
	
	if a:HasTag("NoPhysics") ~= b:HasTag("NoPhysics") then
		return false
	end
	
	if physic.fallTable[a] ~= physic.fallTable[b] then
		return false
	end
	
	if not a:HasTag("Anchored") and not b:HasTag("Anchored") then
		if physic.groups[a] ~= physic.groups[b] then
			return false
		end
	end
	
	return true
end

local function getConnected(part: BasePart, ignoreParts: {BasePart}, isPreWelding: boolean)
	local overlapParams = OverlapParams.new()
	overlapParams.FilterType = Enum.RaycastFilterType.Exclude
	overlapParams.FilterDescendantsInstances = ignoreParts
	
	local queue = {part}
	local results = {}
	
	local isTouchingGround = false
	
	local start = os.clock()
	
	while #queue > 0 do
		local current = table.remove(queue, 1)
		
		if not visited[current] then
			visited[current] = true
			table.insert(results, current)
			
			local neighbors = workspace:GetPartBoundsInBox(
				current.CFrame,
				current.Size + Vector3.new(0.001, 0.001, 0.001), -- Changed vector.create to Vector3.new for standard Luau, or keep vector.create if using native vector library
				overlapParams
			)
			
			if current:HasTag("Anchored") or current:HasTag("NoPhysics") then
				isTouchingGround = true
			end
			
			for _, neighbor in ipairs(neighbors) do
				local key = getKey(current, neighbor)
				
				if neighbor ~= current and not visited[neighbor] then
					if isTouchingGround and weldLookup[key] and not isPreWelding then continue end
					
					if canConnect(current, neighbor) then
						if neighbor:HasTag("Anchored") then
							isTouchingGround = true
						else
							table.insert(queue, neighbor)
						end
						
						if not weldLookup[key] then
							weldLookup[key] = true
							table.insert(weldQueue, {current, neighbor})
						end
					end
				end
			end
		end
	end
	
	print("search time? :",msConvert.Convert(start))
	
	return results, isTouchingGround
end

local function colorLayersGradient(layers)
	local numLayers = #layers
	for i, layer in ipairs(layers) do
		local color = Color3.new(math.random(), math.random(), math.random())
		
		for _, part in ipairs(layer) do
			part.Color = color
		end
	end
end

local function getLayers(parts, layerHeight)
	layerHeight = layerHeight or 16
	local layersMap = {}
	
	for _, part in ipairs(parts) do
		if part:HasTag("Anchored") then continue end
		local layerIndex = math.floor(part.Position.Y / layerHeight)
		layersMap[layerIndex] = layersMap[layerIndex] or {}
		table.insert(layersMap[layerIndex], part)
	end
	
	local layers = {}
	for _, layerParts in pairs(layersMap) do
		table.insert(layers, layerParts)
	end
	
	colorLayersGradient(layers)
	
	return layers
end

local function arePartsTouching(partA, partB)
	return sat.Colliding(partA, partB)
end

local function checkStructure(cluster)
	local fallLayers = {}
	local trussStrengthMultiplier = 4 
	
	for _, parts in pairs(cluster) do
		local layers = getLayers(parts)
		
		for i, layer in ipairs(layers) do
			local upperLayer = layer
			local belowLayer = layers[i + 1]
			
			if belowLayer then
				local currentLoad = 0
				for _, part in pairs(upperLayer) do
					currentLoad += 10
				end
				
				local effectiveSupport = 0
				
				for _, supportPart in pairs(belowLayer) do
					if supportPart:HasTag("NoWeight") then continue end
					
					local isConnected = false
					
					for _, loadPart in pairs(upperLayer) do
						if arePartsTouching(loadPart, supportPart) then
							isConnected = true
							break
						end
					end
					
					if isConnected or i == #layers - 1 then
						local partStrength = 10
						effectiveSupport += (partStrength * trussStrengthMultiplier)
					end
				end
				
				print("Layer", i, "| Load:", currentLoad, "| Effective Support:", effectiveSupport)
				if effectiveSupport < currentLoad then
					table.insert(fallLayers, upperLayer)
				end
			end
		end
	end
	
	return fallLayers
end

local function extractPartData(parts)
	local data = table.create(#parts)
	for i, part in ipairs(parts) do
		data[i] = {
			CFrame = part.CFrame,
			Size = part.Size,
		}
	end
	return data
end

function getBoundingBox(parts)
	if #parts == 0 then return nil end
	
	if #parts == 1 then
		local p = parts[1]
		return p.CFrame, p.Size
	end
	
	local data = extractPartData(parts)
	
	local centerPos = Vector3.zero
	for i = 1, #data do
		centerPos += data[i].CFrame.Position
	end
	centerPos /= #data
	
	local bestCF = CFrame.new(centerPos)
	local bestVolume = math.huge
	
	for i = 1, #data do
		local partCF = data[i].CFrame
		local testCF = CFrame.new(centerPos) * (partCF - partCF.Position)
		
		local minX, minY, minZ = math.huge, math.huge, math.huge
		local maxX, maxY, maxZ = -math.huge, -math.huge, -math.huge
		
		for j = 1, #data do
			local p = data[j]
			local relCF = testCF:Inverse() * p.CFrame
			local size = p.Size
			
			local sx, sy, sz = size.X / 2, size.Y / 2, size.Z / 2
			for _, corner in ipairs({
				Vector3.new(sx, sy, sz),
				Vector3.new(sx, sy, -sz),
				Vector3.new(sx, -sy, sz),
				Vector3.new(sx, -sy, -sz),
				Vector3.new(-sx, sy, sz),
				Vector3.new(-sx, sy, -sz),
				Vector3.new(-sx, -sy, sz),
				Vector3.new(-sx, -sy, -sz),
				}) do
				local worldCorner = relCF * corner
				minX = math.min(minX, worldCorner.X)
				minY = math.min(minY, worldCorner.Y)
				minZ = math.min(minZ, worldCorner.Z)
				maxX = math.max(maxX, worldCorner.X)
				maxY = math.max(maxY, worldCorner.Y)
				maxZ = math.max(maxZ, worldCorner.Z)
			end
		end
		
		local volume = (maxX - minX) * (maxY - minY) * (maxZ - minZ)
		if volume < bestVolume then
			bestVolume = volume
			bestCF = testCF * CFrame.new(
				(minX + maxX) / 2,
				(minY + maxY) / 2,
				(minZ + maxZ) / 2
			)
		end
	end
	
	local minX, minY, minZ = math.huge, math.huge, math.huge
	local maxX, maxY, maxZ = -math.huge, -math.huge, -math.huge
	for i = 1, #data do
		local relCF = bestCF:Inverse() * data[i].CFrame
		local size = data[i].Size
		local sx, sy, sz = size.X / 2, size.Y / 2, size.Z / 2
		for _, corner in ipairs({
			Vector3.new(sx, sy, sz),
			Vector3.new(sx, sy, -sz),
			Vector3.new(sx, -sy, sz),
			Vector3.new(sx, -sy, -sz),
			Vector3.new(-sx, sy, sz),
			Vector3.new(-sx, sy, -sz),
			Vector3.new(-sx, -sy, sz),
			Vector3.new(-sx, -sy, -sz),
			}) do
			local worldCorner = relCF * corner
			minX = math.min(minX, worldCorner.X)
			minY = math.min(minY, worldCorner.Y)
			minZ = math.min(minZ, worldCorner.Z)
			maxX = math.max(maxX, worldCorner.X)
			maxY = math.max(maxY, worldCorner.Y)
			maxZ = math.max(maxZ, worldCorner.Z)
		end
	end
	
	local size = Vector3.new(maxX - minX, maxY - minY, maxZ - minZ)
	return bestCF, size
end

local function getCenterPart(cluster, cf)
	local center, bestPart, bestDist = cf.Position, nil, math.huge
	for _, part in ipairs(cluster) do
		local dist = (part.Position - center).Magnitude
		if dist < bestDist then
			bestDist = dist
			bestPart = part
		end
	end
	return bestPart
end

local hitboxs = {}

local function searchSpliting(startPart, group : {BasePart}, ourVisited)
	local overlapParams = OverlapParams.new()
	overlapParams.FilterType = Enum.RaycastFilterType.Include
	overlapParams.FilterDescendantsInstances = group
	
	local queue = {startPart}
	local results = {}
	
	local start = os.clock()
	
	while #queue > 0 do
		local current = table.remove(queue, 1)
		
		if not ourVisited[current] then
			ourVisited[current] = true
			table.insert(results, current)

			local neighbors = workspace:GetPartBoundsInBox(
				current.CFrame,
				current.Size + Vector3.new(0.001, 0.001, 0.001),
				overlapParams
			)
			
			for _, neighbor in ipairs(neighbors) do
				if neighbor ~= current and not ourVisited[neighbor] then
					table.insert(queue, neighbor)
				end
			end
		end
	end
	
	print("search spliting time? :", msConvert.Convert(start))
	return results
end

local function getSpliting(group : {BasePart})
	local ourVisited = {}
	local clusters = {}
	
	table.sort(group, function(a, b)
		return a.Position.Y < b.Position.Y
	end)
	
	for _, part in ipairs(group) do
		if part.Parent and not ourVisited[part] then
			local spliting = searchSpliting(part, group, ourVisited)
			table.insert(clusters, spliting)
		end
	end
	
	return clusters
end

function physic.process(parts: {BasePart}, ignoreParts: {BasePart}, voxels: {BasePart}, isPreWelding: boolean)
	parts = parts or {}
	ignoreParts = ignoreParts or {}
	voxels = voxels or {}
	isPreWelding = isPreWelding or false
	weldQueue = {}
	deleteTable = {}
	visited = {}
	
	local overlapParams = OverlapParams.new()
	overlapParams.FilterType = Enum.RaycastFilterType.Include
	overlapParams.FilterDescendantsInstances = ignoreParts
	
	local list = {}
	
	local processTable = {}
	
	local check = {}
	
	for _, part in pairs(parts) do
		if not part:IsA("BasePart") then continue end
		if visited[part] then continue end
		
		local connected, isTouchingGround = getConnected(part, ignoreParts, isPreWelding)
		
		local groupId = physic.groups[connected[1]]
		
		if not groupId then
			currentGroupId += 1
			groupId = currentGroupId
		end
		
		if not groupFolders[groupId] then
			-- create group folder
			groupFolders[groupId] = Instance.new("Model")
			groupFolders[groupId].Name = "Group" .. groupId
			groupFolders[groupId].Parent = workspace

			-- create highlight
			--local highlight = Instance.new("Highlight")
			--highlight.Name = "GroupHighlight"
			--highlight.Parent = groupFolders[groupId]

			-- random color
			--highlight.FillColor = Color3.new(math.random(), math.random(), math.random())
			--highlight.OutlineColor = Color3.new(math.random(), math.random(), math.random())

			-- optionally, adjust transparency
			--highlight.FillTransparency = 0.5
			--highlight.OutlineTransparency = 0.3
		end

		if not physic.groupLookup[groupId] then
			physic.groupLookup[groupId] = {}
		end
		
		if not check[groupId] then -- if not already in the check
			check[groupId] = physic.groupLookup[groupId]
		end
		
		for i, v in pairs(connected) do
			if not v:HasTag("Anchored") then
				v.Parent = groupFolders[groupId]
				
				if not physic.groups[v] then
					physic.groups[v] = groupId
				end
				
				table.insert(physic.groupLookup[groupId],v)
				
				if not isTouchingGround then
					local id = v:GetAttribute("_IDVoxel")
					
					if id then
						table.insert(deleteTable, id)
					end
					
					if not physic.fallTable[v] then
						physic.fallTable[v] = true
					end
				else
					if v:HasTag("NoPhysics") then
						local id = v:GetAttribute("_IDVoxel")
						
						if id then
							table.insert(deleteTable, id)
						end
					end
				end
			end
		end
	end
	
	if isDebug then
		if #debugLog > 0 then
			print("\n===== DEBUG SEARCH RESULTS =====")
			print("Current | Neighbor | Distance")
			
			print(debugLog)
			debugLog = {}
			
			print("================================\n")
		end
	end
	
	local s = os.clock()

	for i, data in ipairs(weldQueue) do
		task.defer(function()
			local weld = cache:getWeld()
			weld.Part0 = data[1]
			weld.Part1 = data[2]
			weld.Parent = data[1]

			data[1].Anchored = data[1]:HasTag("Anchored")
			data[2].Anchored = data[2]:HasTag("Anchored")
		end)
	end		
	
	--print(#processTable)
	
	print("Total :", msConvert.Convert(s))
	
	blink.DeleteEvent.FireAll(deleteTable)
	
	if isPreWelding then
		cache:destroy()
	end
	task.spawn(function()
		for _,parts in pairs(check) do
			local clusters = getSpliting(parts)

			if #clusters > 1 then
				currentGroupId += 1
				
				local groupId = currentGroupId
				
				if not groupFolders[groupId] then
					-- create group folder
					groupFolders[groupId] = Instance.new("Model")
					groupFolders[groupId].Name = "Group" .. groupId
					groupFolders[groupId].Parent = workspace
					
					-- create highlight
					--local highlight = Instance.new("Highlight")
					--highlight.Name = "GroupHighlight"
					--highlight.Parent = groupFolders[groupId]
					
					-- random color
					--highlight.FillColor = Color3.new(math.random(), math.random(), math.random())
					--highlight.OutlineColor = Color3.new(math.random(), math.random(), math.random())
					
					-- optionally, adjust transparency
					--highlight.FillTransparency = 0.5
					--highlight.OutlineTransparency = 0.3
				end
				
				if not physic.groupLookup[groupId] then
					physic.groupLookup[groupId] = {}
				end
				
				for _,part in pairs(clusters[1]) do
					physic.groups[part] = groupId
					table.insert(physic.groupLookup[groupId],part)
					
					part.Parent = groupFolders[groupId]
				end
			end
		end
	end)
end

local function getCorners(part)
	local cf = part.CFrame
	local size = part.Size / 2
	
	local corners = {}
	for x = -1, 1, 2 do
		for y = -1, 1, 2 do
			for z = -1, 1, 2 do
				table.insert(corners, cf * Vector3.new(size.X * x, size.Y * y, size.Z * z))
			end
		end
	end
	return corners
end

local edgeIndexes = {
	{1,2},{1,3},{1,5},
	{8,7},{8,6},{8,4},
	{2,4},{2,6},
	{3,4},{3,7},
	{5,6},{5,7}
}

local function getContactPoints(partA, partB)
	local points = {}
	local params = RaycastParams.new()
	params.FilterType = Enum.RaycastFilterType.Include
	params.FilterDescendantsInstances = {partA, partB}
	
	local function test(part1, part2)
		local corners = getCorners(part1)
		
		for _, edge in ipairs(edgeIndexes) do
			local p1 = corners[edge[1]]
			local p2 = corners[edge[2]]
			local dir = (p2 - p1)
			
			for _, mul in ipairs({1, -1}) do
				local rayDir = dir.Unit * dir.Magnitude * mul
				local result = workspace:Raycast(p1, rayDir, params)
				
				if result and result.Instance == part2 then
					table.insert(points, result.Position)
				end
			end
		end
	end
	
	test(partA, partB)
	test(partB, partA)
	
	local center = nil
	if #points > 0 then
		local sum = Vector3.zero
		for _, p in ipairs(points) do
			sum += p
		end
		center = sum / #points
	end
	
	return points, center
end

local accumulator = 0
local interval = 0.1

local keThreshold = 10

local function getLargestAxis(part: Part)
	return math.max(part.Size.X, part.Size.Y, part.Size.Z)
end

--[[

runService.Heartbeat:Connect(function(dt)
	accumulator = accumulator + dt
	if accumulator < interval then return end
	accumulator = 0

	for clusterId, data in pairs(impactQueue) do
		local parts = data[1]
		local id = data[2]
		local cf = data[3]
		local size = data[4]
		local centerPart = data[5]
		
		if not hitboxs[id] then
			local hitbox = Instance.new("Part")
			hitbox.Name = "Hitbox"
			hitbox.Anchored = false
			hitbox.CanCollide = false
			hitbox.Transparency = 0.5
			hitbox.Size = size + Vector3.new(0.001, 0.001, 0.001)
			hitbox.CFrame = cf
			hitbox.Parent = workspace
			
			local weld = cache:getWeld()
			weld.Part0 = hitbox
			weld.Part1 = centerPart
			weld.Parent = hitbox
			
			hitboxs[id] = {parts = parts, hitbox = hitbox, centerPart = centerPart}
		else
			local mass = centerPart.AssemblyMass
			local velocity = centerPart.AssemblyLinearVelocity.Magnitude
			local ke = 0.5 * mass * velocity^2

			if ke >= keThreshold then
				local params = OverlapParams.new()
				params.FilterType = Enum.RaycastFilterType.Exclude
				params.FilterDescendantsInstances = {hitboxs[id].parts, hitboxs[id].hitbox}

				local parts = workspace:GetPartBoundsInBox(hitboxs[id].hitbox.CFrame, hitboxs[id].hitbox.Size, params)

				for _, part: BasePart in pairs(parts) do
					if not hasRequiredTag(part) then continue end

					local points = getContactPoints(hitboxs[id].hitbox, part)
					impactRemote:Fire(points)
				end
			end
		end
	end
end)

]]

return physic
2

You can do some micro optimizations:

  1. Currently table.insert is faster than array[#array] = 5, unless you manually keep track of array length.
local array = {}
local length = 0

length += 1
array[length] = 5

this becomes faster than table.insert and table.remove
2. Reuse math.huge → local inf = math.huge
3. Use gen iterator or next, for _, corner in next, {} do, etc
4. Cache math methods like math.min, math.max in a way i showed in 2
5. Defer whole loop instead of its body

3

you don’t actually need to care for other function since it didn’t get used im only trying to optimize the get connected and get split and I used head,tail for micro optimization

4

Here are tips then:

  1. Do not use GetPartBoundsInBox per each voxel
    GetPartBoundsInBox is expensive, especially when called dozens/thousands of times per frame.

Replace it with spatial chunking / grid lookup
Store voxels in a structure like:
Grid[x][y][z] = part - keys correspond to voxel coordinates.
Then neighbors are lokups like this:

local Offsets = {
   {1, 0, 0}, {-1, 0, 0},
   {0, 1, 0}, {0, -1, 0},
   {0, 0, 1}, {0, 0, -1},
}

for _, offset in next, Offsets do
    local Nx, Ny, Nz = Cx + offset[1], Cy + offset[2], Cz + offset[3]
    local Neighbor = Grid[Nx] and Grid[Nx][Ny] and Grid[Nx][Ny][Nz]
    if Neighbor then
       --// Enqueue neighbor
    end
end

And still stop using pairs and ipairs, regardless of what function uses

5

This would be a great soluation but my voxel destruction physics isn’t like grid system it not voxel it like recursive until get the part that is a voxel and send that to client but the other one get processed in physics module but I might still try this