Danny Heap
danny@gibbs.med.utoronto.ca
The chaos game provides a computationally tractable method for rendering an Iterated Function System (IFS) on a device with a finite resolution, for example a computer monitor. Given a transformation
However, rendering squares is computationally more expensive than
rendering points, but both are compact subsets of
, and
equally suitable as grist for our IFS mill. Also, rendering two length-
compositions of the
is more expensive than using the
length-
suffix of one composition as the prefix of the next.
Finally, some of the transformations require fewer iterations than
others, if they are composed of transformations with smaller contractions.
These ideas form the basis of the chaos game.
choose point![]()
while (you have patience...)
choose transformation![]()
![]()
![]()
![]()
end while
Since the desired fractal
is the fixed point of
,
it's not hard to show that this method gets arbitrarily close to to
. Suppose
is a string of digits,
, each
occurring with nonzero
probability in a random sequence. The chaos game executes the
composition
with probability
, where
is the probability of digit
appearing. So, for a sufficiently long sequence you can be confident
that there is a point near1address
(the image of
under
). Thus, after some
points are chosen, the
chaos game ``fills out''
: every point of
is within 1 pixel of some
.
By choosing the probabilities carefully the length of the
sequence
may be pretty modest, for example a few tens of thousands
to render Sierpinski's gasket on a
grid, and the chaos
game is a reasonable method for rendering fractals. However, it's
reasonable to ask what role does the random choice of the
play?
I propose that we either modify a random sequence, or use a thoroughly non-random sequence to investigate the effects this has on the resulting fractal-like objects. These modifications may alter one of (a) the resulting object, i.e. the limit of the set of pixels drawn by the chaos game, or (b) the uniformity of rendering the object.