Procedural generation of building interiors (part 4)

This post follows on from part 1, part 2, and part 3.

Last time we had got as far as allocating space for rooms and hallways, and ensuring that all hallways connected up. Next, all that space needed to be split up into individuals rooms.

Rather than go straight to rooms, I opted to split the space into rectangular areas that could then be subdivided into the final rooms. In hindsight I can’t remember why I decided to go for this two-phase approach. Perhaps I was worried about being left with unusable or unconnected space. Maybe I’ll try going straight to room-by-room generation for the production game.

To identify these initial areas I added a scan for the first available square of room space, left-to-right and top-to-bottom (just like the hallway scans previously). This established the top-left corner of the area.

But how to set the width and height, and keep the area rectangular? The solution I chose was to work out the maximum possible width for the area before it hit a hallway or exterior square on the first row of squares only, then see how many rows down that same width could be used. Rectangular area achieved!

Repeating this scan-and-allocate process lead to all the available space being partitioned into rectangles. I visualised this on the map, giving each area its own colour.

The second phase required the division of areas into Rooms of a Reasonable Size. For “reasonable size” I picked a 6×6 square, which would translate to something like 24×24 tiles in the final tile map.

I started by dividing the areas in half horizontally. If each subdivision was still wider than the 6 squares then I divided it again, continuing recursively until the limit was satisfied.

I updated the visualisation to show these new narrower areas. This was also the moment I finally realised I could add spacing to the squares in the map to make the grid visible!

By running the same subdivision process in the vertical direction on the narrow areas, I ended up with rooms all under the 6×6 square target.

As I tested the generation with different maps I noticed that sometimes things looked a bit wonky, with uneven division of space. I scaled back my starting map to a single 8×8 square. Uh oh!

I could see the initial 8x8 area in green poking through between the subdivided rooms. Digging into the code I could see that I was getting the boundary conditions wrong. With that fixed, the minimal test case looked a lot better.

I reduced the room limit to 5×5 as a test on the same map as above and everything appeared to be working as expected.

This was a very satisfying milestone to hit. With this achieved I had a full outline of a zone map that I was confident I could turn into a tile map for a game level.

But I needed more than just a map. To turn it into a game level I wanted to divide it into zones, each zone being a puzzle to be solved before players could progress to the next zone. That problem is what we’ll look at in part 5.