The Chaos Game

In the BLOSSOMS video lecture Fabulous Fractals and Difference Equations, Laura Zager presents the Chaos Game, which follows a few simple rules.

1. Draw an equilateral triangle and label the point red, blue, and green
2. Start at any vertex
3. Roll a die to get the next color (red, blue, or green)
4. Draw a point halfway between the starting point and the vertex determined by the die roll
5. This new "halfway point" becomes the starting point for the next iteration
   
6. Keep repeating the procedure until a pattern emerges

The point of the exercise is to try and predict what pattern will emerge. The lecture continues on to talk about Fibonacci numbers, difference equations (or recurrence relations), bound and unbound trajectories, and the Mandelbrot set before it eventually gets back to the result of the Chaos Game.

It takes quite a few iterations for a pattern to emerge, so this is a perfect problem for setting up a simulation. You'll need Python and the Python Imaging Library (PIL) to run the following code.

from PIL import Image
import random

# calculate the midpoint between two points
def midpoint(p1, p2):
   return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)

# define the size of the image and a few color constants
# the hieght of an equilateral triangle is sqrt(3)/2 * base
size = 410, 356 # width, height
white = (255, 255, 255)
black = (0, 0, 0)

# set the corner positions of the triangle
blueCorner = (5, 351)
redCorner = (205, 5)
greenCorner = (405, 351)
corners = (redCorner, blueCorner, greenCorner)

triangle = Image.new("RGBA", size, white)

pivot = blueCorner

for i in range(50000):
   randCorner = corners[ random.randint(0, 2) ]
   pivot = midpoint(pivot, randCorner)
   triangle.putpixel(pivot, black)

triangle.save("triangle.gif")

The code above creates a blank Image canvas and puts random pixels on it, but those pixels form a definite pattern. The pixels are selected by picking a random corner of the triangle and calculating the midpoint between that corner and the previous point drawn.


This is called the Sierpinski triangle, a fractal first described by Polish mathematician Wacław Sierpiński.

This isn't the only fractal that can be created by the Chaos Game. A more general set of rules for the Chaos Game are to start at one vertex of a regular polygon, then draw the next point a fraction r of the distance between it and a vertex picked at random. Most combinations of polygons and fractions won't produce a fractal of course, but there are several that do. From Wolfram MathWorld's article on the Chaos Game we find that for a regular pentagon the fractions 1/3 and 3/8 both produce fractals, as does a regular hexagon with the fraction 1/3.

We'd only need to make a few minor changes to the code above, including the midpoint function, the set of vertices, and the range of the random number generator, in order to generate these fractals. Here are the results.

Pentagon fractal (r = 1/3)


Pentagon fractal (r = 3/8)


Hexagon fractal (r = 1/3)