The "Chaos Game" (See: wikipedia) is a simple algorithm capable of producing some very interesting fractals. Several variants of the algorithm exist, but the simplest version looks something like this:

- Fix a regular n-gon in the complex plane
- Fix a positive real number r to a value less than 1
- Set P = a random point in the polygon
- Repeat many times:
- Set V = a random vertex of the polygon
- Set P = (P+V)/r
- Draw a dot at P

The first, and arguably most important, variant of the above algorithm is to simply not draw the first few points generated. This is because it takes a while for the process to "settle down" into the pattern of the fractal. A typical recommendation is to not draw the first 1000 points generated. The next most common variants involve how to color the points. Perhaps the most popular color scheme is to assign colors to each vertex, and color each point according to which vertex is currently selected. Another common choice is to shade the point by how many times that point has been selected by the algorithm.

One entire family of modifications involve restricting which vertexes may be selected at each step. Such an algorithm is known as a "Restricted Chaos Game". Some examples of how one might restrict the current vertex are:

- The current vertex cannot be the previous vertex
- The current vertex cannot be any of the 3 previous vertexes
- The current vertex cannot be one place away clockwise from the previous vertex
- The current vertex cannot be one place away from the previous vertex
- The current vertex cannot be 2 places away counter clockwise from the previously chosen vertex
- The current vertex cannot be 1 or 3 places from the two previously chosen vertices

Here are a few examples. These were all generated by the same program implementing various forms of the restricted chaos game.

The source code used to generate the images on this page is distributed with the
`mraster`

library as an example. You can find the example source code files on github:
chaos_game.cpp

For a very interesting introduction to the history of Chaos I would suggest James Glick's book: "CHAOS: Making a New Science" (ISBN: 0-14-009250-1). This book has almost no mathematics or formal material regarding Fractals or dynamical systems, but is well worth the read for the historical perspective.

If you are looking for a good introduction to dynamical systems, I would suggest Steven Storgatz's book: "Nonlinear Dynamics and Chaos" ISBN 0-7382-0453-6).

For a good, encyclopedic, introduction to the field in general, I strongly suggest "Chaos and Fractals: New Frontiers of Science" by Peitgen, Jurgens, and Saupe. This book is notable because of it's clear presentation and breadth of coverage. It's a great book to have around for the casual reader because it is broken up into semi self-contained sections that one can just pick up and read.

© 2009 Mitch Richling