Procedural Level Design Using Graph Grammars
Description
In order to be able to automatically generate levels, we first need to have a good understanding of how procedural generation works. Obviously, there are a lot of different ways one can handle proceduralism. We first have a look at what graph grammars really are, and how they can be used to generate levels. We then expand on this concept and have a look at how we could introduce these grammars into the game development sector.
We will be using a concept called gameplay grammars to generate our levels. Using gameplay grammars, instead of the gameplay being influenced by the rules that define the geometry and content of the level, it is the other way around. This makes it possible for the level designers to quickly adapt their graphs, creating entirely different levels, using the same gameplay mechanics. The first part of this case study will have a look at how we could develop a tool that can create, visualize and edit these graphs, that can be read during the generation process of our level. Once we have this system set up, something else we have to focus on is the visual aspect of the games. Besides gameplay, they also play a huge role in making an immersive and believable experience. To do this, we will use Unity’s prefab system. During the generation of an individual room, we will procedurally place fitting prefabs inside of that room.
This hugely simplifies the generation logic, since we can use 2-dimensional placement here, whilst keeping the third dimension inside of the prefab itself. Once all rooms have completed their generation process, the next step will be to link them to each other, creating a dungeon-like environment.
Once we have accomplished this, we will make it slightly more complicated, testing out a system where the generation of the level design and the visuals of the level are separated. Since the logic is mostly already there to handle the level design generation, we can focus on the visual aspect of the game here. The reason we’re splitting this from the level design itself is to be able to give the artists a lot more freedom concerning the environment, in contrast to the use of prefabs. To procedurally generate these worlds, we will experiment to see if it is possible to use graph grammars, in combination with gameplay grammars, to try and achieve this.
On top of this, we will also have a look at whether or not we can add height alterations to give the environment a bit more 3-dimensional characteristics. We will try and add hallways to our rooms that can be used to achieve these height alterations. Whilst having a look at what levels of complexity this introduces when generating our levels. And how we could work around these possible issues.
Engine: Unity 2020.3.43f1
Case Study
The first thing to mention is that every room is generated based on data. This data will contain things like it’s possible sizes, maximum amount of props, and also it’s modules.
The modules each represent a grammar graph, that defines the ruleset on how the room should be generated.
Because these are modules, we can easily share these among different rooms.
This way, I have 1 module that handles the generation of the walls and doors, that are shared between all rooms.
I also have a module that places torches, which not every room has.
Room Generation
With this system, you must be careful that rooms are not overlapping. To prevent this from happening, there is a hallway system in place that will prolong itself until the room will fit. However, there is a maximum hallway length to prevent enormous hallways. If the hallway is longer than that, it will regenerate the hallway and apply height alterations instead.
Results
Want to know more?
Using the generator I was able to make a small demo-application. The game in this showcase is a 3-dimensional roguelike dungeon crawler. In this example you have to defeat enemies and bosses to get your way to treasure rooms and/or pickup rooms that make you stronger. As a unique gameplay feature there are also challenge-rooms, where you could start a challenge that potentially will make your character stronger. To make use of our generation system, this example also introduces the perma-death mechanic. This way, when you die, you have to start over every time. But as you can see in the figures below, because of the huge amount of variation our generator provides, chances of getting dungeons that are similar to each other is very slim.
If you want to know a little more in detail on how I developed this tool, you can read my paper on Procedural Level Design Using Gameplay & Graph Grammars.
Whilst thinking a bit ahead, I decided to use a gameplay flowchart, instead of actual gameplay grammars to define the level-layout.
The gameplay flowchart will only use 2 node types, an option node and an action node.
The option node is there to be able to create some extra variety, in my demo-application, I’m making decisions based on random booleans, but you could replace this expression to for example represent the difficulty of your level.
Tool Development
Now that our individual rooms are generated, it’s time to link them together. To do this, we will follow the order they are positioned in the gameplay flowchart. And for each room, we will find a door that is not yet linked to another door, and link it to a door that is also not linked yet with the next room.
