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:

Those 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.

 

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.

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

One of my long-term goals was to build a completely procedural game, a la Minecraft, but with a deep story. Dwarf Fortress is an effort to do something similar, but it’s very much a depth-first effort, both in terms of gameplay and in terms of world building. The world has much more detail than I could readily use as a player, and the user interface is overwhelmingly complex. Furthermore, while there are great stories told during world generation, the player can’t be part of them: there’s no way to see the consequences of your actions on a global scale. Time stops when you start your fortress. Nations don’t fight wars while you’re on adventures. The player can successfully clear the world of certain types of beasts (the game will often recognize this; if there are only a few great monsters left in the world and you kill them, a ‘new age’ will dawn) or totally destroy a nation of goblins, but nobody will move to fill the power vacuum they leave behind. I’m not faulting Toady for this: he’s given us a very deep and immersive world, down to realistic geology and tracking every elf’s every tooth, but his universe isn’t precisely what I want.

Enter Crusader Kings II. CK2 is a ‘grand strategy’ game, in which the player takes control of a medieval dynasty, starting some time after 867 and ending in 1453, when the game’s approximation of feudalism no longer accurately represents political reality. Cities aren’t simulated down to streets, and the only people who have any agency are noblemen, clergy and mayors. Tactics have no place in war: the player can order his armies about in a mass, but only with enough fidelity to send a ten thousand men to York. He does not order them about on the field or even decide which part of York to control. The day-to-day details of the realm are abstracted away, in other words, almost completely. Instead, the player manages the human relationships between noblemen, arranging marriages to forge alliances, granting lands to barons to curry their favor, or changing inheritance laws in order that a genius third-born son might ascend the throne instead of his inbred eldest brother.

It sounds dry, and it is dry, but it’s the only game out there which really allows the player to play the game of thrones we see in A Song of Ice and Fire or Dune. With more depth in any particular area, it would become a tactical simulator like the Total War series or an accounting simulator or a dating simulator. As it is, it creates very interesting, dynamic alternate histories on a grand scale, and allows the player to feel a monarchical pride in having (for instance) repulsed William the Bastard at Stamford Bridge, or brought the Caliphate all the way north to Scandinavia.

As it allows the player to play the game of thrones, it was the perfect platform on which to build a Game of Thrones mod. The diplomacy in the game is deep enough to allow for the plots and alliances the books and TV show are built around, and the feudalism accurately represents the relationships between lords and their bannermen.

The GoT mod is a total conversion mod. That means it has a completely custom map, entirely new art assets, different cultures, and different events. Other total conversion mods exist; the next most famous being set in the world of The Elder Scrolls.

I see no reason why it shouldn’t be possible to create such mods dynamically, to procedurally generate the world’s map, the noblemen in charge of each area, and the relationships between them. Generating those dynamic worlds would allow dynamic, sensible stories to play out in a fantasy world, and I think the idea very appealing.