Room detection system

Getting into somewhere…

1 Like

Nice, don’t know if it’s much help at this point but you could also try pathfinding from different points and see if you can successfully generate a path outside the walls.

Oh…This i have never thought of ! For my case this would actually work yes!

But besides, making this system was so hard and it still doesnt work in some cases, for example when one node shares more than 2 other nodes:

What algorithm are you using to find cycles? DFS should work without any problems and is easy to implement.

kinda tried to implement that exactly but i dont know, somewhere i do something wrong…

Show the code of the algorithm so I will have a look at it.

The main issue is that you might create a wall ending inside another wall, thus creating a node loop that’s ‘not connected’.
If that wasn’t a problem then you could easily just bruteforce-check every possible node constellation to see if there’s a loop.

To check if your node is inside another wall you could simply just use this function:

local abs = math.abs 
function PartContains(part, pos) 
  local objectPos = part.CFrame:pointToObjectSpace(pos) 
  local partSize = part.Size
  return abs(objectPos.X) <= partSize.X / 2 and abs(objectPos.Y) <= partSize.Y / 2 and abs(objectPos.Z) <= partSize.Z / 2 
end

Every time you create a new wall you’d need to run this for all existing walls but it’s not an expensive function to use so you should be fine.

IF your node is inside a wall, it’s ‘connected’ to both nodes that make up the wall.
Then just run whatever nodeloop checker of your choice to find the rooms :wink:

1 Like

I will send you it on private soon

Hey! I’ve been experimenting with stuff since I’m rusty with computational geometry and I think I’ve got something working…

Room

If we have a graph of vertices and edges and we treat each room as a cycle of edges, then the way I’m using to pick rooms is to do a counter-clockwise walk around edges. Hopefully, this nice MS Paint diagram will help:

Counterclock

To calculate this we’ll need to have some way to determine how to move counterclockwise. Fortunately, this is not too tricky - for each node, sort each neighbour by the relative angle:neighboursort

From this, to find the next anticlockwise neighbour, just add one to the index - neighbour 2 is one after neighbour 1. And don’t forgot to connect the ends: Neighbour 1 is one after neighbour 5!

This is all relative to the blue node of course, so here’s yet another diagram to elaborate:elaborate

We’ll say after[E][B] = A and after[F][C] = I.
backtothepiast

Back to the original MS Paint masterpiece, we can see that if we keep applying after with shifting inputs, we find our room:

after[A][B] = C
after[B][C] = D
...
after[F][A] = B
after[A][B] = C -- hang on a second, we've seen this before! time to stop

And if we record what we’ve passed through, then we’re done! Apply this process to every unvisited edge and we’ve discovered every room. For an example script, the one used to generate the first image is in ServerScriptStorage in: room.rbxl (17.8 KB)

6 Likes

Almost everyone was suggesting to use the DFS algorithm where as you, you used an algorithm i can say that you found it yourself!

Neat one!

I have idea to put every wall in model as primaripart and put bool to the model that is false and when i place it i need to test if the wall colide with another wall and if yes i will move it to the model with wall it is coliding and then test if it is coliding with another wall if yes i will test if the wall is in the same model, if no i will put the wall to the same model and i will test the same thing for the wall, if yes i will put the bool in the model to true and that is saying if the room is completed

sry i am not including code, because every time i try it, it is formated as normal text xC

Oh you can write code here in the code’s format like this

` `` lua (Without spaces between dots and without this text in parentheses)
–YOuR CODE GOES HERE
THEN END IT WITH ```

And i think ive understood now what you mean…
It seems logical!
I should try something like that

1 Like

i havent any code now, i try to say it better, when i send remote event to add new wall i will try if the wall colide with some other wall, now if
no) i will create new model with the wall in it and i will also add bool to the model (with value false)
yes) l will add the wall to model that is parent of the wall that is coliding with the wall i am adding and i will try if there is any other wall coliding with the wall i am adding if
no) i will place the wall and no room there is posible without adding another wall
yes) i will test if it is in same model as the first wall, if
yes) the room is ok so i will set the bool in the model to true
no) i will move it to the model, that is parent of first model (i must clone it if one wall can be wall of 2 rooms)

realy sry, but i havent got time to write code

I tried it ad got soething like this from what i understood from you…
obviously it is not what you mean for sure xd

roomz.rbxl (17.1 KB)

i am not sure if i understand your code, but i think you need to test if another part is touching it and if yes you must test if parent of the part is same as parent of the part that you are placing and if yes it must be conected at the other side, so it is room and there must be bool in every model, that is saying if it is room or not

I really wish you could show me a place example with it, r just a code
I can not understand further than this though

yes i am now trying to make it

1 Like

and you never call the function, that is testing if it is room so how can it work (now i am reparing)

good news it is working (at least for me)roomz.rbxl (17.1 KB)

But purple one is not room?