Grid system room detection

[range_0xE4 (Range)]

I am creating a game in which the construction goes on a three-dimensional grid, there is a block that blocks all the faces of the cell, there is also a wall that blocks one of the side faces of the cell and so on. The goal is to define an enclosed space (room) that is formed from the blocked faces of the grid cells

[safeLast120]

Depends greatly on how you’ve structured your system.

First off, do you keep track of all the blocks? Or the system you’ve made just place them down and then just erases trace of them?
A first step would be ensuring there’s some track of them.

If you’re already keeping track of them and if you’re able to map them out in a 3D cartesian plane, you may refer to this topic in StackExchange to find out whether ant given point is within bounds in a 3D cartesian plane: How to check if point is within a rectangle on a plane in 3d space - Mathematics Stack Exchange

[range_0xE4 (Range)]

Yes, I save my blocks to a table

function ConstructSystem.new(ModelName: string): Construction
	local ConstructData = Items.Constructions[ModelName]
	
	if not ConstructData then warn(`[{script.Name}] Cant find model with name: {ModelName}`); return end
	
	local self = setmetatable({}, ConstructSystem)
	
	self.Model = ConstructData.Path:Clone()
	
	self:InitBlock()
	self:ChangePhase(ConstructData.CurrentPhase or 1)

	table.insert(AllConstuctions, self)

	return self
end

function ConstructSystem:Place(Position: Vector3, RotationVector: Vector3)
	if not self.Model then warn(`[{script.Name}] Cant find model with name: `, self); return end
	
	self.Position = Position or self.Position
	self.RotationVector = RotationVector or self.RotationVector or Vector3.zero
	
	self.Model.Parent = workspace.Constructions
	self.Model:PivotTo(CFrame.new(self.Position))
end

[BlueDeveloper24]

What are you trying to achieve?

if you want to make a box room out of the blocks get the size of the room box minus the interior blocks

[safeLast120]

Looks solid.
Try to apply what the link to StackExchange I shared in my past post directs, perhaps it can help you since I see you’re pivoting these Models to their position, which is a good base for a system like that.
To determine which point to check each time, you can take all the sides of a Model upon being placed, and if you find that the point is within bounds, then it’s an enclosed space.

[safeLast120]

@BlueDeveloper24

What are you trying to achieve?

Pretty sure they’re trying to detect the occurrence of enclosed spaces in their placement system (like, be able to check/determine with every new block if an enclosed space has been created).

[range_0xE4 (Range)]

I checked it but dont understand at all

[safeLast120]

It looks intimidating at first, however, it’s quite easy once you get the hang of it. I’ll try my best to explain.
Each letter represents a point in the plane, so, given the plane:

where (b , c , d , e) are the vertices of a rectangle, and a is a standalone point.

As a preamble, ‘scalar product’ (also known as ‘dot product’) is an operation that, given two vectors (under this context, but, in theory, it could be any kind of numerical set) returns a scalar number with diverse properties we can apply.

Moving on, to check whether point a is inside the bounds of the rectangle (b , c , d , e) we need to do the following:

which, in pseudo-scripting would be something like this (supposing all the letters are points in the 3D cartesian plane):

if ( (DotProduct(b, (c-b)) <= DotProduct(a, (c-b)) <= DotProduct(c, (c-b)) )
and
( DotProduct(b, (e-b)) <= DotProduct(a, (e-b)) ) <= DotProduct(e, (e-b))
then a is within the bounds of rectangle bcde

Applied to Roblox-Luau, to calculate the dot product we have Vector3:Dot() , which calculates the dot product between the Vector3 called on and the Vector3 that’s passed as a parameter.
The above pseudo-code would be applied like something like this (supposing a, b, c, d, e are all Vector3):

if ( b:Dot(c-b) <= a:Dot(c-b) ) and ( a:Dot(c-b) <= c:Dot(c-b) ) and ( b:Dot(e-b) <= a:Dot(e-b) ) and ( a:Dot(e-b) <= e:Dot(e-b) ) then
  -- point a is within bounds b,c,d,e
end

we can furtherly clean that code by doing something like this (will look longer, but it’s more readable):

local cbDifference = c-b
local ebDifference = e-b
if ( b:Dot(cbDifference) <= a:Dot(cbDifference) ) and ( a:Dot(cbDifference) <= c:Dot(cbDifference) ) and ( b:Dot(ebDifference) <= a:Dot(ebDifference) ) and ( a:Dot(ebDifference) <= e:Dot(ebDifference) ) then
  -- point a is within bounds b,c,d,e
end

Hope that helps.

[range_0xE4 (Range)]

What is a and why do I need it to identify rooms, sorry for such a question. I want to make a system that recognizes rooms formed from building blocks, such as foundations, walls, and so on. Since the construction is going on an infinite grid of 8x8x8 in size, I thought I could use this to write to the table which faces of the grid are blocked by blocks and then using some algorithms to determine the closeness to find this space. Rooms can be of any shape, and rooms can also have common faces, for example, the same wall is a common face in both rooms. As a result, I want to make the algorithm find enclosed spaces and return a certain logical model of the room, which has the components of the room - cells 8x8x8, room volume, temperature, and so on.

[0786ideal (ideal)]

You can use Chunk system to place blocks as chunks, then check all chunks around and see if they are full, if they are then you determined closed space

[safeLast120]

@range_0xE4

What is a

a would be the point in space you want to check whether or not is in a confined space (it’s a Vector3, in this case). meanwhile b, c, d, e would be the locations of the nearby Models (if any) to determine whether they form an enclosed space.

@range_0xE4

why do I need it to identify rooms

You’re taking it as a point to do the calculations of whether it’s within an enclosed space or not (that formula checks for the enclose-ness of a specific point, while it doesn’t directly check for the enclosed space itself).

@range_0xE4

sorry for such a question

It’s completely fine, don’t worry.

@range_0xE4

As a result, I want to make the algorithm find enclosed spaces

I’ll try to develop something to show you that way.
In the meantime, here’s a dev-talk with the developers of RimWorld where they discuss how they handle regions internally, and there are multiple mentions and use of enclosed spaces (I haven’t seen it all, that’s why I’m unsure if they really mention how they did it, but it can give you a good idea of how it’s done): https://youtu.be/RMBQn_sg7DA?si=WmP1doqElgWru6jP (around 16:25 they use an enclosed room, and 25:56 as well, for instance).

[safeLast120]

I provided you, @range_0xE4 , a solution in my past posts; I realized that since you want a 3D space, those comparisons were going to be quite expensive to perform.
Therefore, I propose to you a simple 3D flood-fill algorithm to find enclosed spaces (spaces without contact with the rest, which may be referred to as ‘islands’).

@safeLast120

I’ll try to develop something to show you that way.

Credits to this post and its author:

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

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 che…

for implementing a 2D flood-fill algorithm into Roblox-Luau, which served as the base for my 3D implementation of it:

Video (at the end of the simulation, the black blocks represent the enclosed spaces or ‘islands’):

Script:

local WorkSpace = game:GetService("Workspace")

local baseVector = Vector3.new(8, 8, 8) -- 8-base, since each block is 8x8x8.
local size = 40 -- lower this if in a low-end device.
local perlinDivisor = 5

local gridFolder = Instance.new("Folder")
gridFolder.Name = "Grid"
gridFolder.Parent = WorkSpace

local function generateGrid()
	local grid = {}
	gridFolder:ClearAllChildren()

	for x = 1, size do
		grid[x] = {}

		for y = 1, size do
			grid[x][y] = {}

			for z = 1, size do
				local m = math.noise(x / perlinDivisor, y / perlinDivisor, z / perlinDivisor) < 1/perlinDivisor and 0 or 1

				local part = Instance.new("Part")

				part.Anchored = true
				part.Size = baseVector
				part.Position = Vector3.new(x, y, z) * baseVector
				part.Color = Color3.new(m, 0, 0)
				part.Transparency = 0.8
				part.CastShadow = false
				part.Parent = gridFolder

				grid[x][y][z] = {
					part = part,
					flood = false,
					m = m
				}
			end
		end
		task.wait()
	end

	return grid
end

local function checkForIslands(grid)
	local island = false -- until disproven.
	for x, yzGrid in pairs(grid) do
		for y, zGrid in pairs(yzGrid) do
			for z, val in pairs(zGrid) do
				if val.m == 0 and not val.flood then
					val.part.Transparency = 0
					island = true
				end
			end
		end
		return island
	end
end

local function flood(grid, x, y, z)
	if grid[x][y][z].flood then return end

	grid[x][y][z].flood = true
	grid[x][y][z].part.Color = Color3.new(0, 1, 0)
	task.wait()
	--grid[x][y][z].part.Color = Color3.new(0, 0, 1)
	grid[x][y][z].part.Transparency = 1

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

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

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

	if x == size and y == size and z == size then
		print("Island?:", checkForIslands(grid))
	end
end

local grid = generateGrid()

task.wait(1)

flood(grid, 1, 1, 1)

Let me know whether this is what you’re looking for or not.
In case yes, let me know if this is enough and you can take on from here or you would like further guidance for your specific case.

[vyexon (zephyr)]

why are you so smart dude

(this is off topic btw)

[safeLast120]

Quite appreciated, haha!
That script I posted isn’t that advanced: The other member I based-off over provided the actual solution, my 3D implementation is just a simple to-3D extrapolation of it.

[range_0xE4 (Range)]

It’s cool, but it’s not exactly what I need. You have exactly the blocks implemented, but if I need to make a wall, it will also be common for two rooms, for example. It’s like one common blocked face of the grid. Also grid is infinity size, only information we have is blocked faces of this grid. Thats i mean

[safeLast120]

So, instead of having full 8x8x8 blocks you want 8x8x8 thin ‘faces’ (in the 6 directions of the cube), and if there are two adjacent blocks, just remove their adjacent faces (so they’re not rendered and save up resources)?

[range_0xE4 (Range)]

I finally made it, it was 5 days for me. This i get to work. Some bugs i detected with small spaces, but often it work.

local Service = {}
Service.__index = Service

local Directions = {
	Left = Vector3.new(-1, 0, 0), 
	Right = Vector3.new(1, 0, 0),
	Front = Vector3.new(0, 0, -1),
	Back = Vector3.new(0, 0, 1),
	Up = Vector3.new(0, 1, 0),
	Down = Vector3.new(0, -1, 0)
}

local OppositeDirections = {
	[Directions.Left] = Directions.Right, 
	[Directions.Right] = Directions.Left,
	[Directions.Front] = Directions.Back,
	[Directions.Back] = Directions.Front,
	[Directions.Up] = Directions.Down,
	[Directions.Down] = Directions.Up
}

function Service.new(CellSize: number)
	local self = setmetatable({}, Service)
	
	self.CellSize = CellSize
	self.Cells = {}
	
	return self
end

function Service:IsFaceBlocked(CenterPosition: Vector3, Direction: Vector3)
	local Cell = self.Cells[CenterPosition]
	local NextDoorCell = self.Cells[CenterPosition + Direction * self.CellSize]
	
	if Cell and Cell.Blocked[Direction] then
		return true
	end
	
	if NextDoorCell and NextDoorCell.Blocked[OppositeDirections[Direction]] then
		return true
	end
end

function Service:AddCell(CenterPosition: Vector3, BlockedFaces: {})
	self.Cells[CenterPosition] = { Blocked = {} }

	local cell = self.Cells[CenterPosition]
	cell.Position = CenterPosition

	if #BlockedFaces >= 6 then
		cell.CantBeRoomCell = true
	end

	for _, face in BlockedFaces do
		local Direction = Directions[face]
		local NextDoorCell = self.Cells[CenterPosition + Direction * self.CellSize]
		
		if not NextDoorCell then
			self.Cells[CenterPosition + Direction * self.CellSize] = {}
			
			NextDoorCell = self.Cells[CenterPosition + Direction * self.CellSize]
			NextDoorCell.Blocked = {}
			NextDoorCell.Position = CenterPosition + Direction * self.CellSize
		end
		
		NextDoorCell.Blocked[OppositeDirections[Direction]] = true
		cell.Blocked[Direction] = true
	end
end

function Service:RemoveCell(CenterPosition: Vector3)
	self.Cells[CenterPosition] = nil
end

function Service:AddFacesToCell(CenterPosition: Vector3, BlockedFaces: {})
	local Cell = self.Cells[CenterPosition]
	
	for i, v in BlockedFaces do
		Cell.Blocked[Directions[v]] = true
	end
end

function Service:UpdateCell(CenterPosition: Vector3, BlockedFaces: {})
	local Cell = self.Cells[CenterPosition]
	Cell.Blocked = {}

	for i, v in BlockedFaces do
		Cell.Blocked[Directions[v]] = true
	end
end

function Service:FindEnclosedAreas()
	local visited = {}
	local enclosedAreas = {}

	local function isFullyEnclosed(startPosition)
		local queue = { startPosition }
		local areaCells = { startPosition }
		visited[startPosition] = true
		local fullyEnclosed = true

		while #queue > 0 do
			local currentPos = table.remove(queue, 1)
			local currentCell = self.Cells[currentPos]

			for direction, vector in Directions do
				local neighborPos = currentPos + vector * self.CellSize
				local neighborCell = self.Cells[neighborPos]

				if not self:IsFaceBlocked(currentCell.Position, vector) then
					if not neighborCell then
						fullyEnclosed = false
					elseif not visited[neighborPos] then
						visited[neighborPos] = true
						table.insert(queue, neighborPos)
						table.insert(areaCells, neighborPos)
					end
				end
			end
		end
		
		return fullyEnclosed, areaCells
	end

	for position, cell in self.Cells do
		if not visited[position] then
			local enclosed, areaCells = isFullyEnclosed(position)
			
			if enclosed and areaCells then
				for i, v in areaCells do
					local Cell = self.Cells[v]
					
					if Cell and Cell.CantBeRoomCell then
						table.remove(areaCells, i)
					end
				end
				
				if #areaCells < 1 then continue end
				
				table.insert(enclosedAreas, areaCells)
			end
		end
	end

	return enclosedAreas
end

function Service:VisualizeBlockedFaces(CenterPosition: Vector3)
	local cell = self.Cells[CenterPosition]
	if not cell then return end

	if cell.Visuals then
		for _, visual in cell.Visuals do
			visual:Destroy()
		end
	end
	cell.Visuals = {}

	for direction, isBlocked in cell.Blocked do
		if isBlocked then
			local visual = Instance.new('Part')
			visual.Size = Vector3.new(self.CellSize, 0.2, self.CellSize)
			visual.Anchored = true
			visual.CanCollide = false
			visual.CanQuery = false
			visual.Color = Color3.new(1, 0, 0)
			
			local position = CenterPosition + direction * (self.CellSize / 2)
			
			if direction == Directions.Up or direction == Directions.Down then
				visual.CFrame = CFrame.new(position) * CFrame.Angles(0, math.pi * .5, 0)
			elseif direction == Directions.Front or direction == Directions.Back then
				visual.CFrame = CFrame.new(position) * CFrame.Angles(math.pi * .5, 0, 0)
			elseif direction == Directions.Right or direction == Directions.Left then
				visual.CFrame = CFrame.new(position) * CFrame.Angles(0, 0, math.pi * .5)
			end
			
			visual.Parent = workspace

			table.insert(cell.Visuals, visual)
		end
	end
end

function Service:VisualizeRooms()
	if self.RoomVisuals then
		for _, visual in self.RoomVisuals do
			visual:Destroy()
		end
	end
	
	self.RoomVisuals = {}

	local enclosedAreas = self:FindEnclosedAreas()

	local function getRandomColor()
		return Color3.fromRGB(math.random(0, 255), math.random(0, 255), math.random(0, 255))
	end

	for _, areaCells in enclosedAreas do
		local roomColor = getRandomColor()

		for _, cellPosition in areaCells do
			local visual = Instance.new('Part')
			visual.Size = Vector3.new(self.CellSize, self.CellSize, self.CellSize)
			visual.Anchored = true
			visual.CanCollide = false
			visual.CanQuery = false
			visual.Color = roomColor
			visual.Transparency = 0.5
			visual.Position = cellPosition
			visual.Parent = workspace

			table.insert(self.RoomVisuals, visual)
		end
	end
end

function Service:VisualizeAllBlockedFaces()
	for position, _ in self.Cells do
		self:VisualizeBlockedFaces(position)
	end
end

return Service

[safeLast120]

Congratulations, that’s great to hear!
Glad you found a working solution.