Downgen is a small tool for generating levels for vertical scrolling games. It is inspired by rxi's awesome article about using markov chains to generate these levels.

While rxi used Lua and LOVE, I used C and emit a simple gif using gifenc.

The tool generates images that look like this:


The idea is to take an input level (in this case a text file with '0' and '1' characters), split it into rows, and map out which rows occur next to which other rows. I decided to account for both rows that occur after as well as rows that occur before other rows when checking this.

The, starting with a random row, determine the next row in the image by which rows in the original image follow (or proceed) the current row. The likelyhood of choosing a particular next row is determined by how often it is adjacent to the current row.

This makes is essentially a Markov Chain, and it is stored as a table of transitions used to determine transition probabilities. Each row is a state, and the probability of transition from row R0 to R1 is "n / N" where n is the number of times R1 is adjacent to R0, and N is the total number of rows that occur next to R0 the original image.

The tool is very easy to build and run- see the github repo for details- and generates images of a given height, speed, resolution, and with a given text file as the input level.

Note that this tool only accept '0' and '1' characters, and only allows widths < 64. This is simply because the rows are encoded as bitmaps in uint64_ts.

I will leave this post with a gif: