How do you pick an item from a weighted loot table so each item drops in proportion to its weight?
answer
- one draw over the total weight
- running totals, not repeated entries
- first running total above the draw
- binary search on prefix sums
- constant time with paired columns
basics
~20 sSum 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 sBuild 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 linesfunction 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 logo deeper
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.
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.
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.
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.