Dividing a procedurally generated world into countries: a quick and dirty implementation

When I first started developing Winds of Trade, I thought the whole game in terms of cities. You could go with your ships, visiting different ports and doing the usual buy high and sell low stuff.

But after a while that felt a bit unrealistic and not too interesting in terms of gameplay, so I decided that every city in the game had to belong to a country. That opened lots of new possibilities, like having your ships recruited by a ruler because his country was going to war with another; having economic cycles that affect all of the cities of a territory; or having some countries ban certain goods, opening the doors to the wonderful world of smuggling.

That, of course, brought some new challenges. My main two problems were: how to determine what country each city belongs to and how to determine who owns every pixel of virtual land available in the world. Here you can find the incredibly simple, quick and dirty solutions I used to face those problems.

Chapter 1: "Who runs this town?"

Warning: illustrations made by a programmer ahead!

The algorithm I decided to use for deciding who owns what (i.e. what country every city belongs to) is as simple as this:

1) Have your randomly generated map with its randomly placed cities handy. That will be something like this:

2) Decide on a number of countries (in this example, three) and randomly assign a capital city to each one. Here you can see the capital city of Red Country, Green Country and Blue Country:

3) Make a circle around each city that has an owner. Every non-owned city inside that radius will become owned. Repeat the process with larger and larger radii until you have no more non-owned cities. As the old saying goes, an animated gif is worth a thousand words per frame:

And there you go, every city now belongs to a country! But... Who owns each one of the beautiful pixels that make the heightmap of this wonderful world?

Chapter 2: "This pixel is mine!"

Well, once I established who owns every city in the world I proceed to do a similar process in order to determine land ownership. What the algorithm does, basically, is to make a growing spiral out of every city that goes claiming each piece of land until all of it belongs to someone. When doing this humble animation I skipped lots of steps and used squares instead of spirals (that's why the result doesn't look too good) because, honestly, I have very little patience. Sorry about that!

But, as you can see, this incredibly simple algorithm works relatively well. Even if the result doesn't look too natural, that can always be fixed later with some smoothing of the borders and removing very small areas that are isolated from the rest (like the area the Green Country owns in the west part of the northern Blue island) 

Here you can see an example map actually generated in Winds of Trade using these algorithms, where the squares represent cities:

I understand that all of these algorithms are far from being clever or bright, but they were really easy to design and implement and give reasonable results, so I thought that sharing them here could eventually help someone. I hope that's the case!