Room Detection System, for Grid Build Mode

Help and Feedback Scripting Support
#1

So, as the title is saying, im trying to create a room detection system, for my grid build mode. I have searched everywhere, tried to ask help from the community it self, and this is the only thing I have camen up with:

local Module = {}

local Rep = game:GetService('ReplicatedStorage')
	local Node = Rep.Node

function IsThisRoom(wall, fhit)
	local itIs = false
	local tries = 0

	if not itIs then
		tries = tries + 1
		local tp = wall:GetTouchingParts()
		if #tp < 1 then
			return false
		else
			for _, hit in pairs(tp) do
				if hit.Name == "1" or hit.Name == '2' then
					if hit ~= fhit then
						if not itIs then
							if hit.Parent == fhit.Parent then
								itIs = true
								ThisIsRoom(wall.Parent)
							else
								rec(hit, wall)
							end
						end
					end
				end
			end
		end
	else
		return
	end

	return itIs
end

function ThisIsRoom(room)
	local color = BrickColor.Green()
	for _, wall in pairs(room:GetChildren()) do
		wall.BrickColor = color
	end
end

local WALLS = {}

function Module:MakeRoom()
	local walls = workspace.Assets.Walls

	walls.ChildAdded:Connect(function(Child)
		local Model = workspace:FindFirstChild('Wall')
		if Model == nil then
			Model = Instance.new("Model", workspace)
			Model.Name = "Wall"
		end
		
		wait(0.05)
		Child.Parent = Model
		table.insert(WALLS, Child)			
	end)

	for v, wall in pairs(WALLS) do
		for k, wall2 in pairs(WALLS) do
			for a, i in pairs(wall2.Hitbox:GetChildren()) do
				for b, n in pairs(wall.Hitbox:GetChildren()) do
					rec(i, n)
				end
			end
			--rec(wall2.Hitbox, wall.Hitbox)
		end
	end
end

function rec(wall, preferedwall)
	if preferedwall == nil then
		local localParent = wall.Parent
		--Touch
		local t = wall.Touched:Connect(function() end)
		local tp = wall:GetTouchingParts()
		t:Disconnect()
		if #tp < 1 then return end
		
		for _, hit in ipairs(tp) do
			if hit.Name == "1" or hit.Name == '2' then
				local otherParent = hit.Parent
				if otherParent ~= localParent then
					wall.Parent = otherParent
					local room = IsThisRoom(wall, hit)
					if room then
						ThisIsRoom(otherParent)
						wall.Parent.Name = "ROOM"
					end
				else

				end
			end
		end
	else
		wall.Parent = preferedwall.Parent
		local room = IsThisRoom(wall, preferedwall)
		if room then
			ThisIsRoom(preferedwall.Parent)
			wall.Parent.Name = "ROOM"
		end
	end
end

workspace.Assets.Walls.ChildAdded:Connect(function(Child)
	local Model = workspace.Assets.Walls
	
	wait(0.05)
	Child.Parent = Model
	table.insert(WALLS, Child)

	for v, wall in pairs(WALLS) do
		if wall:FindFirstChild('Hitbox') then
			for b, n in pairs(wall.Hitbox:GetChildren()) do
				rec(n)
			end
		end
	end
end)

return Module

Gif:
https://i.gyazo.com/64a7a5011acd59cf274eb5bd065dd6d9.gif

When a node is green, that means its a room.
I really hope that someone could help me out, thanks :slight_smile:

#2

If you view your corners and walls as nodes and edges of a graph, “room detection” is equivalent to finding cycles in the graph. There are well-known fast algorithms for finding cycles in a (undirected) graph, here’s one post explaining it: algorithm - Cycles in an Undirected Graph - Stack Overflow there may be easier-to-follow examples or tutorials somewhere on the internet.

image

Let me know if you’re having trouble understanding the theory or algorithms, or with implementing them. I can go more indepth with the algorithm but if you’re up to it then it’s better if you do it yourself :slight_smile:

1 Like
#3

Hey buddy :slightly_smiling_face:
Could you maybe explain it for me. Its a bit hard for me to understand it

1 Like
#4

Er du fra Danmark? Hvis ja, kunne du måske uddybe det for mig?

1 Like
#5

Ja helt sikkert, men jeg holder det lige på engelsk så andre der læser opslaget også kan følge med :-)

I’m working on the reply, but it might take a bit…

First of all I made a mistake in my previous reply: findings cycles isn’t quite what we’re after, we need only the chordless cycles, which are cycles where no edges “cut it into smaller cycles”. For example

image

ABCDA is a cycle, but it’s chorded because the AC edge cuts it into two smaller cycles, ABCA and ACDA.

This is turning out to a bit harder than I expected, if anyone knows a way don’t hesitate ^.^

1 Like
#6

So, anything new? Or still working on the reply?

1 Like
Wall render system (Grid Build Mode)
#7

Bro, you still working on the reply? It’s been a while since you said that.

1 Like
#8

I have an idea which is to use pathfinding to find the shortest way to cycle.

My idea is to set the starting point and finish point on the same node and let it find the shortest route to go back to the starting point.

And I’m sure that’s going to be a room. There is no multiple rooms included.

Also you will have to ignore all the nodes that only have one connecting wall, they can’t form a room with no doubt.

1 Like
#9

Hi, sorry for the late reply :sweat_smile: exams got in the way then I forgot :stuck_out_tongue:

Don’t have time to do a detailed write up right now, but I this StackOverflow answer has got it right: algorithm - small cycle finding in a planar graph - Stack Overflow

1 Like