If you search “room detection”, the amount of topics without solutions in truly comedic, so this isn’t just for me, but for everyone who didn’t get a solid reply to satisfy or solve there approach.
I know, basic flood fill but, how do you get all the walls in the plot in a line with the table?
What have you tried?
Well like I’ve said previously, I already know how to implement 2d array based flood fill, but reverse engineering it to work with a 3D plot space is very difficult, to say the least.
What doesn’t seen to we functioning?
Everything lol.
I would either make it so you dont place walls individually before the creation of a room, but you can edit it later, after the room is “defined” and a basic shell of walls is created, or make some sort of system which searches for continuous loops of walls based on shared nodes or smthn
Which sounds most promising?
In both of these instances, they create the parts along with the tables and/or are just checking a set of walls. I want to check the entire plot for multiple said rooms.
Okay let me see if I’m understanding you correctly now xD
You have a building “plot” where walls can be built by the player in a grid, and you want to look through the entire plot and find all the fully enclosed rooms? And by “finding rooms” you mean a list of “plot/grid tiles”?
If that’s the case, then yeah flood fill definitely works. You’ll need some definition of what tiles are neighboring, and a definition of what tiles can/cannot be traversed by the filling algorithm.
I don’t know what data structure you’re using for the plot tiles, but I would go with a “2D coordinate to tile map”, or more formally an associative array where each key is a pair of coordinates (i.e. integers) and each value is a tile in the plot, which can be a model, or a table containing info about the tile. I like using tables for that. In Lua, such a 2D map could be defined like this:
function mapGet(map, c1, c2)
assert(c1 % 1 == 0 and c2 % 1 == 0, "mapGet shouldn't be called with non-integer coordinates")
if map[c1] then return map[c1][c2]
end
function mapSet(map, c1, c2, value)
assert(c1 % 1 == 0 and c2 % 1 == 0, "mapSet shouldn't be called with non-integer coordinates")
if map[c1] then
map[c1][c2] = value
end
end
We can automatically set up the map at runtime by looking at the plot and each tile model:
local PLOT_GRID_SIZE = 4
local tileMap = {}
for _, tileModel in pairs(game.Workspace.Plot.Tiles:GetChildren()) do
--TODO: Round coordinates to nearest 1 before calling tileSet
local x = tileModel.PrimaryPart.Position.X / PLOT_GRID_SIZE
local y = tileModel.PrimaryPart.Position.Z / PLOT_GRID_SIZE
mapSet(tileMap, x, y, {x = x, y = y, model = tileModel, walls = {}})
end
I added an empty list of walls for each tile, to keep track of which walls overlap each tile in the plot. That way we can check if traversal is allowed from one tile to the next.
Every time a wall is added or removed by the player, we need to add or remove it from each tile that becomes or was overlapped by said wall. You can use a “get grid cells along line segment” algorithm to figure out which tiles to update, so you avoid looping through every tile in the plot every time a wall is changed. Here’s an article describing it for hexagonal grids, but the idea is the same for rectilinear grids:
Let me know if you need help adapting it.
Now that our tileMap is set up, we can nicely define our ideas of neighbors:
-- Insert a value into a list only if value is not nil, otherwise do nothing.
-- Avoids error on inserting a nil value
function insertIf(list, value)
if value ~= nil then
table.insert(list, value)
end
end
function getTileNeighbors(tile)
local neighbors = {}
insertIf(neighbors, mapGet(tileMap, tile.x - 1, tile.y))
insertIf(neighbors, mapGet(tileMap, tile.x, tile.y + 1))
insertIf(neighbors, mapGet(tileMap, tile.x + 1, tile.y) )
insertIf(neighbors, mapGet(tileMap, tile.x, tile.y - 1))
return neighbors
end
We can combine our ideas of “walls” and “neighbors” to define “traversability”:
function canTraverse(tileFrom, tileTo)
local fromNeighbors = getTileNeighbors(tileFrom)
if #tileFrom.walls > 0 or #tileTo.walls > 0 then return false end --cannot traverse walls
if not table.find(fromNeighbors, tileTo) then return false end --must be neighbors
--TODO: Should probably error if tiles are not neighbors?
return true
end
Now we have everything we need to run our flood fill algorithm (i.e. our graph is well defined). Imma use a slightly modified version of this from wikipedia:
function floodFill(nodeFrom, getNodeNeighbors)
local regionDict = {[nodeFrom = true]}
local stack = {nodeFrom}
while #stack ~= 0 do
local node = stack[#stack]
table.remove(stack, #stack)
for _, neighbor in pairs(getNodeNeighbors(node)) do
if not regionDict[neighbor] then
regionDict[neighbor] = true
table.insert(stack, neighbor)
end
end
end
-- Turn the node->true dictionary into an array
local region = {}
for node, _ in pairs(regionDict) do
table.insert(region, node)
end
return region
end
This is a completely generic version of flood fill that can be used with any graph, and the sole definition of the graph is some starting node in the graph and a function that defines neighborhood in the graph. It doesn’t make any assumptions about the problem space, so we have to build those assumptions into the getNodeNeighbors function (the parameter to floodFill, not out previous definition).
That could look like this:
function filter(list, predicate)
local result = {}
for _, value in pairs(list) do
if predicate(value) then
table.insert(result, value)
end
end
return result
end
local region = floodFill(
mapGet(tileMap, 1, 1),
function(node) --getNodeNeighbors
local allNeighbors = getNodeNeighbors(node) --this is our previously defined function
local validNeighbors = filter(allNeighbors, function(neighbor) --not all "neighbors" are valid
return canTraverse(node, neighbor) --only the neighbors that don't have walls
end
return validNeighbors
end
)
This correctly finds one region from a starting node, but what we want is all regions. We can adapt it to do what we want by repeatedly floodfilling from a starting node that is “not yet in a region”.
--allNodes is modified
function findAllRegions(allNodes, getNodeNeighbors)
local nodeToRegionDict = {}
local noRegionNodes = {}
for _, node in pairs(allNodes) do
noRegionNodes[node] = true
end
local regions = {}
local startNode
while true do
startNode = next(noRegionNodes, startNode) --gets next element of noRegionNodes, even works when some entries have been set to nil
if not startNode then break end
local region = floodFill(startNode, getNodeNeighbors)
table.insert(regions, region)
for _, regionNode in pairs(region) do
noRegionNodes[regionNode] = nil
nodeToRegionDict[regionNode] = #regions
end
end
return regions, nodeToRegionDict
end
Every time a region has been found from a start node, the algorithm updates the dictionary of “nodes not yet in a region” by removing every node in the newly found region from the dict. That way, every time a node is picked from that dict, it is guaranteed to not be in a region yet. Since nodes are only removed from it when their respective region has been found, once the dict is empty we’re guaranteed to have found every region.
You can call this function like so:
local rooms = getRegions(
myListOfTiles,
function(node) --getNodeNeighbors
local allNeighbors = getNodeNeighbors(node) --this is our previously defined function
local validNeighbors = filter(allNeighbors, function(neighbor) --not all "neighbors" are valid
return canTraverse(node, neighbor) --only the neighbors that don't have walls
end
return validNeighbors
end
)
The second parameter, the anon function that starts with function(node) --getNodeNeighbors, is the same as from the call to floodFill.
and rooms will be a list of lists. Each sublist is a “region”, defined as a list of all tiles in that region. It also has a 2nd return value, which is a node to region dictionary. The key of each entry in the dict is a node, and the corresponding value is the region that said node belongs to, represented as a number. This number matches the index of the region in the first return value. Don’t know if you need this, you can remove it from the algo if you don’t.
Unfortunately I can’t test this code right now, so there’s bound to be typos or even conceptual errors. Let me know if you find any that you can’t fix on your own, and I’ll see if I can get Studio running
Also let me know if anything is confusing or you’d like something cleared up, and I hope this is helpful ^.^
I haven’t tried this code yet but remember, I already know how to accomplish basic flood fill.
Example (this is cut, just for reference)
local Table = {}
for x = 0, 20 do
for y = 0, 20 do
local Part = instance.new(‘Part’,Tiles)
table.insert(Table, Part)
end
end
This would create a 20x20 grid, but do you see how I create the parts with the script, then make these rooms from the parts.
I want to know how do I get each wall on the plot in that area.
For example:
Say the area of said tile is vector(2,0,1)
do I create a region3 for said vector and check for walls that way?.
Do you guys see what I’m talking about?
But here’s my best guess: you’re generating the tiles / floor parts with a script and inserting them into a table, so that’s no problem. But you’re unsure how to get a list of all the wall parts / borders between tiles based on that.
Here’s a diagram:
You already have a list of the orange floor tiles, and want to turn that into a list of all the blue walls?
You can do that by using this basic unit of the repeating pattern:
Or in other words, for every floor tile you get of the surrounding walls. If you repeat this for all the tiles you get this pattern:
Notice that two of the outer edges are missing, so that needs to be dealt with.
local PLOT_SIZE = 20
local floorTiles = {}
local walls = {}
for x = 0, PLOT_SIZE do
for y = 0, PLOT_SIZE do
--Create floor
local floorTile = instance.new(‘Part’, TilesFolder)
table.insert(floorTiles, floorTile)
--Create wall in the +X direction
local wallPlusX = Instance.new('Part', WallsFolder)
table.insert(walls, wallPlusX)
--Create wall in the + direction
local wallPlusY = Instance.new('Part', WallsFolder)
table.insert(walls, wallPlusY)
--Create wall in the -X direction only at the -X edge of the plot
if x == 0 then
local wallMinusX = Instance.new('Part', WallsFolder)
table.insert(walls, wallMinusX)
end
--Create wall in the -Y direction only at the -Y edge of the plot
if y == 0 then
local wallMinusY = Instance.new('Part', WallsFolder)
table.insert(walls, wallMinusY)
end
end
end
You didn’t include any code for positioning the floors in the code you posted, so I didn’t add that. Let me know if you’d like help with that too
