Dev Diary #14: How MKA Engine partitions a grand strategy map into locations and provinces

In short: MKA Engine’s map tool first overlays historical state borders and boundaries between old administrative regions to produce small pieces; it then turns those pieces into locations according to settlement and terrain type. The Mandates of History map package used here contains 27,959 land locations and 5,733 water locations; the land is also grouped into provinces, areas and regions. These counts belong to the package built with the game’s map settings.

What was the problem?#

Imagine opening a grand strategy map and clicking a city. That city is more than a dot on the screen. The game’s population, armies, roads and historical records connect to that place. The next action may be to cross into a neighbouring province, count the population of a region or decide which terrain an army can cross. For the game to do those things reliably, the world needs to be divided into meaningful, consistent pieces.

Think of a workshop that makes a paper map. On the table are several transparent sheets: one with historical state borders, another with administrative units, and others with cities and terrain. Stack the sheets and the first outlines appear. Then those outlines are adjusted to follow passable routes, rivers and mountain ridges. At the end, separate pieces become the provinces and regions players recognize.

The challenge is that these layers do not describe the same thing. A state border can change over time. An administrative unit may not line up exactly with a city or a population cluster. Impassable mountains also look artificial when cut by a perfectly straight line. And when the tool uses the same input again, it needs to produce the same package. Otherwise a map rebuild could connect the game’s city records to different places.

In an earlier diary, we explained why map keys need to remain stable. This diary builds the places those keys attach to: the map’s small locations, the provinces above them and the larger areas. The key ledger preserves a place’s identity; partitioning determines which places exist on the map.

How did we solve it?#

First outlines: overlaying historical borders#

A raster is a digital map layer divided into tiny squares. Each square is a pixel, and its stored class says what is there. The tool overlays state rasters from six different years with a raster of historical administrative-unit borders. Connected pieces that remain within the same state and administrative-unit layers become the first shapes. We call these shapes atoms: an atom is a small base piece of the map before the later steps begin.

The first overlay produced 64,075 pieces. Some were too small to be useful on the map, remaining as thin strips or tiny fragments. The tool joined these fragments to their neighbours, reducing the count to 5,648 atoms. During merging it first looks for a neighbour that preserves the same historical state and unit arrangement. If no suitable match remains, it applies a broader neighbour rule. This keeps the first outlines recognizable without letting the rest of the map fill with one-pixel slivers.

Give each atom one map character#

For a player, a location’s possible role matters as much as where it begins. The tool therefore adds a settlement class to the historical pieces: settled land, corridor or impassable land. Each location receives exactly one class, so settled land and impassable terrain follow separate game rules.

Some small settled pieces can merge into a neighbouring class. But an automatic merge preserves a piece if it comes from the game’s hand-written settlement list or contains a settlement from the source data. The measurement record counted 558 pieces protected by these sources. That keeps settled areas around Mecca, Medina, Jeddah and Riyadh from being absorbed into corridors. The detail matters because cities are not merely clusters of pixels: the game recognizes them as places in its content.

Choose location centres: fix important points first#

We call the starting points used to form locations seeds. A seed is the map point from which a location begins to grow; imagine the first worker sent to fill in a region. Instead of placing all seeds at random, the tool fixes certain historical and geographic points first.

In the Mandates package, 14 strait cities are separated into their own locations first. Then 4,953 settlement points from the source data become fixed starting points where there is enough room around them. Each kind of centre keeps its own location even when another centre is nearby. After that, 23,096 free seeds are added to the remaining map according to density. The number and distribution of those free seeds depend on the game’s population and map settings; they are not numbers that the engine imposes on every game.

This order matters. Giving a strait city its own location makes a passage point available for selection on the map, whether a game uses it for an army or a trade route. Giving settlement points a place before the free seeds prevents their surroundings from disappearing into a broad, anonymous area. The free seeds then fill the places that remain. In this way, important centres stay recognizable while distant regions are not left empty.

How do the seeds grow into borders?#

Once the seeds are placed, the map area around each one is assigned to a location. The tool uses a natural cost for this step. Elevation, river size and a broad, slowly changing variation across the map affect the cost of moving from one pixel to the next. Put simply, crossing a flat plain is easy, while crossing a high ridge or a large river costs more. The border is therefore shaped by the terrain instead of being drawn only with a ruler.

The tool grows a watershed from the seeds within each region. A watershed is where water flows downhill and fills low places; here, map pixels are assigned to the seed with the lowest travel cost. Two more passes follow: each finds the centre of a location’s area and moves its movable seed closer to it. This balancing step brings location sizes closer together while city and strait centres stay fixed.

Not every seed moves during this adjustment. Strait and settlement points fixed earlier stay in place. The balancing steps adjust the areas around the free seeds. That preserves centres whose meaning was already known while allowing the remaining locations to grow more evenly.

Split oversized locations again#

If a single location grows too large around a densely populated settlement, it becomes harder to distinguish the different cities or settlement clusters within it. The tool therefore splits populated settled locations whose area, including edge allowances, exceeds 30,000 km². New seeds are placed at the points farthest from the existing seed, and the spread is recalculated.

The process takes several rounds. There were 267 locations over the limit in the first round. After adding seeds and spreading again, the count fell to 101, then 29, 11, 3 and 1; by the final round, none remained over the limit. The process added 415 seeds in total. The aim is not to make every location the same size. It is to divide exceptionally large locations, especially in populated settled areas, into more manageable pieces.

After growing and balancing the locations, the tool checks for detached islands away from a location’s main piece. A large enough detached piece can become its own location; a smaller one joins a neighbour. This keeps one location identity from collecting unrelated patches scattered across the map.

From locations to provinces and regions#

Locations are the smallest places players can select on the map. To group them into provinces players recognize, we build another structure above them. It is like grouping rooms into neighbourhoods, then neighbourhoods into cities: each level brings together the pieces below it.

The province base comes first from historical administrative units. Where those are unavailable, the tool uses historical province centres from 1444 to 1836, and then present-day administrative regions. A base piece that is too small can be joined to neighbouring provinces; the general arrangement keeps most provinces between 3 and 8 locations. This begins with historical and administrative information instead of applying the same geometric grid everywhere.

Areas and regions are a different decision: the game defines these groups in its own map content. In the Mandates package, there are 730 areas and 86 regions. The tool does not invent their names or locations; it groups provinces around the centres supplied by the game. Each area has a historical centre, called its anchor; the province containing that point forms the core of the area. Since the number of regions, areas and anchor names belong to the game’s settings, another game should not be expected to use the same counts.

What did we see?#

The measured package was built with Mandates of History’s map settings. The result is more than one world-wide number; it also shows how the different layers fit together.

The largest counted settled location measured 29,985 km²; the upper limit was 39,140 km². All 179 locations recorded as exceptions were impassable, corridors or empty of population. The cap applies to populated settled locations, so these areas can remain larger; players encounter them as impassable ground, passage corridors or unpopulated areas rather than oversized settlements.

The straight-border share measures how much of the boundary between land locations forms long, straight segments. A lower value means those segments make up a smaller share of the total border. For Mandates of History’s 1337 map, the world value fell from 0.374 in the earlier production version to 0.125 in the new version; in Anatolia it fell from 0.361 to 0.066, and in Europe from 0.352 to 0.053.

The last two runs that rebuilt the same package produced the same output: with the same data and settings, the map tool reproduced the same arrangement of locations. A package build took 24 to 33 minutes on this machine and used up to 9.2 GB of memory. Those numbers describe building map content, not running the game.

Why did we choose this approach?#

Our research note compared four methods:

We chose watershed growth as the main border-forming method, then added two balancing passes, new seeds at the farthest points of large settled areas, and a repair step for disconnected pieces. Together these steps meet three needs: settlement centres keep their place, terrain shapes the borders, and each location forms one connected piece on the map.

The choice is visible where dense settlements and wide landscapes share one world. City and settlement centres are fixed starting points; the remaining area is filled according to the density settings the game supplies for its population groups. Adding elevation and rivers to the border cost brings the lines closer to the terrain than a grid would. Historical borders remain the starting frame, and new location boundaries are built on those historical traces.

For provinces, we also begin with the historical and administrative information available to the game, joining neighbours where needed. We keep area and region names out of the tool. They are part of the game’s story; the map tool places them using the anchors the game provides. This lets the same method serve another game while each game keeps its historical choices in its own content.

What does it cost?#

These measurements belong to a package built with Mandates of History’s map settings. One build took 24 to 33 minutes and used up to 9.2 GB of memory; its eight linked steps run while preparing content, not while the game is running. Content creation follows this eight-part sequence:

• Merge historical map pieces.
• Assign settlement classes.
• Choose fixed centres.
• Place free centres by density.
• Grow and balance locations using terrain costs.
• Split oversized locations.
• Repair detached pieces.
• Build the province hierarchy.

What comes next?#

After grouping locations into provinces and regions, the next question is who controls which country in the same world. In diary #15, we will explain player authority, the observer role and the AI player.

Frequently asked questions#

In an earlier diary, we explained permanent keys on a game map. For an overview of the engine, see MKA Engine; for every diary, visit Developer Diaries; and for questions, see contact.