Mitch Richling: Chaos Game

Author:	Mitch Richling
Updated:	2022-10-05

1. Chaos Game
2. Code
3. Gallery
4. Code
5. References

1. Chaos Game

The "Chaos Game" (See: wikipedia) is a simple algorithm capable of producing some very interesting fractals. Several variants of the algorithm exist, but the simplest version looks something like this:

Fix a regular n-gon in the complex plane
Fix a positive real number r to a value less than 1
Set P = a random point in the polygon
Repeat many times:
    Set V = a random vertex of the polygon
    Set P = (P+V)/r
    Draw a dot at P

The first, and arguably most important, variant of the above algorithm is to simply not draw the first few points generated. This is because it takes a while for the process to "settle down" into the pattern of the fractal. A typical recommendation is to not draw the first 1000 points generated. The next most common variants involve how to color the points. Perhaps the most popular color scheme is to assign colors to each vertex, and color each point according to which vertex is currently selected. Another common choice is to shade the point by how many times that point has been selected by the algorithm.

One entire family of modifications involve restricting which vertexes may be selected at each step. Such an algorithm is known as a "Restricted Chaos Game". Some examples of how one might restrict the current vertex are:

The current vertex cannot be the previous vertex
The current vertex cannot be any of the 3 previous vertexes
The current vertex cannot be one place away clockwise from the previous vertex
The current vertex cannot be one place away from the previous vertex
The current vertex cannot be 2 places away counter clockwise from the previously chosen vertex
The current vertex cannot be 1 or 3 places from the two previously chosen vertices

2. Code

Nothing clarifies an algorithm discussion more than working code. So, here we go:

#include "ramCanvas.hpp"

struct ifs {
    long itrMax;
    long itrToss;
    int numPts;
    int lastAvoidForward;
    int lastAvoidBackward;
    int lastAvoidLast;
    double factor;
    double radius;
};

std::vector<ifs> ifsList {
  { 10000000, 1000,  3, -1, -1,  -1, 2.0, 1.10},
  {100000000, 1000,  4, -1,  1,  -1, 2.0, 1.10},
  {100000000, 1000,  4, -1,  2,  -1, 2.0, 1.10},
  {100000000, 1000,  4, -1, -1,   1, 2.0, 1.10},
  {100000000, 1000,  4, -1, -1,  -1, 2.0, 1.10},
  {100000000, 1000,  4, -1, -1,  -1, 2.3, 1.10},
  {100000000, 1000,  5,  1,  1,  -1, 2.0, 1.10},
  {100000000, 1000,  5,  2,  2,  -1, 2.0, 1.10},
  {100000000, 1000,  5, -1,  1,   1, 2.0, 0.75},
  {100000000, 1000,  5, -1,  1,  -1, 2.0, 1.10},
  {100000000, 1000,  5, -1,  2,  -1, 2.0, 1.10},
  {100000000, 1000,  5, -1, -1,   1, 2.0, 0.84},
  {100000000, 1000,  5, -1, -1,   1, 2.0, 1.10},
  {100000000, 1000,  5, -1, -1,   1, 2.3, 0.70},
  {100000000, 1000,  5, -1, -1,  -1, 2.0, 1.10},
  {100000000, 1000,  5, -1, -1,  -1, 2.3, 1.10},
  {100000000, 1000,  6,  2,  2,  -1, 2.0, 1.10},
  {100000000, 1000,  6,  3,  1,  -1, 2.0, 1.10},
  {100000000, 1000,  7,  1, -1,   1, 2.5, 0.65},
  {100000000, 1000,  7,  2, -1,   1, 2.5, 0.65},
  {100000000, 1000,  7,  3,  3,   1, 2.5, 0.65},
  {100000000, 1000,  7,  3, -1,   1, 2.5, 0.65},
  {100000000, 1000,  7,  5,  5,   1, 2.5, 0.65},
  {100000000, 1000,  7,  5, -1,   1, 2.5, 0.65},
  {100000000, 1000,  8,  1,  1,   1, 2.0, 0.75},
  {100000000, 1000,  8,  1,  1,  -1, 2.0, 1.01},
  {100000000, 1000,  8,  2,  2,   1, 2.0, 0.94},
  {100000000, 1000,  8,  3,  3,   1, 2.0, 0.94},
  {100000000, 1000,  8,  5,  1,   1, 2.0, 0.94},
  {100000000, 1000,  8,  5,  2,   1, 2.0, 0.94},
  {100000000, 1000,  8,  5,  5,   1, 2.0, 0.94},
  {100000000, 1000, 10,  1,  1,   1, 2.5, 0.57},
  {100000000, 1000, 10,  1,  9,   1, 2.5, 0.65},
  {100000000, 1000, 10,  2,  2,   1, 2.5, 0.65},
  {100000000, 1000, 10,  3,  3,   1, 2.5, 0.65},
  {100000000, 1000, 10,  4,  4,   1, 2.5, 0.65},
  {100000000, 1000, 10,  5,  5,   1, 2.5, 0.65},
  {100000000, 1000, 10,  6,  1,   1, 2.5, 0.65},
  {100000000, 1000, 10,  6,  6,   1, 2.5, 0.65},
  {100000000, 1000, 10,  7,  7,   1, 2.5, 0.65},
  {100000000, 1000, 10,  8,  8,   1, 2.1, 0.87},
  {100000000, 1000, 10,  8,  8,   1, 2.3, 0.74},
  {100000000, 1000, 10,  8,  8,   1, 2.5, 0.65},
  {100000000, 1000, 15,  5,  5,   1, 3.8, 0.36}
};

int main() {
  std::chrono::time_point<std::chrono::system_clock> startTime = std::chrono::system_clock::now();
  mjr::ramCanvas3c8b theRamCanvas(2160, 2160);
  theRamCanvas.setDrawMode(mjr::ramCanvas3c8b::drawModeType::ADDCLAMP);
  std::vector<mjr::ramCanvas3c8b::colorType> aColor{ mjr::ramCanvas3c8b::colorType(1, 1, 1)};
  auto numCol = aColor.size();

  std::random_device rd;
  std::minstd_rand0 rEng(rd());

  for(auto &theIFS :ifsList) {
    theRamCanvas.newRealCoords(-theIFS.radius, theIFS.radius, -theIFS.radius, theIFS.radius);
    theRamCanvas.clrCanvasToBlack();

    std::vector<std::complex<double>> points;
    double curAngle = std::numbers::pi/2;
    for(int i=0; i<theIFS.numPts; i++) {
      points.push_back(std::complex<double>{cos(curAngle), sin(curAngle)});
      curAngle += 2*std::numbers::pi/theIFS.numPts;
    }

    std::complex<double> z{0.1, 0.2};
    int lastPoint = -1;
    double maxMag = 0;
    for(int n=0;n<theIFS.itrMax;n++) {
      std::minstd_rand0::result_type rn = rEng();
      int rpi = rn%theIFS.numPts;
      while(((lastPoint !=-1) && (theIFS.lastAvoidLast    !=-1) && rpi==lastPoint) ||
            ((lastPoint !=-1) && (theIFS.lastAvoidBackward!=-1) && (rpi==(lastPoint+theIFS.lastAvoidBackward)%theIFS.numPts)) ||
            ((lastPoint !=-1) && (theIFS.lastAvoidForward !=-1) && ((rpi+theIFS.lastAvoidForward)%theIFS.numPts==lastPoint))) {
        rn = rEng();
        rpi = rn%theIFS.numPts;
      }
      lastPoint = rpi;
      z = (z+points[rpi])/theIFS.factor;
      if(n > theIFS.itrToss)
        theRamCanvas.drawPoint(z, aColor[rn%numCol]);
      double curMag = std::abs(z);
      if(maxMag < curMag)
        maxMag = curMag;
    }
    std::cout << "max mag: " << maxMag << std::endl;

    theRamCanvas.applyHomoPixTfrm(&mjr::ramCanvas3c8b::colorType::tfrmStdPow, 1.0/5.0);

    std::ostringstream stringStream;
    stringStream << "chaos_game";
    stringStream << "," << theIFS.numPts;
    stringStream << "," << theIFS.lastAvoidForward;
    stringStream << "," << theIFS.lastAvoidBackward;
    stringStream << "," << theIFS.lastAvoidLast;
    stringStream << "," << theIFS.factor;
    stringStream << ".tiff";
    theRamCanvas.writeTIFFfile(stringStream.str());
  }

  std::chrono::duration<double> runTime = std::chrono::system_clock::now() - startTime;
  std::cout << "Total Runtime " << runTime.count() << " sec" << std::endl;

  return 0;
}