Cheshire Codes

The chaos game is a neat way of generating fractals with just a polygon and a point - and a smattering of random chance. To play the game, first you start with polygon and a random initial point somewhere inside of that polygon. Then:

Pick a random vertex on the polygon.
Draw a point that is some fraction of the way in between your random point and the vertex you picked.
Repeat the steps, but now using the new point you just drew.

It turns out that if you repeat these steps over and over again, it will sometimes generate a fractal! Whether you get a fractal or not, and what that fractal looks like, depends on how many sides the polygon has as well as what fraction you chose.

Let's use n to refer to the number of sides in our polygon (making it an n-gon), and r to refer to the fraction we'll use to pick each point.

Technically, you can play this game with a paper, pencil, ruler, and die... but we are living in the future and can now make computers do it instead. So without further ado, let's dive in to the simulation.

Just want to play? Click here to skip the text and jump to the simulation.

Playing the chaos game with JavaScript

To simulate this game, I used a JavaScript library called p5.js that gives us a simple framework for drawing graphics on an HTML canvas. However, I will focus more on the chaos game implementation in this blog post than on the specifics of p5.js. I find p5's functions are descriptively named, so it should still be easy enough to follow my source code. But if you'd like to learn more about p5, their official tutorials are a great place to start.

Generating the vertices

The first step in the game is to figure out the coordinates of our polygon's vertices. A polygon with n sides will have n vertices. To calculate them, we'll imagine these vertices as points evenly spaced around a circle. We'll use a bit of trigonometry to calculate the x and y coordinates of these points.

Usually when traversing a circle, we start with the rightmost point and travel counter-clockwise. We can use θ (theta) to refer to the angle we've traveled from the starting point. If the center of the circle is the origin (0, 0), then point on it at angle θ will have the coordinates (r * cos(θ), r * sin(θ)), where r is the radius of the circle.

There are 2π radians in a circle, so if the polygon has n vertices, then each one will be spaced 2π/n radians apart. So we'll simply calculate points for where θ is a multiple of 2π/n. For the radius, we can use half of the canvas size. Our pseudocode, so far, looks like this:

theta = 0;
dTheta = TWO_PI / n;
for(i from 0 to n) {
    vertex = {
        x: (canvasSize / 2) * cos(theta), 
        y: (canvasSize / 2) * sin(theta),
    };
    drawPoint(vertex); 
    theta += dTheta; 
}

Two more notes:

The calculation above assumes the circle is centered at (0, 0). But (0, 0) is actually the top left of the canvas, and our circle's real center is (canvasSize / 2, canvasSize / 2). So we simply add canvasSize / 2 to our calculations to translate the points.
In p5's coordinate system, y-values increase downwards. Since our calculation is for a coordinate system where y-values increase upwards, we'll simply subtract our calculated value from the canvas height to get the correct coordinate.

Our calculations now look like this:

    x: (canvasSize / 2) + (canvasSize / 2) * cos(theta), 
    y: canvasSize - ((canvasSize / 2) + (canvasSize / 2) * sin(theta)),

You can use the widget below to visualize this calculation around the circle.

There is one more thing. Polygons drawn this way come out looking sideways, since we are starting at the right and not the top. Swapping the sine and cosine (using sine for x and cosine for y) will cause us to start from the top of the circle and move clockwise instead, giving us an upright-looking polygon. You can check the "Swap sine and cosine" checkbox in the simulation above to see this in action.

My final code (swapping sine and cosine) looks something like this:

vertices = []; 
dTheta = TWO_PI / n;

for(let i = 0; i < n; i++) {
    vertex = {
        x: (canvasSize / 2) + (canvasSize / 2) * sin(theta), 
        y: canvasSize - ((canvasSize / 2) + (canvasSize / 2) * cos(theta)), 
    };
    vertices.push(vertex);
    drawPoint(vertex);

    theta += dTheta; 
}

From point to point we go!

To calculate the next point from the current one, I moved both the x and y values of the selected vertex some fraction of the distance between it and the chosen point:

nextPoint = {
    x: (currentPoint.x - randomVertex.x) * r + randomVertex.x, 
    y: (currentPoint.y - randomVertex.y) * r + randomVertex.y, 
};

Finally, just before I draw the point, I'll call fill() which sets the color that subsequent drawing operations will render with.

fill(
    nextPoint.x / canvasSize * 255, 
    nextPoint.y / canvasSize * 255, 
    255
);

fill() takes an HSB value, with each value being out of 255. Here, I've set the hue and saturation as percentages of 255 based on the point's location on the screen. This will produce a gorgeous rainbow gradient as the screen fills up.

The final code excerpt looks like this:

randomVertex = vertices[Math.floor(Math.random() * vertices.length)]; 
nextPoint = {
    x: (currentPoint.x - randomVertex.x) * r + randomVertex.x, 
    y: (currentPoint.y - randomVertex.y) * r + randomVertex.y, 
}; 

fill(
    nextPoint.x / canvasSize * 255, 
    nextPoint.y / canvasSize * 255, 
    255
);

drawPoint(nextPoint); 
currentPoint = nextPoint;

The final simulation

Now for the fun part! Here's the final simulation I ended up with. Try giving it different values of n and r and see what happens. Some values of r you might try could be 1/3, 1/5, 3/8.

The default values in the simulation, n=3 and r=1/2, produce the well-known Sierpinski triangle. See what else you can discover as you play around!

Results

When you play around with the chaos game - especially by changing just one of the variables (r or n) at a time - you'll notice some interesting patterns emerge. Below, you can see what happens as you decrease the value of r for n=3, n=5, and n=7. Click the button to run the simulations!