In my game, you can build walls by dragging, these walls can exist anywhere, i.e. there is no grid. Which leads me onto the problem of how do I do room detection if there is no grid.
I’ve looked into marching squares but that is a grid based algorithm. I know the two nodes of each wall and each walls connecting neighbouring walls.
I can’t use the a* algorithm because the start and end wall is the same in order to detect a room, so I’m stuck at what to do. I’ve tried to unsuccessfully create my own algorithm but I’m finding it difficult.
Any help would be greatly appreciated.
Thanks.
The easiest way would be to run through the wall segments and look for loops. Run from corner node to corner node. When you hit the node you started with again, if you’ve traversed at least three wall segments, you’ve found an enclosed area. You’ll need to look for additional walls inside that area to determine if it’s divided into multiple rooms, but that should get you started.
I figured out a solution.
Basically each wall piece has two Nodes, one for the starting point and one for the ending point of the wall. I then run an a* pathfinding algorithm where the start point and end point of the algorithm are the start and end nodes of one wall (doesnt matter what wall it is). However there is no neighbouring connection between the start and end node which forces the algorthim to find a ‘U’- shaped path to connect the start of the wall to its end. You can figure out the neighbours of each node by getting colliding walls for each node.wall and then sorting through them to get only the actual/allowed nodes you want. If the wall is part of a room, the pathfinding will return a list of nodes through which you can iterate and get the walls that make up the room.