Midpoint displacement is simple & I've used it in my game with success. So when you say 2D, are you talking about a vector shape terrain, or tiles, or what?

In any case, midpoint displacement is a recursive algorithm, where you initially pass it two points - left & right most, with preset heights.

Then:

1) Find the middle point between the two points

2) Give middle point a height which is the average of the left & right points, plus/minus a random amount - this random amount should tend towards zero the smaller the X gap between the two points. The max randomness value will govern how rough your terrain will be.

3) Pass the left & middle points back into this algorithm

4) Pass the middle & right points back into this algorithm

You will then have a fractal looking terrain. You probably want to stop recursing once the gap between the two points is less than e.g. 10 pixels.

Tiles actually makes things easier. I'm assuming when you say platformer you mean a side scroller. What you'll want is an array of heights at each tile position along the X axis of your gameworld. You fill in the first and the last heights with whatever random / predetermined values you want. Then pass pointers / indexes of those array positions into the mid-point algorithm, which should stop recursing when the left point is right next to the right point.

If you have tiles, then you probably have integer height values.

Hope that helps.

As far as I know midpoint displacement does not help with the caves ... there is an article with some more text: http://www.gameprogrammer.com/fractal.html

You will probably have to combine several algorithms to get the result you want.

Midpoint displacement can be used to create the base terrain ... then, for example, cellular automata to create caves inside that terrain!?

This is an art rather than a skill, meaning that learning to think the right way is more important than finding the right tutorial.

You should feed Google with those algorithms (http://pcg.wikidot.com/category-pcg-algorithms), pick the ones that inspire you and do simple things with them.

If you have a hard time coming up with a data structure and algorithms for populating a game world, maybe you should work on those basics some more ... for example with some Code Jam exercises.

Argh I didn't see the reference to Terraria! As DareDeveloper says, mid-point would only be useful for generating the surface terrain. You could use mid-point to generate a 2D grid (use 4 x/y points, find the middle, then recurse for top left, top right, bottom left & bottom right squares), but honestly I think fractal generation is probably overkill for your needs.

A simple random up slope / down slope / level with hard upper & lower height limits will generate a terrain with similar properties, and as DareDeveloper points out, there are simple algorithms to generate caves too.