Dev Diary #10: Stable place keys in game map data

In short: Every place, province and region on a game map has a key, a fixed identity, and the game's content binds to these keys, so the keys must not shift when the map is rebuilt. MKA Engine's map tool reads the keys from a register, gives a new place a new key and retires the key of a place that no longer exists; a retired key is never used again. On a world map of about 34,000 places, the same small map change retired 6,039 place keys with the old method and 2,239 with the new one.

In a strategy game, "Cairo" is both a name and a place. The game file holds Cairo as an identity, not as a line of text: the map can be redrawn and the identity stays the same. Historical events, city ownership and trade routes bind to that identity. If the identity shifts, a rule or a saved record attaches to the wrong place. So a key is given once and never given to another place.

Who owns the register?#

The map tool is a Python pipeline that lives in the engine repository; it is not part of the engine's Rust core. The key register, however, lives in the game's own folder. The tool gives out keys and keeps them. The game decides which name a place carries, where the register sits and which places exist in the game. The engine does not carry a list of game-specific identities.

Three rules#

• A key is given once. If a place is missing in a new build, its key is retired and is never used again. A new place gets a new key.
• Provinces, places and sea records match by their centre point, the middle point of the record. If the centre is still in the same spot, the old key stays.
• A named land region, area and subcontinent takes the short form of its name from the configuration as its key. While the name stays, the key stays; if its centre moves, no number is added to the end. Two names that give the same short form are an error.

The problem: a shared dice sequence#

Regions grow from seeds: a seed is the starting point from which a region spreads, and a pixel is one cell of the map grid. When seeds were placed on land, every region drew its seeds from one shared random sequence. A draw is the random choice of which pixels a region takes as seeds. If one region made a different number of draws or its pixels changed, every later region's numbers shifted. It was like pulling one die out of a row of dice: every die behind it showed a different face.

An edge-smoothing change exposed the problem. Edge smoothing softens the stepped lines along the map border. This change altered the impassable terrain (land that units cannot cross) by only 1 percent, yet 6,039 place keys were retired. Of these, 3,367 were more than 50 pixels away from the changed pixels, so places that were not near the change also lost their identity.

The fix: every pixel rolls its own die#

Each pixel's random number now comes from the random seed (the starting value of the random sequence) and the pixel's own position; it does not depend on neighbouring pixels. A region's seeds depend only on its own pixels, on each pixel's weight (how readily it is picked) and on its quota (how many seeds the region gets). A change in another region, or the order of regions, does not change them. The numbers computed from each pixel's weight are compared, and the smallest ones are picked, so the draw depends only on the region's own data.

Measurement#

We measured the same edge-smoothing change under both draw methods. The old method's numbers come from an earlier run; the new method's numbers come from a separate run. Each is a single run:

The measurement comes from a run of the map build tool; the game was not run and build time was not measured. Only key stability was measured. The 131 distant retirements that remain come from the fixed land-place target of each group: when an edge changes, the group's scale changes and its borders shift. That is the intended result of the design.

When we rebuilt the hierarchy (the nested levels of places, provinces, areas, regions and subcontinents) with its own register, the register and the hierarchy file stayed identical byte for byte.

The one-time switch#

On the first move from the old register to the new draw method, 5,098 place keys are retired. The cause is the change of draw method, not an edge change. In the same switch, 32 sea records also received new keys because of a separate change to water draws. If the game's content binds to these keys, the switch needs one content update.

A lake bug in the build#

Lake records did not take keys from the register. Each build added a suffix to their names: abaya, abaya_2, abaya_3. Before the fix, the next build with the same register would have retired 276 water areas and 293 water provinces and reopened them under new keys.

Now a lake record takes the register key whose root is its own name: first by centre, and by name if the centre has moved. Sea records keep matching by centre. We ran a copy of the game's register through the hierarchy twice and got the same result both times. Among water places, 5,863 keys were kept, with no retirements and no new keys. Among water provinces, 1,351 keys were kept, and among water areas, 447. One water region was retired; the cause is not yet verified.

What does it cost?#

• Retired keys stay in the register and are never reused, so the register grows a little with every change.
• A change of draw method asks for a one-time content update: 5,098 place keys.
• The 131 distant retirements that remain are the result of the group target, not zero.
• Not measured: build time, the game's own content checks and the migration of records that bind to keys. Those are the game's work.

Frequently asked questions#

Sources and records#

Related diaries: Lockstep and desync, Column store and memory layout.

If you have questions or suggestions about this diary, write to us through the contact page. For an overview of the engine, see the MKA Engine page; for all diaries, see the Developer Diaries list.