Hello, I’m Isaac, the programmer at inbetweengames, and in this post I’m going to outline the algorithm we’ve developed for creating levels in our game All Walls Must Fall.
All Walls Must Fall takes place primarily in the nightclubs of Berlin. One campaign takes place over a single night in the city, and will see you visit multiple clubs to carry out your missions. Each venue is procedurally generated to be unique for each playthrough. We call the system that creates these levels the DiscoGenerator (Disco here being short for Discotheque, the venue, rather than Disco, the musical genre…).
Above you can see how a few layouts currently look in-engine. Of course, it’s still early days for our project, and this is a somewhat rough version of the algorithm. It’s very much subject to change as we continue development, but I’ve had some requests for detail regarding how it works, so here we go!
Design Goals
Guiding the design of the generator is, of course, the design of the game in general. We have to take into account both the spaces we want to create themselves, but also how we want our toolchain to work for authoring content. As a small team, we want to be able to reuse assets as much as possible while still creating spaces that feel different each time you play. As such, we have a number of high-level requirements:
- Clubs must be relatable spaces that are recognisable as real places – for example, they must have a front entrance, which connects to a lobby, which connects to the rest of the club.
- Clubs are composed of rooms. These rooms are custom-authored by a level designer, as individual levels in the engine. The generator doesn’t deal with actually loading the levels, only about creating the map of how these should slot together, with doors and walls in between.
- Rooms can be either public or private. Public rooms must all connect together, and must be reachable from the public entrance.
- Clubs exist in a square or rectangular space, and must fully fill that space with rooms. The space is split up into a grid of ‘cells’, within which rooms must fit.
Unreal Engine Integration
Before getting into the details of the DiscoGenerator’s algorithm itself, I’d like to describe how it fits into the engine we’re using, UE4. The generator is an independent plugin, with no dependency on our gameplay code. It consists of a runtime component, which is used by the game to generate level layouts, and an editor component, which allows us to visualise the levels generated in the editor itself. The gifs in this post are taken from this editor component, which you can see in all its glory here:
Algorithm Overview
The general approach that I’ve taken is to treat the generator as a packing problem, whereby a finite space must be fully filled with as much stuff as possible, such as filling a truck full of furniture. In our case, the space is the area that the club should take up, and the stuff is the rooms that go inside.
https://www.youtube.com/watch?v=MXHKKY-Powg
However, it’s not an optimization problem: the task isn’t to find the most efficient way to put our stuff in the space. Instead, we have a few constraints that we want to be fulfilled, such as ensuring that certain types of rooms are present in the club, and that they can be reached from the entrance. Otherwise, we want to use randomization where appropriate to generate as many valid clubs as possible.
The underlying approach is a greedy algorithm. This is an algorithm that chooses whatever appears to be the ‘best’ decision at each stage, without regard for consequences later on – hence greedy. We start with an empty club of a defined size, and each iteration of the algorithm involves making a decision about what to add to the club – a room here, or a door there. A valid solution is determined by ensuring a club has the required number of rooms, and that they have their own adjacency requirements met – it’s not about ensuring the space is being filled efficiently. In our case, clubs have a finite space, so we prioritise larger rooms over smaller ones, and rooms with more requirements over those with fewer, so that we fulfill the requirements as early as possible.
Traditionally, a greedy algorithm implements a scoring function, which assigns value to solutions and is used to decide which choice is the ‘greediest’ in each iteration. In our case, we don’t explicitly implement such a function, but instead implicitly define it by simply sorting rooms before adding them, to prioritise those that have more requirements (to minimise the number of unfulfilled requirements) and are larger (to minimise empty remaining space).
0. Selecting Rooms
Before the algorithm starts placing things in the club, it must first choose what rooms the club should contain. Each club definition (created by a level designer) has a set of required rooms, as well as a number of optional rooms. Each room has a type, such as bathroom, dancefloor, or bar, and a set of possible sizes. The generator randomly selects which rooms the club wants to contain, and the desired size for each of the rooms.
1. Placing Entrance Rooms
The first rooms that are placed in the club are Entrance Rooms – that is, they contain a door to the space outside the club. These are pretty important – without them, there’s no way to get inside. Right now, we have two types of entrances: public and private (such as a back- or side-entrance).
We start with the biggest, and gather all the valid locations we could place the room. In this case, those are around the perimeter of the club. We then simply pick one of these at random.
Whenever a room is placed, there is generally at least one requirement that must be fulfilled regarding what the room is adjacent to. As well as placing the room in the correct spot, a door must be placed between the two areas. In this case, the requirement is that it must be adjacent to the external area, so a door is placed there.
Rooms can have the requirement that they are adjacent to a specific other room. In our case, the Lobby must always be adjacent to the Front Entrance. In keeping with the Greedy approach, we want to maximise the fulfilled requirements at each iteration, so as soon as a room is placed upon which another room depends, the dependant room (in this case the Lobby) is inserted. This means that the order of placement is first Front Entrance, then Lobby, then Side Entrance.
2. Placing Chosen Rooms
Once we have valid entrances, we can get on with the meat of the generator, which involves placing all the other rooms that we chose in the first step. Before placing the rooms, they are sorted as follows:
- Public rooms are to be placed first, then private rooms
- The largest rooms are placed before smaller ones
As public rooms have the requirement that they are adjacent to other public rooms, and large rooms have the implicit requirement that they need more space, this greedy approach minimises the chance of an invalid club being generated: if there’s only one spot where a large room will fit, we don’t want to place smaller rooms there first. Similarly, we don’t want to place private rooms in places that will prevent public rooms from being connected together.
3. Placing Filler Rooms
At this point the club requirements should be met. All the rooms that were chosen have been placed, and we should have a working club level. It is possible that some required rooms couldn’t be placed, in which case the club is not valid. In this case we simply increment the seed (the number used to initialize the Random Number Generator), and try again.
If all the required rooms were placed, however, there are still empty spaces in the club. To fill up this space, we have a special “filler” room type, which has no requirements and can be placed anywhere. The generator simply places these whereever they will fit, until they can fit no more.
4. Placing Corridor Rooms
Finally, there may be some spaces remaining that are too small for real rooms. We take the same approach as with the Filler rooms here, but instead with special ‘corridor’ rooms that are only a single cell wide.
5. Placing Doors
Now all the rooms have been placed, along with doors that were needed to fulfill room requirements. However, extra doors may be placed to give the club alternate pathways. Each room type has a minimum and maximum number of doors which it can support. We simply add doors to rooms until we fulfill at least the minimum number of doors, and randomly add extra doors to those rooms which support more.
6. Placing Outside Rooms
Outside “rooms” are not really rooms, but are ways of adding some context to the entrance by placing some objects outside the club in sensible locations, such as a queue of people waiting to get in, or a couple of bouncers. As far as the DiscoGenerator is concerned, they are simply rooms that must be placed outside and adjacent to an entrance. These are placed last.
7. Choosing Levels
The club is now complete. We now connect the generated layout to levels that have been authored in the Unreal Engine. Each room placed so far has a type and a size, and there may be multiple room levels that support this layout. For each room, we simply choose one level at random from the pool of supporting levels.
Disco!
The job of the DiscoGenerator is now complete: we have a finished club layout. Now it’s the job of another system to actually spawn the club and make it playable. How we do that is a topic for another time, but for now here’s a video of this loading happening. Note some of the rooms are empty – those are the (private) backrooms which we haven’t yet authored.
So that’s the basic algorithm we have so far! Of course, it’s very much subject to change as we get further into development. For now though, it has really helped us as it allows us to playtest the game with an unexpected experience every time, even as developers. going from a hand-made level to one where we didn’t know exactly where the objectives are was a great moment!
Let me know if you have any questions (or suggestions) on Twitter or in the comments. Also follow the inbetweengames team for more updates on the game, on Twitter, Facebook, and sign up to our newsletter! Being able to work without any NDAs is awesome and we’ll be posting more updates about our progress soon!
Cheers,
Isaac
inbetweengames
