Grid based dungeon with random room sizes

Question

I'm making a game, where levels are grid based. At first, I have rectangle MxM cells. Then within this rectangle I have to put rooms. Room is another rectangle which is AxB cells, where 2 <= A, B <= 4. Besides, It's necessary to put N rooms in each row and N ones in each column. They should fill all the space, there can't be empty space between them. In other words, I have to feel rectangle with other rectangles the way that there will no be empty space between them and they will form a grid with N rows and N columns.

What I did: I store information about rooms in form of their left-top corner, calculate it and then put rooms based on their and neighbor's corners. To do that:

1. Divide grid on rooms 3x3
2. In each of 3x3 rooms define area which is obligatory floor (2x2 square, let's call it red area)
3. In loop for each room count it's neighbor x and y corner position the way that it doesn't cross none of the obligatory floor ares. For that: a. Get red area of current room and it's neighbors. Set corner somewhere between them, making sure the dimensions of the room are within range above. b. Resolve collisions, when it's not possible to set random corner. For instance, if x position of room above isn't equal to our room, then we can't put horizontal wall between to rooms righter them in random y position, because in that case these rooms will overlap each other.
4. Some other stuff with converting information about corners to rooms themselves

So, what's the problem? My code with a lot of if-statements and crutches became so unreadable and huge that it almost impossible to test and find bugs. Approach I used seems to work but it's impossible to control the way it's working or not working.

Another issue is that I want to have more control on how it looks like. Grid must be interesting, which means that neighbor rooms are preferably not of the same size. There's an example (grid) of such a grid (with red areas that are gray there), which is not bad.

Is there some alternative to solve this? In other questions I saw a lot of similar solutions, but all of them doesn't assume that there's fixed amount of rows and columns. Recommend me some articles I haven't managed to find, probably, literature devoted to this topic, or point the direction where to move and find a working solution.

Answer 1

A traditional method of generating grids containing rooms is to use Binary-Space-Partition trees.

One thing about that method is that it often produces grids that are less densely populated than your example. You might be able to modify some BSP example code and make the map more dense though.

Another possible approach would be to generate the rectangles first, (perhaps with a border along two edges for the gap) then try to pack them using a rectangle packing algorithm. This previous answer has several potential packing algorithms.