Fractals Generated through the Chaos Game: A Study of Iterated Function Systems, the Barnsley Fern, the Collage Theorem, and the Dragon Curve ()
1. Introduction
Over the past several decades, a field of mathematics broadly known as non-linear dynamics, or the theory of chaotic dynamical systems, has developed around the study of complex curves called fractals. These objects are, in a precise mathematical sense, infinitely detailed: successive magnification of any region reveals structure that never resolves into simplicity. Fractals entered popular scientific awareness largely through expository articles such as those of A. K. Dewdney in Scientific American, which made the subject accessible beyond specialist mathematical audiences [1].
There is a deep structural link between fractals and chaos: both arise from iterated functions, in which the state produced by one iteration becomes the input to the next. Some chaotic systems, such as bifurcation diagrams, display exact self-similarity under magnification, while other, more asymmetric fractals can appear visually irregular even though they retain a well-defined self-similar structure. A common feature of chaotic iteration is unpredictability at the level of an individual step: the value produced by a specific iteration cannot, in general, be anticipated without explicitly computing every preceding iteration. In this sense, fractals may be described as a form of ordered, or “beautiful,” chaos -globally structured, yet locally unpredictable.
Theoretical investigation of IFS has its roots in the seminal work of Hutchinson on self-similarity and contraction mappings [2] that later became widely known due to Barnsley’s geometric formulation of IFS and the collage theorem [3] as well as its placement into the context of the fractal geometry program developed by Mandelbrot [4], Falconer [5], and in expository works such as [1] [6]. Continuing this line of research, recent investigations have been carried out in the following directions: algorithmic and probabilistic analysis of chaos game and convergence issues, involving both classical chaos game and its generalizations (standard and disjunctive) along with fuzzy IFS [7]-[9]; quantitative research of contraction ratios and fractal dimension for special families of attractors including Sierpinski n-gons, fractal functions in function spaces, and continued-fraction sets [10]-[12]; extension of the classical Hutchinson-Barnsley scheme onto arbitrary shift spaces, multivalued mappings in neutrosophic metric spaces, and unifying fractal interpolation schemes [13]-[15]; advances in multifractal analysis of inhomogeneous measures under the action of non-doubling projections [16]; application of fractal and fractional descriptors in modeling of material microstructure [17]. A fractal is a mathematically created geometric figure that displays scale invariance: rising into or out of any segment reproduces a structure identical or fundamentally similar to the unique whole [18]. The overall trend of recent research is that of a transition from geometric to computational, probabilistic, and abstract generalization aspects of IFS theory.
Thus, justifying the choice of focus for this research, this paper examines one particular route from randomness to structure: the Chaos Game, and its formalisation as the attractor of an Iterated Function System (IFS). Section 2 introduces the Chaos Game and its classical three-point realisation. Section 3 develops the necessary mathematical framework of IFS theory. Section 4 states Barnsley’s Collage Theorem, which explains why the Chaos Game works. Section 5 describes representative computational implementations. Section 6 presents results and discussion, including the Barnsley fern, the dragon curve, and a generalised n-point Chaos Game, and Section 7 concludes.
2. The Chaos Game
Chaos Game Illustration assists as a powerful method for transforming linear sequence data into revealing visual patterns [19]. The Chaos Game is an algorithm that produces images of fractal structures using nothing more than paper and pencil or, more practically, a computer. The term was coined by the mathematician Michael Barnsley [3]. Notably, the relationship between the random, game-like procedure and the highly structured fractal image it produces is not obvious from the rules alone; there is no evident a priori connection between the two. This element of surprise is part of what makes the result mathematically interesting.
Classical Procedure
In its simplest form, the Chaos Game proceeds as follows. Three points (vertices of a triangle) are fixed in the plane, and an arbitrary starting point is chosen. On each iteration, one of the three vertices is selected at random (for example, by rolling a die and mapping the result onto the three vertices), and the current point is replaced by the midpoint between itself and the selected vertex. This process is then repeated many times.
Intuitively, one might expect that this procedure, repeated indefinitely, would produce a triangle filled uniformly with random dots. This is not the case. When the Chaos Game is implemented on a computer using a pseudo-random number generator for the vertex selection and run for several thousand iterations, the resulting point cloud is not uniform at all: it converges to the well-known Sierpinski triangle (Figure 1), named after the mathematician Wacław Sierpiński, who first described the set.
Figure 1. The attractor produced by the classical three-point Chaos Game: The Sierpinski triangle.
3. Mathematical Formalism: Iterated Function Systems
Barnsley’s Chaos Game exploits the self-similar structure of fractals by using a random walk procedure to plot points of the attractor of a given Iterated Function System (IFS). To make this precise, we require the following definitions.
3.1. Iterated Function Systems
We restrict attention to affine iterated function systems. An iterated function system (IFS) M on a complete metric space
where
and
is the Euclidean distance, is a finite set of affine contraction map pings
,
. Each mapping takes the affine form
, where
and
. The map
is a contraction with respect to
if the eigenvalues
of
satisfy
for
ensuring that every
strictly contracts distances.
3.2. The Attractor of an Iterated Function System
The term attractor is reserved exclusively for the unique non-empty compact set
invariant under
, satisfying
. Any finite set of points used to seed or generate an approximation of
should be referred to as reference vertices or seed points, not as the attractor.
3.3. The Chaos Game: Precise Statement
Let
be a compact metric space (here
is a compact set with
). Let
be contractions with Lipschitz constants
. Let
be the attractor, i.e. the unique non empty compact set with
.
(H1) Contractivity. Each
is a contraction, as above.
(H2) Map selection. The indices
are independent and identically distributed, independent of
, with
and
for every
,
.
The chaos game is
.
Let
be the unique Borel probability measure with
. It is supported on
. Note that
depends only on the maps, while
also depends on
.
Theorem
Assume (H1) and (H2). Then for every starting point
:
a) Convergence of the sampled points (forgetting and attraction).
For every realization
and any two starting points
,
Moreover,
, and if
then
for all
. Also, the law of
converges to
in Wasserstein distance:
.
b) Orbit density (topological statement).
Almost surely, the set of accumulation points of
is
. Equivalently, for every
and
,
for infinitely many n. In particular, if
then
is dense in
almost surely.
c) Convergence of the sampled measure (statistical statement).
Let
. Almost surely,
weakly, i.e.
for all continuous
.
4. Barnsley’s Collage Theorem
The Chaos Game solves the forward problem: given an IFS, find (a picture of) its attractor. Barnsley’s Collage Theorem addresses the inverse problem: given a target image, find an IFS whose attractor approximates it.
4.1. Theorem (The Collage Theorem)
Let
be a complete metric space, and let
be the space of nonempty compact subsets of
, equipped with the Hausdorff metric
. Consider a finite iterated function system
and its Hutchinson operator
Suppose
is contractive with factor
, meaning
For example, if the maps
have Lipchitz constants
, one may take
.
Let
be the unique attractor satisfying
. Then, for every target set
,
.
Consequently, if the collage error satisfies
, then
.
To guarantee an attractor approximation error of at most
, it therefore suffices to require
.
4.2. Illustrative Example: The Sierpinski Triangle as a Collage
The Sierpinski triangle provides the simplest non-trivial illustration of the Collage Theorem. Placing a vertex of the triangle at the origin, the triangle can be exactly tiled by three smaller copies of itself, each scaled by a factor of one-half and positioned at each of the three corners (Figure 2). Each of the three smaller triangles has exactly half the vertical and horizontal extent of the whole. Reading these three placements directly as the three affine contraction maps of an IFS reproduces exactly the classical three-point Chaos Game of Section 2, now derived rigorously from the collage geometry of the target shape rather than assumed ad hoc.
(a) (b)
Figure 2. The Sierpinski triangle as a self-tiling collage of three half-scale copies of itself, illustrating the Collage Theorem.
5. Computational Implementation
The Chaos Game was implemented in MATLAB. The program proceeds in three stages: (i) initialise the set of reference vertices and a starting point; (ii) repeatedly select a vertex at random, with all vertices equally likely and each selection independent of the previous ones, and move the current point
to
where
is the selected vertex and
is the contraction ratio (
gives the midpoint rule of the Sierpinski triangle; other values of
are used in Section 6); (iii) plot the accumulated set of points. For the Barnsley fern and the dragon curve, step (ii) instead applies one of the affine maps given in Section 6, chosen independently with the stated probabilities.
The program does not use graphical animation: all retained points are plotted once the iteration loop has completed, and the number of iterations is supplied interactively by the user. The implementation was validated by checking that, for
and
, the output reproduces the Sierpinski triangle. It was then extended to the more general cases discussed in Section 6.
6. Results and Discussion
6.1. Chaos Game Output for the Sierpinski Triangle
Figure 3 illustrates the progressive formation of the Sierpinski triangle generated via the iterative Chaos Game algorithm (
,
), demonstrating the emergence of deterministic fractal structure from an underlying stochastic process. Beginning with
fixed corner vertices that define a triangle, an initial point is iteratively moved half the distance toward a randomly selected vertex at each step. The sequence captures the transition from an early phase characterized by a sparse point distribution after
iterations (Figure 3(a)) to an intermediate phase where sub-triangular clusters and inverted void regions emerge (
; Figure 3(b)), culminating in a dense, highly detailed representation of the self-similar attractor after
iterations (Figure 3(c)).
(a)
(b) (c)
Figure 3. Sequential formation of the Sierpinski triangle fractal via the Chaos Game algorithm.
6.2. The Barnsley Fern
The Barnsley fern is the attractor of a four-map affine IFS. In the Sierpinski triangle all maps are chosen with equal probability, but here each map is assigned a different selection probability. One map (probability about 1%) generates the central stem. The remaining maps generate the main frond and the successively smaller left- and right-leaning leaflets, each contracted and rotated by a different affine transformation (Figure 4).
The affine maps determine the geometric attractor, that is, the shape of the fern. As long as every
, any choice of probabilities yields the same set. The selection probabilities, by contrast, determine the sampled invariant measure, which governs how many points land in each part of the fern and therefore how dense it looks in the plot. The values 0.01, 0.85, 0.07, 0.07 are Barnsley’s standard empirical choice, which makes the fern clearly visible with reasonably even density after relatively few points. They are not derived from the maps’ relative area contraction (Figure 5).
Figure 4. The Barnsley fern, the attractor of a four-map affine iterated function system.
Figure 5. The Barnsley fern rendered by the Chaos Game with non-uniform map-selection probabilities weighted by relative contraction area.
6.3. The Dragon Curve: Introducing Rotation
The dragon curve fractal extends the Chaos Game to an IFS whose maps combine contraction with rotation (see Figure 6). The dragon curve is composed of two smaller copies of itself, but unlike the Sierpinski triangle, these copies are related to the whole not merely by scaling and translation but also by a rotation. Each copy is obtained by rotating the curve through a fixed angle θ about the origin, contracting it by a factor of
, and applying a horizontal offset of +1 or −1 to obtain the two respective smaller curves. The corresponding rotation matrix follows directly from elementary linear algebra. Equal selection probabilities (
) are assigned to the two affine maps.
Figure 6. The dragon curve, the attractor of a two-map iterated function system incorporating rotation.
As the Chaos Game plots the orbit of this two-map IFS, the dragon curve gradually emerges (Figure 7); points are naturally colourable according to which of the two affine maps was selected at each step, visually distinguishing the two self-similar halves of the curve [6].
Figure 7. The Chaos Game plotting the dragon curve; the left panel colours points by the affine map selected at each iteration, while the centre and right panels show the same attractor in a single colour at increasing iteration counts.
6.4. A Generalised n-Point Chaos Game
Figure 8 demonstrates the structural dependence of the Iterated Function System (IFS) attractor on the contraction ratio
for an
vertex system. In Panel A, applying a scaling factor
results in a disconnected fractal structure consisting of isolated, self-similar triangular clusters separated by clear voids. Conversely, in Panel B, increasing the contraction factor to
causes the sub-attractor regions corresponding to each vertex (color-coded red, green, and blue) to overlap, yielding a denser, continuous triangular distribution with overlapping sub-structures.
Figure 8. Chaos game attractors for
reference vertices after
iterations under two different parameter settings: (a) a disconnected Cantor-like fractal formed with a reduced scaling factor (
), and (b) an overlapping continuous attractor generated with an increased scaling factor
).
Figure 9(a) illustrates Chaos Game attractors for
reference vertices using a contraction factor of
. In Panel A, placing the four vertices at the corners of a square with unrestricted random vertex selection results in a solid, space-filling square split into four equal quadrant regions (color-coded cyan, red, green, and blue). In Panel B, altering the vertex geometry to a trapezoidal layout reveals a complex fractal pattern with self-similar, triangular voids distributed across all four colored regions.
Figure 9(b) depicts the Sierpinski Carpet fractal attractor generated via an 8-transformation Chaos Game system (
) with a contraction factor of
after
iterations. The square domain is partitioned into a
grid, where eight perimeter vertices/sub-regions are assigned as target maps, leaving the central square empty. Points are color-coded according to the chosen transformation at each step, clearly illustrating the eight self-similar, recursively perforated sub-carpets that collectively form the overall fractal structure.
Figure 9. (a): Chaos Game attractors generated with
reference vertices and a contraction factor of
after
iterations. (b): Chaos Game generation of the Sierpinski Carpet fractal (
,
) after
iterations.
Figure 10 depicts the Hexagasket fractal attractor generated via a 6-vertex Chaos Game algorithm (
) with a contraction scaling factor of
after
iterations. Positioning six reference vertices at the corners of a regular hexagon creates a ring of six self-similar sub-hexagons surrounding a central void. The six distinct colors (red, orange, magenta, cyan, green, and blue) delineate the attractor sub-regions corresponding to each target vertex, illustrating the recursive, self-similar structure at multiple spatial scales.
Figure 10. Chaos Game generation of the Hexagasket fractal (
,
) after
iterations.
7. Conclusion
In this article, the mathematics and computation underlying the Chaos Game have been unified into a rigorous treatment of the technique as a means of rendering IFS attractors. Beginning with Barnsley’s original construction using three points and its counter-intuitive emergence into the Sierpinski triangle, the formalism of complete metric spaces, affine contraction mappings, and attractors of IFSes was introduced and used to prove the convergence. In addition, it was shown that the Collage Theorem provides a method to construct an IFS that approximates a predetermined object via its attractor. The examples of using probability weights and adding rotation operations to affine mappings showed the power of the framework in its generality, whereas the generalized n-point Chaos Game allowed us to consider the classical Sierpinski carpet in terms of polygon-based attractors. Collectively, these findings reaffirm one of the main concepts of fractal geometry: namely, chaotic and unpredictable processes at the local level can produce highly deterministic and structured objects governed solely by a few contraction and probability parameters.
Future work can proceed with the framework described here and calculate fractal dimensions numerically.
Author Contributions
Conceptualization, R.A., S.A. and P.A.; methodology, R.A. and T.A.; software, R.A. and P.A.; validation, R.A., S.A. and T.A.; formal analysis, R.A. and S.A.; investigation, R.A.; resources, R.A.; data curation, R.A. and T.A.; writing—original draft preparation, R.A., S.A. and T.A.; writing—review and editing, R.A., and S.A.; visualization, S.A. and P.A.; supervision, P.A.; project administration, R.A.. All authors have read and agreed to the published version of the manuscript.