ConvChain
From the same source as last week’s texture synthesis, here’s a level design approach that uses a Markov chain Monte Carlo simulation to generate level maps.
We’ve encountered Markov Chain Monte Carlo simulations before, though not always under that name. A Markov chain is a sequence of variables, where the probability of moving to the next state depends only on the current state. The “Monte Carlo" part just means that it’s an algorithm that uses random sampling, in reference to the casino in Monaco. The idea is that the state of the Markov Chain will match the desired distribution after a certain number of steps.
You can see this in action in the video: the algorithm takes a sample image or level as input and builds a cellular automata that is most likely to generate that image. It’s a kind of reverse engineering generator that learns the goal and tries to emulate it.
The other interesting thing here is that a level can be treated as an image, or an image as a level. This is an important principle to remember for procedural generation, and why I keep harping on unusual inputs: everything in the computer is just data and code, and you can often use data interchangeably, even if it wasn’t originally designed for that.
Therefore, you can do things like take image filters such as blurring, sharpening, convolution, high-pass filter, distortion, tone-mapping and so on, and apply them to your tile-based level generator.
Which is actually how I originally became aware of ConvChain: the overworld map you can see in the video is made up of tiles sampled from a world map created via Neural Doodle.
Amit Patel of Red Blob Games made an online web-demo and the original code is on GitHub: http://github.com/mxgmn/ConvChain