Procedural Level Generation in The Dungeoning

Introduction

When I started making The Dungeoning, I had a clear idea of what I wanted the game to be - A 2D platformer with some nods to Demon’s Souls, a procedurally generated world with punishing enemies and permadeath, and interesting weapons and items, with the game lore squirrelled away in the item descriptions. Although I’ve worked on some of our other games doing design and art, this was to be my first time programming a game (and doing everything else too), so to me, this was a very valuable learning experience.  One of the most distinctive parts of the game and the area I want to talk about here is the procedural level generation.  I’d been interested in trying this technique for a while and it was a major motivation to make the game in the first place.

Reasons for using PG

There were several personal reasons why I wanted to attempt to create a procedural level system. In no particular order, here are three reasons why, I think, I wanted to use it for this game:

1. I had spent so long creating the levels for our speed running platform game, Mos Speedrun (We are currently working on Mos Speedrun 2).  It takes longer than you might think to create these types of platform game levels and fatigue eventually sets in.  It’s difficult to come up with new ideas and surprises for each level.  At the time, I didn’t want to embark on months of level design.

2. Its an interesting programming problem.

3. You get to play levels that you haven't designed.  When you are making a game where the levels are hand built, you don’t get to experience it as a new player would, since you know exactly what each level is comprised of, there are no surprises or exploration for the creator.
 

Drawbacks of Procedural Generation

Anyone who has played a game with procedural content knows there are often certain down sides to the technique, and The Dungeoning shares some of these problems. For a start, there is no ‘Designer Intent’ to the levels, meaning there is no reason behind the placement of each room, the map of a level tells no specific story.

The levels can also become a little familiar once the player has played a number of games.  They start to recognise the style of the game, the shapes of the rooms and the general rules used to layout each level. There are a finite number of room templates in this system and the player will start to recognise them.

Of course there are ways to mitigate these problems using more advanced techniques, and maybe I’ll pursue those in The Dungeoning II, but for now, this blog addresses the methods I used, warts’n’all.

Basic PG Principles.

Procedural generation is controlled by random, but managed, numbers. The basic principal is that we start off by coding a system that will generate a sequence of (essentially) random numbers.  The sequence is initialised with a seed number, and if we generate a sequence twice with the same seed number, the resulting sequence will be the same.  This is important for a few reasons but for me, the ability to replay a level with the same seed, and therefor layout, while developing the game was very useful. Of course, generating two sequences with different seed numbers should result in two totally different lists of random numbers.

Now, the “random” numbers we are talking about are not truly random, they are generated algorithmically by the computer, but they are “random enough” for our purposes so lets not worry about that too much. When I talk about selecting something “at random” I mean that we use a number from our list of pseudo random numbers to chose a predefined item.

General plan

My plan for generating the levels was pretty simple. I would create a list of room descriptions some how that contained all the collision data (Basically just the walls and floors etc with no information about how it should look).  Each room would have special tiles along the edges that would represent an exit/entrance to the room.

I would then start off by picking a room at random to act as the root room, and paste the room data on to the centre of the map.  Each of the exits from the edges of the room would be added to a list of available doors.  The list contains door descriptors that specify the size and side of the room that the door appears on.  The available door list is really what drives this initial phase of generation.  Now I iterate through a process as follows:
 

At the end of this process, I have a blank map, filled with a very simple level structure that roughly fills the available map area.  At the moment, the data simply represents whether a level tile exists or not, there is no information about how it should look or enemy placements.
 

I run another process on the newly generated map that iterates through all of the placed rooms, and any rooms that are connected to only one other room are marked as “leaf rooms”, later on these will have a chance of becoming a hidden room, which means it will be obscured from the player until they walk through the doorway.  These hidden rooms have a higher chance of containing chests with useful items.

Access all areas

One of the big considerations when designing these types of levels is that we want to avoid a situation where the player can get stuck, and be unable to continue, perhaps because they are in an area where they can’t jump out of, or a jump is too far to be completed.  Top-down rogue likes don’t have this problem because, well, they are top-down.  Spelunky gets around this problem by providing the player with ways to deform the level (Such as creating passages using bombs) and for escaping possible trapping layouts using ropes.  I wanted to avoid going down this route, and wanted to guarantee that the player could never get stuck.  The simple solution was just to be quite disciplined while creating the room templates.  I locked down the player motion and feel quite early in development, so I knew how high and how far the player could jump, so, for example, if the player could at a maximum jump up onto a stack of three level tiles, I just had to make sure all the level geometry in the room templates adhered to this.  Similarly with the horizontal jump distance. Finally, I created a system in the level generator that would find rooms that were connected vertically and insert ladders that started at the lower exit of the upper room and extend down into the lower room until some collision geometry was encountered.

Decorating

Now that we have our level layout ready, it’s time to make it look nice.  There are several steps to this, but first of all, we do a pass through the tile data and mark any tile that is not within a room boundary as solid, this will make sure the player can’t fall through the map anywhere.

There are 5 distinct area styles in the game, including a palace style, dungeon style and so on.  I chose a level style depending on what level the player has reached, so at first the castle style will be selected.  For each style, I have a tile sheet with graphics representing all of the different combinations and shapes that the collision data can form, inner and outer corners, straight edges and solid areas.  It’s a simple process to iterate through all of the collision data and determine what tile image should be used there, for example if a solid tile has another solid tile to the left and right, and no solid tile above, I select a graphic representing a walkable surface.  This is done for the entire level and at the end we have a very basic representation of the level.


 

Now for the fun part, decorating the level with incidental objects. In code, for each level, I define several objects that can be used to decorate the level, for instance, paintings, pipes and torches.  Each of these objects has some rules that define it’s size, image data to use, and placement rules.  As an example, a simple placement rule for a vase would be to find a position in the level that is empty, but has a solid block directly below.  There are some other more complex overriding rules that control placement, like not placing similar objects too close to one another. 

Enemies and other game objects are placed in a similar way: Each enemy descriptor contains rules for where they can be placed, based on their size and the mode of the enemy - bats and hanging slimes must be placed next to a ceiling tile for example.  The number and type of the enemy is governed by how far the player has progressed through the game, with stronger and more difficult enemies in greater numbers appearing later in the game.

Breaking through

Early on in designing the level system, it was obvious that the level layout had a rather dendritic appearance.  It was easy to tell that the level started off from one room and radiated out in all directions.  I overcame this by writing a system that would find near-by rooms that were not topologically close to each other, and attempting to tunnel through the solid tiles separating them in order to form a passage way.  This worked pretty well after a lot of tweaking and helped make the levels a lot less linear.  If the tunnel was vertical, a ladder would be placed allowing traversal between the newly connected rooms. 

Door placement

Placing entrance and exit doors to the level required a bit more thought than placing the other objects. In order to avoid placing the entrance and exit too close to each other and thus making the level quick to complete, I would select two rooms at random and perform some path finding between the two rooms.  It was very quick to pathfind between the room descriptors, so I would do this a few hundred times and select the longest resulting path.  There is probably a less wasteful way of determining this algorithmically, but sometimes it’s better to use a brute force method and spend the time working on some pretty particles or anything else more interesting.

Level shape

I wanted each zone in the game to have a different shape, for instance the palace was the first area, it should be smaller and rather horizontal, and the end levels should be larger and have a more vertical feel. It turned out to be quite easy to do this using my system by defining the bounds of the level generator.  No rooms could be placed outside the level bounds, so for the palace, the bounds were a relatively smaller wide rectangle, and for the dungeon areas, the bounds were much larger and more of a tall rectangle.

Level editor

At first I created a few room templates as plain text while I was getting things up and running, but this soon became too cumbersome to be useful, so I coded a very simple room editor inside the game engine.  This was as basic as possible, and really just consisted of a black screen with a grid representing the size of the room and some text to remind me of the keyboard shortcuts.  From here I could draw the solid blocks for a room template and doorway tiles.  There was some audit information displayed on this screen that kept a running total of rooms grouped by the types of exits in each room.  If I have 20 rooms with a doorway on the left, I want a similar number with a doorway on the right to connect to the left ones.

I could probably have spent more time making a better editor, but this rudimental one worked fine for what I needed.

I’m reasonably happy with how the level generator turned out, it meets a lot of the goals I set out to achieve and it does create interesting environments to explore (Well, I think so anyway!).  If I do make a sequel to this game, there are a few lessons I’ve learned from coding this will definitely help, a lot of them to do with basic game architecture but also specifically in the level generator.  I’m sure I could speed things up a lot by pre-processing the object placement checks (i.e. mark all tiles that would be suitable for a walking enemy to be placed in a single pass).  I’d also look into designing some systems to make the game a bit deeper, like some sort of puzzle generator, maybe a system that can lay out doors and keys in a sensible way.  I also hard coded pretty much everything into the game, and I’d benefit from writing a few simple editors to define objects, enemies and pickups etc. 

- Nick Donnelly

Twitter: @nickd3000
http://www.physmo.com