Pseudo-random numbers

Why you need this

The hub page promises that a map is a seed plus a parameter file: type the same seed, get the same map. That promise depends entirely on the random number generator being deterministic, meaning it produces the same sequence every time it starts from the same seed. Math.random() does not offer that. Every technique in this cluster that draws a random number, which is all of them, draws from a seeded generator instead. This page shows one, and the handful of habits that keep "same seed, same map" true.

The idea

A pseudo-random number generator (PRNG) is a small machine with three parts.

• State: a few bytes of memory, typically one or more 32-bit integers.
• Step function: a fixed arithmetic recipe that turns the current state into the next state.
• Output: a number derived from the state, usually scaled to the interval $[0, 1)$.

Every call runs the step function once and returns one output. Nothing about it is random. The output looks random because the step function scrambles bits thoroughly enough that no simple pattern is visible, and because the state cycles through billions of values before repeating.

The seed is the starting state. Set the state to the seed, call the generator ten times, and you get ten numbers. Set the state to the same seed again and call it ten times, and you get the same ten numbers in the same order. That is determinism, and it is the whole point.

Written as a recurrence: with state $s_t$ at step $t$, step function $f$, and output function $g$,

$$s_{t+1} = f(s_t), \qquad u_t = g(s_t), \qquad s_0 = \text{seed}.$$

Each $u_t$ is a draw $u \sim \mathrm{Uniform}(0, 1)$, a number at least 0 and less than 1 with every sub-interval equally likely.

Why not Math.random()

Math.random() is a PRNG too, but the browser picks its seed for you when the page loads and gives you no way to read or set it. A map built from it is unrepeatable: reload the page and the sequence is different. The only way to keep such a map is to store every tile, which is the thing this whole cluster is trying to avoid. So the rule in this cluster is absolute: no Math.random() anywhere in a generator, not even for a decor flourish.

mulberry32

This is the generator the demos on this site use. It has one 32-bit integer of state, a period of $2^{32}$ (about 4.3 billion draws before the sequence repeats), and passes the usual statistical tests for game use. It is not suitable for anything security related, such as tokens or passwords, because an attacker who sees a few outputs can recover the state.

function mulberry32(seed) {
  let a = seed >>> 0;                      // state: one unsigned 32-bit int
  return function () {
    a = (a + 0x6D2B79F5) | 0;              // step
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;  // output in [0, 1)
  };
}

Usage: const rng = mulberry32(12345); rng(); rng(); returns the same two numbers on every machine, every time. The >>> 0 casts force JavaScript to treat the value as an unsigned 32-bit integer, and Math.imul multiplies 32-bit integers without the precision loss of ordinary floating-point multiplication.

Worked example

Helpers you will need on every page

An integer in a closed range and a shuffle. Both take the generator as an argument so that every draw is traceable to a seed.

// integer from lo to hi inclusive
function randInt(rng, lo, hi) {
  return lo + Math.floor(rng() * (hi - lo + 1));
}

// Fisher-Yates shuffle, in place
function shuffle(rng, arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = randInt(rng, 0, i);
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

With randInt(rng, 1, 6), a draw of $u = 0.62$ gives $1 + \lfloor 0.62 \times 6 \rfloor = 1 + 3 = 4$. Fisher-Yates walks from the last index down, swapping each element with a random one at or before it, so every ordering is equally likely and each element is touched once.

One seed, many independent streams

A generator produces one sequence. A map generator has many consumers: the biome chooser, the tile filler in each chunk, the decor sprinkler, the regime ticker. If they all share one stream, adding a single extra draw in the decor code shifts every later draw and changes the biome layout. The fix is to give each consumer its own generator, seeded from the master seed combined with an identifier for that consumer.

Combining means hashing. A small integer hash that mixes two coordinates:

function hash2(x, y) {
  let h = (x * 374761393 + y * 668265263) | 0;
  h = Math.imul(h ^ (h >>> 13), 1274126177);
  return (h ^ (h >>> 16)) >>> 0;
}

const seed = 12345;
const biomeRng = mulberry32(seed ^ hash2(1, 0));      // stream id 1
const chunkRng = (cx, cy) => mulberry32(seed ^ hash2(cx + 1000, cy + 1000));

Now chunk $(3, 7)$ always gets the same generator regardless of how many chunks were generated before it, and regardless of what the decor code did. This is what lets Layered generation regenerate any single chunk on demand.

Same seed, same parameters, same map

The map is a pure function of two inputs: the seed and the parameter file (tile weights, transition tables, thresholds). Change either and you get a different map; keep both and you get the same one, on any machine, today or in a year. So a save file stores a 32-bit seed and a version number for the parameter file, not a $512 \times 512 \times 3$ array of tile ids. Storing the map instead costs roughly 786 thousand ids for that size, cannot regenerate a chunk the player has not visited yet, and cannot be tweaked afterwards by turning a knob. Storing the seed costs four bytes and does all three.

The only legitimate reason to store tiles is player edits. Store those as a diff on top of the generated map: seed, parameters, then a list of (x, y, new id) overrides.

In a map generator

• Catalog: no randomness. The catalog is a deterministic slice of the tile sheets.
• Layout: a Markov chain over biomes or an HMM over columns draws its next state from a row of a table with one $u$ per step. Each layer gets its own stream.
• Fill: Wave Function Collapse picks a cell and a tile with two draws per step; cellular automata use one draw per cell for the initial fill; noise fields hash the seed with lattice coordinates to place their random lattice values.
• Regime over time: one stream per region, seeded by region id, so a region's history is reproducible from the seed and the tick count.
• Export: the manifest records the seed and the parameter file version. That pair is the map.

Common mistakes

• A stray Math.random(). Symptom: the map is "almost" the same on reload, with one layer, often decor, scrambled. Search the generator for the call and pass a seeded rng instead.
• Changing the order of draws. You reorder two loops, or add a new random feature before an old one, and every existing seed now produces a different map. Same seed, same parameters, different output. Symptom: saved seeds stop matching their screenshots. Isolate consumers into separate streams so that a change in one cannot shift another.
• Consuming a draw conditionally. if (rare) rng() means the number of draws depends on earlier results, so downstream streams shift whenever the condition flips. Draw unconditionally and ignore the value if not needed, or use a separate stream.
• Using a float seed. mulberry32(0.5) casts to 0, and so does mulberry32(0.3). Every "different" seed gives the same map. Seeds are integers.
• Seeding with the current time and not recording it. Fine for a fresh random map, but write the seed into the save file or the map is unrecoverable.
• Same seed for every chunk. Every chunk comes out identical. Combine the seed with the chunk coordinates through a hash, and make sure the hash treats $x$ and $y$ differently. A symmetric mix such as x + y makes hash2(1, 2) and hash2(2, 1) collide, so the chunks at $(1, 2)$ and $(2, 1)$ come out identical.

Cost

Each call to mulberry32 is a handful of integer operations, $O(1)$ time and one 32-bit integer of state, $O(1)$ memory per stream. Generating a map with $W \times H$ cells and $k$ draws per cell costs $O(k \cdot W \cdot H)$ draws, which for a $256 \times 256$ map with a few draws per cell is a few hundred thousand calls and takes well under a millisecond in a modern browser. Cost never comes from the generator itself. It comes from forgetting that the period is $2^{32}$: a long-running regime chain that draws once per region per tick, over thousands of regions and hours of play, is safe, but a stress test that draws $10^{10}$ times from one stream has wrapped around twice.

Going further

• Layered generation, which hands seeds down from map to chunk to cell.
• Random variables and distributions, for turning a uniform $u$ into a weighted choice from a table.
• Noise fields, where the lattice values are hashed from coordinates rather than drawn in sequence.
• Splitmix and xoshiro, two other small generators with longer periods and better statistical behavior, if mulberry32 ever proves too short.
• Linear congruential generators, the historical family, and why their low bits are poorly random.