If you want to lose a few weeks hacking away at something kind of fun, then turn around and try to implement the Fortune's Algorithm[1] Voronoi region/Delauney Triangulation method that underlies Amit's map generator.
Somewhere I have a WinForms app I built a while back that animates the process and draws everything out step by step.
This is actually what I did in my first internship -- generating Delaunay triangulations (or more often, tetrahedralizations) of points, and then adjusting the underlying sets of points to help ensure that the corresponding Voronoi cells have good properties (generally reasonable surface area to volume ratios).
We didn't use Fortune's for historical reasons (the first versions of the code were in Fortran 77, and written well before he published his paper). Instead we generated triangulations and then flipped edges until they were Delaunay, and then used the corresponding Voronoi diagram. It turns out that flipping edges to produce a nicer triangulation is reasonable in two dimensions, but intractable in 3D and up.
