So I have a game that needs randomly generated maps. I need to randomly generate provinces for the landmasses. I can generate decent looking, for my purposes, landmasses. I can even do acceptable heights. The map is 2D but I need heights for terrain and biomes. But I can think of a simple reliable way to generate provinces, even with iffy shapes. I want to generate anywhere from 2000 to 10000 and I have a map size conducive to that. Hand drawn maps in GIMP of the same size can easily fit decent shapes and 10000+ provinces.

I feel like a major issue is the program knowing which pixels are part of congruent landmasses. It'd sort of have to know where coasts are in some sense. I know I can do something like set a pixel total and use a random number generator and expand out from a random starting pixel.

Roughly I could pick a start and then using random directions and distances draw out a border and fill it in. Then prune a bit to make sure the size is okay by counting the total number of pixels with the unique province color.

I'm including a link to an imgur album of some of the maps I generate:

http://imgur.com/a/AlPew

I'm concerned about making sure I don't have a bunch of small leftover areas that can't become a proper size province, although I could just flip all land that doesn't have a unique color to water at the end. Water provinces will be a lot easier I think since they don't need a certain kind of shape.

If you have heightmap data for mountains, and know where your lakes and rivers are, elevation changes and rivers help define national boundaries in real life.

Further, civilization tends to grow most around waterways because bodies of water are natural "highways" of commerce, and provide easy access to food (fish) and fertile soil, while also helping make the surrounding climate slightly less extreme (cooling off overly-heated areas, and warming up overly cold areas). This is important when placing your more-developed cities.

Use a fractal to build up unusual looking shapes. Add in Natural rivers to break up the shapes to keep them convex.

Simulate history by randomly combining land masses, or breaking them into smaller pieces.

Here's an algorithm that might do what you want.

1) "Seed." Iterate over your map in small chunks, e.g. 6x6 tile/pixel chunks. In each chunk, randomly pick a tile inside. If it is land, assign it a new, unique province ID.

2) "Grow." Once you've done that for the whole map, iterate across the entire map repeatedly. For each tile that does not have an assigned province but is adjacent to at least one province, have it adopt the province of a random cardinally-adjacent tile (or any adjacent if you're using hexes). Repeat this process until you walk the map and find no unassigned tiles that have at least one assigned neighbours.

3) "Sweep." Remove all land that has no province assignment at all. These are any islands which you didn't hit during the seed step.

4) "Inspect." Walk the map and get data for every province. You'll want to be able to take a province ID and look up its total area (how many assigned tiles), a location inside its borders (any will do; top-left, original seed location, whatever), and any other data you want to track about them at this stage. You'll also want to generate an adjacency map at this time.

5) "Prune." You'll probably have some provinces too small for your purposes, which won't be able to grow in the next step. For each province under a size threshold which also has zero neighbours, turn it into water and discard the province.

6) "Conquer." At this point, the average size of a province is going to be around the 6x6 area (remember the chunk size, in 1?). But you'll have lots of variety in size and shape everywhere. They will all have grown into irregular, blobby shapes. Now what you should do is start fusing these micro-provinces together! Start randomly picking provinces from the bottom 25% or so of them when ranked by size, and have it merge with a random neighbour. Overwrite the neighbour's tile assignments with its conqueror's, union the adjacency sets, and re-insert the new larger province in the rankings. The wider the conqueror selection is, the more variety in final province sizes you'll have at the end.

Yeah, that was sort of what I was thinking I'd end up doing. Off to the rapid testing phase.

Is it possible to flip it around and create the land map from provinces instead of trying to break-down a pre-existing land map?

That's what I ended up doing in my title to avoid having to solve this problem. My landmass generation looks something like:

for (number of provinces that I want)

1. Pick a single sea cell as a start point (after rolling a dice to decide whether to start attached to existing land, or start a new island)

2. Grow the new province, adding one extra sea cell at a time until its a suitable size

3. If we managed to grow large enough, then accept it, otherwise back to #1 to pick a new start point.

I mean I certainly could do that. It'd take a lot of fiddling to get pretty maps and I'm not sure the provinces would be super pretty. It's pretty simple to get a functioning version in code and test to see if refining it would work.

http://imgur.com/kWfiJNd

All land pixels are now part of provinces. A bit boxy in some cases and several artifacts where it looks like paint drips but the general strategy I used works out. Takes quite a long time though. I'm thinking about adding some code to break up the blockiness a little by spawning random protruding shapes of a couple pixels like some triangles and such off the outside of the initial 16 by 16 pixel drop. Get some more irregular shapes in there.

Woops weird glitch made me double post.