Procedural Generation Implementations

In this post I will give an introductory to procedural generation and cover its use in game development.

How did the developers of Minecraft create a world like this?

You could imagine that creating this virtual world manually, one block at a time, would be tedious and lengthy; and you would be right. Minecraft uses procedural generation to create the environment anytime a player creates a new world.

Procedural Generation

So what is procedural generation? By definition, it is a method for creating data algorithmically instead of manually. So just like any algorithm, rules are used with operations to generate an output. In the case of Minecraft, an initial topographical rough draft is generated and then refined with further textures and objects by using noise functions. A noise function is simply an algorithm that randomly generates some kind of data.

Of course the world being created can’t be completely random because then it would’t make sense. You may end up with whales spawning on dry land, or a frozen lake in a desert in the middle of the day. This is why rules are needed within the algorithms to control what is allowed to be generated.

The benefits procedural generation are apparent, it allows game developers to quickly generate endless unique environments by implementing rules and algorithms.

Now lets take a look at some of the specific techniques that can be deployed to implement or help with procedural generation.

Cellular Automata

Imagine you had a handful of sand spread across a small area on a flat surface. And you blasted the surface with a sound at some frequency. The sand would gradually conform to the frequency of the sound waves that it was being hit by. This is similar to the idea of cellular automata, except instead of sand you are using cells in a grid, and instead of sound you are using algorithms.

This configuration could be created with cellular automata

There are many different ways to implement cellular automata that depend on the circumstances and motives of the situation, but the underlying principle remains the same: a random resulting configuration of cells is created based on the rules and algorithms that are applied.

Polygon mesh

One way to refine a rough draft of a procedurally generated configuration is to use a polygon mesh. A polygon mesh is a formation of polygons that represents some sort of object or geographical orientation. For example, here is a three-dimensional figure of a dolphin represented by a collection of two-dimensional triangles.

Triangle mesh of a dolphin

As mentioned this technique can be used to refine coarse procedural generations into more realistic or visually appealing results. Another point to mention is that even though the cellular automata implementation in the demonstration I will be using is two-dimensional, a polygon mesh can still be applied. This is because instead of fleshing out a three-dimensional figure, we will be smoothing the corners and bends inside a two-dimensional cavern initially created with squares. A formation of triangles can allow for a smoother finish than squares.