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: