3d - How to generate caves that resemble those of Minecraft?

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

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.