The chaos game is played as follows. Pick a starting point at random. Then at each subsequent step, pick a triangle vertex at random and move half way from the current position to that vertex.
The result looks like a fractal called the Sierpinski triangle or Sierpinski gasket.
Here’s an example:
If the random number generation is biased, the resulting triangle will show it. In the image below, the lower left corner was chosen with probability 1/2, the top with probability 1/3, and the right corner with probability 1/6.
Update: Here’s an animated version that lets you watch the process in action.
Here’s Python code to play the chaos game yourself.
from scipy import sqrt, zeros
import matplotlib.pyplot as plt
from random import random, randint
def midpoint(p, q):
return (0.5*(p[0] + q[0]), 0.5*(p[1] + q[1]))
# Three corners of an equilateral triangle
corner = [(0, 0), (0.5, sqrt(3)/2), (1, 0)]
N = 1000
x = zeros(N)
y = zeros(N)
x[0] = random()
y[0] = random()
for i in range(1, N):
k = randint(0, 2) # random triangle vertex
x[i], y[i] = midpoint( corner[k], (x[i-1], y[i-1]) )
plt.scatter(x, y)
plt.show()
Update 2: Peter Norvig posted some Python code with variations on the game presented here, generalizing a triangle to other shapes. If you try the analogous procedure with a square, you simply get a square filled with random dots.
However, you can get what you might expect, the square analog of the Sierpinski triangle, the product of a Cantor set with itself, if you make a couple modifications. First, pick a side at random, not a corner. Second, move 1/3 of the way toward the chosen side, not 1/2 way.
Here’s what I got with these changes:
Source: Chaos and Fractals
Here is my golfed-down JS version: https://jsfiddle.net/ondras/XVNFe/
What fun! I played another few moves in the game: https://github.com/norvig/pytudes/blob/master/Sierpinski.ipynb
As a complete ignoramus, I get a kick out of seeing really smart guys just having fun with math.
Thanks!
I should have said this explicitly, but I got the game from the book referenced at the bottom of the post. I just illustrated it with the code and images.
You can also play the chaos game with the Julia set formula, z -> z²+ c.
Inverting this formula gives you √(z – c). There are two square roots in the complex plane. Pick one at random.
Is there a way to quantify how fast the points converge on lying exactly on the Sierpinski triangle?
Interesting! Continued on this theme using fractional steps instead of midpoints; and then letting the ratio go negative.
https://github.com/cdragun/python-progs/blob/master/Sierpinski.ipynb
What if you did a star shape?