Validate structure for a room escape game

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.

• The first question is "how are you packing your rooms?" Because if all walls are 1 thick, then either they're on a grid or they're all of a common width (or height). Anything else is going to result in dead area. Honestly, I'd suggest you start coming at this from the generation side... Write a script that generates rooms meeting your criteria and validation algorithms for your specific use-case will fall out of that naturally. If you hit issues with an implementation detail, ask here. Commented Sep 27, 2023 at 1:50

1 Answer

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.

• Philipp, thanks for the answer. I think you are right the flood filling is the simplest way. I am just not sure about the proposal for requirements 2 3 4. If I have a big grid and a single small rectangular room in the middle, that would be ok but the external part of the map would be unreachable (as it should be, except for the final door letting the player escape). And if I let the flood traverse the doors, then 2 disjoined rooms would be filled along with the whole map but that would not be ok. I need to think about something in this case. Commented Sep 28, 2023 at 11:30
• @john_smith Your question never mentioned anything about an "external part of the map" existing or a "final door letting the player escape". When you post an algorithm question, then it is important that you mention all the requirements and constraints. Commented Sep 28, 2023 at 11:39
• Sorry if I was not complete in my post. I though the empty tiles could be considered inside or outside, but I should have clarified better. And the final door is a given in most cases of escape games. Commented Sep 28, 2023 at 13:17