Spelunky’s Procedural Space

by Darius Kazemi on September 29, 2009

in BoRT,Spelunky

NOTE: For a way more technical article about Spelunky, see my newer tutorial, Modding Spelunky’s Level Generator.

The following is my first entry into Corvus Elrod’s Blogs of the Round Table. I’ve been meaning to participate in BoRT forever, and I’m pleased to finally get around to it. To make things interesting for myself, I decided at PAX that I would participate in every BoRT for the next year, and that I would write every single BoRT entry about Spelunky. Because I am that much of a fanboy.

This may backfire.

This months’ theme “invites you to explore the ways games have represented the spatial nature of their storyworlds and what this does for the audience experience.”

Room Generation

Spelunky takes place in a series of two-dimensional platform levels. Each level is divided into a 4×4 grid of 16 rooms. Each room consists of 80 tiles, 10 tiles wide and 8 tiles high. In the source code, rooms are structured as 80-character strings. Here’s an example:

“00000000110060000L040000000P110000000L110000000L11000000001100000000111112222111″

If we add line breaks every ten characters, we can begin to see the way rooms are laid out:
0000000011
0060000L04
0000000P11
0000000L11
0000000L11
0000000011
0000000011
1112222111

“L” signifies a ladder. “P” signifies the ledge near the top of a ladder. 1′s and 2′s signify varying chances that a basic brick tile or a block tile will appear. That 6 floating in midair is essentially a trigger that says, “Put a series of random tiles here. Or perhaps nothing.” (It’s funny, if you look at the 10×8 block of characters and squint your eyes, the game starts to look like Rogue, its most illustrious predecessor.)

There are only about 50 basic room layouts for every tile set in the game.

The experienced Spelunky player begins to notice and anticipate these blocks. Although there may be a slightly different layout each time thanks to the 6, I look at that block and I say, “Oh yes, that’s the ladder next to a vertical wall with a pushblock at the top of the ladder. I often see that on the ground floor of a level in the game’s first tile set.” My muscle memory is ready to traverse this room in about two seconds flat. Any given Spelunky level consists of 16 of these rooms. There are only about 50 basic room layouts for every tile set in the game. After 500 playthroughs, it is possible for a player to recall each one.

Obstacle Generation

But space in Spelunky is more than just a layout of ladders, walls, and blocks. Space is rudely interrupted with traps and monsters. Whereas the physical layout of each room is something like 80% hand crafted and 20% randomly generated, the layout of traps and monsters is 100% procedural, based on rules like:

If we are in the first cave tileset, then for every brick tile that is not the ceiling of the level itself, and is not in a shop, and is not in the starting room, and is not on the bottom half of a room, check to see if we have a two by two block of empty tile spaces below this brick. If there is a two by two block of empty tile spaces, and we’re allowed to generate a Giant Spider in this level, and we have yet to generate a Giant Spider in this level, then there is a 1 in 40 chance that we generate a Giant Spider and some cobwebs right beneath this brick. If we do generate a Giant Spider, make sure not to generate another one in this level.

The above works out to about 30 lines of code, simplified somewhat. The code for monster and trap placement is so thoroughly procedural and random that unlike the case of room layouts, no Spelunky player, no matter how experienced, can begin to anticipate the placement of these obstacles.

Spelunky is a Series of Interesting Obstacles

When we speak of Spelunky as a procedurally generated platformer with high replayability, we are speaking of the obstacle generation code far more than we are speaking of the room generation code. Yet when we look at the (excellent, brilliant, fascinating) TIGSource procedural generation thread, the focus is on the generation of rooms and terrain. For the first time, I’m starting to think that they’re barking up the wrong tree. The space that they should be focused on generating is the space of obstacles, the topology of which is tied inextricably to the mechanics of the obstacles themselves.

Please visit the Blogs of the Round Table’s main hall for links to all entries.

{ 5 comments }

kyle September 30, 2009 at 1:04 am

Awesome breakdown of the world. I didn't want to dig into the code myself, so I'm glad you took the role of tour-guide.

Patrick September 30, 2009 at 5:05 pm

Excellent article. Indeed, just space alone is not enough, you need to be able to generate interesting agent behaviors to utilize that space. The largest bit of code in Spelunky outside the main scripts is the behaviors for the Shopkeeper, who is also the most memorable character for many players. More work should be done there. However to complete the arrangement you need some kind of model of the game balance that can be adjusted in real-time, otherwise the complexity becomes prohibitive as I´m sure Derek Yu can attest.

Darius Kazemi September 30, 2009 at 5:30 pm

Now that your article is gone with the erasure of your blog, someone's got to fill the Spelunky level generation analysis gap.

Patrick October 1, 2009 at 9:38 pm

You did a beautiful job summarizing the algorithm.

Darius Kazemi October 3, 2009 at 9:44 pm

Thanks Patrick.

Comments on this entry are closed.

{ 2 trackbacks }

Previous post:

Next post: