The one in the vid is 3d, so your options here are somewhat limited.
While it should be possible to do those kind of curves, the likelihood of it having a good frame rate are slim.
Then a tile based solution could only have hills, and or caves of a specific size, or grade, but you could have a few different types to mix, and match.
You wouldn't figure out the whole map, best bet would be to take a seeded random and interpolate the noise to create a curve.