The idea: random jumps, the same picture every time
The chaos game needs a triangle, a die and a pencil:
- Put the pencil anywhere.
- Roll the die to pick one of the three corners (1–2, 3–4 or 5–6 on a normal die).
- Move halfway from where you are toward that corner and put a dot.
- Go back to step 2.
Each dot lands in a random place, yet after a few thousand dots the picture is always the same: the Sierpinski triangle, a triangle with a hole in the middle, holes in the three corner triangles, holes in those, and so on. (Demo: the first 10 jumps, one by one, then Demo: 50 000 dots draw the Sierpinski triangle.) The page uses a seeded random generator, so Undo and Reset replay exactly the same rolls.
In symbols, with P the current point, c the corner the die picked and r the ratio (½ here):
P_new = P + r · (c − P) r = ½: P_new = (P + c) / 2Why the start does not matter
Two points that jump toward the same corner end up half as far apart. So the distance from the current point to the Sierpinski triangle is at most halved by every jump: after 10 jumps it is under 1/1000 of the side, less than a pixel. That is why the page can start at P₀ = (0.55, 0.15), a point inside the big middle hole, and still lose no time: P₀ is drawn as a hollow circle and is not a dot. A careful program skips the first few dots; at 50 000 dots they do not show.
Why the holes stay empty
Take a point Q in the middle hole. If a jump toward corner c landed on Q, the point before it was twice as far from c:
Q = (P + c) / 2 ⇔ P = c + 2 · (Q − c)For each of the three corners, that P is outside the triangle. But a jump from inside the triangle stays inside (halfway between two points of a triangle is still in it), so no dot is ever outside, and so no dot ever lands in the middle hole. The same argument, one size smaller, empties the hole of each corner triangle, and so on down. (Demo: why the middle hole stays empty: of 50 000 dots, 0 are in the hole.)
Three half-size copies and the dimension
A jump toward corner c shrinks the whole picture by ½ toward c. So the dots that just jumped toward corner 1 fill a half-size copy of the triangle at corner 1, and the same for corners 2 and 3. The page colours each dot by its corner, and the three colours fill exactly the three copies. (Demo: 3 half-size copies, colour = corner.) The Sierpinski triangle is made of three half-size copies of itself: it is self-similar.
That gives it a dimension. A line segment is 2 copies at scale ½, a square is 4 copies at scale ½, a cube 8. In general N copies at scale s give
dimension = log N / log (1/s) Sierpinski: log 3 / log 2 ≈ 1.585More than a line (1), less than an area (2): its area is 0 (each level keeps ¾ of the area, and (¾)ⁿ → 0), but the edges of all its holes add up to an infinite length.
Other shapes, other rules
The shape menu changes the polygon, the ratio r, or the rule for the die. The copies have scale 1 − r.
| shape | rule | what the dots draw | dimension |
|---|---|---|---|
| triangle, ½ | any corner | Sierpinski triangle | log 3 / log 2 ≈ 1.585 |
| square, ½ | any corner | the whole square, evenly: the 4 half-size copies cover it, so nothing is left out | 2 |
| square, ½, no repeat | never the corner of the last jump | a fractal: each quarter misses its own corner piece | log 3 / log 2 ≈ 1.585 |
| pentagon, 0.618 | any corner | 5 pentagons of scale 0.382 that just touch | log 5 / log 2.618 ≈ 1.672 |
| hexagon, ⅔ | any corner | 6 hexagons of scale ⅓ around a snowflake-shaped hole | log 6 / log 3 ≈ 1.631 |
The square with ½ is the surprise: the same game as the triangle gives no pattern at all (Demo: square, ½: no fractal, just noise). Forbid jumping to the same corner twice in a row and a fractal appears (Demo: square, never the same corner twice): a dot in quarter c just jumped toward c, and the jump before went elsewhere, so the sixteenth of the square at corner c stays empty, and the same one level down. Each step keeps 3 of the 4 sub-squares, hence log 3 / log 2.
For a pentagon the ratio 0.618 = 1/φ (φ the golden ratio) is the one where the 5 copies of scale 1 − 1/φ = 1/φ² ≈ 0.382 fit side by side without overlapping (Demo: pentagon, ratio 0.618). For a hexagon the same happens at ⅔ (Demo: hexagon, ratio ⅔).
The same triangle without dice: Pascal's triangle mod 2
Write Pascal's Triangle and colour each odd number. The odd cells form the Sierpinski triangle too: a cell is odd when exactly one of the two cells above it is odd, so row 2ⁿ starts a copy of the first 2ⁿ rows on each side, with even numbers in the middle. Rows 0–15 already show three levels of holes.
So the Sierpinski triangle can be drawn three ways: by removing middle triangles again and again, by Pascal's rule mod 2, and by the chaos game. The chaos game is the general one: any set of "shrink toward a point" maps (an iterated function system) can be played the same way. With four affine maps instead of three shrinks it draws a fern: see The Barnsley Fern. Curves built by the copy rule, such as the Koch snowflake, are on Fractal Curves, and the other famous fractal is the Mandelbrot Set.
Random points that still give a sure answer are also behind Monte Carlo Estimation of π. And for a rule that is not random at all but still looks it, see The Logistic Map.
What the page leaves out
Why the dots spread evenly over the triangle (the chaos game is ergodic: the share of dots in a copy tends to that copy's weight, here ⅓ each, as the share row shows); unequal corner weights, which shade the picture; ratios other than the ones in the menu (a triangle with r = ⅓ has copies of scale ⅔ that overlap and fill it; with r = ⅔ the copies of scale ⅓ fall apart into dust); 3D versions such as the Sierpinski tetrahedron; and the proof that the dimension defined by counting boxes equals log N / log (1/s). The page stops at 50 000 dots.