How to implement flood fill to detect enclose space?

Help and Feedback Scripting Support
#1

  1. What do you want to achieve? Keep it simple and clear!
    I want to use a flood fill algorithm to detect enclosed spaces and do actions accordingly.

  2. What is the issue? Include screenshots / videos if possible!
    My implementation won’t work. It just goes to the side and doesn’t stop when it detects a dead end.

  3. What solutions have you tried so far? Did you look for solutions on the Developer Hub?
    Chatgpt was hopeless, didn’t do anything. I looked into some dev forum posts but they weren’t what I was looking for.

-- my implementation
local ship = script.Parent.Parent
local nodes = ship["Watertight Nodes"]
local attempts = 0

local function FloodFill(pos:Vector3)
	task.wait()
	attempts += 1
	
	local brush = Instance.new("Part") do
		brush.Size = Vector3.new(1, 1, 1)
		brush.Position = pos
		brush.Transparency = 1
		brush.CanCollide = false
		brush.Anchored = true
		brush.Name = "brush"
		brush.Parent = workspace
	end
	
	FloodFill(pos + Vector3.new(1, 0, 0))) -- right
	FloodFill(pos + Vector3.new(-1, 0, 0)) -- left
	FloodFill(pos + Vector3.new(0, 1, 0)) -- up
	FloodFill(pos + Vector3.new(0, -1, 0)) -- down
	FloodFill(pos + Vector3.new(0, 0, -1)) -- front
	FloodFill(pos + Vector3.new(0, 0, 1)) -- back
end

wait(2)
FloodFill(nodes.Node1.Position)
1 Like
#2

im looking at this code and i dont see anything to do with doing anything if the brush hits something
could it be that?

#3

I forgot to update, whoops!
Anyway this is the new code that is sorta working.

local ship = script.Parent.Parent
local nodes = ship["Watertight Nodes"]
local attempts = 0

local function FloodFill(pos:Vector3, prevPart:BasePart)
	if attempts >= 100 then return; end
	
	local shouldTest = true
	
	if prevPart then
		prevPart.Touched:Connect(function(otherPart)
			print(otherPart, prevPart)
			if otherPart.Name ~= "brush" then
				shouldTest = false
			end
		end)
	end
	
	task.wait()
	attempts += 1
	
	if shouldTest then
		local brush = Instance.new("Part") do
			brush.Size = Vector3.new(1, 1, 1)
			brush.Position = pos
			brush.Transparency = 1
			brush.CanCollide = false
			brush.Anchored = true
			brush.Name = "brush"
			brush.Parent = workspace
		end
		FloodFill(pos + Vector3.new(0, 0, 1), brush) -- back
	end
end

wait(2)
FloodFill(nodes.Node1.Position)

but only In the reverse direction

#4

If I try to add 2d in this it simple breaks and does the old behaviour.

#5

i still cant see anything checking if the brush touches anything

#6

wdym its right here

ueioioueqwoiueqwoqweoqwoiuewq

#7

ohhhhhhh
wouldnt this just instantly collide with itself since youre checking if a brush is touching a brush?

#8

or if it didnt instantly collide with itself, wouldnt it go on forever?

#9

This is what’s happening.

also about this

I use a if statement to detect the name of the part it is touching to prevent this from happening.

#10

oh nvm its checking if it is not a brush

im going to run this code in studio and see what i get. brb!

1 Like
#11

ok i think i found the issue!
erex when you set cancollide to false all touch checks return nothing
im busy making a version that should work better!!

1 Like
#12 

local attempts = 0

local function FloodFill(pos:Vector3, prevPart:BasePart)
	if attempts >= 100 then return; end

	local shouldTest = true
	attempts += 1

	if shouldTest then
		local brush = Instance.new("Part") do
			brush.Size = Vector3.new(1, 1, 1)
			brush.Position = pos
			brush.Transparency = 0
			brush.CanCollide = false
			brush.Anchored = true
			brush.Name = "brush"
			brush.Parent = workspace
		end
		local parts = workspace:GetPartsInPart(brush)
		print(parts)
		local shouldtestagain = true
		for _, part in ipairs(parts) do
			if part.Name ~= "brush" then
				shouldtestagain = false
			end
		end
		if shouldtestagain == true then
			FloodFill(pos + Vector3.new(0, 0, 1), brush)
		end
	end
end

wait(2)
FloodFill(workspace.brush.Position)

try this
oh yeah dont forget to edit the variables

1 Like
#13

It works, needed an OverlapParams. But it essentially does the same thing, doesn’t it?

#14

yah checking for parts inside parts

#15

i think i found a bit of an issue though

#16

@Erex_147 when you call the function twice it runs the first func and ditches the rest for some reason

#17

will look into this, also turns out I gotta use get parts in parts because of overlap of brushes

#18

@Exozorcus I’ve almost got it, it works perfectly in 2d

#19

lol I got a stack overflow thing.

#20

your method worked, just needed some changes.
here’s the final script.

local ship = script.Parent.Parent
local nodes = ship["Watertight Nodes"]
local attempts = 0

local olap = OverlapParams.new() do
	olap.FilterType = Enum.RaycastFilterType.Exclude
	olap.FilterDescendantsInstances = {nodes}
end

local attempts = 0

local function FloodFill(pos:Vector3)
	if attempts >= 250 then return; end
	task.wait()
	local shouldTest = true
	attempts += 1

	if shouldTest then
		local brush = game:GetService("ServerStorage").brush:Clone()
		brush.Position = pos
		brush.Parent = workspace
		
		local parts = workspace:GetPartsInPart(brush, olap)
		print(parts)
		local shouldtestagain = true
		--for _, part in ipairs(parts) do
		--	if part.Name ~= "brush" then
		--		shouldtestagain = false
		--	end
		--end
		if #parts > 0 then
			shouldtestagain = false
			brush:Destroy()
		end
		if shouldtestagain == true then
			FloodFill(pos + Vector3.new(0, 0, 1))
			coroutine.wrap(FloodFill)(pos + Vector3.new(0, 0, -2))
			coroutine.wrap(FloodFill)(pos + Vector3.new(-2, 0, 0))
			coroutine.wrap(FloodFill)(pos + Vector3.new(2, 0, 0))
			coroutine.wrap(FloodFill)(pos + Vector3.new(0, 2, 0))
			coroutine.wrap(FloodFill)(pos + Vector3.new(0, -2, 0))
		end
	end
end

wait(5)
FloodFill(nodes.Node1.Position)