Main Docs Examples Download Gallery

3D Cube World Level Generation

Due in part to the popularity of the game Minecraft there has been a resurgence of interest lately in the idea of a game set in a world made of cubes, constructed of 3D terrain filled with interesting things such as caves, overhangs, and so forth. Such a world is an ideal application for noise generated in the style of ANL. This example is a discussion based upon my earlier efforts at discussing this technique. (The linked article was later included in the April 2011 issue of Game Developer Magazine.) There have been a few changes to the structure of the library since that was written.

In (Links to minecraft posts) I discussed using 3D noise functions to implement a Minecraft-style terrain. Since then, the library has evolved a little bit so I'm going to revisit those posts and discuss it again. Since I have had to answer a lot of questions regarding this system, I'm going to try to be a little more clear on the concepts involved. In order to clarify those basic concepts, I'm going to start with the idea of generating a 2D terrain like what you see in games like Terraria and King Arthur's Gold, then extend that to the 3D case like Minecraft. This will allow me to use images more effectively to demonstrate the concepts.

This system has the following abstract goal in mind: to be able to feed the system with the coordinate of a certain point or cell and be able to determine what type of block should be at that location. We want it to be a black box; we give it a point, we get a block type. Note, of course, that this is for initial generation of the world only. Blocks in these kinds of games can be changed by player actions, and at that point it is not appropriate to attempt to describe those changes using the same kind of system. Those changes need to be tracked in some other manner. This system generates the initial world, pristine and untouched by human or non-human hands.

This technique also may not be appropriate for the modeling of some systems such as grass or other biological entities, given that those systems are themselves complex entities that are not so easily modeled in an implicit manner. Same with systems such as snowfall, ice formation, etc... The technique presented here represents an implicit method, ie one that can be evaluated at a point, and whose value at a given point is not dependent upon surrounding values. Biological and other types of systems typically need to be aware of the surroundings in order to perform an accurate simulation. How much sunlight does a block receive? Is there water nearby? These and other questions must be answered to simulate the growth and spread of biological systems and, to a lesser extent, other types of climate-related systems as well. It's also not an appropriate technique for water modeling either. This system has no concept of flow, no knowledge of fluid mechanics or gravity. Water is a complex topic, requiring a lot of complex processing.

This is not to say that implicit methods are totally useless in these areas; that is not so. However, in these systems an implicit method is only one tool of many. They can be used to model regions, perturb areas, and so forth, but the heart of the system will be explicit methods that perform environment analysis and simulation, and that is beyond the scope of this article and this library.

So, we're just modeling the dirt and rocks. We want a function that will tell us if a given location should be dirt, sand, air, gold, iron, coal, etc... To start with, though, we'll stay simple. We want a function that will tell us if a given block is Solid or Air. This function should simulate the earth around us. That is, sky is above, solid below. So let's undertake the Biblical task of dividing the heavens from the earth. To do so, let's explore the Gradient function. The Gradient function is given a line-segment in N-dimensional space (ie, in whatever coordinate space we are working in, be it 2D, 3D, or higher) and calculates a gradient field aligned along this segment. Input coordinates are projected on this line, and their gradient value is calculated depending where on the line they lie in relation to the endpoints of the defining segment. Points that project to somewhere between the segments are assigned values in the range of (-1,1). So this gives us a good place to start. We can set up a Gradient function aligned along the Y axis. At the top of the range, we'll map the gradient field to -1 (open) and at the bottom we'll map it to 1 (solid).

terraintree=
{
	{name="ground_gradient", type="gradient", x1=0, x2=0, y1=0, y2=1}
}

(A quick note on notation. The example code is written in the form of a Lua table of declarations. See the section on Lua integration for more information on the format. Basically, the format is intended to be parsed by a special class, which reads declarations and turns them into actual trees of noise module instances. I prefer this format rather than a more wordy step-by-step C++ format because it is less verbose and far cleaner. The source is, I think, a little more human readable and concise than C++ code is. For the most part, the declarations should be easy to read and understand. Modules are named, sources are specified either by name or by value, where appropriate. The Lua code used to parse a table declaration is included in the source distribution, if you want to use these declarations directly.)

The Gradient function accepts a line segment in the form of (x1,x2, y1,y2) for the 2D case, extended to (x1,x2, y1,y2, z1,z2) for the 3D case. The point formed by (x1,y1) delineates the start of the line segment, which is mapped to 0. The point formed by (x2,y2) is the end of the line segment that maps to 1. So here we are mapping the line segment (0,1)->(0,0) to the gradient. This sets the gradient to lie between the Y=1 and Y=0 areas of the function. So this band forms the Y extents of the world. Any piece of world we map will lie within this band. We can map any region in X (practically to infinity, though limited by the precision of doubles) that we want, but the interesting stuff, ie the ground surface, will lie within the band. Now, this behavior can be tweaked, but as it stands we have plenty of flexibility. Just remember that any values that lie above or below this band are likely to be uninteresting due to the fact that the ones above will likely be all open, and the ones below will likely be all solid. (As you will see in a short while, this statement may actually prove false. More on that later, though.) For most of the images in this series I'll be mapping the square region defined by the box (0,1)->(1,0) in 2D space. In the beginning, then, our world looks like this:

Doesn't look like much, and it certainly doesn't answer the question of "Is a given point Solid or Open?". In order to answer that question, we have to apply what is called a Step Function. Instead of a smooth gradient, we want a sharp divide where all locations on one side are open, and all locations on the other side are solid. In ANL we can accomplish this with a Select function. A Select function takes two input functions or values (in this case they would equate to Solid and Open) and chooses between them based upon the value of a control function (in this case the Gradient function). The Select module has two additional parameters, threshold and falloff that affect this process. For this step, falloff is not desired, so we set it to 0. The threshold parameter, however, is what decides where the dividing line between Solid and Ground is drawn. Anywhere in the Gradient function that is greater than this value will be Solid, and anywhere that is less than threshold will be open. Since the Gradient maps our range between the values of 0 and 1, then a logical place to put the threshold is at 0.5. This splits the space exactly in half. We are going to denote the value of 1 to be solid, and the value of 0 to be open. So we'll set up our ground plane function as so:

terraintree=
{
	{name="ground_gradient",       type="gradient",       x1=0, x2=0, y1=0, y2=1},
	{name="ground_select",         type="select",         low=0, high=1, threshold=0.5, control="ground_gradient"}
}

Mapping the same region of the function as before, we get something like this:

It certainly does answer the question of "Is a given point Solid or Open?" You can call the function with any possible coordinate in 2D space, and the result will be either 1 or 0, depending on where the point lies in relation to the ground surface. Nevertheless, it's not a very interesting function. just a flat line, extending to infinity. In order to liven it up some, we'll talk about a technique commonly called "turbulence".

Turbulence is a fancy word for the concept of adding values to the input coordinates of a function. Imagine that you call the above ground function with the coordinate (0,1). It lies above the ground plane, since at Y=1 the Gradient is valued at 0, which is less than the threshold, 0.5. So this point would be computed to be Open. But what if, before the ground function was called, that point was transformed somehow? What if we subtracted a random value from the Y coordinate of the point. Say, 3? We subtract 3, resulting in the coordinate (0,-2). Now, if we call the ground function with this point, then the point is evaluated as solid, since Y=-2 lies beyond the end of the Gradient segment that maps to 1. So all of a sudden, instead of being open, the point (0,1) would suddenly be solid. You'd have a chunk of solid rock floating in the air. You can do the same to any point in the function, by adding or subtracting a random number from the Y coordinate of the input point before calling the ground_select function. Here is an image of the ground_select function demonstrating this. Each coordinate location has a value in the range of (-0.25, 0.25) added to the Y coordinate before the ground_select function is called.

That's more interesting than a flat line, but it doesn't really look like ground. This is because each point is perturbed by a completely random value, resulting in a messy, chaotic pattern. However, if we use a continuous random function such as ANL's Fractal function, instead of a messy chaotic pattern we'll get something more controlled. So let's go ahead and hook up a fractal to our ground plane and see what we get.

terraintree=
{
	{name="ground_gradient",          type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="ground_shape_fractal",     type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_scale",             type="scaleoffset",        scale=0.5, offset=0, source="ground_shape_fractal"},
	{name="ground_perturb",           type="translatedomain",    source="ground_gradient", ty="ground_scale"},
	
	{name="ground_select",            type="select",             low=0, high=1, threshold=0.5, control="ground_perturb"}
}

A couple things of note here. First, we set up a Fractal module, and chain it with a ScaleOffset module. The ScaleOffset module will scale the output of the fractal to a more manageable level. Some terrain may be mountainous and require a larger scale, while other terrain is flatter with a lower scale. We'll talk more about different terrain types later, but for now this will serve for demonstration purposes. If we output the function now, we'll get something like this:

Now that's more interesting than the one with pure random noise, isn't it? It's ground-like, at least, even if some of the landscape is a bit weird, and those floating islands are definitely strange. This is a consequence of the fact that every single point in the output map is randomly offset by a different value, determined by the fractal. For illustration purposes, here is an output of the fractal that actually does the distortion:

Anywhere that the above image is black represents -0.25, anywhere that is white represents 0.25. So whereever the fractal is the darkest black, the corresponding point in the ground function is distorted "downward" by 0.25. (0.25 represents 1/4 of the screen.) Since one point might be distorted a little bit, and another point above it in space might be distorted more, this results in the possibility of overhangs and floating islands. Overhangs in nature occur naturally. Floating islands, of course, do not. (Except in Avatar, that is. Science!) If your game wants to have weirdly fantastical landscape like this, then this is great, but if you want a bit more realistic model, then we need to tame the fractal function that provides the distortion a bit. Luckily, the ScaleDomain function provides just such a means.

What we want to do is force the function to behave more like a heightmap function. Imagine a 2D heightmap, where each point in the map represents how high up or down a point in a lattice of grid points is raised or lowered. White values in the map represent high hills, black values represent low valleys. We want a similar behavior, but in order to do so we have to basically eliminate one of the dimensions. See, in the heightmap case, we are creating a 3D terrain out of a 2D heightmap. Similarly, in the case of our 2D terrain, we need to have a 1D heightmap. By forcing all points in the fractal that have the same Y coordinate to evaluate to the same value, then we will offset all points with the same X coordinate by the same amount, thus ensuring that no floating islands will occur. We can use ScaleDomain to do this by setting the scaley factor to 0. Thus, before the ground_shape_fractal function is called, we call ground_scale_y to scale the y coordinate by 0. This ensures that the value of Y has no effect on the output of the fractal, effectively turning it into a 1D noise function. To do this, we make the following change:

terraintree=
{
	{name="ground_gradient",          type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="ground_shape_fractal",     type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_scale",             type="scaleoffset",        scale=0.5, offset=0, source="ground_shape_fractal"},
	{name="ground_scale_y",           type="scaledomain",        source="ground_scale", scaley=0},
	{name="ground_perturb",           type="translatedomain",    source="ground_gradient", ty="ground_scale_y"},
	
	{name="ground_select",            type="select",             low=0, high=1, threshold=0.5, control="ground_perturb"}
}

We chain a ScaleDomain function to ground_scale, then correct the source of ground_perturb to be the ScaleDomain function. This will change the fractal that perturbs the ground from the above image into something like this instead:

Now if we look at the output we can see the result:

Much better. The floating islands are eliminated completely, and the terrain more closely resembles rolling mountains and hills. An unfortunate side-effect of this, however, is the loss of overhangs and cliffs. Now all of the ground is continuous and rolling. There are a number of ways that we can correct this if we so desire.

The first way is to use another TranslateDomain function coupled with another Fractal. If we apply a small amount of fractal turbulence in the X direction, we can perturb the edges and surfaces of the mountains just a little bit, enough to maybe form some cliffs and overhangs. Let's see that in action.

terraintree=
{
	{name="ground_gradient",          type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="ground_shape_fractal",     type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_scale",             type="scaleoffset",        scale=0.5, offset=0, source="ground_shape_fractal"},
	{name="ground_scale_y",           type="scaledomain",        source="ground_scale", scaley=0},
	{name="ground_perturb",           type="translatedomain",    source="ground_gradient", ty="ground_scale_y"},
	{name="ground_overhang_fractal",  type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_overhang_scale",    type="scaleoffset",        source="ground_overhang_fractal", scale=0.2, offset=0},
	{name="ground_overhang_perturb",  type="translatedomain",    source="ground_perturb", tx="ground_overhang_scale"},
	
	{name="ground_select",            type="select",             low=0, high=1, threshold=0.5, control="ground_overhang_perturb"}
}

And the result is:

The second way is just to set the scaley parameter of ground_scale_y to something larger than 0. Leaving a little bit of Y scale in the function will allow some variation, although the higher you set the scale, the more the terrain will come to resemble the earlier, un-scaled version.

The results of these are definitely more interesting than just rolling mountains. However, as interesting as it is, it is still going to get very boring exploring a terrain that is endless miles and miles of this same general pattern. What's more, such a terrain would be very unrealistic. The natural world has plenty of variation to keep things interesting. So let's see what we can do to make the world a little more varied.

Looking at the previous example code, we can sort of see a pattern there. We have the gradient function, which is manipulated by functions to give the ground shape, before the step function is applied and the ground is given solidity. So the natural place to start complicating things in order to add varied terrain is the section that gives the ground shape. Instead of using one fractal to perturb in Y and another to perturb in X, we can get as complicated as we like (and as we can afford, of course; each fractal adds processing overhead, so you should only use as many as you really need, and try to be conservative.) We can set up ground shapes representing mountains, foothills, lowland plains, badlands, etc... and use the output of various Select functions, chained to low-frequency fractals, to delineate regions of each type. So, let's take a look at how we might implement some various types of terrain.

For the sake of illustration, we'll device three types of terrain: highlands (gently rolling hills), mountains, and lowlands (mostly flat). We'll use a select-based system to switch between them, and stitch them all into a complex tapestry. And we're off...

Lowlands:

This one is easy. We can use the setup from above, lower the amplitude of the hills a bit, maybe even make them more subtractive than additive to bring the average elevation down. We'll probably lower the octave count to make them smoother as well.

{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=1},
{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.2, offset=-0.25},
{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},

Highlands:

Again, easy. (Actually, none of these are really all that hard.) We'll use a different basis, though, to make the hills dune-like.

{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=2},
{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=0, high=1},
{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.45, offset=0},
{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

Mountains:

{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=1},
{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=0, high=1},
{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.75, offset=0.25},
{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.1},
{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

Of course, you can get more creative than this, but this establishes the general pattern. You think about the characteristics of the terrain, and construct your noise functions to suit. All of these operate on the same principles; the differences are mostly in scale. Now, to tie them all together, we'll set up some additional fractals to act as controls to Select. Then we'll chain the Select modules together to generate the whole.

{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.5},
{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
{name="terrain_type_cache",            type="cache",            source="terrain_autocorrect"},
{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.15},
{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},

So here we're setting up three main types for lowlands, highlands and mountains. We use one fractal to select between all three, so that there is a natural progression from lowlands->highlands->mountains. Then we use another fractal to randomly insert badlands into the map. The final module chain is:

terraintree=
{
	{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=1},
	{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
	{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.2, offset=-0.25},
	{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
	{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},
	{name="ground_gradient",               type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=2},
	{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=0, high=1},
	{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.45, offset=0},
	{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
	{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

	{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=1},
	{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=0, high=1},
	{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.75, offset=0.25},
	{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.1},
	{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

	{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.5},
	{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
	{name="terrain_type_cache",            type="cache",            source="terrain_autocorrect"},
	{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.15},
	{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
	{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select"}
}

Here are a few random panoramic shots of the kinds of terrain this will produce:

You can see that there is a pretty good variation there. Some places have towering, jagged mountains, while other places have gently rolling flats. Now, we want to add caves to the mix, to explore the wonders beneath the ground.

For caves, I use a multiplicative system applied against ground_select. That is, I come up with a function that outputs 1 or 0, and multiply it with the output of ground_select. This has the effect of setting to Open any location in the function that is 0 in the cave function. So anywhere I want a cave to appear must return 0 in cave function, anywhere I want it to be not a cave I set to 1. As far as the shape of the caves, I like to base the cave system on a 1-octave Ridged Multifractal .

{name="cave_shape",               type="fractal",                fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=2},

This results in something like:

If you apply a Select function as a step function, just as we do with the ground gradient, making it so that the low-side of the threshold selects to 1 (no cave) and the high-side selects to 0 (cave), then the result looks something like this:

{name="cave_shape",               type="fractal",                fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=2},
{name="cave_select",              type="select",                 low=1, high=0, control="cave_shape", threshold=0.8, falloff=0},

The result:

Of course, that looks fairly smooth, so let's add some fractal noise to perturb the domain a little bit.

{name="cave_shape",               type="fractal",                fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=2},
{name="cave_select",              type="select",                 low=1, high=0, control="cave_shape", threshold=0.8, falloff=0},
{name="cave_perturb_fractal",     type="fractal",                fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
{name="cave_perturb_scale",       type="scaleoffset",            source="cave_perturb_fractal", scale=0.25, offset=0},
{name="cave_perturb",             type="translatedomain",        source="cave_select", tx="cave_perturb_scale"},

The result:

So that noisifies the caves a little bit, and makes them not so smooth. Let's see what it might look like if we apply the caves to the terrain now:

By playing with the value for threshold in cave_select, we can make the caves thinner or thicker. But one thing we really ought to do is try to make it so that the caves don't gouge out such huge, ungodly chunks from the surface terrain. To do that, we can go back to the highland_lowland_select function which, you'll remember, is the final terrain function used to perturb the ground gradient. What is useful about this function here is that it is still a gradient, that increases in value as the function goes deeper into the earth. We can use this gradient to attenuate the cave function, so that the caves get bigger as you go deeper into the earth. Lucky for us, this attenuation can be performed simply by multiplying the output of the highland_lowland_select function with the output of cave_shape, then pass the result along to the rest of the cave function chain. Now, one important change we are going to make here is the addition of a Cache function. The cache function will store the result of a function for a given input coordinate, and if the function is called again with the same coordinate, it will return the cached copy rather than re-computing the result. This is useful for situations like this, where one complex function (highland_lowland_select) will be called more than once during a module chain. Without the cache, the entire chain of the complex function is recomputed every time it is called. To introduce the cache, we first make these changes:

{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
{name="highland_lowland_select_cache", type="cache",            source="highland_lowland_select"},
{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select_cache"},

This attaches the Cache, then re-directed the input of ground_select to come from the cache, rather than directly from the function. Then we can modify the cave code to add the attenuation:

{name="cave_shape",                    type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
{name="cave_attenuate_bias",           type="bias",              source="highland_lowland_select_cache", bias=0.45},
{name="cave_shape_attenuate",          type="combiner",          operation=anl.MULT, source_0="cave_shape", source_1="cave_attenuate_bias"},
{name="cave_perturb_fractal",          type="fractal",           fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
{name="cave_perturb_scale",            type="scaleoffset",       source="cave_perturb_fractal", scale=0.5, offset=0},
{name="cave_perturb",                  type="translatedomain",   source="cave_shape_attenuate", tx="cave_perturb_scale"},
{name="cave_select",                   type="select",            low=1, high=0, control="cave_perturb", threshold=0.48, falloff=0},

We added a Bias function first of all. This is for convenience sake, allowing us to tweak the range of the gradient attenuation function. We then added the cave_shape_attenuate function which is a Combiner of type anl::MULT. This multiplies the gradient by the cave_shape. The result of this is then handed off to the cave_perturb function. The result looks something like this:

You can see that the caves are made thinner in areas toward the ground surface. (Ignore the stuff at the very top, it's just an artifact of the gradient going negative, and has no effect on the final caves. If it becomes a problem--say, if you use this function for something else, then the gradient can be clamped to (0,1) before being used.) It's a little difficult to see how this works in relation to the terrain, so let's go ahead and composite everything together and see what we get. Here is our entire function chain so far.

terraintree=
{
	{name="ground_gradient",               type="gradient",         x1=0, x2=0, y1=0, y2=1},
	
	{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=0.25},
	{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
	{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.125, offset=-0.45},
	{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
	{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},
	
	{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=2},
	{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=-1, high=1},
	{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.25, offset=0},
	{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
	{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

	{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=8, frequency=1},
	{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=-1, high=1},
	{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.45, offset=0.15},
	{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.25},
	{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

	{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.125},
	{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
	{name="terrain_type_y_scale",          type="scaledomain",      source="terrain_autocorrect", scaley=0},
	{name="terrain_type_cache",            type="cache",            source="terrain_type_y_scale"},
	{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.2},
	{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
	{name="highland_lowland_select_cache", type="cache",            source="highland_lowland_select"},
	{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select_cache"},
	
	{name="cave_shape",                    type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
	{name="cave_attenuate_bias",           type="bias",              source="highland_lowland_select_cache", bias=0.45},
	{name="cave_shape_attenuate",          type="combiner",          operation=anl.MULT, source_0="cave_shape", source_1="cave_attenuate_bias"},
	{name="cave_perturb_fractal",          type="fractal",           fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
	{name="cave_perturb_scale",            type="scaleoffset",       source="cave_perturb_fractal", scale=0.5, offset=0},
	{name="cave_perturb",                  type="translatedomain",   source="cave_shape_attenuate", tx="cave_perturb_scale"},
	{name="cave_select",                   type="select",            low=1, high=0, control="cave_perturb", threshold=0.48, falloff=0},
	
	{name="ground_cave_multiply",          type="combiner",          operation=anl.MULT, source_0="cave_select", source_1="ground_select"}
}

Here is a selection of randomized locations from this function:

Now that looks pretty good. The caves are all fairly large caverns deep below ground, but at the surface they tend to attenuate to small tunnels. This is helpful in creating an air of mystery. While you are out exploring the land, you come across a small cave entrance. Where does it go? How deep does it extend? No way of saying, but as you explore, it begins to widen out into a vast expanse of caverns, filled with darkness and danger. And loot, of course. Always the loot.

There are a whole bunch of ways you can tweak this to get different results. You can modify the threshold settings for cave_select and the settings for cave_attenuate_bias, or change cave_attenuate_bias to a different function to remap the range of the gradient to better suit your needs. You can add another fractal that perturbs the cave system in the Y-axis, to eliminate the occasional appearance of unnatural smooth tunnels in the X direction (caused by perturbing the cave shape only in X). You can add another fractal as another attenuation source, set as a third source to cave_shape_attenuate that scales the attenuation on a regional basis, making it so that caves appear more densely in some areas (say, mountains perhaps) and less densely or not at all in others. This regional selecter would derive from the terrain_type_fractal function to know where the regions of mountains are. It all just comes down to thinking about what you want, understanding what effect the various functions will have on the output, and experimenting with the various parameters until you get something you like. It's not a perfect science, and there are often many ways you can accomplish any given effect.

Drawbacks

There are drawbacks to this method of terrain generation. Generating noise can be fairly slow. It is important to reduce the number of fractals, the octave count of the fractals you do use, and other slow operations as much as possible. Try to re-use fractals when you can, and cache every function that is called more than once. In this example, I was pretty liberal with the use of fractals, providing a separate one for each of the three terrain types. By using ScaleOffset to remap ranges and basing them all on a single fractal, I could have saved myself a lot of processing time. In 2D it's not so bad, but when you start getting into 3D, and trying to map volumes of data, the time really adds up.

Expanding to 3D

Now, this is all great if you are making a game like Terraria or King Arthur's Gold, but what if you want to make a game like Minecraft or Infiniminer instead? What changes do we have to make to the function chain? The answer is "not much." The above function chain will work pretty much right out of the box for a 3D terrain. All you have to do is map a 3D volume, using the 3D variants of the generator and mapping the Y axis to the vertical axis of the volume, instead of a 2D region. There is, however, one change required, and that is to the way that caves work. You see, the Ridged Multifractal works great for a 2D cave system, but in 3D it carves a series of curved shells rather than tunnels, and the effect just isn't right. So in 3D, it becomes necessary to set up 2 cave shape fractals, both of 1-octave Ridged Multifractal noise but with different seeds, Select them to 1 or 0, and multiply them together. This way, wherever the fractals intersect becomes cave, the rest remains non-cave, and the appearance of tunnels is more natural than when using a single fractal.

terraintree3d=
{
	{name="ground_gradient",               type="gradient",         x1=0, x2=0, y1=0, y2=1},
	
	{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=0.25},
	{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
	{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.125, offset=-0.45},
	{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
	{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},
	
	{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=2},
	{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=-1, high=1},
	{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.25, offset=0},
	{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
	{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

	{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=8, frequency=1},
	{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=-1, high=1},
	{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.45, offset=0.15},
	{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.25},
	{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

	{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.125},
	{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
	{name="terrain_type_y_scale",          type="scaledomain",      source="terrain_autocorrect", scaley=0},
	{name="terrain_type_cache",            type="cache",            source="terrain_type_y_scale"},
	{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.2},
	{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
	{name="highland_lowland_select_cache", type="cache",            source="highland_lowland_select"},
	{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select_cache"},
	
	{name="cave_attenuate_bias",           type="bias",              source="highland_lowland_select_cache", bias=0.45},
	{name="cave_shape1",                   type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
	{name="cave_shape2",                   type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
	{name="cave_shape_attenuate",         type="combiner",           operation=anl.MULT, source_0="cave_shape1", source_1="cave_attenuate_bias", source_2="cave_shape2"},             
	{name="cave_perturb_fractal",          type="fractal",           fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
	{name="cave_perturb_scale",            type="scaleoffset",       source="cave_perturb_fractal", scale=0.5, offset=0},
	{name="cave_perturb",                  type="translatedomain",   source="cave_shape_attenuate", tx="cave_perturb_scale"},
	{name="cave_select",                   type="select",            low=1, high=0, control="cave_perturb", threshold=0.48, falloff=0},
	
	{name="ground_cave_multiply",          type="combiner",          operation=anl.MULT, source_0="cave_select", source_1="ground_select"}
}

Some results:

Now, it looks like a few of the parameters would need some tweaking. Maybe reduce the attenuation, or thicken the caves, reduce the number of octaves in the terrain fractals to make smoother terrain, etc... Again, that is all dependent upon what you want to achieve.

All content on page copyright 2011 Joshua Tippetts