Cellular Automata rule sets are quite useful for building cave-like systems.

1. Fill a bitmap with random black and white dots. Black represents filled space, white represents open space.
2. Iterate through the bitmap, applying the CA rules to each pixel
3. create the updated bitmap
4. cycle back to step 2, repeat until desired result

The following is the series, from random noise all the way to a completed cave system. Each image is 64×64, though it can easily be scaled up to any arbitrary size. I have found that images at 256×256 and above tend to bog down somewhat, so be careful.

Once you have tweaked the algorithms to get the desired cave design, you may have more than one disconnected piece. There are three ways you can re-connect those pieces to the cave system

1. go through and eliminate all but the largest open area
   – This might result in a quite small cave, so some experimentation here might be necessary, such as setting an arbitrary number of pixels or percentage of overall area as the minimum allowed cave size
2. draw tunnels to connect the pieces
   – either find the center point of each piece, and draw a tunnel from point A to point B, or iterate through each point in each open area, find there they are closest together, and connect those points
3. in multilevel games, connect to the next level(s) up and down. A cave needn’t be only one level.
   – this assumes that the same issue does not exist in the next level up and/or down. An unfortunate selection of initial starting conditions could result in two “silo” caves next to each other, with few or no connection points.

There will be some back and forth between tweaking the algorithm and deciding what makes for the best caves. You can add logic to sometimes eliminate extra rooms, sometimes connect them, and sometimes connect them to the next level.

Of course, you don’t necessarily need to create all of the levels at load time. You can create them on the fly – though this does make vertical connections more difficult. Do some experimenting; see which method works best for you. I suggest always having at least two lower levels created, to reduce potential conflicts when fleshing out the current level.