Lesson 4: Loops that remember

"""Chaos game: jump a part r of the way to a random corner of a polygon, again and again.
Run: python chaos-game.py   (needs: pip install numpy matplotlib)
"""
import numpy as np
import matplotlib.pyplot as plt

plt.style.use("dark_background")

corners, r, no_repeat = 3, 0.5, False  # triangle, halfway: the Sierpinski triangle
steps = 60000
rng = np.random.default_rng()

angles = np.pi / 2 + 2 * np.pi * np.arange(corners) / corners
vertex = np.column_stack([np.cos(angles), np.sin(angles)])

points, chosen = np.zeros((steps, 2)), np.zeros(steps, dtype=int)
x, last = np.array([0.0, 0.0]), -1
for i in range(steps):
    c = rng.integers(corners)
    while no_repeat and c == last:  # the restricted game: never the same corner twice
        c = rng.integers(corners)
    x = x + r * (vertex[c] - x)  # the whole rule
    points[i], chosen[i], last = x, c, c

plt.figure(figsize=(6, 6))
plt.scatter(points[20:, 0], points[20:, 1], s=0.3, c=chosen[20:], cmap="rainbow")
plt.axis("equal")
plt.axis("off")
plt.show()

# Try: corners, r = 5, 0.618 (a pentagon) or corners, no_repeat = 4, True (a square, restricted)

No Python on this computer? The notebook runs the same script, the exercises and the answers in your browser, on Google Colab.

Line by line

1. vertex = np.column_stack([np.cos(angles), np.sin(angles)])

   The corners of the polygon: their x and y values side by side, one row per corner.

2. c = rng.integers(corners)

   A random whole number from 0 to corners − 1: the corner to jump towards.

3. while no_repeat and c == last:

   The restricted game: as long as the new corner is the last one, draw again.

4. x = x + r * (vertex[c] - x)

   The rule: move the part r of the way from the point to the corner. With r = 0.5, halfway.

5. points[i], chosen[i], last = x, c, c

   Keep the point and its corner, and remember the corner for the next step.

6. plt.scatter(points[20:, 0], points[20:, 1], s=0.3, c=chosen[20:], cmap="rainbow")

   Skip the first 20 points, which are still on their way to the fractal, and colour the rest by their corner.

Try it yourself

1. Draw a pentagon whose five copies just touch.

   Hint

   Change corners and r on one line.

   Answer

   corners, r, no_repeat = 5, 0.618, False

2. Why does the plot skip the first 20 points?

   Hint

   Where does the point start?

   Answer

   It starts at the centre, which is not on the fractal. Each jump halves its distance to the fractal, so after 20 jumps it is less than a millionth (2⁻²⁰) of the picture away.

3. Play the square game with and without no_repeat. What changes?

   Hint

   corners = 4, r = 0.5.

   Answer

   Without the restriction the points simply fill the square; with no_repeat = True a fractal appears.

Quiz