xna - Terrain Generation for Tile-Based 2D Platformer

I'm currently working on a tile-based 2D platformer similar to Terraria in some ways, although I'm having difficulty with the terrain generation. I have some basics done, although they do not come out as anything useful.

I have tried a few different techniques like Perlin Noise and read about some others such as Midpoint Displacement, although I'm not sure what one would be best, or a combination of different techniques to generate different areas. (Such as Midpoint Displacement for the general shape of the terrain and Perlin Noise for the caves.)

I have found an excellent explanation of how I could layer it up with the Accidental Noise Library, although it is in C++, and I do not know enough C++ to compile it into a DLL that I can use from C#. I have tried to copy this in C#, although, I do not know how I can merge two effects together (the gradient for the general base, and then the fractal for detail).

Currently I am using a Plasma Fractal and the results are extremely varied. For example it can generate terrain where there is hardly any surface, or it can generate terrain where there is no surface at all.

An example of an okay map, would be better with some more improvements, though. (Black is solid, white is air):

And an example of a terrible map. (Black is solid, white is air):

Basically, what I'm asking is, what would be a better way of generating the terrain, or forcing it to make sure that there is a reasonable amount of surface area, with the generation time as quick as possible. Or, alternatively, how I would be able to achieve the same result as the Accidental Noise Library, but in C#.

Any examples would be very much appreciated.

Answer

I would try sticking with Perlin noise, but adding a weight to it based on height, to ensure a certain average density at certain altitudes. To quote part of Notch's post on Minecraft terrain generation:

So I switched the system over into a similar system based off 3D Perlin noise. Instead of sampling the “ground height”, I treated the noise value as the “density”, where anything lower than 0 would be air, and anything higher than or equal to 0 would be ground. To make sure the bottom layer is solid and the top isn’t, I just add the height (offset by the water level) to the sampled result.

Essentially, you're taking a little slice of a Minecraft terrain. So generate 2D Perlin noise, but weight it so that anything above a certain point is likely to be air, and anything below a certain point is likely to be earth.

This will give you a good ground terrain, with some overhangs and interesting features, as well as some caves and floating islands. (If you don't want floating islands, you can test for them and remove them manually.) This method won't give you things like tunnels, so you'll want a method for adding those in after terrain generation, such as a random-walk.