Procedural generation of building interiors (part 1)

The core of Subveillance’s game loop will be running a mission and each mission needs a map. I could design a series of maps or glue map sections together randomly as popularised by Spelunky. However, influenced by Elite Dangerous and Heat Signature, I wanted to start by at least trying to use procedural generation. (Or “procgen” as the cool kids call it and I will now stubbornly avoid like the old grump that I am.)

Procedural generation can be applied to many different problems. For Subveillance, at least initially, the maps I need to generate are the interiors of buildings, i.e. a space broken up into rooms connected by hallways.

I spent some time researching to avoid reinventing the wheel but rapidly discovered that most articles describe how to generate a dungeon. Dungeons don’t attempt to fit into an existing space, instead they’re hewn from rock by hardy dwarves. These rooms don’t pack together, they roam without limit, making for a simpler problem based purely on connectedness.

I did find some articles that discussed partitioning space into rooms but without any hallways. Then in an answer to a question posted on the Game Development Stack Exchange I found a reference to the 2008 master’s thesis Procedural Generation of Indoor Environments by Alexander Dahl and Lars Rinde. The key insight for me in this paper was to calculate the path of a “skeleton” hallway through the centre of the building and then fill in rooms around this.

Armed with a starting point I began to put together a prototype map generator in Godot. As Subveillance is likely to use 2D tile-based maps, I based this on a simple grid system using the built-in tile map functionality.

Knowing that I wanted my buildings (and hence maps) to be more interesting than simple rectangles, I opted to take a random sized bite out of the top left corner of a random sized rectangle.

From here I put a twist on the paper’s algorithm, with the idea of lining the outside of the building with space for rooms and then running hallways around the newly established interior perimeter.

In this screenshot, dark grey is outside the building, light grey is unallocated space inside the building, and coloured squares are space for (as yet undefined) rooms. The specific colours indicate the number of neighbouring squares that are unallocated, and not important right now. There are no hallways at this stage.

This screenshot actually represents four passes of the algorithm. Each pass identifies a single square deep perimeter. By running repeated passes the perimeter space allocated to rooms grows inward towards the centre of the building.

I put a limit of six squares deep, along with a check to ensure at least 3 squares of space was left for hallways; this was based on the assumption that player characters would be a single square in size.

As can been seen in this screenshot, these rules can limit the perimeter room size in small buildings.

This screenshot illustrates some of the pitfalls of procedural generation I was starting to learn. It can easily generate unusable layouts, like single square deep rooms, if you don’t put in adequate protections.

Here’s a building with no space for rooms at all!

However, as this was a prototype I didn’t need everything to work perfectly, I just needed to learn if I could make the concept work and take note of the potential pitfalls.

Next I decided to raise the bar by removing some available space inside the building, like you might get with an atrium.

The same perimeter lining algorithm worked just as well in this case!

Unless the atrium space was too close to the edge of the building.

Or in just the wrong place to create the potential for a too-narrow hallway.

Or no hallway at all, leading to potentially unreachable room space.

Okay, deep breath, noted, we’ll deal with those later. Could I at least lay out a hallway in the general case?

Yes! As this final screenshot shows, the same perimeter detection algorithm could be used to create a secondary perimeter (here shown in purple) to be allocated as hallway space.

That’s probably a good place to leave things for today. The introduction of hallways lead to a whole new raft of difficult edge cases. These in turn lead me to a dramatic simplification but I’ll leave you with that as a teaser for part 2!