How to use flood fill to determine different caves

Help and Feedback Scripting Support
#1

Currently I have a 2D cave generation system, however if you look closely you’ll see many of the rooms (the solid sections are floors, the invisible ones will be walls) are isolated from each other. I want to fill each room with it’s own color so I know which rooms are isolated, but I don’t know how. Any help would be appreciated
Also the cells are organized by single digit numbers, I realized after I should’ve used coordinates.
image
Sorry if the code is a little unorganized

local cellsize = Vector3.new(1,5,1)*5
local cavedimensions = Vector3.new(1,0,1)*75 + Vector3.new(0,1,0)
local cavefolder = Instance.new("Folder")
cavefolder.Parent = workspace
function getZNeighbor(cellnumber, value)
	return cellnumber + value
end
function getXNeighbor(cellnumber, value)
	return cellnumber + (cavedimensions.Y * cavedimensions.Z * value)
end
function getAllneighbors(originalcell, adjacent, solid)
	local neighbors = {}
	local neighbornumber = tonumber(originalcell)

	-- FORWARD/BACKWARD 
	table.insert(neighbors, getZNeighbor(neighbornumber, 1))   -- Forward
	table.insert(neighbors, getZNeighbor(neighbornumber, -1))  -- Backward

	-- LEFT/RIGHT
	table.insert(neighbors, getXNeighbor(neighbornumber, 1))   -- Right
	table.insert(neighbors, getXNeighbor(neighbornumber, -1))  -- Left

	-- DOUBLE-FUNCTIONS 
	if adjacent then

		table.insert(neighbors, getXNeighbor(getZNeighbor(neighbornumber, 1), 1))   -- Front-Right
		table.insert(neighbors, getXNeighbor(getZNeighbor(neighbornumber, -1), 1))  -- Back-Right
		table.insert(neighbors, getXNeighbor(getZNeighbor(neighbornumber, 1), -1))  -- Front-Left
		table.insert(neighbors, getXNeighbor(getZNeighbor(neighbornumber, -1), -1)) -- Back-Left

		
	local ToBeRemoved = {}
	for i, v in pairs(neighbors) do
		local cell =cavefolder:FindFirstChild(v)
		if cell ~= nil then
			--print(v)
			if solid then
				if cell.Transparency == 1 then
					table.insert(ToBeRemoved, v)
				end
			end
		else
			table.insert(ToBeRemoved, v)

		end
	end
	for i, v in pairs(ToBeRemoved) do
		--print(v)
		table.remove(neighbors, table.find(neighbors, v))
		if waitt then
			--task.wait()
		end
		
	end
	return neighbors
end
function GetFloorNeighbors(neighbors)
	for i, v in pairs(neighbors) do
		if cavefolder[tostring(v)].Transparency ~= 1 then
			table.remove(neighbors, i)
			task.wait()
		end
		
	end
	return neighbors
end
local i = 0
for x = 1, cavedimensions.X, 1 do
	for y = 1, cavedimensions.Y, 1 do
		for z = 1, cavedimensions.Z, 1 do
			local cell = Instance.new("Part")
			cell.Size = cellsize
			cell.Anchored = true
			cell.Position = Vector3.new(x*cellsize.X,y*cellsize.Y,z*cellsize.Z)
			cell.Parent = cavefolder
			i+=1
			cell.Name = tostring(i)

			--print(cell.Name)
		end
		task.wait()
	end
end
function GenerateBlueprint()
	local random = math.random(1,#cavefolder:GetChildren())
	print(random)
	local nextCell = cavefolder:GetChildren()[random]
	nextCell.Transparency = 1
	for i = 1, (cavedimensions.X*cavedimensions.Y*cavedimensions.Z)/3 do
		local neighbors = getAllneighbors(nextCell.Name, false, true)
		print(neighbors)
		if #neighbors > 0 then
			random = math.random(1, #neighbors)
			nextCell = cavefolder:GetChildren()[neighbors[random]]
			--print(neighbors)
			nextCell.Transparency = 1
		else
			repeat
				print(typeof(nextCell))
				if nextCell == nil then
					nextCell = cavefolder:GetChildren()[math.random(1, #cavefolder:GetChildren())] 
				else
					if math.random(1,2) == 1 then
						nextCell = cavefolder:FindFirstChild(getXNeighbor(tonumber(nextCell.Name),1)) 
					else
						nextCell = cavefolder:FindFirstChild(getZNeighbor(tonumber(nextCell.Name),1)) 
					end
				end
				
				
			until nextCell and nextCell.Transparency == 0 and cavefolder:FindFirstChild(nextCell.Name)
			
		end
		 
		task.wait()
	end
	for i = 1,3 do
		CellularAutomata()
		task.wait()
	end

end
function CellularAutomata()
	print("automata")
	for i, v in pairs(cavefolder:GetChildren()) do
		local solidneighbors= #getAllneighbors(v.Name, true, true)
		print(solidneighbors)
		if solidneighbors <= 3 then
			v.Transparency = 1
			task.wait()
		end
		
	end
end

GenerateBlueprint()
1 Like
#2

So first is that this problem is a bit more complex than flood fill since it technically just has a flood fill algorithm inside of it. So first let’s assume we have a working flood fill algorithm defined as being able to take an input point in and find all the cells touching it. This works simply by having an open list and a closed list. We put the tracked cell in the open list and run a loop while #openlist > 0 do and always pull the first item out of the open list and mark it’s data as a found cell, get it’s neighbors. And if the neighbor isn’t in the closed list already, put the neighbor in the open list. Put the currently checked cell in the closed list (or in the example we actually fill data in the metadata section when we find it which we can use in place of the closed list to determine if a cell has already been visited).

You also have to find a way to uniquely identify rooms

So conceptually here is my pitch.

First we have a room counter (starts at 1 because we will reserve 0 for meaning “empty cell” in the metadata(aka rooms) table)
We make a table that holds metadata for every cell (the room id).
We loop through every cell.
At every cell we check if the metadata for it has a cave assigned. If not we run floodfill on it where floodfill adds metadata about the current room number for every cell. If the cell already has a room number we skip it (and we skip if it doesn’t have anything of course but we set the metadata to 0).
Now that floodfill is done we increment room number since the next valid floodfill run will be a unique room and so we need the next number.
Once the loop ends we have a copy table that is simply full of room numbers for every single cell.
Do with that as you will. (we will likely reserve 0 as an empty room number for consistency).

You could of course also just keep the closed list from your floodfill if that data is a better fit for whatever you plan to do next.