How to implement the Flood Fill Algorithm, for Room Detection?!

Help and Feedback Scripting Support
#1

How would I implement Flood Fill to use as room detection or check
if an area is closed off by surrounding walls?

Unity and python both have specific functions that makes this less difficult.

2 Likes
#2

This is the elementary and easy way to do it.

image
image1226×301 19.5 KB

1 Like
#3

I know how it works…

but how do you implement it into roblox (luau)
Python and C++ have specific functions that makes it less difficult…

so do I put all the grid spaces in an array and region3 for each array?

#4

Back from eating.

I have no idea what “specific functions” you are talking about. You don’t need “specific functions” to make a flood fill. The idea is simple. You start at a specific node given by a x and y coordinate. You consider if the cells adjacent to it are filled. For each one that is not you continue the process.

You use a 2D array and check a specific value at <x, y> then consider if the points <x - 1, y> and <x + 1, y>, and <x, y + 1> and so on are filled. If they are then flood check those and continue from there.

Here I wrote naive approach that does what I just described.

local grid = {}

for x = 1, 15 do
	grid[x] = {}
	
	for y = 1, 15 do
		local z = math.noise(x / 5, y / 5) < 1/5 and 0 or 1
		
		print(z)
		
		local part = Instance.new("Part")
		
		part.Anchored = true
		part.Size = Vector3.new(1, 1, 1)
		part.CFrame = CFrame.new(x, y, 0)
		part.Color = Color3.new(z, 0, 0)
		part.Parent = workspace
		
		grid[x][y] = {
			part = part,
			flood = false,
			z = z
		}
	end
end

local function flood(grid, x, y)
	if grid[x][y].flood then return end
	
	grid[x][y].flood = true
	grid[x][y].part.Color = Color3.new(0, 1, 0)	
	wait(1 / 30)
	grid[x][y].part.Color = Color3.new(0, 0, 1)
	
	if grid[x - 1] and grid[x - 1][y].z == 0 then
		flood(grid, x - 1, y)
	end
	
	if grid[x + 1] and grid[x + 1][y].z == 0 then
		flood(grid, x + 1, y)
	end
	
	if grid[x][y - 1] and grid[x][y - 1].z == 0 then
		flood(grid, x, y - 1)
	end
	
	if grid[x][y + 1] and grid[x][y + 1].z == 0 then
		flood(grid, x, y + 1)
	end
end

wait(1)

flood(grid, 1, 1)

And if you were to “multi thread” it.

	if grid[x - 1] and grid[x - 1][y].z == 0 then
		coroutine.wrap(flood)(grid, x - 1, y)
	end
	
	if grid[x + 1] and grid[x + 1][y].z == 0 then
		coroutine.wrap(flood)(grid, x + 1, y)
	end
	
	if grid[x][y - 1] and grid[x][y - 1].z == 0 then
		coroutine.wrap(flood)(grid, x, y - 1)
	end
	
	if grid[x][y + 1] and grid[x][y + 1].z == 0 then
		coroutine.wrap(flood)(grid, x, y + 1)
	end

8 Likes
Grid Based Room Detection
Help Detecting a Room with Flood
#5

Back from sleeping.

The specific functions I was referencing was, getting the pixel and / or pixel color, I’ve seen some people use this “Pixel” function in Flood Fills.

Also thanks for replying, I will see if I can Reverse Engineer the code to fit what I seek to achieve.

Also so I start from top left of my grid and go towards bottom right?, because I’ve seen some people say that it can be costly running it as so.

Or do I fill from where I placed my wall?

1 Like
#7

And also you are adding the parts to the table and know adjacent parts from it, the same isn’t the case with it in a grid

#8

Can you open source it? I kinda need it for a certain project. Sorry if this is off-topic