Entropy

Why you need this

Wave Function Collapse fills a grid by repeatedly choosing one undecided cell and picking its tile. Which cell? The one it is least unsure about, so that forced choices happen before free ones and contradictions surface early. "Least unsure" needs a number, and that number is entropy.

The idea

Definition

For a categorical distribution $p$ over $N$ outcomes with probabilities $p_1, \dots, p_N$, the Shannon entropy is

$$H(p) = -\sum_{k=1}^{N} p_k \log p_k$$

with the convention that a term with $p_k = 0$ contributes 0. With the natural log the unit is the nat; with $\log_2$ it is the bit.

Every term is non-negative: for $p_k$ in $(0, 1]$, $\log p_k \le 0$, so $-p_k \log p_k \ge 0$. Hence $H(p) \ge 0$.

Intuition

Three readings of the same number:

• How unsure you are before seeing the outcome. A coin flip is more uncertain than a loaded die that lands 6 nine times in ten.
• Average surprise. $-\log p_k$ is the surprise of seeing outcome $k$: rare outcomes are big surprises. Entropy is the probability-weighted average of the surprise, $\sum_k p_k \cdot (-\log p_k)$.
• Average yes-or-no questions (in bits) needed to pin down the outcome. Four equally likely tiles take two questions; a certain tile takes none.

The extremes

A certain outcome gives 0. If $p = (1, 0, 0, 0)$, the only non-zero term is $-1 \cdot \log 1 = 0$. Nothing left to learn.

Uniform gives the maximum, $\log N$. If every $p_k = 1/N$, each term is $-\frac{1}{N} \log \frac{1}{N} = \frac{1}{N} \log N$, and there are $N$ of them, so $H = \log N$. No other distribution over $N$ outcomes scores higher. For $N = 4$ that is $\log 4 \approx 1.386$ nats, or exactly 2 bits.

Two consequences follow. Fewer possible outcomes means a lower ceiling: uniform over 2 is $\log 2 \approx 0.693$, under half of uniform over 4. And skewing a distribution toward one outcome always lowers it.

Bits versus nats

Changing the base of the log multiplies every entropy by the same constant: $H_{\text{bits}} = H_{\text{nats}} / \log 2 \approx H_{\text{nats}} / 0.693$. So $\log 4 = 1.386$ nats is $2$ bits. Because the factor is the same for every distribution, the ranking of distributions by entropy never depends on the base. Wave Function Collapse only ever asks "which cell has the smallest entropy", so it does not care which base you use.

Entropy from raw weights

A cell in Wave Function Collapse holds unnormalized weights $w_k$ for its remaining tiles, with $W = \sum_k w_k$ and $p_k = w_k / W$. Substituting into the definition and using $\log(w_k / W) = \log w_k - \log W$:

$$H = \log W - \frac{1}{W} \sum_k w_k \log w_k$$

This form is handy because a cell can keep running totals of $\sum w_k$ and $\sum w_k \log w_k$ and update them by subtraction when a tile is removed, instead of recomputing from scratch.

Worked example

Four tiles: grass, dirt, rock, water. Three distributions, plus one more for contrast.

Name	$p$	Terms $-p_k \log p_k$	$H$ (nats)	$H$ (bits)
A, uniform	(0.25, 0.25, 0.25, 0.25)	$4 \times 0.347$	1.386	2.000
B, mostly grass	(0.7, 0.1, 0.1, 0.1)	$0.250 + 3 \times 0.230$	0.940	1.357
C, two tiles left	(0.5, 0.5, 0, 0)	$2 \times 0.347 + 0 + 0$	0.693	1.000
D, almost decided	(0.97, 0.01, 0.01, 0.01)	$0.030 + 3 \times 0.046$	0.168	0.242

The arithmetic for B: $-0.7 \log 0.7 = 0.7 \times 0.357 = 0.250$, and $-0.1 \log 0.1 = 0.1 \times 2.303 = 0.230$, three times, for a total of $0.940$.

Compare C and D. C has only two options and D has four, so a "count the options" rule would collapse C first. But D's weights say the cell is 97 percent decided already, and entropy ranks it first, at 0.168 against 0.693. The two rules agree whenever weights are roughly even and disagree when they are skewed.

function entropy(weights) {
  const W = weights.reduce((s, w) => s + w, 0);
  let sumWLogW = 0;
  for (const w of weights) if (w > 0) sumWLogW += w * Math.log(w);
  return Math.log(W) - sumWLogW / W;    // nats
}
console.log(entropy([1, 1, 1, 1]));    // 1.3862943611198906
console.log(entropy([7, 1, 1, 1]));    // 0.9404479886553267
console.log(entropy([1, 1, 0, 0]));    // 0.6931471805599453
console.log(entropy([97, 1, 1, 1]));   // 0.1677005368398108

The weights here are integers rather than probabilities, and the function normalizes for you. Multiply every weight by 10 and each line prints the same number.

In a map generator

• Fill. Wave Function Collapse repeatedly picks the undecided cell whose remaining tile weights have the lowest entropy, collapses it, and propagates the consequences to its neighbors. Cells with one tile left have entropy 0 and are already decided. The cheap approximation many implementations use is the count of remaining options plus a tiny random tie-break, for example the count plus $u \times 10^{-6}$ with $u \sim \mathrm{Uniform}(0, 1)$ from the seeded generator. The tie-break matters: on a fresh grid every cell has the same entropy, and without it the scan always picks the first cell, giving every map the same top-left-to-bottom-right sweep regardless of seed.
• Layout. The entropy of a row of the transition matrix $A$ says how decisive that state is. A row near 0 always goes to the same next state; a row near $\log N$ is a coin flip across all $N$. After fitting with Baum-Welch, rows with high entropy are rows the training data did not pin down.
• Regime over time. The same audit applies to a regime table: a high-entropy row is a region whose next state is nearly random, which may or may not be the design intent.

Common mistakes

• Taking $\log 0$. $0 \times (-\infty)$ is NaN. Symptom: every cell reports NaN entropy and the picker chooses cell 0 forever. Skip zero weights, as the code above does.
• Plugging raw weights into $-\sum w \log w$. Symptom: entropy comes out negative, or grows when you scale all weights up, so heavily weighted cells look "uncertain".
• Picking the highest entropy instead of the lowest. Symptom: contradictions appear everywhere at once and the solver restarts constantly.
• No tie-break. Symptom: a visible diagonal sweep and the same structure for every seed.
• Recomputing every cell every step. Symptom: fine at 20 by 20, unusable at 200 by 200. Update only the cells whose options changed, and keep them in a priority queue.
• Treating option count and entropy as the same thing. They rank C and D above in opposite orders. Symptom: mostly cosmetic, but nearly-forced cells get collapsed late and can trigger contradictions that entropy would have avoided.

Cost

Computing $H$ for one cell with $T$ remaining tiles is $O(T)$. A naive Wave Function Collapse scans every undecided cell every step: with a $W \times H$ grid that is $O(W H T)$ per step and $W H$ steps, so $O((WH)^2 T)$ overall. With incremental updates and a priority queue, choosing a cell is $O(\log(WH))$ and each cell touched by propagation is $O(T)$ to update. The naive version starts to hurt around a 100 by 100 grid with a couple of hundred tiles.

Going further

• Wave Function Collapse, the consumer of this number.
• Constraint satisfaction: the minimum-remaining-values heuristic is the same idea under another name.
• Cross-entropy and KL divergence, for comparing a generated map's tile mix against a target mix.
• Shannon's 1948 paper, "A Mathematical Theory of Communication".