Foundations: Types, Seeded Random Number Generator & Hex Math

Before writing a single line of Wave Function Collapse (WFC) logic, the pipeline needs a foundation: the data shapes that flow through every stage, a deterministic random number generator (RNG), and the hex-grid math that underpins all spatial reasoning. This entry builds those pieces.

Goal

Establish the type definitions, seeded RNG, and hex math utilities that every subsequent module depends on. By the end, you have a small library of pure functions that are independently testable and carry no runtime dependencies on the Entity Component System (ECS), Three.js, or any rendering code.

Prerequisites

None. This is the starting point.

Key Concepts

The data that flows through the pipeline

The WFC pipeline transforms data through a series of stages — taking a seed and config as input and producing vertex arrays as output. Three type definitions carry data between stages:

LevelConfig ──> [zone pass] ──> [tile pass] ──> [noise pass] ──> GeneratedLevel
                                                                   └── Map<string, TileVertexData[]>

LevelConfig is the input — it holds the master seed, grid dimensions, chunk radius, and biome identifier that together describe what level to generate. TileVertexData is a single vertex in the output, carrying a world position, height displacement, four splat-channel weights, texture indices, and an RGB tint. GeneratedLevel is the final result — it bundles the solved zone grid with a map of per-chunk vertex arrays, ready for the rendering system to consume.

Why determinism matters

The game stores only the seed in save data, not the generated level. Loading a save regenerates the level from its seed. If generation uses Math.random() anywhere, the same save file produces different terrain on every load. The seeded RNG guarantees that seed 42 always produces the exact same level, on every platform, every time.

Hex coordinate system

Hex grids can be addressed with several coordinate systems — offset, cube, or axial. This project uses axial coordinates (q, r) with flat-top orientation. The Red Blob Games hex grid reference covers all three systems in depth; the rationale for axial is summarized here.

Why axial over offset? Offset coordinates (the row/column approach used by rectangular grids) break when you need consistent neighbor math. Depending on whether a row is even or odd, the neighbor offsets change — every function that touches adjacency needs an if (row % 2) branch. Axial coordinates eliminate this: neighbor offsets are the same six (dq, dr) pairs regardless of position, which simplifies the WFC solver, chunk iteration, and boundary stitching.

Why axial over cube? Cube coordinates (q, r, s) where q + r + s = 0 are powerful for distance calculations and range queries, but the third axis s is always redundant (s = -q - r). Axial is cube with the s axis dropped — the same algorithms work, with one fewer coordinate to store and pass around. When cube math is needed (like the chunk cell iteration below), s is computed on the fly.

Flat-top means the hex has flat edges on top and bottom, with pointy corners on the left and right. The q axis runs horizontally, the r axis runs diagonally down-right.

Flat-top hex orientation:

        ___
       /   \        Corner 0 = East (0 degrees)
      /     \       Corner 1 = North-East (60 degrees)
     /       \      Corner 2 = North-West (120 degrees)
     \       /      Corner 3 = West (180 degrees)
      \     /       Corner 4 = South-West (240 degrees)
       \___/        Corner 5 = South-East (300 degrees)

Corners numbered 0-5 counterclockwise from East.

Six edges, each connecting two adjacent corners:

  Edge 0: corners 0-1 (E  side)   = direction E
  Edge 1: corners 1-2 (NE side)   = direction NE
  Edge 2: corners 2-3 (NW side)   = direction NW
  Edge 3: corners 3-4 (W  side)   = direction W
  Edge 4: corners 4-5 (SW side)   = direction SW
  Edge 5: corners 5-0 (SE side)   = direction SE

The conversion between axial and world-space positions uses the flat-top formulas:

axial → world:    x = HEX_SIZE × (3/2) × q
                  z = HEX_SIZE × (√3/2 × q + √3 × r)

world → axial:    q = (2/3) × x / HEX_SIZE
                  r = (−1/3 × x + √3/3 × z) / HEX_SIZE
                  (then cube-round to snap to the nearest hex)

These formulas live in hex-math.ts as hexToWorld and worldToHex. The world-to-axial direction requires cube rounding — converting to fractional cube coordinates (q, r, s), rounding each to the nearest integer, then adjusting the component with the largest rounding error so the constraint q + r + s = 0 holds. This is the standard approach described in the Red Blob Games rounding section.

Hexagonal chunk storage

Chunks are not rectangular — they are hexagonal. A chunk of radius R is the set of all hex cells reachable in R or fewer steps from a center cell. This produces a hex-shaped region, not a square one. Using hexagonal chunks means every chunk has exactly 6 neighbors (just like every hex cell), which keeps the WFC solver's boundary logic uniform — no special-casing for corners or edges of a rectangular grid.

Radius-2 hex chunk (19 cells):

        __    __
       /  \__/  \
       \__/  \__/
       /  \__/  \
    __/  \__/  \__
   /  \__/  \__/  \
   \__/  \__/  \__/
   /  \__/  \__/  \
   \__/  \__/  \__/
      \__/  \__/
         \__/

Storage shape. Internally, a chunk's cells are stored as a flat array produced by iterating the cube-coordinate constraint max(|q|, |r|, |s|) ≤ R (where s = -q - r). The iteration scans q from −R to +R, and for each q computes the valid range of r:

for q in [-R, R]:
    r_min = max(-R, -q - R)
    r_max = min( R, -q + R)
    for r in [r_min, r_max]:
        emit (q, r)

This produces exactly 3R² + 3R + 1 cells in a deterministic order. Every system that needs to walk all cells in a chunk — the WFC solver, the noise pass, the vertex builder — uses this same iteration, so array indices are consistent everywhere.

Coordinate spaces. Each cell has two sets of coordinates: local (q, r) relative to the chunk center (ranging from −R to +R), and global axial coordinates in the world. Converting between them is a simple offset by the chunk center's global position. The pipeline works in local coordinates during generation and converts to global only when producing final world-space vertex positions.

Keying convention. When chunks need to be stored in a map (for example, the GeneratedLevel.chunks output), the key is a string. The WFC pipeline uses "col,row" keys during generation (zone grid coordinates), while the rendering system uses "q_r" keys (global axial coordinates). The handoff in the chunk integration step (dev log 06) converts between these formats.

Chunk cell count

A hex chunk of radius R contains all cells within R steps of the center cell. The total cell count follows directly from the iteration above:

cells = 3R² + 3R + 1

Radius	Cells
1	7
2	19
4	61
8	217
16	817

This formula appears everywhere — sizing arrays, iterating cells, computing memory budgets.

Implementation Steps

Step 1: Define the zone and tile type enums

File: src/wfc/types.ts

These enums classify chunks and cells. Zone types describe the coarse layout (what kind of content a chunk holds). Tile types describe individual hex cells within a chunk.

/** Coarse chunk classification -- one per chunk in the zone grid. */
export enum ZoneType {
  RoadStraight = "road_straight",
  RoadLeft = "road_left",
  RoadRight = "road_right",
  Open = "open",
}

/** Fine cell classification -- one per hex cell in a chunk. */
export enum TileType {
  RoadFill = "road_fill",
  RoadEdge = "road_edge",
  Ground = "ground",
}

Zone types are used by the zone pass (dev log 03). Tile types are used by the tile pass (dev log 04). Defining them now keeps the type system consistent from the start.

Step 2: Define the vertex data shape

File: src/wfc/types.ts (append to same file)

Every vertex the pipeline produces has the same shape. This mirrors the VertexData consumed by the chunk rendering system, but lives in the WFC module with no rendering dependencies.

/** Per-vertex output from the terrain pipeline. */
export interface TileVertexData {
  /** World X position */
  x: number;
  /** World Z position */
  z: number;
  /** Y displacement from noise (height above the base plane) */
  height: number;
  /** Splat channel weights -- 4 channels, must sum to 1.0 */
  weights: [number, number, number, number];
  /** Texture index per splat channel (placeholder until biome integration) */
  textureIndices: [number, number, number, number];
  /** RGB tint multiplier -- [1,1,1] = no tint */
  tint: [number, number, number];
}

The weights array controls texture blending. Four channels allow up to 4 textures per vertex, blended by their respective weights. The textureIndices map each channel to a texture in the registry. The noise pass populates both fields; biome integration later replaces the placeholder indices with real texture identifiers.

Step 3: Define the level config and generated level shapes

File: src/wfc/types.ts (append)

/** Input to the generation pipeline. */
export interface LevelConfig {
  /** Master seed -- determines the entire level */
  seed: number;
  /** Zone grid width in chunks (e.g. 5) */
  gridWidth: number;
  /** Zone grid height in chunks (e.g. 12) */
  gridHeight: number;
  /** Hex chunk radius (cells from center to edge) */
  chunkRadius: number;
  /** Biome identifier for texture selection (placeholder for now) */
  biomeId: string;
}

/** Output of the generation pipeline. */
export interface GeneratedLevel {
  /** The solved zone grid from the zone pass */
  zoneGrid: WfcGrid;
  /** Per-chunk vertex arrays, keyed by "col,row" */
  chunks: Map<string, TileVertexData[]>;
}

/** A solved WFC grid -- array of cells with their collapsed state. */
export interface WfcGrid {
  width: number;
  height: number;
  cells: WfcCell[];
}

/** A single cell in a solved WFC grid. */
export interface WfcCell {
  /** Remaining valid states (1 element if collapsed, 0 if contradiction) */
  candidates: string[];
  /** The collapsed value, or null if not yet collapsed */
  collapsed: string | null;
}

The WfcGrid type is generic -- it carries string state identifiers. Both the zone pass (where states are like "road_straight:0") and the tile pass (where states are like "road_edge:2") use the same grid shape. The solver does not need to understand what the strings mean.

Step 4: Build the seeded random number generator

File: src/wfc/rng.ts

The RNG uses the mulberry32 algorithm: 32-bit state, one multiplication, one XOR shift. It passes statistical randomness tests (SmallCrush) and is fast enough for real-time generation.

/** Seeded pseudorandom number generator interface. */
export interface Rng {
  /** Returns a float in [0, 1) */
  (): number;
  /** Returns an integer in [0, max) */
  int(max: number): number;
  /** Returns a random element from the array */
  pick<T>(arr: readonly T[]): T;
  /** Fisher-Yates in-place shuffle, returns the same array */
  shuffle<T>(arr: T[]): T[];
}

/** Create a seeded RNG using the mulberry32 algorithm. */
export function createRng(seed: number): Rng {
  let state = seed | 0;

  function next(): number {
    state |= 0;
    state = (state + 0x6d2b79f5) | 0;
    let t = Math.imul(state ^ (state >>> 15), 1 | state);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  }

  const rng = next as Rng;
  rng.int = (max: number) => Math.floor(next() * max);
  rng.pick = <T>(arr: readonly T[]) => arr[Math.floor(next() * arr.length)];
  rng.shuffle = <T>(arr: T[]) => {
    for (let i = arr.length - 1; i > 0; i--) {
      const j = Math.floor(next() * (i + 1));
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
  };

  return rng;
}

The next() function is the core -- everything else is a convenience wrapper. The | 0 coercions keep the state as a 32-bit integer, which is what Math.imul expects.

Step 5: Add positional sub-seed derivation

File: src/wfc/rng.ts (append)

Each chunk needs its own sub-seed. Deriving sub-seeds positionally (from the master seed and the chunk's coordinates) rather than sequentially (from the Nth call to the parent RNG) ensures that modifying the grid layout does not cascade changes to unrelated chunks.

/**
 * Derive a sub-seed from a master seed and a position.
 * Uses a simple hash combining function. The output is
 * deterministic for a given (seed, q, r) triple.
 */
export function positionalSeed(masterSeed: number, q: number, r: number): number {
  let h = masterSeed | 0;
  h = (Math.imul(h ^ (q * 374761393), 668265263) + 374761393) | 0;
  h = (Math.imul(h ^ (r * 668265263), 374761393) + 668265263) | 0;
  h = (h ^ (h >>> 13)) | 0;
  h = Math.imul(h, 0x5bd1e995) | 0;
  h = (h ^ (h >>> 15)) | 0;
  return h >>> 0; // unsigned 32-bit
}

The hash constants are borrowed from MurmurHash. The key property: positionalSeed(42, 3, 7) always returns the same value, and changing q or r produces an unrelated value. No sequential dependency.

Step 6: Reference existing hex math utilities

File: src/utils/hex-math.ts (already exists)

The project already has hex math in src/utils/hex-math.ts. The WFC pipeline imports from there rather than duplicating:

• hexToWorld(q, r) -- axial coordinates to world XZ position
• worldToHex(x, z) -- world XZ to axial coordinates (with cube rounding)
• hexCorners(q, r) -- the 6 corner vertices of a hex cell

The WFC modules import these directly. No wrapper needed.

The project already has a hexChunkCells function in hex-math.ts that iterates all cells in a hex chunk of radius R. The WFC pipeline imports it directly:

/**
 * Iterate all axial coordinates within a hex chunk of the given radius.
 * Returns (3R^2 + 3R + 1) coordinate pairs centered on (0, 0).
 */
export function hexChunkCells(radius: number): Array<{ q: number; r: number }> {
  const cells: Array<{ q: number; r: number }> = [];
  for (let q = -radius; q <= radius; q++) {
    const r1 = Math.max(-radius, -q - radius);
    const r2 = Math.min(radius, -q + radius);
    for (let r = r1; r <= r2; r++) {
      cells.push({ q, r });
    }
  }
  return cells;
}

This uses the standard cube-coordinate constraint max(|q|, |r|, |s|) ≤ R (where s = -q - r) to enumerate cells in a hexagonal area.

Step 7: Add hex neighbor lookup

File: src/utils/hex-math.ts (append)

The WFC solver needs to find the 6 neighbors of any hex cell. Flat-top hex axial neighbor offsets:

/** Axial direction offsets for flat-top hexes, indexed 0-5 (E, NE, NW, W, SW, SE). */
export const HEX_DIRECTIONS: ReadonlyArray<{ dq: number; dr: number }> = [
  { dq: 1, dr: 0 },   // 0: E
  { dq: 1, dr: -1 },  // 1: NE
  { dq: 0, dr: -1 },  // 2: NW
  { dq: -1, dr: 0 },  // 3: W
  { dq: -1, dr: 1 },  // 4: SW
  { dq: 0, dr: 1 },   // 5: SE
];

/** Get the neighbor of (q, r) in the given direction (0-5). */
export function hexNeighbor(q: number, r: number, dir: number): { q: number; r: number } {
  const d = HEX_DIRECTIONS[dir];
  return { q: q + d.dq, r: r + d.dr };
}

/** Get the opposite direction index (0 <-> 3, 1 <-> 4, 2 <-> 5). */
export function oppositeDir(dir: number): number {
  return (dir + 3) % 6;
}

Direction 0 is East, and they go counterclockwise: E, NE, NW, W, SW, SE. The opposite of direction d is always (d + 3) % 6. These show up constantly in the solver's propagation step.

Visual Checkpoint

Create a small test script (or run in a browser console) that verifies the two foundation pieces:

RNG determinism test:

import { createRng } from "./wfc/rng";

const rng1 = createRng(42);
const rng2 = createRng(42);

const values1 = Array.from({ length: 10 }, () => rng1());
const values2 = Array.from({ length: 10 }, () => rng2());

console.log("RNG1:", values1);
console.log("RNG2:", values2);
console.log("Match:", JSON.stringify(values1) === JSON.stringify(values2));
// Expected: Match: true

Both arrays must be identical. If they diverge at any position, the mulberry32 state management has a bug.

Hex math round-trip test:

import { hexToWorld, worldToHex, hexChunkCells } from "./utils/hex-math";

// Round-trip: axial -> world -> axial should return the same coordinates
const testCoords = [
  { q: 0, r: 0 },
  { q: 3, r: -2 },
  { q: -5, r: 7 },
];

for (const { q, r } of testCoords) {
  const world = hexToWorld(q, r);
  const back = worldToHex(world.x, world.z);
  console.log(`(${q},${r}) -> world(${world.x.toFixed(2)}, ${world.z.toFixed(2)}) -> (${back.q},${back.r})`);
  console.assert(back.q === q && back.r === r, "Round-trip failed!");
}

// Cell count verification
const r4 = hexChunkCells(4);
console.log(`Radius 4 chunk: ${r4.length} cells (expected 61)`);
console.assert(r4.length === 61);

Expected output: all round-trips succeed, radius-4 chunk has exactly 61 cells.

What's Next

With types, RNG, and hex math in place, the next dev log builds the generic WFC solver. The solver takes a grid of cells in superposition and a compatibility function, and collapses them to a valid assignment. It has no knowledge of zones, tiles, or hexes -- that genericity is what lets us reuse it for both the zone pass and the tile pass.

Next: 02 - The Wave Function Collapse Solver