# Cyclic Cellular Automata part 2 … an interesting variant

I made other experiments with Cyclic Cellular Automata  using other neighborhoods and rules, and this one is particular interesting:

using the Moore neighborhood (eight cells surrounding the central one: N, NE, E, SE, S, SW, W, NW); if a cell is in state C and is surrounded by two or more cells in state C+1, then it will switch to state C+1 at the next generation

If the total number of states are well calibrated, the automata easily reach a “stable state” (no more state changes)

These are two demo videos I made. In the youtube video description of the first, there is also a link to the source code (in P5.js).

# Conway’s Game of Life variations

This is a three-part post about Conway’s Game of Life and some easy-to-implement  variations that can lead to interesting visual results.

• Part 2: extending the neighbourhood [… coming soon …]
• Part 3: moving to the third dimension [… coming soon …]

The Conway’s Game of Life is a cellular automaton created by the British mathematician John Horton Conway in 1970. It is a theoretically infinite grid of cells; each cell can be in two states: dead ($0$) or alive ($1$). Initially the grid has a particular initial configuration  (for example a percentage of the cells are set to alive).  Then the cells evolve, and the state of cell $(x,y)$ at generation $N+1$ depends only on its state and the state of its eight neighbours at generation $N$. The rules are simple:

• if a dead cell at generation $N$ is surrounded exactly by 3 alive cells then it willl be alive at generation $N+1$
• if an alive cell at generation $N$ is surrounded by  2 or 3 alive cells, then it will stay alive, otherwise it will become a dead cell at generation $N+1$

Despite the simple rules, the Conway’s Game of Life is a Turing Complete model of computation (i.e. it can simulate any computer).

The visual configurations and the animations are also visually interesting.

A first variant can be obtained in the following way:

• overlap three independent cell grids (one for each component Red-Green-Blue)
• animate each grid using the standard rules, but for each cell $(x,y)$ in each grid also keep a fractional (float) value $C(x,y)$ in the range (0,1) ($C_r$ for the red grid, $C_g$ for the green grid, $C_b$ for the blue grid) and update it using the following rules:
• if a cell becomes alive then add a fixed constant $v_1$ to it: $$C(x,y) = C(x,y)+v_1$$
• if a cell becomes dead then subtract a fixed constant $v_0$ to it: $$C(x,y) = C(x,y) – v_0$$
• render each cell $(x,y)$ with a square (or pixel) and color it according to the three RGB components values $C_r, C_g, C_b$ that it has in the three independent grids: $Red = C_r(x,y)*255$, $Green=C_g(x,y)*255$ , $Blue=C_b(x,y)*255$

This is a video that shows the resulting animation made with Processing 3 using $v_1=0.3$, $v_0=0.04$, starting from an initial random configuration:

https://www.algoritmarte.com/vdisk/code/ColoredLife.zip

# Cyclic Cellular Automata

A cyclic cellular automaton (CCA) is defined as an automaton where each cell takes one of N states 0, 1,…, N-1 and a cell in state i changes to state i+1 mod N at the next time step if it has a neighbor that is in state i+1 mod N, otherwise it remains in state i at the next time step. Classically CCA are applied on the 2-dimensional integer lattice with Von Neumann neighborhoods (nearest 4 neighbors): if cell is at coordinate (x,y), the four neighbours are those at coordinates (x+1,y), (x-1,y), (x,y+1), (x,y-1).

The cells are arranged in a bidimensional grid and initially they are in a random state. At each generation a cell in state i evolves to state i+1 mod N if at least one of its neighbors is in state i+1. The color of each cell is determined by its state.

The following image is generated using Von Neumann neighborhood:

[click to enlarge]

But very interesting behaviors can also be obtained if we pick irregular/random neighborhoods.

# The Collatz Tree

The Collatz sequence is a sequence of numbers that follows these simple rules (or “algorithm”):

1. we start from a positive integer number N
2. if N is odd then we multiply it by 3 and add 1 (N’ = 3*N +1)
if N is even then we divide it by 2 (N’ = N / 2)
3. we repeat the rule 2 for the new number N’ and generate another new number N”, and so on …

For example if we start from number 7 the sequence is:

7→ 22→ 11→ 34→ 17→ 52→ 26→ 13→ 40→ 20→ 10→ 5→ 16→ 8→ 4→ 2→ 1→ 4→ 2→ 1→….

the final sequence 4→2→1 repeats forever.

Using computers we have checked the sequence generated by the first 10^20 numbers and all sequences soon or later reaches the value 1.

The Collatz conjecture says that ALL numbers converge to 1 … though the problem is simple, no one has been able to prove (or disprove) it formally. Jeffrey Lagarias stated in 2010 that the Collatz conjecture “is an extraordinarily difficult problem, completely out of reach of present day mathematics”.

I recently found a very interesting and well done video explaining how the Collatz sequences can be visualized graphically. Using simple rules they can be used to build an interesting tree-like pattern. For further details see the original video on the Numberphile channel.

I decided to implement the visualization in Processing and tried to vary some parameters that generate the Collatz-tree. Slowly varying those parameters results in a hypnotic abstract animation. I recorded it (saving each frame and combining them with the free ffmpeg tool) and added an abstract music (the music itself is partially generated using a Collatz sequence and manually adjusted trying to make it more harmonious).

This is the final video:

This is the Processing code; you can experiment with it and freely modify it; let me know if you find interesting variants (you can also download the code CollatzTtree.7z):

/**
* The Collatz Tree v1.0
*
* Put this file in a directory named CollatzTree and open it with Processing.
* https://www.algoritmarte.com/the-collatz-tree/
*
*
*  Some PARAMETERS to play with ...
*
*/
float FIRST_BRANCHLEN = 26;   // the length of the first branch of the tree
float START_AEVEN =  4;       // angle increase for even branches (degrees)
float START_AODD  = -8;       // angle increse for odd branches (degrees)
int BRANCHES = 24;            // number of branches
float SPEED_AEVEN = 0.4;      // "speed" of even angle (degrees per second)
float SPEED_AODD = -0.3;      // "speed" of odd angle (degrees per second)
int rollcol = 3;              // seconds between the roll of palette
int currscene = 1;            // current scene (used in animation) 0=static 1=forward 2=backward

// ------------------------------------------------------------
/**
* Other parameters used for the animation
*/

boolean frecord = false;             // set to true if you want to generate the frames
String recorddir = "D:/tmp/video/"; // where the frames are generated (warning they can occupy a lot of space)
int numsaved;
long scenelen[] = {
//0, 2000, 3000
//0,  8000, 124000
0,  8000, 100000
};
// ------------------------------------------------------------

/**
* "internal" parameters
*/
int FPS = 30; // frames per second
float ae = START_AEVEN * (PI/90); // convert start angle even in radiants
float ao = START_AODD * (PI/90);  // convert start angle odd in radiants
float acce = 0.001; // acceleration even
float acco = 0.001; // acceleration odd
float currspeede = 0;  // speed even
float currspeedo = 0;  // speed odd
float target_speede = SPEED_AEVEN;
float target_speedo = SPEED_AODD;
float zoom = 1;
float maxy, miny;
float cx, cy;
boolean fsetup = true;

int colray[] = {
0xff0000ff,0xff2000ff,0xff4000ff,0xff6000ff,
0xff8000ff,0xffA000ff,0xffC000ff,0xffE000ff,
0xffff00E0,0xffff00C0,0xffff00A0,0xffff0080,
0xffff0060,0xffff0040,0xffff6020,0xffff8000,
0xffffA000,0xffffC000,0xffffE000,0xffffff00,

0xffffE000,0xffffC000,0xffffA000,0xffff8000,
0xffff6020,0xffff0040,0xffff0060,0xffff0080,
0xffff00A0,0xffff00C0,0xffff00E0,0xffE000ff,
0xffC000ff,0xffA000ff,0xff8000ff,0xff6000ff,
0xff4000ff,0xff2000ff,
};

// ------------------------------------------------------------
int coff;       // value for shifting colors
long tm0 = 0;   // milliseconds at first draw
long maintimer; // current milliseconds
long tmbye;
/**
* A Collatz number
*/
class TCollatzPoint {
float branchlen = FIRST_BRANCHLEN;
float x, y, angle;
int num;
public TCollatzPoint( int num, float x, float y, float angle ) {
this.num = num; this.x = x; this.y = y; this.angle = angle;
}
public TCollatzPoint branch( int num2, float deltaangle ) {
float angle2 = angle + deltaangle;
float x2 = x + branchlen * cos( angle2 ) * zoom;
float y2 = y + branchlen * sin( angle2 ) * zoom;
TCollatzPoint res = new TCollatzPoint( num2, x2, y2, angle2 );
return res;
}
}

/**
* Initilization stuff
*/
void setup() {
frameRate( FPS );
size( 1280, 720, JAVA2D);
background(0);
cx = width / 2;
cy = height / 2;
if ( frecord ) currscene = 0;
zoom = 1;
cy = height-height/10;
drawCollatz(  ae , ao, BRANCHES );
drawCollatz(  ae , ao, BRANCHES );
fsetup = false;
}

/**
* Draw the Collatz tree
*/
void drawCollatz( float aeven, float aodd, int maxdepth ) {
TCollatzPoint buf[] = new TCollatzPoint[1024];
TCollatzPoint buf2[] = new TCollatzPoint[1024];
TCollatzPoint bufswap[];
int depth = 0;
int n = 0, m;
buf[n++] = new TCollatzPoint( 1, 0, 0, PI / 4 );
maxy = 0;
miny = 0;
strokeWeight( 2 ) ;
noFill();
while ( depth < maxdepth ) {
if (currscene == 0) {
stroke( 0xffffffff );
} else {
int c = colray[(coff + depth) % colray.length];
//c = (c % 0xffffff) | 0x80000000;
stroke( c );
}
m = 0;
for (int i = 0; i < n; i++) {
TCollatzPoint p = buf[i];
int num2 = p.num * 2;
if ( m >= buf.length - 1 ) break;
TCollatzPoint p2 = buf[i].branch( num2, aeven );
if (!fsetup) line( cx + p.x, cy - p.y, cx + p2.x, cy - p2.y );
if ( p2.y > maxy ) maxy = p2.y;
if ( p2.y < miny ) miny = p2.y;

buf2[m++] = p2;
if ( p.num > 1 && (p.num - 1 ) % 3 == 0) {
num2 = (p.num - 1) / 3;
p2 = buf[i].branch( num2, aodd );
if (!fsetup) line( cx + p.x, cy - p.y, cx + p2.x, cy - p2.y );
if ( p2.y > maxy ) maxy = p2.y;
if ( p2.y < miny ) miny = p2.y;
buf2[m++] = p2;
}
}
n = m;
bufswap = buf2;
buf2 = buf;
buf = bufswap;
depth++;
}
strokeWeight( 2 ) ;
stroke( 0xff00ff00);
fill(0xffffffff );
for (int i = 0; i < n; i++) {
TCollatzPoint p = buf[i];
if ( ! fsetup) ellipse( cx + p.x, cy - p.y, 7, 7 );
}
float f = (maxy - miny) / height;
float fy = (maxy + miny) / 2;
if ( fsetup) {
zoom += (0.92 - f );
cy += (height/2 + fy - cy);
} else {
if ( currscene == 0 ) {
//println( "maxy=" + maxy + " miny="+miny + " fy="+fy + " cy="+cy + " f="+f );
//zoom = 1 / f;
//cy = height;
} else {
zoom += (0.92 - f )/10;
cy += (height/2 + fy - cy)/100;
}
}
}

/**
* Current elapsed millisecodns (measured differenty if recording)
*/
long elapsedMs() {
if ( frecord ) {
return (long) 1000.0*(frameCount-1) /FPS;
} else {
return millis() - tm0;
}
}

/**
* Check if we've reached a new scene; if it has changed change the animation parameters
*/
void checkScene() {
int sc = 0;
for (int i = 0; i < scenelen.length; i++) {
if (maintimer > scenelen[i]) sc = i;
}
if ( abs( ae ) < 11*PI/180 && abs( ao ) < 11*PI/180 ) sc = 3;
if (sc != currscene) {
currscene = sc;
switch( currscene ) {
case 1 :
break;
case 2 :
target_speede = -SPEED_AEVEN;
target_speedo = -SPEED_AODD;
break;
case 3 :
acce *= 2; acco *= 2;
tmbye = maintimer + 10000;
target_speede = 0;
target_speedo = 0;
break;
}
}
}

/**
* Very naive speed management
*/
float changeSpeed( float curr, float target, float acc ) {
if ( curr < target ) {
curr += acc;
if ( curr > target ) curr = target;
}
if ( curr > target ) {
curr -= acc;
if ( curr < target ) curr = target;
}
return curr;
}
/**
* Main draw routine
*/
void draw() {
maintimer = elapsedMs();
background(0);
drawCollatz(  ae , ao, BRANCHES );
if ( currscene > 0) {
ae += currspeede * (PI/90) / FPS;
ao += currspeedo * (PI/90) / FPS;
currspeede = changeSpeed( currspeede, target_speede, acce );
currspeedo = changeSpeed( currspeedo, target_speedo, acco );

if ( ( frameCount % (rollcol*FPS) ) == 0 && currscene < 3) coff++;
}
if ( frecord ) {
checkScene();
if ( tmbye == 0 || maintimer < tmbye ) {
numsaved = frameCount;
saveFrame( recorddir + "vid-######.tga" );
} else {
strokeWeight( 1 );
stroke(0xffffffff);
fill(0xffffffff);
text( "VIDEO ENDED RECORDED FRAMES: " + numsaved, 50, 50 );
}
}
}