Implement seeded PRNG with deterministic sub-RNG derivation

rng/ is the load-bearing primitive for simulation determinism
(ARCHITECTURE.md §26). All gameplay randomness routes through
createRNG; Math.random is forbidden in gameplay code by ESLint.

  rng/derive.ts    xmur3 string hash + deriveSeed(parentSeed, label),
                   stable across processes and runs
  rng/seeded.ts    SeededRNG interface, mulberry32 implementation,
                   next / nextInt / nextBool / pick / weightedPick / sub
  rng/index.ts     public re-exports

Sub-RNG derivation is the key technical move: seeding a child with
hash(parent_seed + label) lets NPCs' trajectories be regenerated
deterministically from their identity tuple alone — which is how
Tier 3 NPCs stay off-disk until the player needs them.

29 determinism tests in tests/determinism/rng.test.ts cover: same
seed → same sequence, sub-RNG independence from parent consumption,
sub-order matters, input validation, and a byte-level inline
snapshot that locks the PRNG output for seed "hollowdark". The
snapshot is load-bearing — if mulberry32 or xmur3 changes, every
existing save diverges, so treat a snapshot break as a migration
concern, not an update-the-snapshot fix.

4 files changed, 387 insertions, 0 deletions

diff --git a/rng/derive.ts b/rng/derive.ts
new file mode 100644
index 0000000..9bb728d
--- /dev/null
+++ b/rng/derive.ts
@@ -0,0 +1,31 @@
+/**
+ * Deterministic string hashing and sub-seed derivation. Shared between the
+ * PRNG and any other system that needs stable-across-runs uint32 from
+ * string keys.
+ */
+
+/**
+ * xmur3 string hash. Returns a uint32. Pure function — same input always
+ * produces the same output.
+ */
+export function hashString(input: string): number {
+  let h = 1779033703 ^ input.length
+  for (let i = 0; i < input.length; i++) {
+    h = Math.imul(h ^ input.charCodeAt(i), 3432918353)
+    h = (h << 13) | (h >>> 19)
+  }
+  h = Math.imul(h ^ (h >>> 16), 2246822507)
+  h = Math.imul(h ^ (h >>> 13), 3266489909)
+  h ^= h >>> 16
+  return h >>> 0
+}
+
+/**
+ * Derive a child seed from a parent seed and a label. Stable: same
+ * (parentSeed, label) always produces the same child seed, which is what
+ * lets Tier 3 NPCs be regenerated on demand from their (world, identity)
+ * tuple without storing their state.
+ */
+export function deriveSeed(parentSeed: number, label: string): number {
+  return hashString(`${parentSeed >>> 0}:${label}`)
+}
diff --git a/rng/index.ts b/rng/index.ts
new file mode 100644
index 0000000..fbc4251
--- /dev/null
+++ b/rng/index.ts
@@ -0,0 +1,2 @@
+export { createRNG, type SeededRNG } from 'rng/seeded'
+export { hashString, deriveSeed } from 'rng/derive'
diff --git a/rng/seeded.ts b/rng/seeded.ts
new file mode 100644
index 0000000..8aff2fb
--- /dev/null
+++ b/rng/seeded.ts
@@ -0,0 +1,121 @@
+import { deriveSeed, hashString } from 'rng/derive'
+
+/**
+ * Seeded PRNG. All gameplay randomness routes through this interface —
+ * Math.random is forbidden in gameplay code (see ARCHITECTURE.md §26
+ * and eslint.config.js).
+ *
+ * Guarantees:
+ *   - Same seed produces the same infinite sequence, bit-for-bit.
+ *   - sub(label) produces a deterministic child stream, independent of
+ *     how the parent stream is consumed.
+ *   - Byte-level reproducibility across runs and machines.
+ */
+export interface SeededRNG {
+  readonly seed: number
+  /** Float in [0, 1). */
+  next(): number
+  /** Integer in [min, max], both inclusive. */
+  nextInt(min: number, max: number): number
+  /** Bernoulli draw with the given success probability. */
+  nextBool(probability: number): boolean
+  /** Uniform choice from a non-empty array. */
+  pick<T>(items: readonly T[]): T
+  /** Weighted choice from a non-empty list of (value, weight) tuples. */
+  weightedPick<T>(items: readonly (readonly [T, number])[]): T
+  /** Derive a new, independent RNG keyed by label and this RNG's seed. */
+  sub(label: string): SeededRNG
+}
+
+/**
+ * mulberry32 — 32-bit PRNG. Small, fast, and has good statistical
+ * properties for game-scale use. Not cryptographic; not intended to be.
+ */
+function mulberry32(seed: number): () => number {
+  let state = seed >>> 0
+  return () => {
+    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
+  }
+}
+
+class SeededRNGImpl implements SeededRNG {
+  readonly seed: number
+  readonly #gen: () => number
+
+  constructor(seed: number) {
+    this.seed = seed >>> 0
+    this.#gen = mulberry32(this.seed)
+  }
+
+  next(): number {
+    return this.#gen()
+  }
+
+  nextInt(min: number, max: number): number {
+    if (!Number.isFinite(min) || !Number.isFinite(max)) {
+      throw new Error(`rng.nextInt: bounds must be finite (got ${min}, ${max})`)
+    }
+    const lo = Math.ceil(min)
+    const hi = Math.floor(max)
+    if (hi < lo) {
+      throw new Error(`rng.nextInt: empty range [${min}, ${max}]`)
+    }
+    return lo + Math.floor(this.#gen() * (hi - lo + 1))
+  }
+
+  nextBool(probability: number): boolean {
+    if (probability < 0 || probability > 1 || !Number.isFinite(probability)) {
+      throw new Error(`rng.nextBool: probability must be in [0, 1] (got ${probability})`)
+    }
+    return this.#gen() < probability
+  }
+
+  pick<T>(items: readonly T[]): T {
+    if (items.length === 0) {
+      throw new Error('rng.pick: items is empty')
+    }
+    const idx = Math.floor(this.#gen() * items.length)
+    return items[idx] as T
+  }
+
+  weightedPick<T>(items: readonly (readonly [T, number])[]): T {
+    if (items.length === 0) {
+      throw new Error('rng.weightedPick: items is empty')
+    }
+    let total = 0
+    for (const [, weight] of items) {
+      if (!Number.isFinite(weight) || weight < 0) {
+        throw new Error(`rng.weightedPick: invalid weight ${weight}`)
+      }
+      total += weight
+    }
+    if (total <= 0) {
+      throw new Error('rng.weightedPick: total weight is zero')
+    }
+    const roll = this.#gen() * total
+    let cumulative = 0
+    for (const [value, weight] of items) {
+      cumulative += weight
+      if (roll < cumulative) return value
+    }
+    // Numerical safety: if we fall off the end due to floating-point drift,
+    // return the last item rather than throw.
+    return items[items.length - 1]![0]
+  }
+
+  sub(label: string): SeededRNG {
+    return new SeededRNGImpl(deriveSeed(this.seed, label))
+  }
+}
+
+/**
+ * Create a new seeded RNG. Accepts a string (which is hashed) or a number
+ * (used directly as a uint32 seed).
+ */
+export function createRNG(seed: string | number): SeededRNG {
+  const numeric = typeof seed === 'number' ? seed >>> 0 : hashString(seed)
+  return new SeededRNGImpl(numeric)
+}
diff --git a/tests/determinism/rng.test.ts b/tests/determinism/rng.test.ts
new file mode 100644
index 0000000..ee41716
--- /dev/null
+++ b/tests/determinism/rng.test.ts
@@ -0,0 +1,233 @@
+import { describe, expect, test } from 'vitest'
+import { createRNG, deriveSeed, hashString } from 'rng'
+
+describe('hashString', () => {
+  test('is deterministic', () => {
+    expect(hashString('hello')).toBe(hashString('hello'))
+  })
+
+  test('different inputs produce different hashes', () => {
+    expect(hashString('hello')).not.toBe(hashString('world'))
+  })
+
+  test('handles empty string without crashing', () => {
+    expect(hashString('')).toBeGreaterThanOrEqual(0)
+  })
+
+  test('returns a uint32', () => {
+    const h = hashString('any input')
+    expect(Number.isInteger(h)).toBe(true)
+    expect(h).toBeGreaterThanOrEqual(0)
+    expect(h).toBeLessThan(2 ** 32)
+  })
+})
+
+describe('deriveSeed', () => {
+  test('is deterministic', () => {
+    expect(deriveSeed(42, 'label')).toBe(deriveSeed(42, 'label'))
+  })
+
+  test('different labels from same parent produce different seeds', () => {
+    expect(deriveSeed(42, 'a')).not.toBe(deriveSeed(42, 'b'))
+  })
+
+  test('different parents with the same label produce different seeds', () => {
+    expect(deriveSeed(1, 'x')).not.toBe(deriveSeed(2, 'x'))
+  })
+
+  test('normalizes negative parent seeds via uint32 cast', () => {
+    expect(deriveSeed(-1, 'x')).toBe(deriveSeed(0xffffffff, 'x'))
+  })
+})
+
+describe('createRNG — equality of streams', () => {
+  test('same string seed produces the same sequence over 1000 draws', () => {
+    const a = createRNG('test-seed')
+    const b = createRNG('test-seed')
+    for (let i = 0; i < 1000; i++) {
+      expect(a.next()).toBe(b.next())
+    }
+  })
+
+  test('same numeric seed produces the same sequence', () => {
+    const a = createRNG(12345)
+    const b = createRNG(12345)
+    for (let i = 0; i < 100; i++) {
+      expect(a.next()).toBe(b.next())
+    }
+  })
+
+  test('different seeds produce different sequences', () => {
+    const a = createRNG('seed-a')
+    const b = createRNG('seed-b')
+    const drawsA = Array.from({ length: 16 }, () => a.next())
+    const drawsB = Array.from({ length: 16 }, () => b.next())
+    expect(drawsA).not.toEqual(drawsB)
+  })
+
+  test('string and equivalent-hash numeric seed produce the same sequence', () => {
+    const s = 'string-seed'
+    const str = createRNG(s)
+    const num = createRNG(hashString(s))
+    for (let i = 0; i < 50; i++) {
+      expect(str.next()).toBe(num.next())
+    }
+  })
+})
+
+describe('createRNG — output shape', () => {
+  test('next() returns values in [0, 1)', () => {
+    const rng = createRNG('range')
+    for (let i = 0; i < 10000; i++) {
+      const v = rng.next()
+      expect(v).toBeGreaterThanOrEqual(0)
+      expect(v).toBeLessThan(1)
+    }
+  })
+
+  test('nextInt stays within inclusive bounds', () => {
+    const rng = createRNG('int')
+    for (let i = 0; i < 1000; i++) {
+      const v = rng.nextInt(3, 7)
+      expect(v).toBeGreaterThanOrEqual(3)
+      expect(v).toBeLessThanOrEqual(7)
+      expect(Number.isInteger(v)).toBe(true)
+    }
+  })
+
+  test('nextInt with a single value always returns that value', () => {
+    const rng = createRNG('single')
+    for (let i = 0; i < 50; i++) {
+      expect(rng.nextInt(5, 5)).toBe(5)
+    }
+  })
+
+  test('nextInt rejects empty ranges', () => {
+    const rng = createRNG('range')
+    expect(() => rng.nextInt(10, 5)).toThrow()
+  })
+
+  test('nextBool rejects out-of-range probability', () => {
+    const rng = createRNG('bool')
+    expect(() => rng.nextBool(-0.1)).toThrow()
+    expect(() => rng.nextBool(1.5)).toThrow()
+  })
+
+  test('nextBool(0) is always false, nextBool(1) is always true', () => {
+    const rng = createRNG('edges')
+    for (let i = 0; i < 50; i++) {
+      expect(rng.nextBool(0)).toBe(false)
+      expect(rng.nextBool(1)).toBe(true)
+    }
+  })
+
+  test('pick throws on empty array', () => {
+    const rng = createRNG('empty')
+    expect(() => rng.pick([])).toThrow()
+  })
+
+  test('pick returns an element of the array', () => {
+    const items = ['a', 'b', 'c', 'd']
+    const rng = createRNG('pick')
+    for (let i = 0; i < 100; i++) {
+      expect(items).toContain(rng.pick(items))
+    }
+  })
+
+  test('weightedPick rejects empty / zero-total / negative weights', () => {
+    const rng = createRNG('wp')
+    expect(() => rng.weightedPick([])).toThrow()
+    expect(() =>
+      rng.weightedPick([
+        ['a', 0],
+        ['b', 0]
+      ])
+    ).toThrow()
+    expect(() => rng.weightedPick([['a', -1]])).toThrow()
+  })
+
+  test('weightedPick with overwhelming weight reliably selects that side', () => {
+    const rng = createRNG('skew')
+    let lowCount = 0
+    for (let i = 0; i < 500; i++) {
+      const pick = rng.weightedPick([
+        ['rare', 1],
+        ['common', 99]
+      ])
+      if (pick === 'rare') lowCount++
+    }
+    // Expected ~5, allow plenty of slack for variance; just confirm the
+    // distribution isn't inverted.
+    expect(lowCount).toBeLessThan(50)
+  })
+
+  test('weightedPick with a single item always returns that item', () => {
+    const rng = createRNG('one')
+    for (let i = 0; i < 50; i++) {
+      expect(rng.weightedPick([['only', 1]])).toBe('only')
+    }
+  })
+})
+
+describe('SeededRNG.sub — sub-RNG derivation', () => {
+  test('sub-RNG is deterministic across independent parent constructions', () => {
+    const a = createRNG('parent').sub('child')
+    const b = createRNG('parent').sub('child')
+    for (let i = 0; i < 100; i++) {
+      expect(a.next()).toBe(b.next())
+    }
+  })
+
+  test('different labels produce independent streams', () => {
+    const parent = createRNG('parent')
+    const a = parent.sub('branch-a')
+    const b = parent.sub('branch-b')
+    const drawsA = Array.from({ length: 10 }, () => a.next())
+    const drawsB = Array.from({ length: 10 }, () => b.next())
+    expect(drawsA).not.toEqual(drawsB)
+  })
+
+  test('consuming a sub-RNG does not advance the parent stream', () => {
+    const p1 = createRNG('p')
+    const p2 = createRNG('p')
+    const child = p1.sub('x')
+    for (let i = 0; i < 20; i++) child.next()
+    expect(p1.next()).toBe(p2.next())
+  })
+
+  test('deeply nested subs remain stable across runs', () => {
+    const chain1 = createRNG('root').sub('a').sub('b').sub('c')
+    const chain2 = createRNG('root').sub('a').sub('b').sub('c')
+    for (let i = 0; i < 50; i++) {
+      expect(chain1.next()).toBe(chain2.next())
+    }
+  })
+
+  test('sub() order matters', () => {
+    const ab = createRNG('root').sub('a').sub('b')
+    const ba = createRNG('root').sub('b').sub('a')
+    expect(ab.next()).not.toBe(ba.next())
+  })
+})
+
+describe('byte-level determinism snapshot', () => {
+  // Locks the PRNG implementation. Saved worlds depend on exact byte
+  // reproduction — if this test breaks, it means the PRNG changed, and
+  // every existing save relying on this seed will diverge. Treat failure
+  // as a migration concern, not a "just update the snapshot" fix.
+  test('createRNG("hollowdark").next() × 5 matches canonical sequence', () => {
+    const rng = createRNG('hollowdark')
+    const first5 = [rng.next(), rng.next(), rng.next(), rng.next(), rng.next()]
+    // Values computed from the current mulberry32 + xmur3 implementation.
+    // Reproducible locally via: createRNG('hollowdark').next() × 5.
+    expect(first5).toMatchInlineSnapshot(`
+      [
+        0.14088608953170478,
+        0.7713804871309549,
+        0.22113240463659167,
+        0.6266801964957267,
+        0.8969542379491031,
+      ]
+    `)
+  })
+})