Procedural Map Generation for Crusader Kings II, Part 3: Dividing the Map

First, I needed to build data structures for the polygons themselves – this is kind of a roundabout task, since each edge tracks its left and right seed and its two vertices. I ended up iterating over each seed point, then iterating over all the edges and creating an array of edges for each seed, then sorting the endpoints of those edges to give us an array of points that we can actually use to draw the polygons. I’ve never been happier to see pseudorandom gibberish:



Now we have an array of corner points, each of which is associated with a seed point. I added simplex noise generated using Heikki Törmälä’s Noise.cs to the distance between each seed point and the center of the image, resulting in an approximately circular continent with a little bit of excitement around the edges, including coastal islands:



Each county object has an isWater property so that I can keep track of what we’ll be doing with it later.

Generating Duchies is accomplished by randomly selecting between 250 and 350 counties as seeds, then iterating over all the counties on the map, computing the nearest duchy seed, and assigning the county to the appropriate duchy. If the seed county is a water county, we force any neighboring land counties to choose the nearest land county instead. The image below won’t be used by the game at all, but right now it allows me to visualize what’s going on.



We repeat the same process for kingdoms, assigning duchies to the kingdom which has its seed closest to the duchy’s seed:



I’m a little bit disappointed at how few kingdoms I’m seeing, because the ocean is eating a lot of them. I’m choosing between 30 and 40 seed counties for the kingdoms just to get a dozen or two.

Finally, we assign the kingdoms to empires:

empires_sythrynThose are pretty big empires, and surprisingly regular.

Here’s an empire map produced by a different seed:



As you can see, the general shape of the continent is almost identical (since we’re just adding some fuzz to a circle) but the political divisions are much more variable.

With that second seed, some of the empires are just single kingdoms. I’m not sure how much I like that, so I might end up forcing single-kingdom empires to merge with a neighbor.