procedural level generation using impossible spaces

During the last few days, I decided to focus a bit on level generation. I wanted to try adding new variations for existing generators and clean up generation code/definitions a bit.

Most of the people are familiar with procedural generation, but not the impossible spaces. There are various papers and videos that explain the concept pretty well and it is worth checking them out (https://www.ims.tuwien.ac.at/projects/flexible-spaceshttps://youtu.be/aaSycGxUUXIhttps://youtu.be/kEB11PQ9Eo8​).

World in Tea For God is organised into a hierarchy. A single level is a region. Each region breaks down into more regions. They can be chosen based on anything. Randomly, to create a certain narrative, based on mood. At the moment, as I am prototyping, each part is randomly selected. Then, each region can be composed of rooms or nested regions.

Chosen level pieces. This is an example of a “longer” level (5 sections/regions). The region generator will now connect them.

How rooms are put together? Imagine that each room is a piece of a puzzle. It can connect in a certain manner with other pieces. World/region generator grabs any existing pieces, creates new, if required, and puts them together. A simple example: a maze is composed of 3 to 5 rooms. Each room may have 2 or 3 exits. The maze is provided with two (or more) exits. Rooms connect to each other or to those exits.

Connected level pieces. Note that there are also two hanging connectors. These lead to the start and the end rooms.

During this phase, the logical layout of the level is created. At this point, we know how many set pieces do we have, how they are connected. What rooms are between and so on. We don’t know yet how rooms are placed, what are their exact sizes. We just know what they’re supposed to be and how do they connect with other rooms. This is possible because we utilise impossible spaces and most of the rooms overlap each other anyway.

This is a maze region that contains 7 rooms. The outer circle is the region. Two connectors below it are connectors from the level layout that lead to other regions. What we have inside is more interesting. Brown connectors are children connectors of the region. Region defines how many maze rooms are inside and there is no other way to add more rooms/pieces – this is visible through brown-yellow connectors. Small blue circles are individual rooms. Some have two exits, some have three. Note that this not describes how they are placed in the world. Just what is connected to what. Think with impossible spaces.

Next phase brings the actual creation of rooms. This is done by room generators but before I explain what they are, I’d like to tell a bit about what happens when rooms are created in general. The most important thing done here is how a room is placed within the play area. In particular, where doors/portals to other rooms are placed. There is only one rule to follow, there should be enough space on the other side of the door, to put another room. It can be as small as a single tile.

Oh! Tiles! The play area is built around the idea of a tile. It is divided into a grid. Rooms can be aligned to tiles but that is not a must. What’s more important is that a single room cannot be smaller than a single tile. And that’s what has to be left on the other side of the door.

There is only one rule to follow to make level generation possible. But, there are more rules that allow for better layouts. Some rooms may be forced to be placed next to each other, so the doors match, etc.

Now you may want to know, what happens when doors do not match. When we have two rooms that should connect to each other but we didn’t place them next to each other (for any reason). We build a corridor. Or two. Or more. And sometimes when there is not enough place to put a corridor (or based on a chance) we can put an elevator. Corridors and elevators are created in a similar manner to any other room. Using a room generator.

On the left, there are two doors that should be connected. The big rectangle is the play area. On the right, we see that the code has chosen to create the green door next to the red door. This will lead to adding there a short corridor. Eventually, we will have to connect the blue and green doors. Most likely we will have another corridor that will be on a blue door’s plane. Then we will have one short straight corridor and one 180′. Two actual rooms will be connected through three corridor rooms. Each can be a plain corridor or a shaft or a bench on a side of a building or anything else.

Room generator is a piece of code that creates everything in the room. Meshes, points of interest, nodes, AI managers and so on. And while the world/region generation is quite a general piece of code (it is so general that I also used it to generate rooms themselves but also sentences that characters in other game that I was working on, used to say), room generation is heavily specialised.

There is a room generator that creates moving platform maze. There is a room generator that creates balconies. There is a room generator that creates towers. And of course, there are room generators for corridors and elevators. These generators are specialised as they know, what they want to create. But when it comes to details (how walls look like, how corridors bend) this is decided based on parameters that are set for a particular room. Or a region that room is in. Or region that region is in and so on.

Moving platform maze. This is from the demo, it uses max 2×2 layout with an inverted parabola shape. This is probably my favourite generator. The fun starts with larger levels that also go vertical. This is also, where enemies can actually flank and surprise you. But only if it is a challenge level of difficulty – although I plan to allow tweaking the difficulty level in any detail.

If room/region definitions do not have their own preferences, this allows deciding how things look like at a much higher level. At the moment, I use different setups for each region, but in the final game, I plan to have levels more consistent when it comes to look and feel. There still will be different set pieces, but they will look more similar to each other. They shouldn’t look like a mix of random things put together.

Such an approach doesn’t end with level layout alone. By setting certain parameters at the main region level, we may decide what NPCs will be spawned there.

This is a tower region. Uses balconies generator. Simply, balconies are put on a side of a tower.

And now I shall explain room generator variations. Let’s talk about balconies room generator. It is a generator that creates a certain number of balconies. How balconies are connected is defined by region. There can be a simple corridor. Or a small maze. Or some other set piece. The parameters I mentioned before, may tell how each balcony look like. How walls look like, etc. But – the room generator itself does not define how balconies are placed in relation to each other. Is it a single long wall? Or maybe inside a huge well? Or on a tower. For balconies room generator this is handled with a specialised mesh generator. It knows how many balconies have to be there. It may add a few before or after. It tells how we where they should be placed in 3d space – the important thing here is that while some rooms are placed within the play area (corridors, simple small rooms), other rooms are actually divided into smaller bits and each bit is placed within the play area (each balcony, each tower). And that specialised mesh generator also manages other meshes and things in the room. Beforementioned well. Or a tower. City vista etc. These I call room generator variations.

A well region. Another example of using balconies generator. Although here, balconies are put inside of a well. In both examples, there are no details on the walls, they are plain. But this will be changed eventually.

And this is one of the things that I was working on recently. I also simplified the corridor/elevator definition. Before I had corridors and elevators defined separately for each kind of region/room. Now I have one general set of various corridors and elevators and I just tell which are fine to be used by given room/region.

The general idea, as you can see, is quite simple. What I did not mention is lots of details. For example door shapes and frames that should match. There is a specialised part of the code that allows handling that. It chooses which door shape should be used when we have two rooms using different door shapes. It also manages whether we have door frames or not – we want door frames between rooms or between a room and a corridor, but when it comes to joining corridors – if they have the same cross-section, we don’t want to put a door frame in the middle of a corridor.

This is a room list from the same level as above (longer level). It did not fit to a single screen, although less than a half are actual rooms (from “tower” to “towers”). The corridors, even if broken into three separate rooms, appear many times as just one long, bent corridor.

And there’s more such small things and corner cases.

There’s lots of fun working with it. With sometimes crazy problems that bug you for days until you find a solution. Or a workaround. There is always a solution. You just need to have your mind open. And busy.