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
1 Like
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
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
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
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.
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).
I checked it but dont understand at all
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.
1 Like
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. 
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
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.
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).
It’s completely fine, don’t worry.
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).
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’).
Credits to this post and its author:
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.
2 Likes
why are you so smart dude
(this is off topic btw)
1 Like
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.
2 Likes
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
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)?
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
1 Like
Congratulations, that’s great to hear!
Glad you found a working solution.