Generating Worlds in a Minecraft-like Game

With the runaway success of the game Minecraft, I've been seeing a bit of a resurgence of interest lately in the idea of procedurally generated worlds. I haven't played Minecraft, but I must admit that, judging from the youtube videos I've watched, it seems like it would be right up my alley, and I can certainly understand the desire to draw inspiration from it in some fashion. The idea of a very large/infinite sandbox world is very appealing. Unfortunately, once you get beyond simple random numbers, procedural generation of a world isn't always the most approachable subject and I see a lot of people asking questions about where they should start generating a Minecraftian world, or, more generally, a procedural world that can theoretically extend infinitely far in all directions.

For the purposes of this post, I'm going to shoot for a world made of chunks, where each chunk is sized 128x128x128, and there is no practical limit on the size of the grid of chunks that can be generated on the X/Z plane; ie, the world is only 128 layers deep, but "infinitely" long and wide. Doing a chunked approach like this enables you to build your world in pieces, and to only build the pieces you currently need to display or interact with in your game. Once generated, a chunk can be saved to a file when unloaded, to be loaded the next time you need that chunk, rather than generating it from scratch. In this manner, the world save file would dynamically grow as chunks were visited, taking up only as much disk space as needed to remember the currently visited world. To save disk space, you can save only the parts of a chunk that were modified; then when loading, you would generate the level from the generator, and apply the changes from the file to bring it up to date.

But before I get started, I want to lay some groundwork.

Implicit vs. Explicit Methods

An implicit procedural method is highly self-contained, expressible as a mathematical abstraction. You call a function with a set of coordinates, you get a result. The value of the function at a given point or cell is not dependent upon or derived from any surrounding cells or points; it is self-contained. Also, it is not necessary to evaluate neighboring points in order to evaluate the desired point. An explicit method, on the other hand, is typically implemented across large areas of the "function" at a time, and the value at a given point is typically highly dependent upon the values of surrounding points; it is frequently not possible to simply evaluate one point of the function; an entire neighborhood must be evaluated instead.

An example of an explicit method would be using the Diamond Squares or Midpoint Displacement algorithms to generate a fractal heightmap out of an allocated chunk array. You create a large buffer of data, and iterate across it a number of times to generate the features for that particular area. By nature, these algorithms can only generate a chunk of data, and can not generate merely a single point. The size of the chunk produced also directly impacts the overall nature of the function.

An example of an implicit method would be using a Perlin noise function to generate a height map. The values of the heightmap are drawn directly from a "pure" mathematical process, rather than a process of iteration and filtering performed on a large array. There is no need to store large blocks of data. You can simply call the function with any possible coordinate point and obtain the value of the function at that point.

While on the face of it these techniques frequently produce similar results, the macro behavior of them is completely different. For one thing, with an explicit terrain generation method it can sometimes be difficult to ensure continuity across the borders between blocks of data. An explicit method takes into account other points in the neighborhood of a point as long as those points exist within the chunk. It does not take into account points outside the chunk; hence, it is possible for discontinuities or regularities to develop if we are generating a vast world, since it is not possible to generate the entire world explicitly all at once; at least, not without some highly expensive calculations and large-scale use of disk space. By subdividing the world into chunks, we are creating discrete pieces of world that conceptually have no knowledge about their neighbors, and possibly do not relate or correlate to them in any fashion. It is necessary to ensure that chunks will superimpose upon one another in a meaningful and cohesive manner, and sometimes this can be difficult to achieve using explicit methods, requiring ofttimes intricate hacks, kludges, workarounds, and storage of unnecessary state.

In contrast, all of the form and feature of an implicit method is inherent to the inner workings and nature of the function(s) upon which the method is founded; intimate knowledge of neighboring chunks is not necessary in order for a chunk to build itself. In most cases, we can simply store a simple random seed for our world and, as long as we do not change the underlying generator, this seed can be used to fully reconstruct the world, or any segment thereof.

Of course, in this as in many other ventures, there is no such thing as purity, and we will at some point be forced to rely upon explicit methods for one reason or another. There are aspects of procedural level generation that simply can not be represented easily using implicit methods; processes such as hydrology/water-flow, erosion, propagation of vegetation, etc... While we can, of course, use implicit methods to help with some of it, others represent a more difficult problem.

Still, a large portion of the work can be done using implicit methods in a highly elegant fashion. If we hold to our goal of prefering implicit methods over explicit, the end result of our efforts, ideally, will be a comprehensive set of functions governing every single cell in the world. We'll have functions that can tell us if a cell is stone, or sand, or dirt, is steeply inclined or flat, etc... The domain of these functions will be limited only by the precision of the underlying floating point format; by using double-precision floats we can achieve a domain so large as to be practically infinite in scope.




Functions

Functions are the fundamental building blocks of our world. They come in a wide variety of shapes and sizes; we'll be using Perlin noise fractal functions extensively, of course, as integral parts of the process, but not only those. We can produce functions to generate smooth, directional gradients, functions to create sharp edges or discontinuities, functions to generate regular, repeating patterns, etc... All of these are potential tools in our tool box. As a good starting point let's go ahead and hammer out what we mean by functions, and how they are going to work.

Mathematically, of course, a function is an abstract entity or process that associates an input with some output. The same input will always produce the same output; in this manner a function is deterministic. In our case, most, if not all, of our functions will be of the 3 dimensional variety, accepting input of an (x,y,z) coordinate location representing a single cell in the world.

A function can be made as a composite of a number of other functions. They can operate on the output of another function or set of functions, or they can transform the input to another function or set of functions in some fashion. In this way, complex functions (translating to complex worlds) can be built up, a piece at a time, from simpler building blocks. In light of this, I have become an advocate of a modular approach such as that implemented by libnoise; modules can have some arbitrary number of inputs, and produce output via a get() function. They can be tweaked using adjustible parameters, and complex module trees can be built up using the simple building blocks of basis functions, combiners, domain transformations, and so forth. While I am writing this post in the context of my own personal noise library, the ideas concerned can easily be translated to a library such as libnoise. I do have plans to release my own library in the future; currently, however, it is still quite messy and needs a significant amount of cleanup.

The basic format of a function is as follows:

Each function provides a set of get() methods which can be called to obtain a value for a given coordinate location. In my library, I provide 4 different get() methods, for providing fractal noise in 2, 3, 4 and 6 dimensions. (The 4 and 6 dimensional varieties are for the purpose of generating seamless 2D noise and seamlessly animated 2D noise or seamless 3D noise, as per the technique I detailed here.) I provide separate functions for efficiency; while it would be simpler to provide merely the highest dimensionality, and set unneeded coordinate components to 0, I chose to downgrade the underlying generators to fit the number of coordinates for speed.) For the purpose of this post, the 2, 4 and 6 dimensional varieties can be ignored, since we don't need to generate anything seamlessly.

Functions that are generators do not take inputs. These include gradient generators, fractal octave basis functions (value noise, gradient noise, simplex noise, white noise), and so forth. They may have parameters that alter their behavior. (I classify fractals as generators, but in my library a fractal is merely a special type of combiner that provides a default set of inputs for the octaves; each of the inputs may be overridden with another function as desired.)

Functions that are combiners, modifiers or transformers accept arbitrary numbers of inputs, specified using a setSource() type of function. Some functions accept only a single source (examples include Invert(multiplies the source by -1), Bias(modifies the output using a bias function), MapToCurve(maps the source output to a user-specified spline curve), etc...) and operate by taking the output of their source, performing some operation on it, and outputing the modified value. Others accept a specified number of inputs greater than 1; these are indexed in typical C fashion, starting at 0 and ending at MAX_SOURCES-1, an API-defined value (currently 20). Examples of these include Combiner(which can Add, Subtract, Multiply, Max, Min, or Average a set of inputs), Turbulence (which can accept a main source, up to 6 Axis sources(each optional), and an optional Mask source), and so forth.

Rather than build a function tree out of a sequence of actual function calls and code, I will adopt a notational scheme that demonstrates how the module types are chained. Here is an example of such notation, expressed as a Lua table:



The above definition declares a fractal function of type Ridged Multifractal, using Gradient noise as a basis and quintic interpolation for smoothing, specified in 8 octaves with a frequency of 2. Another example:



This table sets up a turbulence modifier that acts upon our Fractal1 and uses a second fractal, Fractal2, as the noise source for the X axis turbulence.

Expressing an entire module tree as a sequence of Lua tables allows me to build the chain using concise notation, and I can feed the sequence to a parsing function that actually builds the module tree.



The Basic Terrain

We can talk theory until we're blue in the face, or we can dig our hands in and try some stuff out. Let's do that right now. Our world is going to be fundamentally split into 2 basic types of area: Solid and Open. Open, of course, is air, or empty space (or water, at a later stage), whether above ground or deep in a cave. Solid is anything of a solid nature: rock, dirt, sand, etc... So a good first step is to build a function for us that will separate the land from the air.

The easy and obvious way to do this is to represent the ground terrain as a heightmap, derived directly from a 2D Perlin noise fractal:



Heightmaps are great; they in effect encode volume information (the ground) as a single value per location (height). Heightmaps have been used for a long time to represent terrain for a number of reasons: efficient storage space, rapid rendering of large areas with level-of-detail, easy terrain texturing, etc... However, if you look at games such as Minecraft, they are very volumetric in nature. They have cliffs, overhangs, caves, tunnels and mines: you name it. A traditional heightmap just doesn't quite cut it for a volumetric world. What we need is a function that operates in 3D space to tell us if a given cell is solid or open, and even what type of solid cell it should be.

To begin with, then, we are going to build a 3D function that will separate the sky from the ground. We can base this on a simple gradient function. A gradient function will assign a smooth gradient of values from -1 to 1 along an axis defined by two endpoints, in this case endpoints chosen to align the gradient along the Y axis. Points at Y=1 output 1 and points at Y=0 output -1.



We can couple this function with a threshold function that outputs -1 for anything less than or equal to 0(or some other specifiable threshold), and 1 for everything greater than 0. The result is a function that makes solid everything in the space where Y<=0.5. We can use a Select module to act as the threshold function.



This particular bit of code works by creating some constant sources, sources that output a given constant regardless of the input. Then we create a selection function. A selection function will select value from either its low source or its high source, depending on the value output by its third source, in this case the gradient function, GroundGradient. If the value of the third (control) source is less than a specified threshold, the value of low source is output; otherwise the value of high source is output. A second parameter, falloff, can be used to implement a smoothing zone around the threshold, to gradually ease from one function to the other; in our case, however, we want a sharp divide between ground and air, so set falloff to 0.

If we visualize a chunk made from this function, setting any cell that is equal to -1 to solid, we'll get a flat plane. It's a good representation of a flat stretch of ground, certainly, but it's definitely not very interesting. What we need to do is apply some more functions to add surface features. To create these, let's look at a technique commonly called "turbulence."

Turbulence, in the context of noise functions, is simply a method for transforming the inputs of a function based on the outputs of another set of functions. To begin with, we will transform the Y coordinate of the input of our baseline function, to create some basic hills and valleys. To do so, we need another function to act as the turbulence source.

A good place to start with this might be a basic Perlin noise fractal, what is commonly called an fBm (fractional Brownian motion) fractal. This article is not intended to be an in-depth discussion on the principles of Perlin fractals; for that, I might direct you elsewhere. fBm is the type of fractal commonly used for generating heightmaps, and in our case it is going to act in a very heightmap-ish manner, since we are going to use it to adjust the value of Y passed to the baseline function. The behavior of a fractal can be tweaked in a number of different ways. First, a fractal is composed of layers of noise functions of different frequencies summed together. We can change the number of layers using the setNumOctaves() function; fewer octaves results in smoother, less jagged noise; the more octaves we add, the more detailed the noise becomes.

We can also modify the frequency of the function; a higher frequency means that the features of the function, the wave crests and troughs if you will, are closer together; lowering the frequency in effect spreads the function out. Here is a composite of images showing the effect of increasing the number of octaves of an fBm fractal (shown here increasing horizontally) as well as increasing the frequency of the function.



A turbulence function can take a number of inputs. The first input is obtained from the output of the function to perturb, in this case our thresholded gradient function. There are also a set of inputs representing each axis of the coordinate system, so that we could have a separate function perturb each of the x, y and z coordinates. In this case, we are only perturbing Y, so we'll set the Y axis source to our fBm fractal.

Now, a turbulence function operates by obtaining output values for each of the axis sources, and using those output values to modify the input coordinates to the main source function. The amount or magnitude of variation is specifiable by using the setPower() method of the turbulence function. The higher the value you set for power, the more the axis function will affect the corresponding coordinate value. Let's go ahead and setup our turbulence function, and set a few preliminary values for our number of octaves, frequency and power of turbulence, and see what we get.



Here, we first set up our gradient as before, only this time, before we apply the select function to split the gradient range, we create fractal, GroundShape, specifying the type (fBm), the type of basis (options are: VALUE, GRADIENT, VALUEGRADIENT, SIMPLEX, and WHITENOISE), and the type of interpolation to use for the basis function (chosen from: NONE, LINEAR, CUBIC, QUINTIC). All of these parameters, of course, are tweakable, and it is even possible in my library to override any of the default fractal octaves with custom functions; however, for our purposes now a simple default setup is fine. This fractal will give shape to our ground surface.

We set the number of octaves to 2; this results in a rather smooth function; adding more octaves contributes to a chaotic, highly turbulent effect. And we set the frequency to give a good sample of the character of the function. Finally, we setup the turbulence module, apply sources, and set the power to 0.5 on the Y axis. By adjusting the power of the Y turbulence, we adjust the effect the turbulence source fractal has upon the gradient basis function; a higher power results in a more highly turbulent ground surface. So let's go ahead and see what kind of ground surface we get from this.



That actually looks pretty good.

This image was created by mapping a unit-sized cube of the function, from (0,0,0) to (1,1,1), sampling it in 128 steps along each axis, and setting voxels to solid as appropriate. The voxel chunk was converted to a mesh using PolyVox, then imported to Blender for quick visualization.

We're using a relatively low octave count to make the contours of our terrain smoother; we can decrease or increase the octave count and see how it affects the output by making the terrain less or more complex:


(Lower Octave Fractal)


(Higher Octave Fractal)

We could also modify the frequency of the function and see how it tightens the features or spreads them out:


(Lower Frequency)

(Higher Frequency)

Now, you can see that the turbulence function is acting in a manner very similar to a heightmap, raising the terrain in some places and lowering it in others. However, if we increase the power of the turbulence function, you can see exactly how different this approach is to using a heightmap:

(
(Lower turbulence)

(Higher turbulence)

The higher the power is, the more "frothy" the surface of the terrain becomes. This is because, rather than moving whole columns of ground up or down based on a 2D heightmap, we are instead shifting each individual cell up or down in the gradient function based on a 3D volumetric function. Higher powers can create an extremely convoluted and alien landscape; which, of course, may be exactly what you want depending on your scenario. Turn up the turbulence power high enough, and you can end up with floating rocks and islands.

Now, the beauty of composing functions out of combinations of other functions is that we can drastically alter the behavior of the system merely by changing a few parameters or by swapping out one set of functions for another set. In this case, we can alter the character of the landscape by changing the basic fractal type to another variety, for instance a ridged multi-fractal:






For now, this technique gives us a pretty good foundation to work upon. We'll come back to it later to flesh it out and add some more complexity, but first I want to segue into one of the most interesting features of Minecraft, in my opinion: caves and tunnels.

Caves and Tunnels

I've watched plenty of Minecraft vids of people out toodling around the countryside, riding pigs and chasing chickens, when all of a sudden the ground sort of opens up before them into a shadowed, mysterious tunnel twisting down into the depths. A rolling landscape covered in hills and trees is great; an enigmatic, dark cave to explore is sheer awesome.

Now, all the mystery and excitement aside, a cave is pretty simple. It's just an open space. Typically, from what I've seen in Minecraft, the tunnels are relatively narrow and long, with few large caverns or openings. I'm not sure how Minecraft does it, but from where I sit, a low-octave Ridged Multifractal with some tweaks just might do the trick. However, it is going to take some massaging to get it to look right.

To begin with, a basic Ridged Multifractal in 2 dimensions with a single octave looks like this:



If we apply a threshold function to it, mapping the function to either solid or open, we get a series of contoured areas that sort of fits what we want. Here is a series of fractals with varying thresholds:



Now, in 2 dimensions, this seems to work great, so let's take a look at what it's like in 3D:



That's not really what we want. In 3 dimensions, the ridged multifractal doesn't carve lines or tunnels or tubes like you might expect, but rather it carves a network of curved surfaces or shells. However, what we can do is set up another identical ridged noise source function, seed it with a different seed, and multiply the two sources together. This has the result of keeping the portions of the shells wherever they intersect, and discarding the rest of the areas.





That's more like it. We have plenty of interconnected, narrow little tunnels to explore, as well as some areas where the caves open up just a little bit. We can play around with the various thresholds of the two cave sources in order to play with the thickness of the caves. Note that the selection functions for the cave networks output values of 0 or 1, rather than -1 or 1. This is because we are using the cave network as a multiplicative source, used to "mask" off areas of the final base function. We want the base function to be open anywhere the cave function evaluates to 1, and solid where it evaluates to 0.

Now, this gives us the interconnected system of tubes, but since we are using a 1-octave fractal for the basis, the caves seem sort of weirdly smooth. We can roughen them up by applying some turbulence:



This sets up 3 noise sources and a turbulence function to apply to our multiplied caves network. Each axis source is set with a different seed. Rendering the output of this on our cave network gives us:



I like that. That gives a nice, chunky, natural look to the caves.

To wrap up the process, we need to invert the cave function (since it currently acts as a solid function where the caves are, and open surrounding them; we need the caves to be the open space, and the surrounding function to be solid) and multiply it by our ground function to get the final open/solid function for our ground formation:




Render a chunk of it and see how it looks:




And there we have a nice, hilly chunk of ground laced with a network of caves and cracks, ripe for the exploring. Here is the entire set of modules in table form to generate the above function:



As you can see, the full specification for the module is relatively simple: 18 different modules to get a complex terrain. Of course, we can easily modify the way we do things at any step of the way; in particular, the ground shape function should probably be tweaked a bit to provide more variety. If you look at a topo map of a region of Earth's landscape, you can see that the surface of the ground is not homogenous. There are flat areas, hilly areas, areas of mesas and tabletop mountains, deep canyons, steep mountains, etc... Our current implementation merely uses a simple fBm fractal to perturb the surface, but to get more varied results we could replace the fBm fractal with more complex tree of fractals, select functions, blend functions, and more, to create a non-homogenous function that can produce widely different terrain types.

We can also tweak the cave generator to produce more varied and intricate caves. A possible tweak might be to add another fractal source that is scaled by the ground gradient, so that as it draws nearer the surface it approaches zero. By tweaking the frequency of this, and adding a thresholding function, then combining it with the cave network function using a combiner such as Add or Max, we can effect the addition of larger voids and caverns near the bottom of the world, voids that scale down and disappear nearer the surface. We can fill these deep caverns with lava and demons to create dangerous, hellish depths to test the player's skills.

Other things that still need to be done are to tie the ground shape gradient function to a curve that can give us layer types. The top 3 or 4 layers of the ground should be dirt, then stone meta-types all the way down to the final layer which should be unbreakable bedrock to keep us from digging through to the Abyss. Further functions drawing off the ground gradient can define layers where mineral deposits may occur.

All of this I'll try to address in a later post.