Markov chains

Platform

Windows

Language

C++/HLSL

Project Type

Course Work

Role

Solo

Duration

~3 Months

As part of a 3rd-year module, we were tasked to create an application which generated some sort of procedural content. This half of my application is a procedural tile-based map generator, the other half is discussed here.

To generate new maps the program uses a Markov chain, simply put this is a where the frequency of all of the different states in a system is used to generate a new state based on the previous state. The base 'system' I used was the first level from Super Mario Bros. The inspiration for this project came from several papers by Sam Snodgrass and Santiago Ontanon (here and here). I thought it would fun to try to implement this for myself.

This first step in this process was to load in an image and get the relevant information out of it (the number of different tiles, and where they were in the map). To do this, the user first tells the program what the dimensions of each tile are (in the case of the Mario map, this is 16x16 pixels) it scans through the map and assigns each tile a number and creates a text-based version of the map, as this is more efficient to

read in than the image for subsequent generations. The next step is to calculate the frequency of each unique tile combination, this is determined by

by the neighbours of each tile (on the left, the green tile is the current tile and the red tiles are its possible neighbours). Once this has been calculated the Markov chain can begin. To start the process the top left of the original map is used to start off the chain, this then looks at the current neighbours (red tiles) and randomly chooses a new tile to add (the green one), graphically this looks like the picture below (which in that case a pipe tile is chosen has been generated.

As the Markov chain isn't perfect it may generate combinations that were not in the original map, like the one seen below (left). To combat this, the program uses two methods; first, it attempts to generate a new tile a set number of times (usually five), if this fails it will go backwards in the x-axis and try again. If this doesn't work it will go diagonally back and up and continue from there (picture below/right).

At this point, the maps that it creates would be a tad difficult for Mario to complete. As such t

two more steps need to be taken. The first is to add a border around the original map, this makes the map create more ground tiles. The second is the split the map up horizontally into section as the distribution of tiles differs throughout the original map (e.g.

(e.g. there are no ground tiles in the top section). Once this is done the generated maps are actually reasonable playable, or would be if they were put into a Mario game.