Perhaps the simplest option would be just working in voxel space, such as what Minecraft does. MC uses quantized, interpolated, multi-dimensional fractal noise maps to define elevation and biome, for example. I see noise maps used in many different experimental terrain engines; it's a strong technique.
Another option is using Voronoi cells to define biome areas. Multiple adjacent cells could be joined together to provide large biome cells with interesting borders.
For the gameplay I want, however, a one-size-fits all approach would be hard to work. I'd like to play with borders between biomes, put unique cells in the middle of (eg) a forest biome, and some other stuff. Mostly, I came across a hierarchical algorithm and figured it could provide a lot of interesting options.
So let's take a look at that image. The first step of the algorithm is to define a 7-hex island surrounded by ocean. The blue hex is 'water', and the other three types are plains, forest, and mountain. The idea is that I can decide the layout of these biome types before I go in and pick a particular subtype of forest, such as pine / oak / blooming / autumn / ghostly / etc. That's what step 2 does: in this case, the water node is just converted to ocean (had it been in the center, it would have become a lake). The plains, mountains, and forest are actually converted to subtypes here, but you can't tell because the colors are the same -- I'll explore this more in later posts, but for now the think to note is the subsequent steps.
Step 3 takes the 5x5 grid of hexes and magnifies it to a 20x20 grid. The magnification isn't strictly 1:16, however; some sub-hexes are halfway within one parent and halfway within another, and I use a random-number generator to decide which one they take after. In this image, steps 1, 2, and 3 are all from the same seed, so you can see how the magnification process starts to break up the regular look of the first level.
The four images on the bottom-right are created from different island seeds, showing how a huge variety of island types and shapes are possible.
Not pictured: the algorithm proceeds further: step 4 is another cleanup step, step 5 is a second magnification step, then step 6 is cleanup again. Step 7 figures out elevations for everything, step 8 adds rainfall, lakes, & rivers, then step 9 converts the whole thing into voxels.
