Procedural generation of building interiors (part 2)

This post follows on from part 1.

Having lined the outer perimeter of our building with space for rooms followed by space for a connecting hallway, the next question was how to fill the remaining space? With the “fill space inward from the perimeter” algorithm already coded, why not just do the same again and keep filling inward?

To recap, the predominantly yellow areas are for rooms and purple is for hallways. This looked pretty promising! (There’s a tiny grey square in the middle unused. Perhaps we could turn that into a support pillar or light well?)

A key lesson I’ve learned is that it’s important to run a lot of generations to see if any (or more realistically how many) problematic edges cases turn up.

In this example the part of the algorithm reserving 3 squares of space for inner hallways has lead to a very narrow space for rooms being created. That got added to the list of future worries.

I took the brakes off on the second pass for room space to see what would happen in larger buildings.

This lead to huge internal rooms. If I decided to have an upper limit to individual room size, which seemed likely, this could result in room space unreachable from a hallway. But perhaps we could divide oversized rooms up later, with rooms connecting to rooms?

This didn’t feel right and if every building only had one internal hallway then they might all start to feel the same. (Regarding variation, I forgot to mention in part 1 that I had always intend to take a random selection of chunks out of the starting rectangle to add variety beyond the L-shaped buildings seen in all the screenshots here.)

I decided to limit the size of the inner perimeter of rooms to twice that of the outer perimeter. So, if the outer rooms were a maximum of 4 squares deep then the inner rooms would be a maximum of 8 squares deep.

I could then alternate the algorithm back to hallway space to create a second, inner hallway. This was why I let the inner perimeter of room space be twice as deep; this area could potentially be accessed from both the first and second hallways. It even appeared to work nicely in the general case.

I hope by this point that you’re triggered by phrases like “in the general case” when thinking about procedural generation. Of course when I tested further, I discovered situations where specific building dimensions lead to very narrow spaces for both inner rooms and inner hallways.

These narrow space problems kept cropping up. What could be done to prevent this?

The nuclear option was to detect problems, abandon that particular attempt at procedural generation, then try all over again from a different starting point. My main worry there was that it’s not very efficient and if you find yourself with a low “yield” of viable maps then you might leave the player waiting a long time. So no, what else could be done?

I started considering limiting the dimensions of the building to “friendly” values that I could predict would not lead to bad results. But could I really do that prediction reliably given all the factors in the algorithm?

As I stared at one of the narrow hallways a thought occurred: What if that narrow hallway was not a problem? Why were these single square narrow spaces bad in the first place? Because the player was going to occupy a single square. What if the player was smaller? That had its own share of problems but what if I stood that idea on its head and took each square on this procedurally generated map and used it to create, say, a 4×4 set of tiles in a separate, final map?

Bingo! The map I was generating would be a first pass for high-level zoning not the final, more detailed map of tiles that would be rendered for players. With this realisation a whole set of problems just vanished; no more complicated reservation of space for future hallways, no more difficult narrow spaces.

Rooms could reasonably be as small as a single square now, say for a closet.

Room space perimeters a single square deep were at least workable now, if a little odd.

As you can see from these last screenshots, I also extended the algorithm to allocate a third perimeter of rooms space inside the second hallway. Of course at this point you’ll notice that the inner and outer hallways don’t connect. I’ll explain how I solved that problem in part 3.