How can I “grow” regions representing countries in a 2D grid?

Question

My friend started to make a 'country-generator' type of thing. We have some starting points, and we want to 'grow' countries from them randomly until the whole area is filled. What's is an effect effective way to create something like this?

This is an image of a desired possible end result:

Answer 1

Here is the general algorithm that could be used to achieve a similar result:

Let N be the number of countries you wish to have

1. Randomly pick N^2 points on the 2D plain.
2. Create the Voronoi diagram to split the plain into N^2 cells.
3. Use Union Find between 2 random neighboring cells (that are on disjoint sets) N*(N-1) times
4. Use the newly created trees of cells as the countries' polygons.
5. Apply a wave / noise filter to get the fuzzy look you desire.

You can play with Voronoi here:

http://blog.ivank.net/voronoi-diagram-in-as3.html

Learn how to apply apply noise here (to make the cells less rigid):

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

Answer 2

For a 2D grid, like in the image you posted.

While probably not the most efficient in terms of speed and memory usage, I find that a brute force approach could still be useful, since it's easy to get it started. Especially if this is not to be used in places with time or memory constraints.

//Get some random cells for countries to start extending from.
for each Country in Countries
  Cell unoccupiedCell = Map.GetRandomUnoccupiedCell()
  Country.OccupiedCells.Add(unoccupiedCell)
  unoccupiedCell.occupier = Country
end for each

//Extend each country at random
while Map.UnoccupiedCells.Count > 0
  for each Country in Countries
    Cell unoccupiedCell = Map.RandomUnoccupiedCellInVicinityOf(Country)
    if (unoccupiedCell exists)
      Country.OccupiedCells.Add(unoccupiedCell)
      unoccupiedCell.Occupier = Country
    endif
  end for each
end while