Finding groups of blocks

[Elttob (dphfox)]

I’ve been working on a method of finding connected groups of blocks, and would like some feedback with regards to the method I’m using.

I’m only using parts here as a visual aid; the actual algorithm will be operating on Lua data.

Suppose we have a structure of blocks like this, where every block is snapped to a uniform grid:

Imagine all those blocks are welded together.

That red block is going to be deleted, and we would like to find what groups of connected blocks the structure will be split into. For example, the above structure would be split into two groups:

I’m currently using a simple flood fill algorithm to recursively spread throughout the structure and detect these groups. Starting from the red block, each direction is given its own group (represented as a unique colour) and spreads out as far as it can from that red block. If two groups meet, they merge into one group.

Here’s what that looks like:

This method works perfectly, but I’m concerned about performance, since it’s a recursive flood fill and those can get expensive with more complex structures. Is there a more optimal method for detecting these groups?

Again, the parts are just a visual aid, and the method will have to work on Lua data. Thanks in advance

edit: here’s the place file with the algorithm in. Feel free to have a play about, but I’d like to warn you that this is just prototype code, so it’s pretty messy: connections.rbxl (19.6 KB)

[sebi210]

Would be nice if you could post the code here, so we don’t have to download the file.
(It is no problem at all, I just have big mess on my computer and don’t wanna make it bigger.)

[Elttob (dphfox)]

Alright:

Code

local blocks = {}

local format = "x%dy%dz%d"

local normals = {
	Vector3.new(1, 0, 0),
	Vector3.new(0, 1, 0),
	Vector3.new(0, 0, 1),
	Vector3.new(-1, 0, 0),
	Vector3.new(0, -1, 0),
	Vector3.new(0, 0, -1)
}

local colours = {
	Color3.new(1, 0, 0),
	Color3.new(0, 1, 0),
	Color3.new(0, 0, 1),
	
	Color3.new(0, 1, 1),
	Color3.new(1, 0, 1),
	Color3.new(1, 1, 0),
}

local function place(pos)
	local x, y, z = pos.x, pos.y, pos.z
	blocks[format:format(x, y, z)] = pos
end

local function get(pos)
	local x, y, z = pos.x, pos.y, pos.z
	return blocks[format:format(x, y, z)]
end

local function drawNormal(pos, normal, col)
	local n = script.Normal:Clone()
	n.Color = col
	n.CFrame = CFrame.new(pos*4 + normal*2, pos*4 + normal*4)
	n.Parent = workspace.Normals
end

for _, block in pairs(workspace.Blocks:GetChildren()) do
	local pos = block.Position / 4
	local x, y, z = pos.x, pos.y, pos.z
	block.Name = format:format(x, y, z)
	place(pos)
end


local openSet = {}
local closedSet = {}

local function recolourNormals(colour1, colour2)
	for _, ins in pairs(workspace.Normals:GetChildren()) do
		if ins.Name == "Normal" and ins.Color == colour1 then
			ins.Color = colour2
		end
	end
	
	for i, data in pairs(openSet) do
		if data.colour == colour1 then
			openSet[i] = {pos = data.pos, normal = data.normal, colour = colour2}
		end
	end
	
	for i, data in pairs(closedSet) do
		if data.colour == colour1 then
			closedSet[i] = {pos = data.pos, normal = data.normal, colour = colour2}
		end
	end
end

local function mlen(t)
	local len = 0
	for _ in pairs(t) do
		len = len + 1
	end
	return len
end

local function goTo(newPos, normal, colour)
	if newPos.Magnitude < 0.1 then return end
	local ind = format:format(newPos.x, newPos.y, newPos.z)
	if not closedSet[ind] then
		openSet[ind] = {pos = newPos, normal = normal, colour = colour}
	else
		local data = closedSet[ind]
		if data.colour ~= colour then
			print("joined!", colour, data.colour)
			recolourNormals(colour, data.colour)
		end
		drawNormal(newPos - normal, normal, data.colour)
	end
end

local function close(pos)
	local ind = format:format(pos.x, pos.y, pos.z)
	if openSet[ind] then
		local data = openSet[ind]
		drawNormal(data.pos - data.normal, data.normal, data.colour)
		openSet[ind] = nil
		if not closedSet[ind] then
			closedSet[ind] = {pos = pos, normal = data.normal, colour = data.colour}
		end
	end
end

local function spread(pos, col)
	for normindex, normal in pairs(normals) do
		local newPos = pos + normal
		if get(newPos) then
			goTo(newPos, normal, col or colours[normindex])
		end
	end
	close(pos)
end

spread(Vector3.new(0, 0, 0))

repeat
	local blocksToTraverse = {}
	for i, data in pairs(openSet) do
		blocksToTraverse[i] = data
	end
	
	for _, data in pairs(blocksToTraverse) do
		spread(data.pos, data.colour)
	end
	
	print "step"
	wait(1)
until mlen(openSet) == 0

for _, data in pairs(closedSet) do
	workspace.Blocks[format:format(data.pos.x, data.pos.y, data.pos.z)].Color = data.colour
end

print "done"

It’s pretty messy, but I’ll be happy to clear up anything you need to know

[sebi210]

Chill, this is code review, it is to make your code better. So no need to be stressed about it.

[VoidedBlades (Plushie)]

the code is looking pretty good. however I’d use some modules to make the mainscript look more cleaner. for example making a seperate module for all the arrays (normal array and colours array).

alongside from that put all the functions that are alike or in a similar base of functionality in the same module and call them from the mainscript. this will keep the overview on the main script more clear and makes reading seperate parts of code easier.

[Elttob (dphfox)]

Thanks - I’m intending to do this when I rewrite the algorithm to use in production, but would you have any performance concerns about the algorithm or any suggestions for optimisations?

[VoidedBlades (Plushie)]

not at a quick look over it. you avoided using raycasts so that’s 1 thing i must compliment you about. maybe instead of wait(1) let it wait every RunService.HeartBeat:Wait(). which is 1/60th of a frame. it might run smoother if replacing that or it might lag a little depending on how heavy the preformance is of the script. just keep me up to date

[Elttob (dphfox)]

The yielding is just there so I can keep an eye on the code as it works; the entire function will run to completion without yielding most likely

[VoidedBlades (Plushie)]

Even better. I don’t see anything that could improve it even more good job!