Generating random interlocking regions (i.e. countries)

(Reposted and updated from here, as it turns out my question did not strictly have to do with Mathematica.)

I am trying to subdivide a finite portion of the plane into a set of at least 20 or so random interlocking shapes, with the shape boundaries having a fractal dimension around that of borders between countries that aren't simply straight lines (which I crudely estimate to be 1.15 ± 0.1, based upon visual inspection of Wikipedia's list of fractals by Hausdorff dimension). Preferably, the plane would have toroidal boundary conditions, although generating another single country-like shape to serve as the overall boundary would also be acceptable. (As I found out, this question does not strictly have to do with any language in particular, so I am looking for a general algorithm, or at least something to get me started in the right direction.)

Running Kruskal's algorithm for maze generation on a torus (and keeping only the boundary) gives about the right fractal dimension, but that only creates one shape that tiles the plane by translation. Running several instances of the DFS algorithm at once (again, keeping only the boundaries between the various sub-mazes) generates highly unrealistic narrow portions. (Additionally, in both cases, the result is made of tiny discrete units, which isn't a problem for high enough resolutions, and may simplify things somewhat). Using a Delauney triangulation is an excellent method to make a graph representing a system of countries, but its corresponding Voronoi diagram makes for perfectly straight borders.

(unfortunately cannot post images at this time due to lack of reputation on this particular Stack Exchange site, but they're in the link)

---

As an update from the original post, I have found a suitable method to create a single country-like shape using the Life-like cellular automaton B5678/S45678 (Majority). It proceeds as follows (in case this gives anyone any ideas):

1. Start with a small filled random shape (easy enough to do by running until stabilization a small 2D array of random bits in the aforementioned rule).
2. Replace every element of the array with a 2×2 block of that element.
3. Expand the array by adding a suitable margin of 0s around the outside. (This step may not always be necessary.)
4. Randomly toggle about 25% of all cells in the array, to induce a perturbation.
5. Run the array in the aforementioned rule until stabilization.
6. Repeat steps 2-5 until desired size is achieved.