Procedurally Generated Buildings

As I’ve been working on making a decent looking map generator for After the Collapse over last month, this article will serve a multi-purpose goal of being a devlog, a coding tutorial for other programmers, and a modding tutorial for you guys. We’ll be talking about making good looking buildings using procedural generation and putting everything needed in a small, human-friendly text file. I’ll try to keep it simple and understandable for anyone, even without coding experience.

Introduction

Let’s go over the why, how, and the common solution to this problem first. The very reason for this article is because After the Collapse’s default environment is urban, and to the surprise of absolutely no one, generating a decent looking urban environment is way more complicated than a simple terrain using a height-map. But let’s not get carried away, before we can generate a whole city, we need a way to design individual buildings. This is what we’re going to talk about here.

If you ask google, the most common answer to that question is quite vague, it doesn’t cover the rooms’ content, and its general logic is to design a rectangle, cut it in two parts, and recursively cut each part down in 2 until you reach either the amount of room you want or a specified minimal room size. That was the system I used in my old Grand Rogue Auto freeware for the “dungeons”. It has clear advantages. It’s very easy to code, you have a perfect control over the building’s size and room count. However, managing rooms’ size is difficult, and making any non rectangular building quickly becomes a pain to write. I won’t go over the code, it’s very simple. Get your rectangle, cut it in 2 at a random position around the middle, put the 2 resulting rectangles in a list, call the same function on each sub rectangle until you reach a specified room count or size. Below is a nice animated GIF showing the steps in drawing such a building:

While it is fine and dandy to have some buildings like that in my game, it would still make for a very boring looking map to only use those. I want uneven buildings. I want houses that may have one to three bedrooms while using the same data file. And most importantly, I want to be able to set the size of each room individually. So I came up with another system entirely. But to explain that system, we’ll have to start from the very bottom.

Summary of the Problem

As with any programming problem, what we need to do is to divide it in much smaller and manageable tasks. But before we start, I am not going to post actual code. Do not bother asking for it either. I am fine detailing each step individually, but you will have to fill out the blanks yourself and code your own system based on it.

First, what’s a building? Well, any building is a collection of rooms. For instance a house would be a collection containing a kitchen, a living area, at least one bedroom (maybe two) and by the rules of video game logic, no toilets. Simple enough. We can expand on that, but it’s good enough for now. What’s a room, tho? Well it’s a collection of furniture, but said furniture can’t be just randomly placed, we need some basic rules to place them in a sane way, fine we’ll get to it next.

So a building is a collection of rooms and each individual room has a set of furniture we want to place in a fairly logical manner (for instance, we expect chairs around a dining table, or a nightstand next to a bed). Simple enough apparently. Let’s start at the bottom and use a bed, that will end up in a bedroom that will end up in a house here.

Generation

Furniture

Those are your very basic game objects: tables, containers, chairs, and so on. Their individual data are game dependent, and we’re not going to address that. What is relevant to us here is how they relate to each other. In instance, a bed will in general have a nightstand next to it, but not always.  So let’s put that information in our bed’s data file.

"Name": "Bed"
"Data": [insert your game relevant data here]
"SubFurniture": [
{
  "DataFile": "NightStand",
  "MinCount": 0,
  "MaxCount": 1,
  "Placement": "Beside"
}]

So, for each furniture we keep in mind what other furniture relate to it, and how they need to be placed. A dining table might have 2 to 4 chairs around it, and a chance to spawn plates on top of it. A TV might have a sofa on the opposite wall, the sofa might, in turn, spawn a small table in front or next to it. The key is to have a SpawnFurniture() function with a large variety of placement options and the ability to call itself when it encounters more items to spawn.

Now that we have basic grammatical rules to place our items in relation to each other, we still need to place them in the room itself. Technically that’s information we could supply at the furniture level, but given the same object could be placed differently in 2 different rooms, it’s generally best to supply it at the room level to avoid duplicates.

Rooms

The definition file of a room is pretty simple. It contains the minimum and maximum size and a list of objects you want to place (and where). If you think about how most rooms are designed, there’s only so many places to place furniture: alongside walls, in a corner, in the middle, or neither. Well, that’s about all we need here.

"Name": "Bedroom",
"MinSize": 5,
"MaxSize": 7,
"Items": [
{
  "Item": "Bed",
  "MinCount": 1,
  "MaxCount": 2,
  "Placement": "NextWall"
},
{
  "Item": "Carpet",
  "MinCount": 0,
  "MaxCount": 1,
  "Placement": "Center"
},
{
  "Item": "Lamp",
  "MinCount": 1,
  "MaxCount": 1,
  "Placement": "RoomCorner"
}]

Things get a bit more complex with multi-tile objects and taking rotations into account, but that’s the gist of it. Note that in our example here, the bed will spawn its own nightstand, that’s why we don’t have said nightstand in the list. This is the reason why we can keep this file very simple as everything that must be placed related to another object is taken care of already. The idea is to guide the generator with clear locations for each item, while leaving it some leeway so 2 rooms using the same data won’t looks like a copy/pasted version of each other.

Building

And this is where things get interesting: placing rooms in a coherent manner. First, we place the first room/rectangle in the top-left position of the area in which you want a house in. Then the idea will be to maintain two lists: one where we store each room/rectangle placed, and one in which, for each room/rectangle, we store its top-right and bottom-left positions. Then, we pick a point at random from that second list and try to build a rectangle from there. If the new rectangle intersects with one stored in the first list, we pick another point. If not, we remove the point from the list, add our new rectangle and new spawn positions to our lists, and loop until we get to the room count we want. We end up with a building process looking more or less like this:

Of course this animated GIF shows the optimal version of what is supposed to happen. With no additional code you’d often get much uglier buildings for three reasons, all of which are pretty easy to fix:

First, we could be plain unlucky and get a building with 4 or 5 rooms all spawned in a single (horizontal or vertical) line. It might be something you’d occasionally want, but it’s certainly not the default behavior I want here. The answer to this problem is pretty straightforward. For each point we store in our spawn-point list, we also store if it’s a bottom or right-sided one. Then, we just have to make sure that when selecting the next point, if our previous one was “right-sided” then we pick a “bottom” point (and vice versa). It will make sure you never end up with this kind of building.

Secondly, as you can see in this picture, the first time we tried to place the 3rd rectangle, we did not have enough room. What is not shown in the picture is that normally we’ll retry multiple times with different sizes (within the constraints specified by that particular room) to make it fit until we start trying at another location. But there’s another case, pretty common, but not aesthetically pleasing. When Room 3 and 2 are just a tile away from each other. If not corrected it can create “holes” in the building. That’s why, after each new rectangle spawned, I check if there’s another rectangle 1 square away below or to it’s right. If there is one, I increase its size accordingly (no matter if it go over the limit specified in the room’s data file). Here’s a visual example:

Of course, depending on the game, you might want to check for rectangles that are 2 tiles apart, but that’s still the same idea.

And third but not last, by always starting in the top left corner to spawn our rooms, we’d end up with only a few of all the possible shapes. For instance, we’d have T shaped ones but never an upside down T. Well, it’s easy to fix with the magic of math.  I added a few functions to flip and rotate our buildings by 90° increments. Those functions are called a few (random) times after we’re done placing our rooms.

In-Engine Results

And with everything combined, we end up with a fairly large selection of interesting shapes. I still occasionally generate less than optimal buildings, but it’s still infinitely more interesting to look at than purely rectangular ones. With a mix of both, I should be able to generate decent looking urban maps.

Details, Improvements, Follow-up

Of course, I left aside a lot of small details which would have distracted from the main point. Placing windows and doors, making sure that furniture won’t block a door, and so on and so forth. But those are pretty easy to figure out. Our data files will also contains fields to populate the outside area with items, trees, and stuff. And more importantly, given it’s a post-apocalyptic game, now that we built a house, we need to destroy it!

Simply put, once the map has been generated, we’ll apply “bomb” impacts in semi random locations to damage and/or destroy walls and furniture. We’ll also apply some level of decay to the whole map, mutating most of the new looking beds and furniture into old broken ones and/or trash piles. Not so surprisingly, the destruction part should be much easier than the construction one 🙂

Other Stuff

I’m also in the process of putting all the basic parts together to make an actual game. It mostly means that I am writing the intro menu, the “start a game” alongside working on the procedural generation. When done, I will add some random enemies, fix some animations, add a bunch of factories and items, and we should have something that’s at least playable as a game. Then, and that’s the tricky part, I’ll have to make that complex and fun to play.

 

One thought on “Procedurally Generated Buildings”

Comments are closed.