Procedural Content Generation in XSPelunker (MSX)

A few weeks ago, I finished my second entry for the MSXDev'17 competition, XSpelunker, a roguelike platformer for MSX heavily inspired by the amazing Spelunky, and with some touches from Opera Soft's "Livingstone Supongo".  For those of you who are not familiar with the MSX, it is a family of compatible 8bit computers released in the early 80s. The target computer for XSpelunker is an MSX1 with 16KB of RAM, and an 8bit Z80 CPU at 3.56MHz. Screen resolution is 256x192 pixels, with a color palette of 16 colors. So, do not expect to see Call of Duty here! :)

If you have not seen the game, here's a short video showing the intro and some gameplay:

One of the main features of XSpelunker is that levels are generated using Procedural Content Generation (PCG). So, each time you play a new game, levels are different from the last time you played, and you need to find your way to the exit again. In this blogpost I just wanted to explain how did the PCG algorithm of XSpelunker works, now that it's fresh in my mind! :)

(spoiler alert, it works VERY similarly to how the original Spelunky generates levels)

The key idea is to use a set of "preauthored chunks" and then recombine them randomly to form new levels (this is also how Spelunky generates levels). For example, here are some of the chunks used for the jungle levels of the game:

So, for each type of levels I wanted to have in the game, I just had to author a set of chunks. One problem of combining them randomly, however, is that it might result in levels that contain no valid path from the beginning to the exit of the level! In order to address that, we need to introduce two new concepts: "chunk types" and the "level path".

Chunk Types

In order to let the game generate levels that ensure that there is a path from start to finish of the level, I labeled each chunk with a "type". This type determines things like:

• Special chunks: originally I had all chunks be 16x16 tiles in size. However, some puzzles I wanted to create required a larger space than that. So, I have some chunks that are 32x16 and others that are 16x16. 32x16 are SPECIAL chunks that are used differently than REGULAR chunks, which are 16x16.
• Where in the level can this chunk be placed (for example, chunks like the left-hand-side one above only make sense if they are at the bottom part of a level because of the water part). So, chunks can be labeled as: TOP, BOTTOM, or ANYWHERE
• Layer: levels are generated by stacking two layers of chunks one on top of the other. One layer contains the "background" (the foliage that you see at the top of the jungle levels, or the candles you see in the ruins levels), and the "foreground" (walls, platforms, etc.). I have a few BACKGROUND chunks to create a background, and on top of that, I overlay FOREGROUND chunks that define the level proper.
• Connections: some chunks allow the character to navigate form left to right, others only allow the character to go up, etc. So, I defined six types of chunks depending on the paths that they allow the character to take:

Also, chunks of a given type might allow more than the necessary paths, but at least they need to guarantee that these paths are supported.

So, for example, the three chunks shown above are (from left to right):

• REGULAR-BOTTOM-FOREGROUND-TYPE4
• REGULAR-ANYWHERE-FOREGROUND-TYPE1
• REGULAR-ANYWHERE-FOREGROUND-TYPE3

Level Path

Now that we have each chunk classified into a type, the game can now reason about which chunks to use if it wants the character to be able to follow a specific path. So, the first step in level generation is to generate a path. Let us assume that we want to generate a level of size 4x4 chunks. Generating a path involves the following steps:

Now, we know the type of chunks that we can use for each section of the level. Those sections without constraints (marked as "-"), can use any chunk, and those with constraints can only use chunks of the designed type.

Adding Chunks

Background: Once we have the path, the next step is to generate the background. The only constraints that are used are that chunks need to be BACKGROUND, and also TOP and BOTTOM chunks can only be at the top or bottom of the level respectively. After this, we will have the empty canvas of a level, that might look like this (you can see some foliage at the top already nicely formed):

Special Chunks: After that, notice that there might be lots of sections si the level that do not belong to the path (marked as "-" above). Those are sections where we can spawn SPECIAL chunks. So, the next step is to look to see if there are any two side-by-side "-" sections in the level. If there are, then there is a small probability of selecting a SPECIAL chunk to occupy that space.

SPECIAL chunks always contain one of the "kick-ass" items of the game (boots, shield, bow, mask, gun, or belt). Notice that since we are generating them off the path, there is no guarantee that there will actually be a path to get those items. So, if the player wants to get them, she will have to find her own way there!

Regular Chunks: After SPECIAL chunks, REGULAR chunks are put in the map. Every location where no SPECIAL chunk was placed needs to have a REGULAR chunk. The game uses the constraints defined by the path, and selects one chunk at random from all the chunks in the chunk library that satisfy the constraints. At this point the level will look something like this:

Notice that the level does not look very good yet. We see that some tree trunks are cut half way through for example! That will be fixed in the next step.

"Beautifying" Levels 

In this step, the game goes through the level and fixes some aesthetic aspects of the levels. For example, in the jungle, it completes all the tree trunks all the way to the top of the screen. In other sections of the game, there are other elements such as ropes or beams that need to be completed as well.

Another detail that is added in this step is a small marker for the exit of the level (the small yellow arrow).

After beautifying the previous level, it'll look like this:

Which starts looking better, but still looks quite empty, since there are no enemies, items, or anything else!

Spawning Enemies and Items

Some chunks are annotated with places that are good "item spawning" spots. So, at this point, any of those items are added to the map. For example, some chunks have a spot marked as SUPPLIES, which is translated to either a rope, a bomb, a stone or an arrow.

In addition to those, every horizontal surface of the map has a small chance to spawn a rock or an arrow.

For enemies, each enemy has a specialized routine that determines where is it a good spot for spawning it (for example, monkeys only get spawned in tree trunks, piranhas in water, bee nests hanging form a wall, etc.).

After enemies have been spawned, the game checks to see if a minimum number of enemies has been spawned (since the randomness of the process might result in levels with very few enemies). If not enough enemies were spawned, this step is restarted until enough enemies are generated.

Once the level is generated, it is ready for use in the game! A small routine goes over the map identifying those tiles that need an animation (water, fire, etc.) and adds the necessary data structures. After that the game starts!

The Different Areas of the Game

The above process explains how jungle levels get generated. To generate levels for the other two sections of the game, some steps are slightly modified in order to slowly increase the difficulty.

For example, in the "Ruins" levels (2-1, 2-2, 2-3 and 2-4), one of the chunks of TYPE 5 is actually missing a connection (on the top-right). So, whenever that chunk is spawned there is a chance that there is no direct path to the exit. So, the player will have to use ropes/bombs to create a path.

In the final levels (3-1, 3-2, 3-3, and 3-4) there is one final twist: in addition to having a chunk missing a connection, the bottom part of the levels gets filled with water. So, if the path happened to go through there, then the player will have to either go through water, or find a different path. This might result in some pretty hard levels. But it usually is not a problem, since, if the player makes it to levels 3-*, usually she is loaded with bombs/ropes or even might have the diving mask, with which the last levels are much easier.

The last level (3-4) in particular has a very particular shape (if you made it there, you'll know!), and unless you are prepared, can be VERY difficult. But, once you know what to expect, it's really not that hard. But I won't say more, since otherwise, I'll spoil the fun of figuring out how to beat the game! hahaha

So, that's pretty much it at a high level. That's how levels are generated (not much different than the way Spelunky does it!). So, no need to read more if you just wanted to have a high-level idea. If you want to know a bit more of the implementation details, then you should keep reading :)

MSX Implementation Details, Memory Usage, etc.

Let me start by explaining what is the usual tool chain that I use for creating MSX games. I created a diagram that I thought would explain it better, but after I drew it, I am now unsure if it helps. But in any case here it is:

So, the bottom line is:
- I draw graphics (e.g. tilesets) with GIMP
- I then load the tilesets with TILED to author level chunks, which get saved to TMX files (which are xml files).
- I then use a small Java script to translate these TMX files to the binary file I use in the game
- These binary files are then compressed using Pletter, and built into the ROM compiled with Glass.

Also, a few times I've used the OpenMSX Debugger, but I'm still not very familiar with it, so, I only use it when I'm desperate! But anyway, I would be really curious to hear which development tool chains other people use! :)

Level Chunks: All right, now that we have that out of the way, let's get back to PCG for XSpelunker... Consider the Jungle level generation process. For this, I defined exactly 26 chunks (you can see them in github in the data/rooms-jungle folder). When converted to assembler, a chunk looks like this:

So, when compiled into the ROM these 26 chunks would use a whopping 7272 bytes!

Remember that I wanted to fit it all in a 32KB ROM, so, if just chunks for the jungle use this much, if we add the chunks for the ruins, and those for the inner ruins, that'll be about 21KB just in chunks, leaving only 11KB for the rest of the game... that was not acceptable.

Compression: An obvious way to reduce space is to use some form of compression (e.g., what you'd do with a ZIP file in your modern computer). In my first game, naively I just implemented my own "compression" code (using a simple Run Length Encoding scheme, which is not technically even considered compression, but "encoding"). But folks at the msx.org forums recommended me to use a better compressor, such as Pletter. So, that's what I am using now.

I considered two separate options for compressing the chunks:

1. Putting ALL the level chunks into a single binary file, and compressing it.
2. Compressing each level chunk separately.

The advantage of the first is that I would save more space (since, it's well known that sizeof(compressed(A+B)) <= sizeof(compressed(A)) + sizeof(compressed(B))). The problem is that then to decompress it when the game runs, I would need to have 7272 bytes of free RAM, which I do not have...

So, I had to go with the second alternative, compressing each chunk separately. This uses more space in the ROM, but I do not need to decompress all the chunks at once, and thus worked better for XSpelunker.

(beginning of off-topic paragraph)
Finally, about compression, I just wanted to say that it is very easy for us in 2017 to use compression and pack a lot of features into a very small cartridge, compared to what the guys in the 80s did. But we must have in mind that compression algorithms are quite recent: the common LZW algorithm is from 1984, and DEFLATE (usually used in the ZIP format) is from the early 1990s... So, clearly game developers from the 80s did not have easy access to these technologies! There were compression algorithms dating back to the late 70s, but I am not sure that (given there was no Internet back then) it was easy for game developers to actually know about them. So, all of this is just to say that when we compre modern homebrew MSX games, I would not compare them to older games, since the comparison is unfair: we have way more resources nowadays than they had. So, creating an MSX game in 2017 is much easier than it was back in the 1980s...

(end of off-topic paragraph)

Chunk Simplification: However, even after compressing each chunk, that was still using too much space. The problem is that chunks contain complex patterns that do not compress very well. So, the solution was to simplify how chunks are stored. What I did was this: instead of authoring a chunk exactly as it would look in the game, I would just author a "skeleton of the chunk" that would be enough for then reconstructing the chunk in the game. I think it's better explained with an example.

Here you can see a chunk how I want it to look in the game (left), and how I ended up authoring it (right):

As you can see, what I have done is this:

1. Since there is a piece of code that completes all the partial tree trunks anyway, I only need to add the bottom of a tree trunk. No need to have the rest.
2. The solid rock part contains many different types of tiles (tiles with grass, edge, tiles, etc.). What I did was to just use a single type of rock tile, and then write a small assembler routine that would replace those by the proper tiles. The routine was smaller than the amount of space I saved by this, so it was worth it.

The result are chunks that are use less space after they are compressed! So, after all of this, the 26 chunks that originally were 7272 bytes, ended up occupying only 1453 bytes in the ROM. Which is more acceptable!

Level Progression: Once everything was setup, the level generation function takes in a set of parameters: size of a level, probability of appearance of each enemy type, which level chunks are available, minimum number of enemies, etc. So, in order to create a level progression, I defined the following table:

where, for each level, I specify its parameters. For example, you can see that level 1, is a small "64x32" level (i.e. 4x2 chunks), where only the enemy types 1, 3 and 5 can be spawned (pinecones, piranhas and scorpions), and where at least there has to be 4 enemies.  Level two is larger (64x64), but has the same enemy types, and in levels 3 and 4, more enemy types can be spawned.

In that way, adding a new level to the game requires actually only 17 extra bytes. So, I went for 12 levels just for not making the game repetitive. But adding more levels is not a problem at all!

So, anyway, there you go! That's how the procedural level generation in XSpelunker works! It's not rocket science, but it was fun to create it, finetune all the parameters, level chunks, etc. so that the difficulty level was what I was going for!

This was a long post, but I just wanted to write it now when it's still fresh in my mind, before I completely forgot about how I did it, hahaha

And btw, if you are interested in PCG in general, you could check the book that some good colleagues wrote a few years ago: http://pcgbook.com or if you want to see experiments and cool things, head over to the http://www.procjam.com website!