the chaos game

By iteratively applying specific sets of transformations to the unit square, we can generate fractals.  For example, the famous Sierpinski triangle can be generated from three simple transformations:

Three transformations (shown in black, red, green), shown by their action on the unit square (grey), produce the Sierpinkski triangle

Rather than iteratively transforming shapes (the base Iterated Function System approach), these plots are produced using the “chaos game” algorithm: start with a random point, and plot its position as it is successively transformed by a random choice of transformation:

x := rnd
repeat
   choose transform w_i with probability p_i
   x := w_i(x)
   plot x

The resulting plot converges to the relevant fractal.

Different sets of transformations give different fractals.

Here, the black and green transformations are as before, but the red transformation includes a rotation

One nice feature of this approach is that smoothly changing the transformations smoothly changes the fractal.

Of course, there can be more than three transformations:

A pentagonal fractal produced by five transformations

The transformations don’t all have to have the same scale factors:

A “snowflake” produced from four transformations, one with a smaller "shrinkage" than the others

This is where the probabilities in the algorithm come into play.  When all the transformations have the same scale factor, we can choose transformations with a uniform random distribution.  When different scale factors are used together, a good heuristic is to choose transformations with probabilities weighted by the area of the relevant transformed square (given by the determinant of the transformation matrix).

The transformations don’t actually have to be squares: we can have different scalings in different directions, and shears, giving more complicated looking fractals:

A “coral tree”

And then we can smoothly transform between quite dissimilar fractals, by linear interpolation between their transformation sets:

From pentagon to coral, and back.

Probably the most famous fractal of this form is the “Barnsley fern”.

What is marvelous for playing about with these systems is that the plots can be produced with very little code: the code to define the transforms, plot the points, and construct the animated gifs, outweighs the core of the chaos game algorithm itself.