# Room detection system

Currently i have a wall building system for a house building mode i am working on which looks like this:

Now, i really wonder if somehow someone could make a system that detects when a room is formed (walls closed)

For example, when something like this happens, it prints “Room created” returning all the walls which form the room (so with them i could auto generate a floor or roof etc)

I thought of using regions, raycasts, linked walls and stuff but could not think a solid way of doing it, does anyone of you do?

3 Likes

First idea that comes to my mind is treating walls as connected nodes in a graph and finding cycles in that graph.

2 Likes

Yeah as i said before, i thought of “linked walls” but the problem is here

Connecting a wall to a point of another wall which is not in any of its corners?

1 Like

I think most obvious solutions are using either raycasting methods or regions

1 Like

When a wall is created you can check if it collides with another wall and if this happens in a place where no node exists then you can create a new node there.

1 Like

So would i create nodes in every start and end point of each wall? That would also create a node when a wall is touching another wall as it would already create one on end point of it…

How do i connect the nodes properly

1 Like

You create nodes at the beginning of the wall and at the end. Now when walls touch we have three cases:

1. The ending/beginning point of the newly created wall touches the second wall at its beginning or ending point. Then these nodes just merge into one.
2. The ending/beginning point of the newly created wall touches the second wall at some point that is not its beginning nor ending point. You create a new node in that place, split the wall into two parts and merge the nodes.
3. Newly created wall touches the secoond wall and no nodes overlap
Something like that:

Then a node is created in the point where they overlap and both walls are split into two smaller walls.

This is my idea, maybe someone will come up with a better one but I think it’s efficient.

2 Likes

You have explained brilliantly how and when and where to create the nodes!
Although, how do i KNOW when some nodes create a room? Do i just loop through all nodes every time a new node is created to see
if any node have passed its previous self then
i say here i create a room with those nodes
and move on to next nodes??

1 Like

At the moment I can only think of the idea where you go through the whole graph using e.g. DFS algorithm to find cycles. I’ll think about that later and if I find a better solution I will let u know.

2 Likes

We can also try using pathfinding algorithms.

1 Like

More in depth detail?

1 Like

If you marked every node where the wall crosses, it would be a bit easier. However, this is a bit tricky since you allow many different angles. In The Sims, you are limited to increments of 45 degrees, which simplifies the problem greatly.

If all nodes are marked, then you could use @Kacper’s technique to find a loop.

1 Like

Currently ive managed to make what @Kacper have said before with the nodes creation system
It forms walls with nodes like this

Which all nodes has 2 object values named “Next” and “Previous” with the values of the next/previous nodes of the current ones

Now, what is the algorithm to detect if the nodes create a room?

I don’t know what do you mean by next and previous because there can be more than two walls connecting on one spot. I would just store the nodes and their connections with other nodes. Then you can use DFS algorithm to find cycles in the graph (V, E), where V are nodes, and E are the connections. And how to use DFS to find cycles - https://discuss.codechef.com/t/how-to-detect-all-cycles-in-a-undirected-graph/15732.

1 Like

IMO, the easiest way to do this is a simple floodfill. Use floodfill algorithm to collect all nodes in a given area. Regarding the algorithm, instead of checking nodes that are the same, you check to see if they are divided by a wall.

I’ve used floodfilling to define regions in a similar manner before in order to figure out walkable NPC nodes.

Oh true…And i was wondering why something is off

Could someone provide a simple code for the solution
If you already got the idea of the code because i am still thinking how to write it

I just want a function to return the nodes that form a room…
It would mean a lot for me

What do you mean “in a given area?”
Why wouldnt i jsut loop through all the nodes?

a possible solution would be to use polygon triangulation to basically fill the room with parts, and then just turn those parts into a region, and then check if the player is in the region.

basic polygon triangulation:

``````local points = {} -- put your nodes in here.
table.sort(points, function(a,b) return tonumber(a.Name) < tonumber(b.Name) end)
local verticeCount = #toPolygon:GetChildren()

function GetPointInFront(point, listOfPoints)
if point == #listOfPoints then
return listOfPoints[1]
else
return listOfPoints[point+1]
end
end

function GetPointBehind(point, listOfPoints)
if point == 1 then
return listOfPoints[#listOfPoints]
else
if point == 4 then
print("______")
print(listOfPoints[point-1])
end
return listOfPoints[point-1]
end
end

function IsPointConvex(behind, point, infront, previousDirection)
local v1 = point.Position - behind.Position
local v2 = infront.Position - point.Position

local crossproduct = v2:Cross(v1)
local currentDirection
if crossproduct.Y > 0 then
currentDirection = 1
else
currentDirection = -1
end
return currentDirection ~= previousDirection
end

function GetAreaOfTriangle(A, B, C)
local BA = A.Position - B.Position
local CA = C.Position - B.Position

return (BA:Cross(CA).magnitude/2)
end

function GetEarOfPolygon(parts, direction, folder)
local i = 1
local earFound = false
local newTable
while not earFound and i <= #parts do wait()
local point = parts[i]
local A, B, C = GetPointBehind(i, parts), point, GetPointInFront(i, parts)
if IsPointConvex(A,B,C, direction) then
local contained = false
for x,v in pairs(parts) do

if v ~= A and v ~= B and v ~= C then
local a1,a2,a3 = GetAreaOfTriangle(A, B, v), GetAreaOfTriangle(A, C, v), GetAreaOfTriangle(B, C, v)

if a1 + a2 + a3 == GetAreaOfTriangle(A, B, C) then
contained = true
end
end

end

if not contained then
earFound = point
drawTriangle(A.Position, B.Position, C.Position, folder)
newTable = {}
for x,v in pairs(parts) do
if v ~= point then
table.insert(newTable, v)
end
end
end
end
i=i+1
end
return earFound, newTable
end

function TriangulatePolygon(points)
local folder = Instance.new("Folder", game.Workspace)
while true do
local newTable = points
local done = false
while #newTable > 2 do
done,newTable = GetEarOfPolygon(newTable, -1, folder)
table.sort(newTable, function(a,b) return tonumber(a.Name) < tonumber(b.Name) end)
wait()
end
wait(0.5)
folder:ClearAllChildren()
end
end

local wedge = Instance.new("WedgePart")
wedge.Material = Enum.Material.SmoothPlastic
wedge.Transparency = 0
wedge.Anchored = true
wedge.CanCollide = false
wedge.TopSurface = Enum.SurfaceType.Smooth
wedge.BottomSurface = Enum.SurfaceType.Smooth
wedge.Color = Color3.fromRGB(125, 125, 125)
local wedgeMesh = Instance.new("SpecialMesh", wedge)
wedgeMesh.MeshType = Enum.MeshType.Wedge
wedgeMesh.Scale = Vector3.new(1,1,1)

function drawTriangle(a, b, c, parent)
local edges = {
{longest = (c - b), other = (a - b), position = b};
{longest = (a - c), other = (b - c), position = c};
{longest = (b - a), other = (c - a), position = a};
};
table.sort(edges, function(a, b) return a.longest.magnitude > b.longest.magnitude end);
local edge = edges[1];

local theta = math.acos(edge.longest.unit:Dot(edge.other.unit))
local s1 = Vector2.new(edge.other.magnitude * math.cos(theta), edge.other.magnitude * math.sin(theta));
local s2 = Vector2.new(edge.longest.magnitude - s1.x, s1.y);

local p1 = edge.position + edge.other * 0.5
local p2 = edge.position + edge.longest + (edge.other - edge.longest) * 0.5

local right = edge.longest:Cross(edge.other).unit;
local up = right:Cross(edge.longest).unit;
local back = edge.longest.unit;

local cf1 = CFrame.new(
p1.x, p1.y, p1.z,
-right.x, up.x, back.x,
-right.y, up.y, back.y,
-right.z, up.z, back.z
);
local cf2 = CFrame.new(
p2.x, p2.y, p2.z,
right.x, up.x, -back.x,
right.y, up.y, -back.y,
right.z, up.z, -back.z
);

local w1 = wedge:Clone();
local w2 = wedge:Clone();
w1.Parent = parent;
w2.Parent = parent;
w1.Size = Vector3.new(0.01, s1.y, s1.x);
w2.Size = Vector3.new(0.01, s2.y, s2.x);
w1.CFrame = cf1;
w2.CFrame = cf2;
end;

TriangulatePolygon(points)
``````

Well i already have that in my “Floor system”
But all i wanted is to know when some walls all CLOSED so that it forms a ROOM…And to detect that i generated nodes in every point of the wall (start / end point) and then see when the points form a circle then collect those points to generate a floor with them. I want this