procedural generation - How do I make a natural-looking map from some Voronoi regions?

I'm using Voronoi regions to create a map for my game, much like this. However, the lines are too straight and perfect. How do I make the borders more natural looking? As in, less like US state borders and more like international borders in Europe or Asia.

Answer

Simply add smooth noise in the form of waves of different amplitudes and frequencies. You would need to add more vertices and split these edges. You could use a noise map to compute nice looking points based on the original edges at random.

Here is some working code:

/*****************************************************************************
 * Artur Wulf White - 18/1/14
 *****************************************************************************/



kernel Pres3D
<   namespace : "AWW37";
    vendor : "Arthur";

    version : 1;
    description : "Add noise to map"; >
{
    input image4 src;
    input image4 src2; // some smooth random colorful noise
    output float4 dst;

    parameter float4 coeffx;
    parameter float4 coeffy;


    void
    evaluatePixel()
    {
        const float2 imgSize = float2(512.0, 512.0);

        float2 c2D = (outCoord() / imgSize) - float2(0.5, 0.5);

        float4 tmp = sampleLinear(src2, outCoord());
        c2D.x += tmp.x * coeffx.x + tmp.y * coeffx.y + tmp.z * coeffx.z + tmp.w * coeffx.w;
        c2D.y += tmp.x * coeffy.x + tmp.y * coeffy.y + tmp.z * coeffy.z + tmp.w * coeffy.w;

        if(outCoord().x < imgSize.x && outCoord().y < imgSize.y){
            dst = sampleLinear(src, (c2D + float2(0.5, 0.5)) * imgSize);
        } else{
            dst = float4(0.0, 0.0, 0.0, 0.0);
        }

    }
}

And the result:

I used Pixel Bender for prototyping quickly. Can be re-written in another language.