How to do room detection on non-grid based walls

Question

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.

Answer 1

Answer by FortisVenaliter · Apr 13, 2017 at 07:25 PM

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.

Add comment · Show 3 · Share

FortisVenaliter · Apr 13, 2017 at 07:53 PM 0

Share

Just thought of a second way to do it: Use a triangulation algorithm. There are algorithms that take edges and generate triangles out of them to build a mesh. You can use that to get the triangles, and then merge any that share an edge without a wall on that edge. Then your rooms would be defined by the collection of triangles.

KubaPrusak · Apr 13, 2017 at 07:54 PM 0

Share

Thanks for replying. I've created an algorithm in my $$anonymous$$d on how to do it, the problem I have is actually writing it as code. alt text

I've attached what I think is the correct way of approaching this. However as you can see there are lots of nested for loops which could go on for a long time, eg. Wall5 has another neighbour which has another neighbour etc. I can't figure out how I'm meant to allow for basically infinite for-loop regression further and further down the wall neighbours (Wall5 and further) and then go back up the tree to move onto the next neighbour (Wall2 => Wall3).

$$anonymous$$any thanks.

example.jpg (415.2 kB)

FortisVenaliter KubaPrusak · Apr 13, 2017 at 07:56 PM 0

Share

I would look at the A* pathfinding algorithm for inspiration (you're basically traversing paths through the wall nodes as part of this algorithm after all). Using open and closed lists will allow you to limit yourself so you don't get stuck in infinite loops.

Answer 2

Answer by KubaPrusak · Apr 15, 2017 at 04:29 PM

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.

Add comment · Show 1 · Share

bre_dev · Jun 02, 2019 at 10:27 PM 0

Share

Hi, any chance you could provide a code snippet for this? I have been looking for a solution for weeks. Also, what if it would have been grid-based walls ins$$anonymous$$d? Would the solution have been different?

How to do room detection on non-grid based walls

2 Replies

Your answer

Follow this Question

Related Questions