Monday, February 7, 2011

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 ="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.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)


John said...

It's amazing the complex patterns that emerge from simple rules.

The Sierpinski triangle is particularly interest because it can be generated in so many different ways.

Anonymous said...

The sierpinski gasket makes Jonathan Coulton wanna cry.

Rational Explorer said...

This can be extended into three dimensions as well. I remember using qbasic to generate a gigantic pov ray file way back when doing this same thing. Pick 4 points in three dimensional space and use r=1/2 works just as well. This makes me wonder what the relationship is between r, p, and dimensionality that will produce fractals?

Matt Boehm said...

Your code syntax highlighter isn't preserving indentations, which is crucial for Python programs. granted, it's easy enough to figure out in this case, but I just thought I'd mention it.

Bill the Lizard said...


Thanks for the heads up on the code formatting. Blogger's editor "fixes" indentation for you when you switch from HTML view to the normal editor, so blogging about programming can be a particular pain sometimes. :)

Anonymous said...

God, the Creator, is orderly. This attribute can be found in many and unexpected ways and places. Amazing.