In this article, I will show how to implement in C++ the classical Chaos Game. We start with a regular polygon and a random initial point inside the polygon. Next, we randomly select one of the polygon vertices and add a new point at a fraction of the distance between the initial point and the polygon vertex. We take as initial point the newly generated point and iterate for a large number of steps. Following the above process can, in some cases, produce a fractal shape.
In the next image you can see various fractal shapes generated with the program we are going to write in this post:
Before writing the actual code, we need to decide how we are going to visualize the results of our simulation. In the first version of this code, I’ve saved the points in a text file and visualized the results using a separate Python and Matplotlib script, but this was slow and cumbersome to use, especially in the debugging phase.
A better approach is to save the result of a simulation directly as an image from the C++ program. This makes the code easier to share with other people and it is also faster to iterate during development. An even better approach will be to use a library like SDL2 to visualize a result as soon as it is generated. In this article, we are going to implement two graphical backends for the simulator - one based on a saving the result as a BMP image and one based on drawing the generated points using SDL2.
Another problem that we need to solve is how to map the points from the world, or the real space, to the 2D screen space of our computer. For our simulator, the world space is contained by the [-1, 1] x [-1, 1] square. Another element to keep in mind is that different graphical libraries or image formats have different conventions about how the Y axis is oriented. For example, most image formats will have the Y pointing down - the BMP image format we are going to use can have Y pointing down or up, but it is typically used with Y pointing up and the origin in the lower left corner. SDL2, on the other hand, uses the convention that the Y axis points down with the origin in the upper left corner.
A linear mapping between the world space and the screen space can be defined by the next relations:
You can find the complete code in the GitHub repository for this article.
In order to implement the above relations, we need a way to represent 2D points and rectangles:
Now, we can implement the mapping from the world to the screen space:
Let’s test the above transform by writing a driver test for our two backends. I want to chose between the two backends at compile time, this will let other people build the program even when they don’t have the SDL2 library installed. For the BMP backend I will use the code from my previous article.
For this test, we are going to define a world space [0, 800) x [0, 800) and a square, screen space, with an 800 x 800 pixels surface. The test will consist in drawing 11 points diagonally from (0, 0) to (799, 799):
The BMP backend header file will define a backend_bmp function that will take as arguments the output BMP file name, the width and height of the image, the world and screen_space, a vector with points to be drawn and a so called point radius which is the size in pixels of a point. The last parameter is useful only for debugging purposes in order to better see what it is actually drawn on the image, by default a point will be drawn as 1 x 1 pixel.
The implementation of the BMP backend starts by creating a width x heightBMP surface and fill it with white. Next, we convert the points to be drawn to the screen space using the above mapping. We draw every point from the input vector in black on the BMP image. If point_radius is larger than 0 a crude filled “circle” is drawn around the point. Finally, we save the image to the disk.
You can build the above code on Linux, macOS, WSL or Windows with MSYS2 like this:
or, with g++:
If you are using MSVC on Windows, build it with:
This is what you should see, if you run the above code:
The SDL2 backend is similar with the BMP, except that instead of saving the result in a BMP image a window is shown in which you can see the points drawn. Here is a snipped from backend_sdl2.cpp, remember to define USE_SDL2_BACKEND if you want to be able to build the SDL2 backend.
You can build the above code with the SDL2 backend on Linux, macOS, WSL or Windows with MSYS2 like this:
or, with g++:
If you are using MSVC on Windows, I recommend to install SDL2 globally with vcpkg and use Visual Studio to create a project. You can also build from the command line, but it is more tedious and you’ll need to manually link with the library and instruct the compiler where to find the header files.
As mentioned at the beginning of the article, we are going to use regular polygons to contain the generated set of points. In order to do this we need a way to define a regular polygon.
Remember that a regular polygon is a polygon that is equiangular (all angles are equals) and equilateral (all edges are equals).
For simplicity, we’ll consider regular polygons inscribed in a circle with radius 1.0 and center at (0, 0). This means that all vertices of the polygon will be on this circle.
The center angle of a polygon is the angle made at the center by any two adjacent vertices of the polygon. For a regular polygon the center angle is:
For example, for an equilateral triangle a center angle is 120 degrees, for a square it is 90 degrees, for a regular hexagon it is 60 degrees and so on.
This means, that we can calculate the position of every vertex of a regular polygon using the parametric equation of a circle with radius 1 and center at (0, 0). We just need to add the center angle for every vertex.
Say that we want to calculate the vertices of an equilateral triangle. If we start with the first vertex from (0, 1), the second vertex will have the coordinates:
for the third vertex:
We can implement the above considerations in a struct named RegularPolygon:
We can test the above code with the polygons_test.cpp driver. This is basically, backend_test.cpp slightly modified to use a different world [-1, -1] x [1, 1] and to draw the polygon vertices:
If you build and run the above code, you should see the vertices of an octagon:
At this point, we are ready to implement the rules for the game of chaos:
Generate the vertices of a regular polygon.
Take a random point inside the above polygon. For simplicity, we’ll take this as the first vertex of the polygon.
Pick a random vertex of the polygon.
Take the next point at a ratio between the last point and the random polygon vertex. Here, you can add more rules, for example that the last and the next vertex randomly selected from the polygon should be different. If they are the same, simply reject the generated point.
Repeat the above steps for a large number of iterations.
When you plot the generated points, drop the first couple of them.
We can implement the above rules as ChaosGame:
In the above code, we chose to run for 100000 iterations and drop the first 10 generated points. Next, we pick as the last point the first vertex of the polygon and as the last vertex the same. We initialize a random generation engine and an uniform distribution to pick a random vertex of the polygon.
The get_next_point member function picks a random vertex and checks if this vertex can be used, than it takes a new point at a fraction of the distance between the last point and the vertex. The function also drops the first couple of points generated.
Next, we implement a free function that generates the points. The full code has 14 rules for generating 14 different fractal shapes. In the next snippet, we present the first two rules, or selections:
If you call generate_points with the default selection = 0 it will generate the Sierpinski triangle.
We can modify polygons_test.cpp in order to use the ChaosGame.h and draw the generated points.
When you run the above program, you can pass your selection of the rule to use from 0 to 14. If you pass a wrong number the program will try to correct the value. Running the program without a numeric parameter will use the first selection and generate the Sierpinski triangle.
Here is an example of building and running the program with the BMP backend:
This is what you should see if you pass the number 3 to the program:
The code repository for this article contains a folder interactive that uses the SDL2 backend to let you go back and forth in the available shapes selections. Hint - use the left/right arrow keys to navigate.
If you want to learn more about C++17 I would recommend reading C++17 in Detail by Bartlomiej Filipek: