Monthly Archives: January 2014

Procedural Map Generation for Crusader Kings II, Part 4: Markov Names

All of those counties, duchies, kingdoms and empires need names to go with the shiny new borders we’re drawing.

The easiest way to do procedural naming is with something called a Markov chain, a mathematical concept which models changes from one state to another based only on the current state, and not on any ‘memory’ of what happened before (which is not to say that a Markov chain doesn’t use RAM!). Markov chains have applications to other areas, notably in finance, Baseball, and biological population studies, but their most readily apparent application is to generating pronounceable random text.

It works like this: you look at the last N characters of your text, and then at the characters which are allowed to follow them in your sample words, choosing the next character from those among them at random. (The first character is chosen at random from all the characters used to start words in your sample.) We call N the ‘order’ of the Markov generator. Given a vocabulary of English text, Markov generators of order 4 or higher will regularly produce real words, and only rarely give output to make spellcheck unhappy.

I grabbed a Markov generator from the guys at Silicon Commander Games, and found its features to match exactly with my requirements. They were using it to name characters, but naming locations works just as well. I then copied the lists of counties, duchies, kingdoms and empires from the CKII wiki, massaged them as necessary to make comma-separated text files, and fed them to my program. There are only 15 empires in the vanilla game, so I added some more seed data, such as the “Romulan Empire.”

Here are the first few counties for one particular world seed:

Duchies:

All the Kingdoms:

Empires:

As you can see, the Empires are a little weird. I’ll add some custom logic to improve the imperial nomenclature later. The word list for kingdoms doesn’t seem to be long enough, since we’re seeing a lot of kingdom names from the vanilla game. It’s expected that you’ll see a few over time, but seeing Sicily, Arabia, Greece, Hungary, Italy, Denmark and Mesopotamia on my first run indicates that we’d be seeing multiple vanilla kingdom names in every game.

 

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:

provinces_sythryn

 

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:

water_sythryn

 

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.

duchies_sythryn

 

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

kingdoms_sythryn

 

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:

empires_orthan

 

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.

 

Procedural Map Creation for Crusader Kings II, Part 1: Voronoi Polygons

One of the greatest things about being alive in the 21st century is that other people provide source code on the internet for free. One such person calls himself BenDi, and he saved me the trouble of implementing an algorithm to compute Voronoi diagrams myself. Furthermore, one Maxim Barsuk provided example client code for BenDi’s project, which I was able to modify to suit my needs. 

Specify a set of points, call them ‘seeds,’ and distribute them upon a plane. Given those points, we can make a Voronoi diagram, showing the plane divided into polygons in such a fashion that each polygon contains those points which are closer to a given seed than to any other. Each polygon will be a county for our random CKII map.

A Voronoi diagram. Seeds are the red circles.

A Voronoi diagram. Seeds are the red circles.

I still have some work to do to color the polygons as the CKII engine demands, but this is a good start.