How to generate caves that resemble those of Minecraft?

Question

I've been working on a 3D procedural world for a while now and am wanting to start adding cave systems. I'm currently using 2D/3D Perlin Noise for the terrain generation in combination with Marching Cubes for smoother terrain. I'm just getting stumped when it comes to long interconnecting caves.

I'm hoping to get something more like Minecraft's cave systems. They seem to be very connected, branch off randomly in nearly any direction, and nearly any point in the cave would have a fairly circular look with a fairly equal radius throughout (not the best wording, but not quite sure how else to put it).

The biggest challenge for generating caves like I'm wanting is that I want to generate the world on the fly. The world is generated chunk by chunk currently, starting where the player is and it generates outwards from there. I would NOT want to generate any of the world and then dig the caves out using a wandering pattern, cellular automata, etc.

Are there any well known algorithms that can be used for this? If so, does anyone want to share how they do something similar? I'd greatly appreciate any help.

A good example:

Answer 1

Minecraft's caves are generated by "perlin worms" method. The generator snakes through terrain and caves out a tunnel. Minecraft does not use 3d perlin noise for cave generation, because it tends to leave unconnected pockets in the terrain. Minecraft caves have not been generated through 3d Perlin noise since very early Alpha versions.

Here are caves in Gnomescroll generated from the "perlin worm" method.

These are the libnoise "Perlin Worms" from the libnoise tutorial. The technique closely reproduces the caves generated in Minecraft.

The snaking parameters affects the quality of the cave system and determine how vertical the caves are and how fast they change direction. Caves in minecraft branch and the radius of the cave tunnel is varied over the length of the caves.

Minecraft generates the caves on a chunk by chunk basis. The approach required is complicated and no one has perfectly reverse engineered Minecraft's cave generator yet, despite interest by server modders.

The most likely approach generates the snaking caves chunk by chunk as the infinite map is generated and expands outward. The caves on the current chunk are functions of the cave seeds on the closest N chunks for some N. Using a random number generator which is a function of chunk coordinates to seed the caves it is possible to compute the caves on the current chunk for an infinite map while only evaluating the chunks within a finite chunk radius.

Answer 2

I would generate a cloud of points inside areas where the terrain is solid - you can experiment with different densities. Then I would use an algorithm like a minimum spanning tree to connect all of the points - this will ensure that every area is reachable. Then simply draw big hollow (composed of air) areas from node to node (i.e. a thick line of voxels).

Answer 3

Game Developer Magazine's April 2011 issue goes into detail on this with iterative Perlin noise functions - see the Creator of Worlds article starting on page 21.

Answer 4

Use a noise function to assign values for every chunk to determine if it has tunnels or not and then use them to decide where to place caves. If you want tunnels, simply use more noise functions (with different seeds) and use their values to determine if there are tunnels. After that, use ordinary "drawing" functions to create the tunnels. To make everything more realistic, use more noise to do random displacement for origin points of said caves/tunnels.

If you don't want to use multiple noise functions, you can probe at bigger distances - for example, rather than do noise3d(2,2,2) for chunk at (2,2,2) do noise3d(2,2,16) and use (2,2,16) for one value, (2,2,17) for second value, etc.... then just tune your frequency accordingly to either make all the values independent or correlated at short scales.

To vary cave density thorough the world, use another, lower frequency function that will influence said values.

In case this results in messy caves, simply increase distance of said interconnected points or otherwise tune the algorithm.

I'm not sure if Minecraft does caves like this(although I think it does), but this solution should yield satisfactory results.

Answer 5

Although most caves such as the ones above use Perlin worm, some people would rather do it manually. This way they can make it the way they want it exactly block for block. A cave made by using Perlin worm can be inaccurate and may only make the cave 5 foot high and 6 foot wide, this can be inaccurate as you might want it 10 foot high and 15 foot wide.