Procedural generation of an infinite world
Procedural generation is a technique that can be used in video games to create an infinite amount of data for maps, textures and sounds to make game worlds that never end.
As described in my previous post, I recently entered the JS13k Games competition and I wanted to make a game that felt big but would fit within the 13 kilobytes size limit imposed by the competition. I chose to use procedural generation since it meant I could generate the game world within the game code, thereby keeping the size of the overall package small.
Here I discuss some of the background behind how I did it. Although I used procedural generation to make the terrain for a 2d platform game, the techniques also work for generating game structures, sprites, textures and sounds.
Procedural generation in general uses a procedure that creates features according to some fixed input arguments. Given the same inputs, the same feature will be output. To create an infinite terrain for my game I needed a source for the inputs with the following characteristics:
- apparently random and never repeating, so that the world is interesting to play
- the same inputs are generated every time the game is run, so that the world is the same every time we play
- the current output doesn’t depend on any previous output, so that we can generate any part of the world in any order
In other words, a function that maps its inputs to its outputs in an unpredictable yet repeatable way.
Here is an example of one such function that returns unpredictable values between 0 and 255.
The function has only a single input parameter. To generate a 2D terrain, I needed a function that gave a repeatable output for every
(x,y)coordinate in the world. To use the function above I needed to map the
yvalues to a single number.
A way to do this is to treat the
(x,y) pair as a vector and calculate the dot product of that vector with some other fixed vector. Here’s how that looks. It’s the same function as above, modified to take two inputs.
Plotting the output of this in a plane looks like this:
Although many pairs of numbers have the same dot product, they are skewed across the 2D plane so the repetition isn’t apparent.
The noise here looks random enough, but it’s quite harsh and not very natural. A more natural effect can be achieved by combining several layers of noise at different scales.
Each layer is generated by “zooming in” on the noise, skipping pixels and interpolating the values between them.
Here’s how it looks when we zoom in 128 times, i.e. only one pixel in every 128 comes from the pseudo-random function and the rest are interpolated.
I’ve used linear interpolation here, which means the brightness varies in a straight line from point to point. That makes the regular sampling grid very much apparent — you can still see ‘squares’ in the output.
There are more sophisticated approaches to interpolation. (Perlin noise is a well known example.) However, the simple linear interpolation shown here is sufficient for the world I wanted to generate.
Here are four different sample spacings (or periods), shown as separate layers, then overlaid.
This gives a slightly more natural looking noise, known as “fractal noise” because the different layers are essentially the same but at different scales. It’s often used in computer graphics to generate natural looking textures like rust or clouds.
(In signal processing this is equivalent to filtering the noise to remove higher frequencies. The same effect is achieved here by adding lower frequencies of noise together.)
A game world
You might be able to see how this type of noise could be used to create a world for a game. It could be interpreted as a map of hilly or bumpy ground, viewed from above.
In my game I used it to create a network of underground caves, viewed from the side. By applying a simple threshold function, where every pixel value above the threshold is drawn and the rest is left empty, the noise looks like this:
This is the basis of the network of caves in my game. The caves here go on forever, but I wanted the caves to begin and end at fixed levels. By adjusting the cutoff value of the threshold function away from 50% I could vary the density of thecaves between entirely solid and entirely empty. This let me create different bands of sky, caves and bedrock:
By using a second threshold function I added a layer of earth, and by shading the background different below a fixed
y coordinate I created the effect of water.
I added grass as a thin layer on top of the earth. To ensure that it only appears on the top surface and not underneath I modified the code to test the gradient of the underlying noise field. Since empty areas have lower noise values that the solid ones, the
y-component of the gradient at any point can be used to tell whether the surface is facing upwards or downwards.
Finally, in order to confine the player horizontally, I created the effect of an island by varying the threshold along the
xaxis as well as the
yaxis. I did this by offsetting the
ycoordinate according to the square of the
This formed the basic terrain for my game. It makes for a reasonably sized game world that doesn’t consume much space in the game bundle. To complete the world, and make it a bit more fun to play, I added a castle and a few other platforms and ladders, which you can discover for yourself by playing the finished game.
I’m a software engineer based in London. I help companies to build web applications.