Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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: enter image description here

share|improve this question
2  
Take a look here, and scroll down. –  William 'MindWorX' Mariager Aug 5 '12 at 14:24
    
There's a game developer magazine issue within the past 24 months that has in depth discussion on how to do what you're trying to do. I would hit their site. –  Joey Green Aug 7 '12 at 21:16
    
@JoeyGreen What's the name of the magazine? Or do you have a link to their site? –  jumpnett Aug 11 '12 at 0:39
1  
It's called game developer magazine. gdmag.com. You can get a subscription and get pdf versions of the magazine for the last 10+ years. If you sign up, there is a way to search through previous issues and find the issue you want. –  Joey Green Aug 11 '12 at 0:46

5 Answers 5

up vote 23 down vote accepted

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.

Gnomescroll Cave System First Person View 1

Gnomescroll Cave System First Person View 2

Gnomescroll Cave System Third Person View 2

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

Linoise Tutorial Perlin Worms

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.

share|improve this answer
3  
Can you add some information or resources to learn about this "perlin worms" thing? –  David Gouveia Aug 7 '12 at 20:59
1  
This is a tutorial on "perlin worms" libnoise.sourceforge.net/examples/worms/index.html –  HaltingState Aug 8 '12 at 15:04
    
Not necessary, but if you could elaborate on that last paragraph, I'd greatly appreciate it. To generate a worm, I'd assume you'd need a starting point per worm, which would need to be within N chunks of any player where N is the max length of a worm. –  Tim Winter Aug 14 '12 at 15:27
2  
Exactly. Each worm has a starting point and is terminated if it wanders outside of certain chunk radius. There is a random number generator which deterministicly generates a pseudo random number sequence which is a function of the chunk coordinates. These random numbers determine where and how many worms originate in that node. Worms can also branch. The computational burden is decreased if the worms are more "local" and cannot venture more than a small chunk radius. –  HaltingState Aug 15 '12 at 6:44
    
Maybe not exactly what I wanted to hear, but what I was expecting. Thanks again HaltingState. :) –  Tim Winter Aug 15 '12 at 11:55

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.

share|improve this answer

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).

share|improve this answer
    
I may just not understand exactly what you mean by this, but how would I do this on the fly chunk by chunk as the world generates? –  Tim Winter Aug 5 '12 at 21:23
    
One possible way is to generate the minimum spanning tree within each chunk separately, then connect each chunk by finding the closest two nodes between the two chunks. After a chunk is filled in with your default terrain algorithm, you could hollow it out around the minimum spanning tree. –  Gavan Woolery Aug 5 '12 at 22:58
1  
another (easier) solution, although less efficient and probably "noisier", is to use brownian motion to carve out a path (kind of like an ant digging around randomly). –  Gavan Woolery Aug 5 '12 at 23:00

http://gdmag.com/issue/2011/April goes into detail on this with iterative perlin noise functiosn

share|improve this answer
    
They show screenshots for each step(function) and show variations –  quantumpotato Aug 7 '12 at 22:59

here is

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.