Regime chains

Why you need this

A generated map that never changes is a static map with extra steps. The second half of "dynamic" on the hub page is change over time: a meadow that becomes contested, then depleted, then calm again; a lowland that floods and drains. A regime chain does this with the same table-and-dice machinery as a Markov chain, run once per tick per region instead of once per column. The layout stays fixed; what the player sees and meets on it does not.

The idea

Divide the map into regions: chunks on a top-down map, rooms in a dungeon, or sections of a side-scroller. Each region $r$ carries a regime $X_t^{(r)}$, one of $N$ states. Every game tick (or every $K$ seconds) each region rolls on its current row of a transition matrix $A$, $A_{ij} = P(X_{t+1} = j \mid X_t = i)$, rows summing to 1, and moves to its next regime. Regions roll independently, each from its own row, so a single $A$ animates the whole map.

The regime is hidden bookkeeping. What the player sees is the emission table: for each regime, a row of parameters that the game reads every frame. Spawn rate. Resource yield. Weather. Which decor set is swapped in. Which palette variant is active (seasons are a palette swap). Whether cells are passable. Unlike the emission matrix $B$ of an HMM, this table is not a probability distribution; it is a lookup of tunables keyed by state. The chain decides the state, the table says what the state means.

Expected time spent in a regime before leaving follows from the diagonal entry, the same derivation as run length on the Markov chain page. Let $p = A_{ii}$. Each tick the region either leaves (probability $1 - p$) or stays and faces the same choice again, so the expected dwell $D$ satisfies $D = 1 + p \, D$, giving

$$D_i = \frac{1}{1 - A_{ii}} \text{ ticks}.$$

Multiply by the tick length $K$ for seconds.

Worked example

Four regimes: 1 Calm, 2 Contested, 3 Depleted, 4 Flooded.

From \ To	Calm	Contested	Depleted	Flooded	Row sum
Calm	0.85	0.10	0.03	0.02	1.00
Contested	0.20	0.60	0.20	0.00	1.00
Depleted	0.30	0.05	0.60	0.05	1.00
Flooded	0.25	0.00	0.05	0.70	1.00

Read the zeros as design rules: a fight does not flood the field (Contested never goes directly to Flooded), and a flood does not start a fight (Flooded never goes directly to Contested). Fighting tends to deplete (0.20). Depletion usually recovers to Calm (0.30 of the 0.40 that leaves each tick).

Emission table, one row per regime:

Regime	Spawns per minute	Resource yield	Weather	Decor set	Passable
Calm	1	100%	clear	flowers, tall grass	all cells
Contested	4	60%	overcast	campfires, banners	all cells
Depleted	1	20%	dust haze	stumps, bare dirt	all cells
Flooded	0	0%	rain	reeds, driftwood	bridges and high ground only

Expected dwell times with $K = 10$ seconds per tick: Calm $1 / 0.15 = 6.67$ ticks, about 67 seconds. Contested $1 / 0.40 = 2.5$ ticks, 25 seconds. Depleted $2.5$ ticks. Flooded $1 / 0.30 = 3.33$ ticks, 33 seconds.

Now trace one region for ten ticks, starting Calm. Running totals per row: Calm 0.85, 0.95, 0.98, 1.00; Contested 0.20, 0.80, 1.00, 1.00; Flooded 0.25, 0.25, 0.30, 1.00. Suppose the region's seeded stream produces these draws.

Tick	Draw $u$	Row used	New regime	Player sees
0			Calm	flowers, 1 spawn/min
1	0.42	Calm	Calm	no change
2	0.91	Calm	Contested	campfires appear, 4 spawns/min, yield drops to 60%
3	0.57	Contested	Contested	no change
4	0.13	Contested	Calm	banners removed, spawns back to 1
5	0.78	Calm	Calm	no change
6	0.99	Calm	Flooded	rain, low cells become water, yield 0%
7	0.66	Flooded	Flooded	no change
8	0.31	Flooded	Flooded	no change
9	0.08	Flooded	Calm	water drains, flowers return
10	0.50	Calm	Calm	no change

Tick 6: from Calm, $u = 0.99$ passes 0.98 and lands in the last slot, Flooded, a 2% event. Tick 9: $u = 0.08$ is below 0.25, so back to Calm. Over ticks 1 to 10, 100 seconds, this region was calm for 5 ticks (50 seconds), fought over for 2 (20 seconds), and under water for 3 (30 seconds), counting each tick by the regime it entered.

Design guidance

Tick rate and dwell. Dwell in seconds is $K / (1 - A_{ii})$. If you halve $K$ to make transitions feel less like a metronome, you must raise $A_{ii}$ to keep the same dwell. Calm at 67 seconds needs $A_{ii} = 0.85$ at $K = 10$ and $A_{ii} = 1 - 5 / 66.7 = 0.925$ at $K = 5$. Tune dwell in seconds in the tool and derive $A_{ii}$ from it.

Coupling neighbors. Independent regions produce a patchwork: one flooded chunk surrounded by dry ones. Real floods spread. Let a Flooded region raise the flood probability of its neighbors: for a Calm region, $P(\text{Flooded next}) = 0.02 + 0.10 \cdot (\text{number of Flooded neighbors})$, taken out of the Calm self-transition. Now a region's next state depends on its neighbors' current states, not only its own. That is no longer a Markov chain per region; it is a Markov random field evolving in time, the same structure as a probabilistic cellular automaton. Update all regions from a snapshot of the previous tick so that order of evaluation does not matter, and keep the coupling small or the whole map synchronizes.

Previewing. Because the whole timeline is a function of the seed, the tool can compute regimes for ticks 0 to 1000 in a few milliseconds and let the designer scrub a slider. Show a strip per region colored by regime. Too much red? Lower the Contested column. Never floods? The designer sees it before a player does.

Determinism. Seed the regime stream separately from the layout stream: derive both from the map seed but with different salts, and give each region its own sub-stream (seed hashed with the region index). Then regenerating the layout does not change the timeline, and regenerating region 12's timeline does not touch region 13's. This is the same discipline as per-chunk seeds in layered generation.

Saving. Do not store the regime history. Store the map seed and the current tick count. On load, replay from tick 0 with the same seeded streams, or, if regions are uncoupled, jump straight to tick $t$ by skipping the stream ahead. A save file of two integers reproduces a thousand ticks of weather. If the player's actions can change a regime (clearing a Contested region), store those events with their tick as well and replay them.

Running it. One function call per tick:

// regimes[r] is the current state index of region r; streams[r] is region r's seeded generator.
function tick(regimes, A, streams) {
  for (let r = 0; r < regimes.length; r++) {
    const row = A[regimes[r]], u = streams[r]();
    let acc = 0, j = 0;
    while (j < row.length - 1 && u >= (acc += row[j])) j++;
    regimes[r] = j;
  }
}

When to promote to an HMM

A regime chain is a plain Markov chain whose states are never observed by the player. Promote it to a hidden Markov model with an emission matrix $B$ only when you need one of two things: to fit $A$ from play logs, treating logged events (kills, resource pulls, floods) as observations and running Baum-Welch; or to infer a region's regime from observed events, for example on a server that receives only the event stream and must reconstruct state with the forward algorithm. If you are authoring $A$ by hand and the game holds the state directly, the HMM adds tables you would never read.

Common mistakes

• Dwell too short. The field changes weather every few seconds and reads as a glitch. Raise $A_{ii}$; the dwell formula tells you by how much.
• Dwell too long. A regime with $A_{ii} = 0.99$ at $K = 10$ dwells about 17 minutes. Most players never see it change and the feature might as well not exist.
• A rare regime that never returns. Flooded with a 0.02 entry and a 0.70 self-loop is fine; Flooded with a self-loop of 0.98 traps the region for the session. Check every state's dwell.
• One shared stream for all regions. Adding a region shifts every other region's draws and changes saved games. One sub-stream per region.
• Emission swaps that break passability mid-move. A cell turns to water under the player. Apply passability changes at region edges, or fade in over a few frames and push the player out.
• Coupling that synchronizes. Every region floods at once because the coupling term is too large. Cap the boost so no transition probability exceeds a few tenths.

Cost

Each tick costs $O(R \cdot N)$ time, with $R$ the number of regions and $N$ the number of regimes: one row scan of at most $N$ entries per region. Memory is $O(R)$ for the current regimes plus $O(N^2)$ for the table plus one generator state per region. With coupling, add a neighbor lookup per region, still $O(R \cdot N)$ on a grid. A thousand regions at ten ticks a second is well under a millisecond. It starts to hurt only when the emissions are expensive: swapping decor for a thousand regions on one tick is a rendering problem, not a chain problem, so spread the visual updates across frames.

Going further

• Markov random fields, for what coupled regions become mathematically.
• Cellular automata, the deterministic cousin of a coupled regime grid.
• Continuous-time Markov chains, if you want transitions at random moments rather than fixed ticks.
• Baum-Welch, for fitting $A$ from play logs once you have them.
• Layered generation, for seed derivation and per-region sub-streams.