algorithm - How can I generate Worms-style terrain?

I'm working on a Worms-styled game and want to generate some terrain procedurally. I've previously done a lot of terrain generation using perlin noise, and this is what I started out using for this game. The only problem with it is that it's too simple and boring, giving me some hills but not the complexity I want. I'd like to have features like caves and hanging mountains and I don't mind floating islands and such. Something like this, but even crazier would be ok:

I thought of first generating the terrain using classic perlin noise, then just removing parts to create caves and what not, but I'm having trouble guiding the removal of those parts. Are there any alternatives to generating such a terrain?

Answer

I'd suggest you start with 2D Perlin-noise. Something like this:

Then apply a threshold on the image, so that you get several isolated islands, as shown here:

I chose a threshold of 0.04, everything above the threshold would be colored blue. The rest remaining black. Then after that, it's time to determine which "islands" to keep and which to throw away.

A possible approach would be to run through the image from left to right at various heights and select intersecting "islands" given a certain probability. In the example picture, the lowest line has a probability of 100%, so every island it crosses will be selected (filled white). The second line has a probability of 50% and the topmost line has a probability of 10%.

Once you have your islands marked like that, you can close the gaps in between by applying a morphological operation (dilate)

And there's a possible landscape.

The "granularity" of the noise is going to determine how small the details in your world are going to be. So it's probably best to experiment with these values.

Also where and with what probabilities your "selecting-lines" are positioned, the result is going to be vastly different. If you have a line near the top of the image with high probability to "select" an island, then you can build some sort of cave-landscape, etc.