Room Detection System (Grid Placement)

Im trying to make a room detection system on a grid placement.
I have tried to work with undirected- & directed graphs so far, and I cant really figure it out.
I got bunch of code down below, which shows what I have done so far. I really hope people would help me out, cause, this have been giving me a very big headache. Being working with this 5 days in a row…

The first code here is just the main structure for the wall system, its the server sided code:

["Wall"] = function(player, data)
		local origin = data.Origin
		local destination = data.Destination
		
		local plotInfo = placementUtil:GetPlayerPlot(player)
		local plot = plotInfo:GetPlot()
		
		-- Creating Wall
		local Wall = Instance.new('Model', plot.Placed.WallClass)
		Wall.Name = tostring(#plot.Placed.WallClass:GetChildren())
		
		local mainBase = Instance.new("Part")

		mainBase.Parent = Wall
		mainBase.Name = tostring(#plot.Placed.WallClass:GetChildren())
		mainBase.Anchored = true
		mainBase.TopSurface = Enum.SurfaceType.Smooth
		mainBase.BottomSurface = Enum.SurfaceType.Smooth
		mainBase.CFrame = origin
		
		Wall.PrimaryPart = mainBase
		
		mainBase:SetAttribute("Node1", origin.Position)
		mainBase:SetAttribute("Node2", destination.Position)
		
		mainBase:SetAttribute("Color", mainBase.Color)
		mainBase:SetAttribute("Transparency", mainBase.Transparency)
		mainBase:SetAttribute("Material", mainBase.Material.Name)
		
		local distance = (destination.Position - origin.Position).Magnitude
		mainBase.Size = Vector3.new(0.5, 13, distance)
		mainBase.CFrame = (CFrame.lookAt(destination.Position, origin.Position) * CFrame.new(0, 0, -distance/2)) + Vector3.new(0, (13/2), 0)
		
		-- Creating Pillars
		
		local cyl = Instance.new("Part")
		cyl.Parent = mainBase
		cyl.Size = Vector3.new(13,0.5,0.5)
		cyl.CFrame = CFrame.new(origin.Position+Vector3.new(0, 13/2, 0)) * CFrame.Angles(0, 0, math.rad(90))
		cyl.TopSurface = Enum.SurfaceType.Smooth
		cyl.BottomSurface = Enum.SurfaceType.Smooth
		cyl.Shape = "Cylinder"
		cyl.Anchored = true
		cyl.Name = "node1"
		
		local originalCyl = cyl
		
		cyl = Instance.new("Part")
		cyl.Parent = mainBase
		cyl.Size = Vector3.new(13,0.5,0.5)
		cyl.CFrame = CFrame.new(destination.Position+Vector3.new(0, 13/2, 0)) * CFrame.Angles(0, 0, math.rad(90))
		cyl.TopSurface = Enum.SurfaceType.Smooth
		cyl.BottomSurface = Enum.SurfaceType.Smooth
		cyl.Shape = "Cylinder"
		cyl.Name = "node2"
		cyl.Anchored = true
		
		-- Get Touching Node
		
		local connection = cyl.Touched:Connect(function() end)
		local touchingParts = cyl:GetTouchingParts()
		
		for index, value in pairs(touchingParts) do
			if value:FindFirstAncestor("WallClass") and value:IsDescendantOf(plot) and not value:IsDescendantOf(mainBase) and value.Name ~= mainBase.Name then
				value = (value.Name == "NODE" and value.Parent) or value
				mainBase:SetAttribute("Connected", value.Name)
				--createWall(value.Position.X, value.Position.Y, cyl.Position.X, cyl.Position.Y)
				connection:Disconnect()
				break
			end
		end
		
		-- Get Touching Node 2
		
		connection = originalCyl.Touched:Connect(function() end)
		touchingParts = originalCyl:GetTouchingParts()

		for index, value in pairs(touchingParts) do
			if value:FindFirstAncestor("WallClass") and value:IsDescendantOf(plot) and not value:IsDescendantOf(mainBase) and value.Name ~= mainBase.Name then
				value = (string.match(value.Name, "node")~=nil and value.Parent) or value
				value:SetAttribute("Connected", mainBase.Name)
				--createWall(value.Position.X, value.Position.Y, cyl.Position.X, cyl.Position.Y)
				connection:Disconnect()
				break
			end
		end
		
	end

This peace of code here, also does some room finding system methods:

local walls = workspace.Assets.Walls

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

	if not itIs then
		tries = tries+1
		--if tries > #room:GetChildren() then
		--	return
		--end
		print("waiting for touch")
		--local t = wall.Touched:Wait()
		print("touch returned")
		local tp = wall:GetTouchingParts()
		print(#tp)
		for _, hit in pairs(tp) do
				--[[if #tp == 1 then
					wall.BrickColor=BrickColor.Black()
				end
				if #tp >1 then
					wall.BrickColor=BrickColor.White()
				end]]
			print(hit)
			print("Name ",hit.Name=="Wall")
			if hit.Name=="Wall" then
				print(hit~=fhit)
				if hit ~= fhit then
					print(itIs)
					if not itIs then
						print(hit.Parent==fhit.Parent)
						if hit.Parent == fhit.Parent then
							itIs = true
							print "SAME"
						else
							rec(hit,wall)
						end
					end
				end
			end
		end
	else
		return
	end


	--[[local t = original.Touched:connect(function() end)
	local tp = original:GetTouchingParts()
	t:Disconnect()
	
	local hit1 = tp[1]
	
	local t2 = hit1.Touched:connect(function() end)
	local tp2 = hit1:GetTouchingParts()
	t2:Disconnect()
	
	local hit2 = tp2[1]
	
	if hit2.CFrame~=original.CFrame then
		if #tp >= 2 then
			r(hit2)
		end
	else
		itIs = false
	end
	]]
	return itIs
end

function ThisIsRoom(room)
	local color = BrickColor.Random()
	for _, wall in pairs(room:GetChildren()) do
		wall.BrickColor = color
	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

		local hit = tp[1]
		if hit.Name == "WallPart" then --if touching another wall
			local otherParent = hit.Parent
			if otherParent ~= localParent then
				--local oldwall=wall
				--wall=wall:Clone()
				--wall.Name="wallClone"
				wall.Parent = otherParent
				local room = IsThisRoom(wall,hit)
				if room then
					ThisIsRoom(otherParent)
					wall.Parent.Name="ROOM"
				end
			else

			end
			--rec(hit)
		end
	else
		--local oldwall=wall
		--wall=wall:Clone()
		--wall.Name="wallClone"
		wall.Parent = preferedwall.Parent
		local room = IsThisRoom(wall,preferedwall)
		if room then
			ThisIsRoom(preferedwall.Parent)
			wall.Parent.Name="ROOM"
		end
	end
end
print(".....")
local WALLS = {}

workspace.Assets.Walls.ChildAdded:Connect(function(Child)
	local Model = Instance.new('Model', workspace)
	Model.Name = 'Wall'
	
	wait(0.25)
	Child.Parent = Model
	table.insert(WALLS, Child)
end)

while wait() do
	for v, wall in pairs(WALLS) do
		rec(wall)
	end
end

This code here, basically does the same, as the other to codes. Each time a new node have been created, it gets stored inside a table, and then the stored nodes would be ran over and over again, until it finds a “room”

local nodesFolder = workspace.Nodes
local adjList = {} -- adjacency list
local nextNode = {} -- what node is next when walking anticlockwise around walls ?
-- a setup loop
for _, vPart in pairs(nodesFolder:GetChildren()) do
	adjList[vPart] = {}
	nextNode[vPart] = {}
end

for _, vPart in pairs(nodesFolder:GetChildren()) do
	for _, w in pairs(vPart:GetChildren()) do
		-- Build up adjacency list connecting nodes to its neighbours
		local wPart = nodesFolder:FindFirstChild(w.Name)
		table.insert(adjList[vPart], wPart)
		table.insert(adjList[wPart], vPart)
	end
end

local visited = {} -- have we visited this edge before ?
local angle = {} -- what is the angle of a point relative to another point ?
for node, neighbours in pairs(adjList) do
	visited[node] = {}
	angle[node] = {}
	
	-- calculate angles with some basic trigonometry
	for _, neighbour in pairs(neighbours) do
		local delta = neighbour.Position - node.Position
		angle[node][neighbour] = math.deg(math.atan2(delta.X, delta.Z))
	end
	
	-- sort each adjacency list by angle, we can now walk anticlockwise around a node
	table.sort(neighbours, function(a, b)
		return angle[node][a] < angle[node][b]
	end)
	
	if #neighbours >= 1 then
		-- connect end of list to front
		nextNode[node][neighbours[#neighbours]] = neighbours[1]
		-- and the rest together
		for i = 2, #neighbours do
			nextNode[node][neighbours[i-1]] = neighbours[i]
		end
	end
end

-- just some visualisation code
local colorId = 1
local function drawWalls(perimeter)
	local function rand()
		return (math.random() - 0.5) * 0.5
	end
	for i = 2, #perimeter do
		local vPart, wPart = perimeter[i-1], perimeter[i]
		print(vPart, wPart)
		-- Draw Walls
		local line = Instance.new("Part", workspace)
		line.Anchored = true
		line.Size = Vector3.new(0.2, 0.2, (wPart.Position - vPart.Position).magnitude)
		local noise = Vector3.new(rand(), rand(), rand())
		line.CFrame = CFrame.new(wPart.Position:lerp(vPart.Position, 0.5), vPart.Position) + noise
		line.BrickColor = BrickColor.palette(colorId)
		line.Transparency = 0
		line.TopSurface = Enum.SurfaceType.Smooth
	end
	colorId = (colorId + 11) % 256
end

-- the main loop
for nodeA, neighbours in pairs(adjList) do
	for _, nodeB in pairs(neighbours) do
		-- if we've visited an edge before, it's already part of a room or not a part of any room
		if not visited[nodeA][nodeB] then
			visited[nodeA][nodeB] = true
			local room = {nodeA, nodeB} -- the room has at least one wall, let's find the rest
			local pivot, from = nodeB, nodeA -- by doing a counter-clockwise walk
			local totalAngle = 0 -- ensure we're not walking along the exterior by keeping track of the total angle walked
			while true do
				local to = nextNode[pivot][from]
				if visited[pivot][to] then
					break
				else
					totalAngle = totalAngle + (angle[pivot][to] - angle[pivot][from]) % 360
					visited[pivot][to] = true
					table.insert(room, to)
					pivot, from = to, pivot
				end
			end
			if totalAngle/(#room-2) < 180 then -- ensure not an exterior
				drawWalls(room) -- the room is found! let's draw it
			end
		end
	end
end

All in all, nothing seems to be working, like really, it doesn’t seem to be counting anything / not picking up anything. I really tried over and over, never gave up, but right now, I’m thinking to give up on it…

It would help if you explained a little bit about your setup and what this code is supposed to do.

I’m guessing you’re trying to do some kind of flood fill algorithm but I’m not sure and don’t want to figure out your setup from these three huge code blocks :slight_smile:

2 Likes

What you mean by my setup? I have showed all the code I got. Im trying to detect when a room have been created, when I connect walls together, in a grid placement system.

There’s a few hundred lines of code there, it would be faster for other people to get a grasp of if you had a little introductory paragraph or sentence for each section.

1 Like