Chaos game

In mathematics, the term chaos game originally referred to a method of creating a fractal, using a polygon and an initial point selected at random inside it.

Repeating this iterative process a large number of times, selecting the vertex at random on each iteration, and throwing out the first few points in the sequence, will often (but not always) produce a fractal shape.

The term has been generalized to refer to a method of generating the attractor, or the fixed point, of any iterated function system (IFS).

Starting with any point x0, successive iterations are formed as xk+1 = fr(xk), where fr is a member of the given IFS randomly selected for each iteration.

The "chaos game" method plots points in random order all over the attractor.

These parameters are useful for applications of fractal theory such as classification and identification.

At each iteration of the chaos game, the point xk+1 can be placed anywhere along the line connecting the point xk and the vertex of choice, v. Defining r as the ratio between the two distances d(xk,xk+1) and d(xk,v), it is possible to find the optimal value of r, i.e., ropt, for every N-sided regular polygon, that produces a fractal with optimal packing, i.e., the subscale polygons are in contact but do not overlap.

Where θ is the internal angle of the polygon and n is the index of the most protruding vertex, counted starting from the base, i.e.

If r>1 (the point xk+1 jumps at a greater distance than the distance between the point xk and the vertex v), the generated figure extends outside the initial polygon.

[5] When r=2, the algorithm enters in a meta-stable state and generates quasi-symmetric figures.

For values of r>2, the points are placed further and further from the center of the initial polygon at each iteration, the algorithm becomes unstable and no figure is generated.

However, if restrictions are placed on the choice of vertices, fractals will appear in the square.

For example, if the current vertex cannot be chosen in the next iteration, this fractal appears:

If the point is prevented from landing on a particular region of the square, the shape of that region will be reproduced as a fractal in other and apparently unrestricted parts of the square.

When the length of the jump towards a vertex or another point is not 1/2, the chaos game generates other fractals, some of them very well-known.

For example, when the jump is 2/3 and the point can also jump towards the center of the square, the chaos game generates the Vicsek fractal: When the jump is 2/3 and the point can also jump towards the midpoints of the four sides, the chaos game generates the Sierpinski carpet: With minor modifications to the game rules, it is possible to use the chaos game algorithm to represent any well-defined sequence, i.e., a sequence composed by the repetition of a limited number of distinct elements.

In fact, for a sequence with a number N of distinct elements, it is possible to play the chaos game on an N-sided polygon, assigning each element to a vertex and playing the game choosing the vertices following the progression of the sequence (instead of choosing a random vertex).

In this version of the game, the generated image is a unique representation of the sequence.

[5][10] The expansion of the chaos game using r=2 can be useful to magnify small mutations in the comparison between two (or more) sequences.