skip to content

Randomness and Noise

How game PRNGs work and why seeds make replays reproducible, unbiased shuffles, weighted loot drops and gradient noise (Perlin, Simplex). Interviewers ask because loot and procgen are daily work.

on this pageshow

explore

questions

5

How do you pick an item from a weighted loot table so each item drops in proportion to its weight?

level: juniorimportance: must knowfreq 48%

answer

  1. one draw over the total weight
  2. running totals, not repeated entries
  3. first running total above the draw
  4. binary search on prefix sums
  5. constant time with paired columns

basics

~20 s

Sum the weights, draw one uniform number in [0, total), then return the first item whose running (cumulative) total is greater than the draw. Each item owns a slice of the range exactly as wide as its weight.

solid answer

~50 s

Build a prefix-sum array once: weights `70, 25, 5` (common, rare, legendary) give running totals `70, 95, 100`. Draw `r` uniformly in `[0, 100)` and return the first index whose total is greater than `r`: `r < 70` is common, `70 <= r < 95` is rare, `95 <= r < 100` is legendary. A linear scan is fine for a handful of entries; for long tables, binary-search the prefix sums for `O(log n)` per draw, which works in any item order because running totals of non-negative weights never decrease. The classic bugs are an inclusive upper bound that runs off the end, comparing with `<=` instead of `<`, and float totals that drift; integer weights avoid most of them. For a hot table drawn millions of times, the alias method trades an `O(n)` build for `O(1)` draws.

code

pseudocode · 19 lines
pseudocode
function build_totals(weights):
    totals = new array of length(weights)
    running = 0
    for i from 0 to length(weights) - 1:
        running = running + weights[i]
        totals[i] = running
    return totals

function pick(totals, rng):
    r = rng.int_below(totals[last])      // uniform integer in 0 .. total - 1
    lo = 0
    hi = length(totals) - 1
    while lo < hi:                        // first index with totals[i] > r
        mid = (lo + hi) / 2               // integer division
        if totals[mid] > r:
            hi = mid
        else:
            lo = mid + 1
    return lo

go deeper

for a junior

Recall the number-line picture: running totals, one uniform draw in a half-open range, and the first total greater than the draw. Be ready to walk a 70/25/5 table by hand.

for a middle

Explain the boundary traps (inclusive upper bound, less-or-equal comparison, float totals) and why binary search works on prefix sums in any item order.

for a senior

Choose the structure from the access pattern: scan, binary search, alias table or Fenwick tree, depending on table size, draw rate and how often weights change at run time.

for a principal

Treat drop tables as data with tests: a shared selection routine, integer weights, a statistical check in the build, and draws from the loot stream so seeded replays stay reproducible.

## The idea: every item owns a slice of one number line A **weighted loot table** lists items with **weights**: relative numbers that say how often each should drop compared with the others. Weights do not have to sum to 1 or to 100. If a chest holds `common: 70`, `rare: 25` and `legendary: 5`, the total is 100 and the legendary drops 5 times in 100 on average; double every weight and nothing changes. The standard technique lays the weights end to end on a number line from 0 to the total. The common item owns `[0, 70)`, the rare item `[70, 95)`, the legendary `[95, 100)`. One **uniform** random number in `[0, total)` lands in each slice with probability equal to the slice's width divided by the total, which is exactly the item's weight share. ## Building the table and drawing from it 1. Compute the **prefix sums** (running totals) once when the table loads: `70, 95, 100`. 2. Draw `r` uniformly in `[0, total)`: half-open, so the total itself can never come up. 3. Return the **first** index whose running total is strictly greater than `r`. With integer weights, draw an integer in `0 .. total - 1`. With a draw of `r = 95`, the first total greater than 95 is 100, so the legendary drops; a draw of `r = 94` still gives the rare. A **linear scan** costs `O(n)` per draw and is the right choice for a table of a few entries. For a table of hundreds of entries, a **binary search** for the first total greater than `r` costs `O(log n)`. Binary search works whatever order the items are listed in, because the prefix sums of non-negative weights never decrease. ## Edge cases that ship as bugs - **Inclusive upper bound.** Drawing an integer in `0 .. total` inclusive gives one extra value that no slice covers; the scan runs off the end or quietly returns the last item, biasing it. - **`<=` instead of `<`.** Using "first total greater than or equal to `r`" shifts every boundary by one: with integer draws, `r = 70` now returns the common item, so common gets 71 of 100 values and the legendary only 4. - **Zero weights.** A zero-weight item has an empty slice and must never be returned; check that the search does not land on it at a boundary. - **Floating-point totals.** Summing float weights and scaling a float in `[0, 1)` by the total can, through rounding, produce a value equal to the total. Clamp the result to the last index with a non-zero weight, or keep weights as integers. - **Rolling each item separately.** Giving every item its own roll and taking the highest does not give proportional odds: with weights 2 and 1 and rolls uniform in `[0, 2]` and `[0, 1]`, the first item wins 3 times in 4, not 2 in 3. ## Faster draws: the alias method When a table is drawn constantly (a horde mode that rolls a drop for every kill, or a spawner rolling every enemy's type), the **alias method** gives `O(1)` draws. It rescales the weights so their average is 1, then cuts them into `n` columns of height exactly 1, where each column holds part of one item and, above a threshold, its **alias**: one other item that tops the column up. For `70, 25, 5` the scaled heights are `2.1, 0.75, 0.15`. The legendary column keeps `0.15` and is topped up by the common item; the rare column keeps `0.75` and is topped up by the common item; the common item's own column is left with exactly 1. Check: common gets `(1 + 0.25 + 0.85) / 3 = 0.7`, rare `0.75 / 3 = 0.25`, legendary `0.15 / 3 = 0.05`. A draw is two uniform numbers: pick a column `i` uniformly, then flip a biased coin: return `i` if `u < prob[i]`, otherwise `alias[i]`. | Method | Build | Per draw | Memory | Weight change | |---|---|---|---|---| | Linear scan over running totals | `O(n)` | `O(n)` | `n` totals | rebuild `O(n)` | | Binary search over prefix sums | `O(n)` | `O(log n)` | `n` totals | rebuild `O(n)` | | Alias table | `O(n)` | `O(1)` | two arrays of `n` | rebuild `O(n)` | | Array with one entry per weight unit | `O(total)` | `O(1)` | `total` entries | rebuild `O(total)` | ## When weights change at run time A table whose weights shift every roll (a drop chance that rises after each miss, luck stats, difficulty scaling) changes the trade-off. Every method above needs a rebuild, so when weights change about as often as you draw, a plain linear scan with no precomputation is often the cheapest. A **Fenwick tree** (binary indexed tree) over the weights updates one weight and draws in `O(log n)` each, which suits large tables that change one entry at a time. Whatever the structure, the draw should come from the generator stream that owns loot, so a seeded run gives the same drops on replay.

  • How does the alias method reach constant time per draw?
    It rescales weights to average 1 and splits them into `n` columns of height 1, each holding one item's share plus at most one alias item on top. A draw picks a column uniformly and flips a biased coin against that column's threshold: two random numbers and one comparison, independent of `n`. The build is `O(n)` with two worklists of under-full and over-full columns.
  • Why not fill an array with 70 copies of common, 25 of rare and 5 of legendary and index it?
    For small integer weights it is correct and `O(1)` per draw, but memory grows with the total weight rather than the item count. A weight of 1 in 100,000 needs a 100,000-entry array, fractional weights need scaling and rounding, and every change rebuilds the whole array.
  • A designer wants the legendary chance to rise after every miss until it drops; what changes in the data structure?
    The weights now change on every roll, so precomputed structures are rebuilt constantly. For a short table, skip precomputation and scan the live weights each draw. For a large table that changes one entry at a time, a Fenwick tree updates a weight and finds the slice in `O(log n)` each, while an alias table would need a full `O(n)` rebuild.

  • Weights must be normalised to sum to exactly 1 before a draw works.
  • Drawing an integer from 0 to the total inclusive is harmless.
  • Give every item its own roll and drop whichever rolled highest.
  • Binary search over the totals needs the items sorted by weight first.
  • The alias method gives slightly different odds than a cumulative table.
open as a page

Why is a shuffle that swaps every slot with any random index biased, and how does Fisher-Yates make every ordering equally likely?

level: middleimportance: must knowfreq 45%

basics

~20 s

Swapping every slot with any of n indices gives n^n equally likely sequences, which cannot split evenly over n! orderings. Fisher-Yates swaps slot i only with an index in [0, i], giving exactly n! equally likely paths, one per ordering.

open as a page

When scattering dropped loot uniformly inside a circle around a defeated enemy, why must the random radius use a square root?

level: middleimportance: should knowfreq 30%

basics

~20 s

Area grows with the square of the radius, so a radius drawn as radius * u crowds points toward the centre. Drawing radius * sqrt(u) with an angle of 2 * pi * v makes every equal patch of the disk equally likely.

open as a page

For a terrain heightmap, how do value, Perlin and Simplex noise differ, and what do fBm octaves add on top?

level: middleimportance: should knowfreq 40%

basics

~20 s

Value noise blends random heights stored at grid points and looks blocky; Perlin noise blends random gradients for smoother, less grid-bound hills; Simplex noise uses a triangle grid with fewer corners and artifacts. fBm sums octaves of rising frequency and falling amplitude.

open as a page

Players of a roguelike share a run seed, yet the same seed gives different loot on some machines; how do you find and fix the divergence?

level: seniorimportance: should knowfreq 36%

basics

~20 s

A seed replays only when every gameplay draw happens in the same order with the same algorithm. Log draws on both machines and diff for the first mismatch, then give gameplay its own codebase-owned generator streams that cosmetic, frame-rate or thread-order draws never touch.

open as a page