Generate Realistic Maps I drew this map of the regions of an imaginary word in a few minutes in MS Paint:

I think that being able to generate maps like this programmatically would be really cool.
Challenge
Write a program that takes in positive integers W and H, and a non-empty set of positive integers S.
Generate a standard true color image that is W pixels wide by H pixels tall.
For each integer i in S, draw a planar region in the image whose area in pixels is proportional to i, using a color different from any neighboring regions. Specifically, the number of pixels in the region should be W * H * i / sum(S), rounded either up or down to ensure that every pixel in the image belongs to a region.
A planar region is a set of pixels with the property that any pixel in the region can be reached from any other by staying within the region and only moving orthogonally (and not diagonally). My map above has 10 planar regions.
All the pixels in a planar region must be the same color, which must be different than the color of any neighboring regions. Regions may be the same color if they are not neighbors.
Otherwise, there are no limitations on how you shape, position, or color your regions. This is a popularity-contest. The goal is to create a program that makes realistic maps of imaginary worlds, physical or political, with any geography, at any scale.
Naturally, please show off your best output images, not just your code.
Details

Take input from file, command line, stdin, or similar. Save the image in any standard format or display it to the screen.
Your program should be deterministic for identical inputs. That is, the output image should always be the same for some particular H, W, and S. (Note that S is a set, not a list, so its ordering doesn't matter.) Otherwise you may employ randomness where desired, though you are not required to (but I highly suggest it).
The output image geography does not need to &quot;scale&quot; for different values of W or H (though it could). It may be completely different.
You may randomly assign colors, disregarding the neighbor-color rule, as long as there at least 32 random color possibilities, since it would be unlikely for two neighbors to get colored the same.
The regions stop at the image boundaries. There is no wrap around.
Regions may contain zero pixels (and thus be nonexistent), as would be the case when there are more regions than pixels.

Example Input
A valid submission might have generated my map above with the parameters:
W = 380
H = 260
S = {233, 420, 1300, 3511, 4772, 5089, 9507, 22107, 25117, 26744}

These S values are the exact same as the number of pixels in each region but that need not be the case. Remember that S is a set, so it is not necessarily always sorted.
I agree with the others, This was a surprisingly difficult challenge. Partially due to the requirement to have adjacently connected pixels of the same region type, but also due to the aesthetic challenge to make the regions look like a map of countries.

Here is my attempt... it is horribly inefficient but seems to produce reasonable output. Continuing the trend of using common input for comparison purposes:

Parameters : 380 260 233 420 1300 3511 4772 5089 9507 22107 25117 26744



Parameters : 380 260 8 5 6 7 8 4 5 6 7 9 4 6 9 5 8 7 5



Dark Age of Camelot 213 307 1 1 1



My larger example: (640 480 6 1 7 2 9 3 4 5 6 1 9 8 7 44 3 1 9 4 5 6 7 2 3 4 9 3 4 5 9 8 7 5 6 1 2 1 2 1 2 6 7 8 9 63 3)



An example with more countries: 640 480 6 1 7 2 9 3 4 5 6 1 9 8 7 44 3 1 9 4 5 6 7 2 3 4 9 3 4 5 9 8 7 5 6 1 2 1 2 1 2 6 7 8 9 63 5 33 11 88 2 7 9 5 6 2 5 7

package GenerateRealisticMaps;

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import javax.imageio.ImageIO;

public class GenerateRealisticMaps
{
    private static final Random rand = new Random(3);
    private static final Color[] paletteizedColours = new Color[100];

    // create colour palette
    static
    {
        paletteizedColours[0] = new Color(0xFF000000);
        for (int i = 1; i &lt; paletteizedColours.length; i++)
        {
            paletteizedColours[i] = Color.getHSBColor(rand.nextFloat(), rand.nextFloat(), 0.5f + rand.nextFloat() * 0.4f);
        }
    }

    /**
     * Represents a pixel that is the boundary of a region
     * @author default
     *
     */
    public static class BoundaryPixel
    {
        public BoundaryPixel(int x, int y, int otherRegionId)
        {
            super();
            this.x = x;
            this.y = y;
            this.otherRegionId = otherRegionId;
        }

        int x;
        int y;
        int otherRegionId;
    }

    /**
     * Group of adjacent pixels that represent a region (i.e. a country in the map)
     * @author default
     *
     */
    public static class Region
    {
        static private int masterId = 0;

        Region(int desiredSize)
        {
            this.desiredSize = desiredSize;
            id = ++masterId;
        }

        int desiredSize;
        int size = 0;
        int id;
        List&lt;BoundaryPixel&gt; boundary = new ArrayList&lt;GenerateRealisticMaps.BoundaryPixel&gt;();

    }

    /**
     * Container of regions
     * @author default
     *
     */
    public static class Regions
    {
        List&lt;Region&gt; regionList = new ArrayList&lt;GenerateRealisticMaps.Region&gt;();
        Map&lt;Integer, Region&gt; regionMap = new HashMap&lt;Integer, GenerateRealisticMaps.Region&gt;();
    }

    public static void main(String[] args) throws IOException
    {
        int width = Integer.parseInt(args[0]);
        int height = Integer.parseInt(args[1]);
        int[] s = new int[args.length - 2];

        // read in the region weights
        int sum = 0;
        for (int i = 0; i &lt; args.length - 2; i++)
        {
            sum += s[i] = Integer.parseInt(args[i + 2]);
        }

        int totalPixels = width * height;

        double multiplier = ((double) totalPixels) / sum;

        // convert region weights to pixel counts
        int runningCount = 0;
        for (int i = 0; i &lt; s.length - 1; i++)
        {
            runningCount += s[i] = (int) (multiplier * s[i]);
        }
        s[s.length - 1] = totalPixels - runningCount;

        Regions regions = new Regions();
        int[][] map = new int[width][height];

        // initialise region starting pixels
        for (int v : s)
        {
            Region region = new Region(v);
            regions.regionList.add(region);
            regions.regionMap.put(region.id, region);

            int x;
            int y;
            do
            {
                x = rand.nextInt(width);
                y = rand.nextInt(height);
            } while (map[x][y] != 0);

            map[x][y] = region.id;
            region.size++;

        }

        // initialise a "height" map that provides cost to claim a unclaimed region. This allows for more natural shaped countries
        int[][] heightMap = new int[width][height];
        for (int i = 0; i &lt; width; i++)
        {
            for (int j = 0; j &lt; height; j++)
            {
                heightMap[i][j] = rand.nextInt(50);
            }
        }

        boolean equal = false;

        // main loop
        do
        {
            growRegions(map, heightMap, width, height, regions);

            // determine whether regions have reached their desired size
            equal = true;
            for (Region region : regions.regionList)
            {
                equal = equal &amp;&amp; region.size == region.desiredSize;
            }

            if (equal)
            {
                HashMap&lt;Integer, Set&lt;Integer&gt;&gt; commonIsolatedRegions = new HashMap&lt;Integer, Set&lt;Integer&gt;&gt;();
                int isolatedRegionId = 0;
                int[][] isolatedRegions = new int[width][height];
                List&lt;Integer&gt; isolatedRegionSize = new ArrayList&lt;Integer&gt;();
                isolatedRegionSize.add(-1); // add dummy entry at index 0 since region ids start at 1

                // go though each pixel and attempt to identify an isolated region from that point if it as not
                // yet been identified... i.e. an enclosed area.
                for (int i = 0; i &lt; width; i++)
                {
                    for (int j = 0; j &lt; height; j++)
                    {
                        if (isolatedRegions[i][j] == 0)
                        {
                            isolatedRegionId++;

                            Point point = new Point(i, j);
                            int size = identifyEnclosedArea(map, isolatedRegions, width, height, point, isolatedRegionId);

                            // add this isolated region id to the group of isolated regions associated with the region at this pixel
                            Set&lt;Integer&gt; isolatedRegionSet = commonIsolatedRegions.get(map[i][j]);
                            if (isolatedRegionSet == null)
                            {
                                isolatedRegionSet = new HashSet&lt;Integer&gt;();
                                commonIsolatedRegions.put(map[i][j], isolatedRegionSet);
                            }
                            isolatedRegionSet.add(isolatedRegionId);
                            isolatedRegionSize.add(size);
                        }
                    }
                }

                // only keep the largest isolated region in each group. Mark the other members in the group areas as unclaimed.
                for (Region region : regions.regionList)
                {
                    Set&lt;Integer&gt; isolatedRegionSet = commonIsolatedRegions.get(region.id);

                    // find the largest isolatedRegion mapped to this region
                    int largestIsolatedRegionId = -1;
                    int largestIsolatedRegionSize = -1;
                    for (Integer isolatedRegionIdentifier : isolatedRegionSet)
                    {
                        if (isolatedRegionSize.get(isolatedRegionIdentifier) &gt; largestIsolatedRegionSize)
                        {
                            largestIsolatedRegionSize = isolatedRegionSize.get(isolatedRegionIdentifier);
                            largestIsolatedRegionId = isolatedRegionIdentifier;
                        }
                    }
                    // remove the largest isolated region (i.e. retain those pixels)
                    isolatedRegionSet.remove(largestIsolatedRegionId);

                    if (isolatedRegionSet.size() &gt; 0)
                    {
                        equal = false;

                        // for all remaining isolated regions mapped to this region, convert to unclaimed areas.
                        for (Integer isolatedRegionIdentifier : isolatedRegionSet)
                        {
                            for (int i = 0; i &lt; width; i++)
                            {
                                for (int j = 0; j &lt; height; j++)
                                {
                                    if (isolatedRegions[i][j] == isolatedRegionIdentifier)
                                        map[i][j] = 0;
                                }
                            }
                        }
                    }
                }
            }

        } while (!equal);

        saveOutputImage("out.final.png", map);
    }

    /**
     * Renders and saves the output image
     * 
     * @param filename
     * @param map
     * @throws IOException
     */
    public static void saveOutputImage(String filename, int[][] map) throws IOException
    {

        final int scale = 1;
        final int width = map.length;
        final int height = map[0].length;
        BufferedImage image = new BufferedImage(width * scale, height * scale, BufferedImage.TYPE_INT_RGB);

        Graphics2D g = (Graphics2D) image.getGraphics();

        for (int j = 0; j &lt; height; j++)
        {
            for (int i = 0; i &lt; width; i++)
            {
                g.setColor(paletteizedColours[map[i][j]]);
                g.fillRect(i * scale, j * scale, scale, scale);
            }
        }

        ImageIO.write(image, "png", new File(filename));
    }

    /**
     * Grows the regions of the world. Firstly by unclaimed cells and then by distributing cells amongst the regions.
     * 
     * @param map
     *            cell to region map
     * @param heightMap
     *            the "height" cost of unclaimed cells. Used to give more natural shapes.
     * @param width
     * @param height
     * @param regions
     */
    public static void growRegions(int[][] map, int[][] heightMap, int width, int height, Regions regions)
    {
        // reset region sizes
        for (Region region : regions.regionList)
        {
            region.size = 0;
            region.boundary.clear();
        }

        // populate corners with adjacent pixel region id... these pixels cannot ever be "grown" into.
        map[0][0] = map[1][0];
        map[width - 1][0] = map[width - 1][5];
        map[width - 1][height - 1] = map[width - 2][height - 1];
        map[0][height - 1] = map[1][height - 1];

        int i, x, y, dx = 0, dy = 0, currHeight, currentId = -1, pixelRegionId;
        Region currRegion = null;
        ;

        // calculate initial region sizes
        for (y = 0; y &lt; height; y++)
        {
            for (x = 0; x &lt; width; x++)
            {
                if (map[x][y] &gt; 0)
                    regions.regionMap.get(map[x][y]).size++;
            }
        }

        // expand regions into surrounding unclaimed pixels.
        // construct a list of region boundary pixels in the process.
        for (y = 1; y &lt; height - 1; y++)
        {
            for (x = 1; x &lt; width - 1; x++)
            {
                int cellId = map[x][y];
                if (cellId &gt; 0)
                {
                    if (cellId != currentId)
                    {

                        currRegion = regions.regionMap.get(map[x][y]);
                        currentId = currRegion.id;
                    }

                    currHeight = heightMap[x][y]++;

                    for (i = 0; i &lt; 4; i++)
                    {
                        switch (i)
                        {
                        case 0:
                            dx = x - 1;
                            dy = y;
                            break;
                        case 1:
                            dx = x + 1;
                            dy = y;
                            break;
                        case 2:
                            dx = x;
                            dy = y - 1;
                            break;
                        case 3:
                            dx = x;
                            dy = y + 1;
                            break;
                        }
                        pixelRegionId = map[dx][dy];
                        switch (pixelRegionId)
                        {
                        // unclaimed cell...
                        case 0:
                            if (heightMap[dx][dy] &lt; currHeight)
                            {
                                map[dx][dy] = currRegion.id;
                                currRegion.size++;
                            }
                            break;
                        // claimed cell...
                        default:
                            if (pixelRegionId != currRegion.id)
                            {
                                currRegion.boundary.add(new BoundaryPixel(dx, dy, pixelRegionId));
                            }
                            break;
                        }
                    }
                }
            }
        }

        HashMap&lt;Integer, List&lt;BoundaryPixel&gt;&gt; neighbourBorders = new HashMap&lt;Integer, List&lt;BoundaryPixel&gt;&gt;();

        // for all regions...
        for (Region region : regions.regionList)
        {
            // that are less than the desired size...
            if (region.size &lt; region.desiredSize)
            {
                neighbourBorders.clear();

                // identify the boundary segment per neighbour of the region
                for (BoundaryPixel boundaryPixel : region.boundary)
                {
                    List&lt;BoundaryPixel&gt; neighbourBorderSegment = neighbourBorders.get(boundaryPixel.otherRegionId);
                    if (neighbourBorderSegment == null)
                    {
                        neighbourBorderSegment = new ArrayList&lt;GenerateRealisticMaps.BoundaryPixel&gt;();
                        neighbourBorders.put(boundaryPixel.otherRegionId, neighbourBorderSegment);
                    }
                    neighbourBorderSegment.add(boundaryPixel);
                }

                out:
                // for each neighbour...
                for (int id : neighbourBorders.keySet())
                {
                    Region neighbourRegion = regions.regionMap.get(id);
                    int surplusPixelCount = neighbourRegion.size - neighbourRegion.desiredSize;
                    // that has surplus pixels...
                    if (surplusPixelCount &gt; 0)
                    {
                        // and convert the border segment pixels to the current region...
                        List&lt;BoundaryPixel&gt; neighbourBorderSegment = neighbourBorders.get(id);
                        int index = 0;
                        while (surplusPixelCount-- &gt; 0 &amp;&amp; index &lt; neighbourBorderSegment.size())
                        {
                            BoundaryPixel boundaryPixel = neighbourBorderSegment.get(index++);
                            map[boundaryPixel.x][boundaryPixel.y] = region.id;
                            region.size++;
                            regions.regionMap.get(boundaryPixel.otherRegionId).size--;
                            // until we reach the desired size...
                            if (region.size == region.desiredSize)
                                break out;
                        }
                    }
                }
            }

            // if region contains more pixels than desired...
            else if (region.size &gt; region.desiredSize)
            {
                // and the region has neighbours
                if (region.boundary.size() &gt; 0)
                {
                    // choose a neighbour to off load extra pixels to
                    Region neighbour = regions.regionMap.get(region.boundary.remove(rand.nextInt(region.boundary.size())).otherRegionId);

                    ArrayList&lt;BoundaryPixel&gt; adjustedBoundary = new ArrayList&lt;&gt;();
                    // iterate over the boundary neighbour's boundary pixels...
                    for (BoundaryPixel boundaryPixel : neighbour.boundary)
                    {
                        // and then for those pixels which are of the current region, convert to the neighbour region
                        if (boundaryPixel.otherRegionId == region.id)
                        {
                            map[boundaryPixel.x][boundaryPixel.y] = neighbour.id;
                            neighbour.size++;
                            region.size--;
                            // stop when we reach the region's desired size.
                            if (region.size == region.desiredSize)
                                break;
                        }
                        else
                        {
                            adjustedBoundary.add(boundaryPixel);
                        }
                    }
                    neighbour.boundary = adjustedBoundary;
                }
            }
        }

    }

    /**
     * identifies the area, starting at the given point, in which adjacent pixels are of the same region id.
     * 
     * @param map
     * @param isolatedRegionMap
     *            cells identifying which area that the corresponding map cell belongs
     * @param width
     * @param height
     * @param point
     *            the starting point of the area to be identified
     * @param isolatedRegionId
     *            the id of the region to assign cells with
     * @return the size of the identified area
     */
    private static int identifyEnclosedArea(int[][] map, int[][] isolatedRegionMap, int width, int height, Point point, final int isolatedRegionId)
    {
        ArrayList&lt;Point&gt; stack = new ArrayList&lt;Point&gt;();
        final int EXPECTED_REGION_ID = map[point.x][point.y];
        stack.add(point);
        int size = 0;

        while (stack.size() &gt; 0)
        {
            Point p = stack.remove(stack.size() - 1);
            int x = p.x;
            int y = p.y;
            if (y &lt; 0 || y &gt; height - 1 || x &lt; 0 || x &gt; width - 1 || isolatedRegionMap[x][y] &gt; 0)
                continue;
            int val = map[x][y];
            if (val == EXPECTED_REGION_ID)
            {
                isolatedRegionMap[x][y] = isolatedRegionId;
                size++;
                stack.add(new Point(x + 1, y));
                stack.add(new Point(x - 1, y));
                stack.add(new Point(x, y + 1));
                stack.add(new Point(x, y - 1));
            }
        }

        return size;
    }

}


Explanation (from comments)

The algorithm is pretty simple: Firstly initialise the map with random weights, choose random seed pixels for each of the country regions. Secondly "grow" each region by attempting to claim unclaimed adjacent pixels. This occurs when the weight of the current pixel exceeds the unclaimed weight.

Each pixel in a region increases its weight each growth cycle. Additionally if a region has neighbours then if the current region being considered has less pixels than desired, then it will steal pixels from its neighbour if the neighbour has more pixels than desired. If the current region has more pixels than its neighbour then it randomly chooses a neighbour and then give all the surplus pixels to that neighbour. When all regions are of the correct size, then the third phase occurs to identify and convert any regions that have been split and are no longer continuous.

Only the largest split of the region is kept and the other splits are converted into unclaimed pixels and the second phase starts again. This repeats until all pixels in a region are adjacent and all regions are of the correct size.