Chaos game

From Wikipedia, the free encyclopedia

Originally the chaos game referred to a means of creating a fractal, using a polygon and a random point inside it. The fractal is created by finding the point a given fraction of the distance between the previous point and one of the vertices, chosen at random, a large number of times. Using a regular triangle and the factor 1/2 will result in the Sierpinski triangle. In this way, a great many shapes can be generated, all the more realistically if the original shape has a hidden fractal order. The chaos game is an example of a random process leading to a predetermined result.

Animated creation of a Sierpinski triangle using the chaos game

Today the meaning of chaos game has been generalized and now refers to a way of generating the attractor, or the fixed point, of an iterated function system (IFS). Starting with any point x₀, successive iterations are formed as x_k+1 = f_r(x_k), where f_r is a member of the given IFS randomly selected for each iteration. The iterations converge to the fixed point of the IFS. Whenever x₀ belongs to the attractor of the IFS, all iterations x_k stay inside the attractor and, with probability 1, form a dense set in the latter.

Fractal fern created using chaos game

The process for n functions can be described in pseudo-code

  (x,y) = a random point in the bi-unit square
  iterate {
     i = a random integer from 0 to n-1 inclusive
     (x, y) = F_i(x, y)
     plot(x, y)
  }

The points that are plotted show up in random order all over the attractor. This is in contrast to how most fractals are drawn, which is one pixel at a time, in order on the screen. Instead the image of the attractor emerges from the many dots plotted by the algorithm.