Procedural Level GenerationAhren Stevens-Taylor
In this article by Dale Green, the author of the book Procedural Content Generation for C++ Game Development, the most iconic and defining feature of rogue-like games is their procedurally generated levels. This is one of the main features that contributes to the replayability the genre is renowned for having. It keeps the game fresh and challenging and keeps the player on their toes.
Throughout the course of the article, we’ve gone from the the simple generation of single numbers to implementing complex procedural behavior, such as pathfinding. It’s time for our pièce de résistance: generating our mazes procedurally.
In addition to this, we’ll work on making our levels more distinct, using the functions we created on procedural game art earlier in our chapter.
In this chapter, we’ll cover the following topics:
- Randomly generating dungeons
- Choosing the correct tiles
(For more resources related to this topic, see here.)
Benefits of procedural level design
The procedural generation of levels and game environments bring with it a myriad of benefits not only for the player, but for the developers as well. It’s always good to understand the positives and negatives of a technology before we use it, so let’s look at some of the biggest benefits it brings to our games.
The most obvious benefit of procedurally generated levels is their variety and the replayability that they bring to a game. With each run, the environment changes, which means the player cannot learn the locations of items, enemies, and so on, keeping the challenge alive and fresh.
Reduced development time
Another benefit, common with all implementations of procedural generation, is the time that it saves in development. In our rogue-like game, we’re going to have an endless number of unique levels. If we were creating our levels manually, this would simply not be possible; we would be limited to perhaps a hundred at most.
Utilizing procedural generation, however, takes this workload off the developers, saving both time and money.
Allows larger game worlds
Remember, procedural generation in itself is in no way random. We induce randomness using random values in our algorithms and calculations. This given, we can use procedural generation within level designs to share levels without actually having to store them.
Lots of games that generate worlds randomly will allow you to input, or store, the world seed. With this value, two people can be sure to generate the same level. With this approach, you could generate a theoretically never-ending level, ensuring that all players generated the same one, and you’d only have to store the world seed.
As with everything, there are always two sides to a coin, so for each benefit a procedural-level generation brings, there are also some considerations and compromises to be made.
Lack of control
A common pitfall of procedural generation in general, but perhaps never more prevalent than when generating levels. Game levels are the arena in which stories are told and mechanics are experimented with. They are usually handcrafted by dedicated level designers, so to leave this job to an algorithm requires a significant yield in control.
Games with simple mechanics and stories will generally fair okay, but if you have complex mechanics, or a story you want to tell in a particular way, procedural-level generation may require you to relinquish more control than you can afford. An algorithm can never replicate the slight touch that a seasoned professional can.
Another consideration to be taken into account is the computing power required. In our case, it’s not too bad; we only have a 2D array of a small size to generate. If, however, you’re generating 3D terrain, this cost becomes more significant and needs to be factored.
Imagine if we were working with a level grid of 1000 by 1000. Each time we would need a level, there would be a significant number of calculations that would need to happen, and we need to ensure that all our player’s hardware can cope! With the increase in computing power, this is becoming less of an issue, and is why games are becoming more complex and dynamic in fact; we have the hardware to do it!
The final consideration is simply whether your game will benefit from procedural generation. Just because it might be technically possible to implement in a title doesn’t mean it belongs there. If you don’t require lots of levels and have complex mechanics and systems, then it’s probably not worth implementing. You’d be better off spending the time in handcrafting a selection of levels that you know work really well.
An overview of dungeon generation
Dungeon generation is a vast topic with an equally vast range of individual implementations. Different algorithms bring with them different characteristics. All odd and even matching algorithms can be implemented differently, producing varying results. Underneath the varying algorithms, however, dungeon generation generally involves the generation of rooms, a maze, and joining the two together. The following screenshot shows the result of joining rooms a and maze together:
Generating dungeons procedurally is not all that different from the work we did on pathfinding. It’s all about viewing our level as nodes and manipulating them. Before we implement it for ourselves, we’ll break it down into the three main stages identified earlier: generating rooms, generating a maze, and joining it all together.
Dungeons are a series of interconnected rooms, so the first step in many systems is to generate these rooms. There is no complex algorithm behind this; we simply choose a room size and place a number of algorithm in the level. The characteristic of the level will be determined by factors such as the number rooms, and their size will determine the character of your dungeons. The following is a screenshot of rooms:
Generating a maze
Another important step in dungeon generation is to generate a maze throughout the playable area. This turns the level into a series of connected hallways that either join existing rooms or can have rooms carved into them to create open areas. There are a number of algorithms that are used to generated mazes like these, and we’ll be using the popular recursive backtracker algorithm. Don’t worry; we’ll look at this in more detail shortly! The following is a screenshot of the maze:
Connecting rooms and mazes
If you choose to generate rooms first and then select a maze to connect them, the final step is to join it all together. Currently, the maze will run right past all of our rooms, but thankfully it’s an easy task to join them up. We just look around each room and add a connecting block to the adjacent path. The following screenshot the the result of connecting rooms with a maze:
In our implementation, we’re actually going to this the other way around. We’ll generate a maze, and then we’ll cut open areas into it. I found this method created more open and maze-like areas, whereas the first one created interconnected, closed rooms.
In this article, we’ve taken our game from loading a predefined level of data from a text file to generating its own game at runtime. This brings a great level of replayability to the game and will help make the gameplay fresh and challenging for longer. We also used a function we defined earlier in this article to bring more character to our levels.
Resources for Article:
- Integration with Spark SQL [article]
- Introducing the Boost C++ Libraries [article]
- Introduction to GameMaker: Studio [article]