Spelunky PCG

About this project

Implementation of Spelunky's procedural level generator. My goal was learning a more design-focused approach to PCG, which mixes random and authored content to allow for design-conscious level generation.

During the development of a small game for my Mobile Game course at Stockholm University, my interest in procedural generation in games such as Nuclear Throne led me to create a simple level generator based on the Random Walk algorithm, which consists of a “walker”, which keeps track of its position and direction, taking a number of steps on a grid and picking a new cardinal direction placing floors every step, thereafter placing walls around them.

It had some basic compositional control, namely, how much of the grid was going to be filled and some other parameters to tweak the random number distribution to, for example, generate longer corridors. Sadly, although it was cool to see the levels being generated, they were messy, unfocused, and full of dead ends most of the time. It had all the randomness parts right, ensured connectivity between every place in the map but it lacked the level design.

My goal with this project was to learn how to get control over that randomness instead of being at the mercy of a random number generator for making an interesting level. Introducing a more design-focused approach, the approach I will be focusing on is Constructive PCG, which mixes random and authored content to allow for design-conscious level generation.

The Spelunky Algorithm

Every level in Spelunky is generated by a script that starts with the same basic shape and size 16 rooms in a 4x4 grid and takes the following steps:

• Pick a random room from the top row and makes it the entrance
• Randomly places a room to the left, right, or beneath it.
• Step 2 is repeated from room and if the path hits the edge of the level, it also goes down until it reaches the lowest row.
• When it tries to go down once more an exit is placed.

Every room on this main path has openings to the left and right, but rooms where the path goes down have exits on the bottom while the rooms you drop into are givens exit on the top.

What this accomplishes is a guaranteed path through the level that you’ll always be able to get through without using special items (ropes for climbing up or bombs for clearing out tiles).

The rest of the rooms which are not on the critical path are randomly selected and may be open or walled off depending on their design.

Loading Authored Templates

After the algorithm defines what kind of rooms will be placed and where, the next step is giving each room a random template from a lookup table, handcrafted designs with different layouts for rooms where you drop down from (3), rooms you land into (2), corridors you run through (1) and rooms not on the critical path (0) are selected and placed.

As you can see the templates are very noticeable because the human brain is really good at pattern recognition, this leads us to the next step.

Final Steps

These room templates are not completely set in stone and parts of them are randomly generated. Each room contains "probabilistic" tiles which have a chance of becoming a wall. Even though you might eventually start to notice familiar set-ups and patterns, they will always have their own quirks.

The final step is placing out items, weighing out the amount of items depending on how many items are nearby and the surrounding tiles. More loot should be hidden behind walls to make the player curious about exploring!

Closing thoughts

I have had a wonderful time trying to recreate Spelunky's level generator, I have learnt many PCG concepts which I am looking forward to apply in future projects.

It was great to be able to visualize how the levels are generated in such a simple but elegant way. My course supervisor displayed this small project to all new game development students at my Stockholm University during their introduction course to inspire them to start with their own side projects, small experiments and prototypes!

Overall I feel I surpassed my own expectations and I can't wait to build upon and learn even more about level generation and design.