Procedural Level Generation

The Algorithm

For this project, I want to create a tech demo which creates randomly generated levels. I want these levels to represent indoor, manmade environments, so I'll leave terrain generation for another time. The levels should meet the following criteria:

They should look as though a human designed it
They should not be entirely linear
They should be beatable 100% of the time

All of the images in this post come from layouts returned from my tech demo. Here are some results from the finished product:

The Drunkard's Walk

There are countless ways to randomly generate game levels. Most algorithms involve first placing the rooms around the space, then connecting them with hallways. This works, but sometimes it can result in unbeatable levels. I want to make sure all rooms are connected together in an intuitive way, so another approach would be ideal. Additionally, this can cause generated levels to look pretty similar, and more variation is better. This leads us to the Drunkard's Walk algorithm, which goes as follows:

Place an agent somewhere in the empty level
For some number of steps:
- Place a floor at the current location
- Pick a new random direction
- Move forward

This yields levels which guarantee a path from the start to the end of the level. Additionally, it will make sure levels look unique due to the amount of randomness involved.

Data Structures

To represent this data, I will use a multidimensional array of integers. Each integer corresponds with a room type. I used 0 to represent nothing or walls, 1 for floors, 2 for combat challenge rooms, 3 for loot rooms, 4 for loot chests, 5 for traps, etc. These values can go on to describe the type of room or even fine details within the room. The array will end up looking something like this:

Step 1: Placing Floors

Here we will implement the basic Drunkard's Walk algorithm:

For some number of tiles:
- Place a floor tile
- Pick a random direction
- Move forward

If this suits your game, you could stop here. However these levels look very random and chaotic, so the next step is to contain the randomness a bit.

Results (100 tiles)

Step 2: Containing Randomness

Here instead of turning every step, we now turn a certain percentage of the time. This looks like a nice hallway, but it still doesn't look much like a level. The next step is to add rooms for the player to explore.

100 tiles, 15% turn chance

Step 3: Placing Rooms

Next up is placing rooms. To place a room, we can carve out a square section of the array centered at the current position. The loop will go as follows:

For some number of rooms:
- Place a room
- Place a corridor

Now we're getting somewhere. The main issue is that rooms can overlap, so the next step will fix this. It's worth noting that this is not a necessary fix, and if you like the way this looks, you can keep it.

4-5 rooms, 15% turn chance

Step 4: Non-Overlapping Rooms

This modification entails not placing a room until there is enough space for it. While the space is occupied, keep placing hallways until there is enough space. After this is done, we now want to make sure the levels are not entirely linear.

10 rooms, 5% turn chance

Step 5: Branching Rooms

The idea here is to drop branch points randomly every time we place a room. After the main path is generated, we will go through and do the same for each branch point. Here is the updated loop:

For some number of rooms:
- Place a room:
- If we pass a random check:
  - Add this location to a list of branch points
- Place a corridor
For each branch point:
- Do the above again

Now we have a completed level layout! For a 2D game, these tiles can be placed directly into the game world. For a 3D game, we can then build a mesh based on the level layout array.

8 rooms, 6% turn chance, 80% branch chance

Demo Video

Note: all code is available on my GitHub here

Which games should use procedural generation?

Truthfully, any game could benefit from procedural generation. Adding randomly generated content to a game theoretically adds infinite replayability since there are so many possible levels to explore. Some games have been more successful than others at this. While procedural generation can add variety to a game, one of the major drawbacks is that it can cause each level to look and feel the same. Players can often tell when a level is designed by a computer as opposed to a human, and these levels can tend to feel lifeless and repetitive. One example of a game which fell into this trap is No Man's Sky released by Hello Games in 2016. In this game, players fly around a massive galaxy filled with countless procedurally generated planets. Each planet even includes randomly generated plants and creatures that roam the surface. The problem was that on release, there was nothing to do on these planets, so there was no incentive to explore them. The lesson to learn here is that randomness does not define the game. Procedural generation will make your game more interesting, not act as one of the main game mechanics. With that said, procedural generation has led to many successful games.

A level generated in Rogue, which went on to define a whole genre of games.

Minecraft generates an entire world, and is now one of the most successful games of all time.

One of the first games which procedurally generated levels was Rogue, developed in 1980 for Unix-based systems. This game was so successful that it went on to spawn an entire genre of video games, now known as Roguelikes. I'm a huge fan of roguelikes due to their replayability and variety, and these games inspired me to make this project. Needless to say, if you are developing a roguelike game, some form of random level generation is almost mandatory. Additionally, any form of sandbox game would greatly benefit from procedural generation. Minecraft is an extremely popular game which heavily leverages random generation to create an entire world. This game generates landscapes, caves, dungeons, and other features to constantly keep the player engaged and always allow more content to explore. Finally, if there are limitations imposed on your team, random level generation can be a clever way to save time. Sebastien Benard is the lead designer of Dead Cells, a roguelike game which randomly generates levels. In the early stages of development, Benard says that the team tried to hand-design levels, but the small team did not have enough members to create enough content in their ideal time frame. As a result, Benard hooked up a system that takes a human-planned "skeleton" of how the level should look including keys, locked doors, etc, then lets the random algorithm loose to fill in the gaps. Using random level generation can be a great way to focus less on individual levels and more on core gameplay mechanics.

Which platforms can implement this technique?

Any modern platform can handle procedural level generation. Since games like Rogue have been doing it since 1980, quite frankly us modern developers should have no problem implementing this on modern machines. A game for PC or a modern console should be able to handle random generation, provided the algorithms used are decently optimized. The problem doesn't come from deciding the level layout, but rather in converting this layout to a graphically pleasing level. Converting a multidimensional array of tiles into a game world usually involves some form of mesh manipulation, and may not be suitable for mobile platforms. However, this is not always true, and light procedural generation frequently makes its way into mobile titles. As long as the algorithms are optimized to some degree, level generation can be used in nearly any platform.

Random maze generation from Maze Craze (1980) on Atari 2600.

References

http://www.jthomasbacher.com/bacherJuniorISWriting.pdf Thomas Bacher wrote a short piece detailing an overview of several procedural level generation methods. Going back to the first procedurally generated levels in Rogue, Bacher explores several different approaches with varying complexity and results. This is a good starting point for a general overview of pros and cons of each method.https://publications.lib.chalmers.se/records/fulltext/256132/256132.pdf Several individuals from the University of Gothenburg have written this thesis describing many different approaches to randomly generated levels. This thesis includes images, theory, and practical descriptions of each method used in modern video games. Once a particular method is chosen, this source is a great place to read more about fine details of the desired method.Millington, Ian. AI for Games. CRC Press, 2022. Millington’s AI for Games includes source code for generating levels. This is a good place to get an idea of data structures needed to implement these levels into a game engine. Despite the fact that Millington includes full implementations of several random level generation methods, he somehow overcomplicates the code while excluding critical information involving generating the level. As a result, this code can not actually be used for a level implementation, but it can be helpful to read over for more technical details of each approach.https://www.raywenderlich.com/2637-procedural-level-generation-in-games-tutorial-part-1 This guide gives short descriptions of handy helper-methods for implementing random levels. It also gives a realistic look at necessary data structures needed. This is another good place to get a general overview of the technical side of things and start to formulate how one will implement procedurally generated levels in their own project.https://www.gamedeveloper.com/design/building-the-level-design-of-a-procedurally-generated-metroidvania-a-hybrid-approach- Finally, Sebastien Benard is the lead designer for the critically acclaimed roguelike game Dead Cells. Here, Benard explains how he combined hand-placed and deliberately designed level elements with procedural generation to fill in the gaps. One of the major disadvantages of random level generation is that it can be hard to assure a quality level which feels unique from the rest. Using this hybrid approach involving human and AI-generated levels, one can ensure that levels are fun and interesting to the player while still being random and unique each playthrough.