The idea I had was to represent a unit or chunk of terrain not as a rigidly square tile, but as a arbitrarily random-ish, roundish "splat" of terrain that occupies not a fixed location in the game world, but a general area. Meaning that instead of placing the "tile" at, say, (14,26) and having it line up exactly with its neighbors, instead I throw it somewhere in the vicinity of (14,26), with a bit of random perturbation. The splats are built overlarge, with softly blending edges so that they blend with their neighbors, rather than matching edges. This, of course, poses some constraints upon the tiles. The technique seems to work best with natural textures: water, dirt, etc...
By providing an arbitrarily large set of splats per terrain type, I can take long steps toward eliminating any obvious repetition, and by obviating the need for rigidly constrained terrain transition tiles that line up on cell boundaries and that make the grid-based nature of the world all too painfully obvious, I free up storage space for more variants. In effect, there are no special-case tiles.
The idea is still in the fermentation and experimentation stage. I'm sure someone has done something like it. Here is a quick mock-up example of what I'm talking about:
The splats (water, sand/dirt, and dirt; in practice, these have alpha transparency for smooth blending):
The first step in creating an island is to splat down some water:
Then "trace" the perimeter of the island in sand/dirt blend tiles. (plain sand tiles also work, of course)
Then block in the middle of the island with dirt splats:
This example used only 1 variant of each type, so there repeat shapes. I have tested the method using pre-built splat maps in the Archipelago game, and it works surprisingly well. The basis of an Archipelago map is a hash-map of buckets, where each bucket is a list of sprites/splats/objects. So only buckets that end up with something inserted into them actually have any real existence in memory, creating in effect a sparse map.
The method works well with editor-built maps, and I am in the process of defining the constraints within which I have to operate for the purposes of randomly generating the islands using splatting.
This splatting technique lends itself very well to procedural generation; the above splats were generated procedurally using the Accidental noise library I've been working on.
Of course, this sort of hap-hazard splatting doesn't work very well for some cases, such as artificial (man-made) environments. However, for the natural areas it seems to be working fairly well.
Update:
Here is a shot of TestGuy running around a randomly generated island.
The biggest problem I see with this technique is the massive amounts of overdraw, but considering the relative simplicity of the maps, I still have plenty of framerate to spare, and I can do some pre-processing on solid areas to remove the underlying layers to help the problem a bit.
