Validate structure for a room escape game

Question

In a game like a simple adventure or a room escape game, I would like to know if there are established algorithms to check for simple constraints on the layout.

I would like some pointers so I could do my own research, or on the algorithms or on this kind of problems.

In a simplified case, if we guess the game is 2D, and the environment is the classic grid N x M, where a cell can be an empty place, a wall or a door, there could be these requirements:

• every room must be a rectangle
• every room must have a door at least
• every room must be reachable from any other (aside the possibile locked doors)
• all the rooms must be connected, so no disjoint groups of rooms
• all the walls must be thick only one cell

I know this sound strange because if I design my own game with few room obviously it's possible check with bare eye if everything is ok in the map. But I like the theory side of the things.

Answer 1

The requirement 1 (every room must be rectangular) can be tested using the flood fill algorithm. This algorithm allows you to start from somewhere on a tile-based map and find all tiles that can be reached from it. This is a very common and well-documented algorithm, so I don't think I need to go into detail how to implement it.

When you start this algorithm in a room and stop at any doors, then you end up with a list of all the tiles the room consists of. Are they in a rectangle? You can find that out by

1. find the the upper-leftmost tile in the array
2. find the lower-rightmost tile in the array
3. calculate the area of the rectangle formed by those two tiles
4. check that the length of the array matches the area of the rectangle

If you have less tiles, then you don't have an unbroken rectangle. If you have more tiles, then your flood-fill implementation is broken, because you are double-counting tiles.

The requirements 2, 3 and 4 (no unreachable areas) can also be tested using the flood fill algorithm, but instead of stopping at doors, you continue. If all tiles of the map are either reachable or walls, then you know that all the rooms are connected.

Requirement 5 (no double-walls) can be verified by scanning for "2x2 squares" of wall. For each tile that is wall, check that at least one of the tiles (x+1, y), (x+1, y+1) and (x, y+1) is empty.