Simple Procedural Building Generation

Outlining a technique to rapidly generate top-down buildings, with a focus on their use as gameplay elements.
It’s important to start with a clear idea of just what problem you are trying to solve, so let’s begin with the goals of building generation in Maggot Blaster.

  • Relatively fast - The buildings do not need to be generated whilst the player is actively playing, but they do need to be generated during a loading pause before each level.  Typically the player will move between levels every two minutes, so the loading pause should be no more than a couple of seconds on a reasonably recent machine.
  • Provide interest for combat – The purpose of these buildings is to act as obstacles to move in and around during fast-paced combat, so they should be interesting for that purpose.  Large hangar-like buildings are no more interesting to fight in than an empty field.  Plenty of passageways and rooms for the player and enemies to wind their way through will give a distinct feel to indoor combat.
  • Aesthetically appealing – Possibility for variation between buildings is important.  If all the buildings end up looking like different sizes of the same concrete box, then this use of procedural generation will fail at its goal of keeping the game feeling fresh.
  • Don’t be completely impractical – Although there’s no need for these buildings to be in any way functional as real dwellings or workshops, they should avoid obvious errors such as having large sections that are completely inaccessible.

The technique I used (so far as I know it’s original, but I’m not so naive to think that someone hasn’t come up with it before in a slightly different context) relies on a grid representation of the building.  The grid begins as filled with the background grass of the map.

grid1

As a first stage, we block out an outline for the building.  The nice thing about the technique we will use for generating the walls is that it will produce reasonable results on virtually any building outline.  Maggot Blaster keeps it simple, and first draws a rectangle, then subtracts from that another smaller rectangle.  This can produce “L”, “U”, and “O” shaped buildings of various forms.

grid2

Now we draw on outer walls wherever the building outline meets the grass.  At this stage gaps on the outer walls are also inserted on random edges to act as doors.  A prime area for improving this technique would be in placing these doorways more intelligently.  Maggot Blaster errs on the side of free movement, and tends to add more doorways than would be expected for a real building, but it helps keep combat flowing.

grid3

Next is the clever bit – adding the interior walls.

A random point within the outline of the building is selected where the grid lines intersect.  This will be the starting point for our “trip”.

grid4

The grid lines are then followed for one step in a random direction, and a wall is placed along the grid line that was followed.

grid5

If that led us to an existing wall, then we stop.  In this case it didn’t, so we repeat and follow another grid line from our new position.  We keep repeating this process until we do reach a wall.

The one condition is that at each step we do not move to a point that has already been visited on this wall-laying trip.  This condition requires us to keep a list of points that have been visited so far on the trip.  A special case to handle at this point is when there are no valid moves possible – this turns out to be a rare occurrence, but needs to be dealt with.  Maggot Blaster chooses to simply end the wall-laying trip if it finds there are no valid moves to make.

The next steps could look like this:

grid6

grid7

grid8

grid9

We have reached a wall and so stop.

We can now pick another interior point that does not yet have a wall lying on it, and perform another trip following the same rules to add more interior walls.  The more trips we perform, the less open areas will exist in the resulting building.

grid10

Here two further trips have been completed.  Note that one of these new trips ended when it met a wall placed by the first trip, creating a “T” junction in the interior walls.

By following this procedure it is guaranteed that so long as the building has at least one doorway – no matter where it is – all areas of the building will be accessible.  It also tends to produce reasonable looking layouts of walls; never including pointless short walls sitting in the middle of a large room.

As an extra garnish Maggot Blaster looks through the finished building and identifies grid squares that have walls on three of their sides, and marks them as potential areas for supply crates to spawn.  That way supplies always spawn in dead-ends so picking them up forces the player into a dangerous position, which helps keep things tense.

One thought on “Simple Procedural Building Generation

  1. Very interesting, could be useful in a game I’m working on at the moment. I want to add procedural building generation to keep it interesting. This will certainly help when I get to that stage in development, thanks.

Leave a Reply

Your email address will not be published.

* Copy this password:

* Type or paste password here:

16,851 Spam Comments Blocked so far by Spam Free Wordpress