Identify doorways to partition a collection of walls with gaps into rooms

Question

I am looking for an algorithm that can find separate rooms inside a set of walls, by determining which openings should be considered doorways between adjacent rooms. All is defined on a grid. My main problem is that I cannot be sure that both sides of the same passage will be in one straight line.

In the picture there is an example with five rooms separated with red lines and black walls, although it might be acceptable to merge the middle room with one of the others. I have the black walls as input, and I want to generate the red lines marking the doorways as the output.

Basically I am trying to avoid having to mark them manually to minimize any chance of making a mistake. I made some attempts with focusing on the corners, but got stuck with the passageways not in a straight line problem.

Any ideas?

The walls are stored in a two dimensional array of (half-)bytes storing a bitmask where

• 1 means that the wall in this cell has a connection to the cell above
• 2 -> connection to the cell to the right
• 4 -> connection to the cell below
• 8 -> connection to the cell to the left
• 0 -> cell is empty room

If the wall in a cell has multiple connections the sum of the connections is stored. For example a '3' would represent a "L" shaped wall segment, 'E'(14 in hex) would represent a "T" shape and 'F'(15) would represent a "+" shape.

The example would be stored like this:

6AAEAAC  
5001005  
5000005  
780002D  
5000005  
5005005  
3AA9029 

Answer 1

This is a variation of an algorithm I used myself in a grid based randomly generated level (a simply 0= empty 1= wall grid) to place doors.

Finding possible doorway tiles

There are some simple rules depending on the surrounding tiles to determine whether or not there can be a door.

The tile itself must be empty and have at least two neighboring wall tiles that are not connected with each other (only within the neighbors).

For this you can examine the neighboring tiles counter-clockwise. Whenever you examine a "wall" tile after examining an "empty" tile you increase a counter by 1. If that counter is exactly 2 after one complete circle (examining the first tile a second time as last tile). you have a possible doorway.

However this will produce "to many" doorways, often adjescant to each other. In your example the door at the lower edge has two possible doorway tiles. The "real" doorway you marked as red in the image and the empty tile directly above that.

Finding the right doorway tiles

Now that we have all possible doorway tiles (here X but maybe marked with -1 in the array)

6AAEAAC  
5001005  
50X0X05  
780002D  
50X0X05  
5005X05  
3AA9X29 

To solve this problem you could create a "ranking" on how the best/worst doorway situations look like. For this ranking we can continue using negative numbers in the array, e.g. -1 being "the best" doorway and "-F" being the worst

1. The "best" doorway tile is a tile that has exactly two adjescant wall tiles that are exactly opposite of each other and only empty tiles as neighbors otherwise.
2. Next come those with more than two adjescant wall tiles but who still have two exactly opposing wall tiles
3. Next those that have exactly two adjescant wall tiles which are not exactly opposite of each other
4. And lastly all remaining doorways.

With the ranking in place we can always delete the worse of two adjescant doorway tiles or a random one in case of equal ranking.

This should leave you with nicely placed doorways.

Answer 2

It took a while, but I think I got some thing.

It might not work with small rooms, but with at least 3 fields in diameter should work.

1. Assign to each field an integer value equal to its distance to the nearest wall. This will create disconnected patches of higher numbers. Each patch will be a core of a room.
2. Expand each patch by adding to it every field adjacent to it that does not neighbors a field with an assigned number higher than its own, unless the field with a higher number already is a part o the patch.
3. Repeat until no new fields are added to any of the patches.
4. A few fields may still be outside of every patch. Add them to the nearest patch (several if more than one patch are at the same distance).

Curious thing happens with a long corridors between large chambers, if the is no narrowing at the end. In that case the corridor is considered a part of both chambers. Which turns out suits my purpose.