RoboCatz.com

## Playbook: Cellular Automata -- The Exercise

Purpose: Learning how to program a cellular automata algorithm.

The goal of this exercise is to be able to create an algorithm to generate cellular automata.

### Requirements

This exercise requires you to use the Computer Art program from the RoboCatz website. You will write a program according to the instructions below. Try not to just jump to the end of the lesson and copy the whole program. You won't learn much by doing that. Follow the individual steps shown below. Follow them in order--so that you'll know what to do when you have to write your own programs some day.

Initialize 2 variables to help generate the dimensions of the cellular world:

numRows = 14
numCols = 28

In the Computer Art program, click on "Lesson 1", delete all of the code from that lesson and insert the two variable assignment statements above.

Add to your new program, two statements to calculate the width and height of each cell in the maze:

rowHeight = maxy / numRows
colWidth = maxx / numCols

In generating the cellular world, we will use colors to help observe the program in action. The world will also require an Array to store information about the location of the cells in the world. Add the following assignments to your new program:

Arr = [] // Empty Array
colors = ['white','green']

At this point, your program should appear as:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']```
Feel free to copy the above program to get started.

Next, add the following for() loops to the end of your program. These loops will help to create each cell in the cellular world.

Example:
```for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column

}
}```
At this point your program should appear as follows:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
}
}```
Feel free to copy the above program.

Now we will add cells to the array by pushing a literal object. Each cell will contain two properties: .isAlive and .continueLiving. Both of these properties will be initially set to false. Later in the program we will write code to set certain cells to be "alive".

Add the following line to the inner for() loop:

`Arr[i].push( {isAlive:false, continueLiving: false} ) // Create a cellular organism`

At this point, your program should appear as follows:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
Arr[i].push( {isAlive:false, continueLiving: false} ) // Create a cellular organism
}
}```
Each cell is an object that has two properties. Both properties are set to "false".

### Drawing the Cell Walls

The walls of the cells will be drawn using the rectangle function. It is also necessary to store the rectangle object within the cell object itself. In this case, the return value from the rectangle() function will be assigned to a property .rect which is going to be defined as part of the cell. Add the following three (3) lines to your inner for loop:

`x = colWidth * j                           // Calculate a X-coordinatey = rowHeight * i                          // Calculate a Y-coordinateArr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle`

At this point, your code should appear as:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
x = colWidth * j                           // Calculate a X-coordinate
y = rowHeight * i                          // Calculate a Y-coordinate
Arr[i].push( {isAlive:false, continueLiving: false} ) // Create a cellular organism
Arr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle
}
}```
Run the program and you should see the cells--none of which are alive at this point. Adjust the color of the border to the following string: "#f0f0f0". See below:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green','blue','yellow','purple','black']
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
x = colWidth * j                           // Calculate a X-coordinate
y = rowHeight * i                          // Calculate a Y-coordinate
Arr[i].push({isAlive:false, continueLiving: false}) // Create a cellular organism
Arr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle
Arr[i][j].rect.border('#f0f0f0')           // Light border on the rectangle
}
}```
We will use the .fill() method to indicate the life of the cell. Cells that are filled with "white" are dead cells and cells that are filled with color are alive cells. This .fill() method will be used inside a function which we will create called render. Add the following render function to the end of your program.

```function render() {                            // Show the status of every organism
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].rect.fill(colors[Arr[i][j].isAlive*1])  // Fill with color (from array)
}
}
}```
Notice that the render function uses two for loops to scan each cell and .fill() it with colors[] which is indexed based on the .isAlive property of the cell. The multiplication of the .isAlive property by 1 is done to "normalize" it by converting it to a numeric value whether it was a Boolean, String, or Number.

Your program should now appear as:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
x = colWidth * j                           // Calculate a X-coordinate
y = rowHeight * i                          // Calculate a Y-coordinate
Arr[i].push({isAlive:false, continueLiving: false}) // Create a cellular organism
Arr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle
Arr[i][j].rect.border('#f0f0f0')           // Light border on the rectangle
}
}
function render() {                            // Show the status of every organism
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].rect.fill(colors[Arr[i][j].isAlive*1])  // Fill with color (from array)
}
}
}```

Any error messages? I hope not.

The next step is to add a function to toggle the state of the cell. This function will toggle the cell's life from "alive" to "dead" and then back to "alive". This function will also become part of the cell itself which we will refer to as a method of the cell object. Add the following statements:

`Arr[i][j].clicked = function clickCell() {     // Click handler function  this.isAlive = !this.isAlive                 // Toggles the state of isAlive  this.rect.fill( colors[this.isAlive*1] )     // Fill with color based on state}`

Notice that this function includes statements that use the keyword: this In JavaScript the keyword this will refer to the object that encapsulates the method. Because we are encapsulating the method within the "cell object", any reference to "this" will refer to the cell itself and any (and all) properties of the cell.

The encapsulation of the method into the "cell object" is performed by assigning the value of a function to a property of the cell. You are "assigning" through the assignment operator (=) the value "function()" to a property of the cell called .clicked. This assignment will make .clicked a method that can be used on the cell (and ONLY on the cell). The method is "scoped" so that it can ONLY be used with the cell and not with anything else. It will only recognize the properties of the cell and any global variables that may have been defined earlier.

Your program should now appear as:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
x = colWidth * j                           // Calculate a X-coordinate
y = rowHeight * i                          // Calculate a Y-coordinate
Arr[i].push({isAlive:false, continueLiving: false}) // Create a cellular organism
Arr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle
Arr[i][j].rect.border('#f0f0f0')           // Light border on the rectangle
Arr[i][j].clicked = function() {           // Allow interaction with user
this.isAlive = !this.isAlive             // Toggles the state of isAlive
this.rect.fill( colors[this.isAlive*1] ) // Fill with color based on state
}
}
}
function render() {                            // Show the status of every organism
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].rect.fill(colors[Arr[i][j].isAlive*1])  // Fill with color (from array)
}
}
}```
You have just added a method to the cell. The purpose of the method was to toggle the .isAlive status. The .isAlive status is toggled using:

`this.isAlive = !this.isAlive`

This is a common technique to toggle Boolean states. If it was false, it will become true. If it was true, it will become false. The exclamation point means "not" in JavaScript. Once the state has been toggled, the cell will be filled with color depending on the now current state of the cell:

`this.rect.fill( colors[this.isAlive*1] )     // Fill with color based on state`

The encapsulation of the function is performed by assigning the function to a property of the "cell object" using:

`Arr[i][j].clicked = function() { ... }`

In this statement, a function is being assigned to the property of .clicked which is being created here. This will enable us to execute a statement such as:

`Arr[i][j].clicked()`

This function is now a method of the cell. And executing the method will change the state of the cell from dead to alive and back to dead. This method will toggle the state of the cell.

### Click Handler - Processing Mouse Events in Windows

Clicking a mouse button or pressing a keyboard key will cause an "event" to be sent to your program. The event is handled using an "event handler" function. The "event handler" function can be created in the same way we created the method to toggle the state of the cell. In this example, we will use a pre-defined property (.onclick) of the "window" object. Whatever function we assign to this property will be executed when the mouse is clicked. As an event handler the system will send details about the event into the function through an argument which we will call: event. Add the following to the bottom of your program:

`canvasDiv=document.getElementById('canvas')window.onclick = function(event) {             // Will handle the clicks in the panel let x = event.x - canvasDiv.offsetLeft        // Boxes are offset on left and top j=floor(x/colWidth)                           // Calculate an index value for j (col) let y = event.y - canvasDiv.offsetTop i=floor(y/rowHeight)                          // Calculate an index value for i (row) Arr[i][j].clicked()                           // Execute the object's click handler}`

The purpose of this function is to determine which cell the user clicked and to then toggle the state of that cell. With a mouse event, the event's value will have several properties including: .x and .y which correspond to the coordinates of the mouse at the time it was clicked. The above function will calculate the index values of i and j based on the x coordinate divided by the width of each cell and the y coordinate divided by the height of each cell. The row and column index values will identify the cell that the user was over when they clicked the mouse. You can then toggle the state of that cell by calling the cell's .clicked() method.

Your program should now appear as follows:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
x = colWidth * j                           // Calculate a X-coordinate
y = rowHeight * i                          // Calculate a Y-coordinate
Arr[i].push({isAlive:false, continueLiving: false}) // Create a cellular organism
Arr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle
Arr[i][j].rect.border('#f0f0f0')           // Light border on the rectangle
Arr[i][j].clicked = function() {           // Allow interaction with user
this.isAlive = !this.isAlive             // Toggles the state of isAlive
this.rect.fill( colors[this.isAlive*1] ) // Fill with color based on state
}
}
}
function render() {                            // Show the status of every organism
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].rect.fill(colors[Arr[i][j].isAlive*1])  // Fill with color (from array)
}
}
}
canvasDiv=document.getElementById('canvas')
window.onclick = function(event) {             // Will handle the clicks in the panel
let x = event.x - canvasDiv.offsetLeft        // Boxes are offset on left and top
j=floor(x/colWidth)                           // Calculate an index value for j (col)
let y = event.y - canvasDiv.offsetTop
i=floor(y/rowHeight)                          // Calculate an index value for i (row)
Arr[i][j].clicked()                           // Execute the object's click handler
}```

### Conway's "Game of Life"

#### Rules

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
These rules can be simplified to:
1. Any live cell with two or three live neighbours survives.
2. Any dead cell with three live neighbours becomes a live cell.
3. All other live cells die in the next generation. Similarly, all other dead cells stay dead.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

We will use a function to determine if a cell should be alive or dead. We will call this function: "willLive". We will pass through arguments into the function the index values for the row and column of the cell being analyzed. Inside the function, we will create a "sum" of the number of currently alive neighbors of our target cell. Each time an "alive" neighbor is found, we will increment the sum by one (1). Then we will check the sum to determine if it qualifies for "continuing life". See outline of the function below:

Example:
```function willLive(i, j) {
let sum = 0                                  // Initialize a sum variable
// Check each of 8 neighboring cells
}```
This function will return a Boolean value indicating if the cell should be alive or dead. The default return value will be "false" indicating a dead cell. If the conditions are met for life, then a value of "true" will be returned.

Example:
```function willLive(i, j) {
let sum = 0                                  // Initialize a sum variable
// Check each of 8 neighboring cells
return false
}```
Next, we will add two rules for determining life: 1) If alive and exactly two live neighbors, remain alive, 2) If exactly 3 live neighbors, then life.

Example:
```function willLive(i, j) {
let sum = 0                                  // Initialize a sum variable
// Check each of 8 neighboring cells
if ( Arr[i][j].isAlive && sum == 2 ) return true // remain alive if sum==2
if ( sum == 3 ) return true  // remain alive if sum==3; or spawn new life if sum==3
return false // die from lack of neighbors or from overcrowding; or just remain dead
}```
Next, we will check each of the surrounding 8 neighbor cells.

Example:
```function willLive(i, j) {
let sum = 0                                  // Initialize a sum variable
// Check each of 8 neighboring cells
if (Arr[Math.max(i-1,0)][Math.max(j-1,0)].isAlive) sum++
if (Arr[Math.max(i-1,0)][j].isAlive) sum++
if (Arr[Math.max(i-1,0)][Math.min(j+1,numCols-1)].isAlive) sum++
if (Arr[i][Math.max(j-1,0)].isAlive) sum++
if (Arr[i][Math.min(j+1,numCols-1)].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][Math.max(j-1,0)].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][j].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][Math.min(j+1,numCols-1)].isAlive) sum++
if ( Arr[i][j].isAlive && sum == 2 ) return true // remain alive if sum==2
if ( sum == 3 ) return true  // remain alive if sum==3; or spawn new life if sum==3
return false // die from lack of neighbors or from overcrowding; or just remain dead
}```
When checking each of the neighbors, we will use .max() and .min() to help make sure we are not checking array elements that are not in the array. For example, the row above our target cell will be referenced by Math.max(i-1,0). The Math.max() will help ensure that if the expression i-1 ever returns a negative number, then the index to be used will be zero (0) since zero is "max" to any negative number.

The Math.min() will help ensure we do not reference a row greater than the number of rows in the array. The greatest index number for rows will be numRows-1. If the expression, i+1 returns a value greater than numRows-1, then use the "min" value (which will be: numRows-1).

Your program should now appear as follows:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green']
function willLive(i, j) {
let sum = 0                                  // Initialize a sum variable
// Check each of 8 neighboring cells
if (Arr[Math.max(i-1,0)][Math.max(j-1,0)].isAlive) sum++
if (Arr[Math.max(i-1,0)][j].isAlive) sum++
if (Arr[Math.max(i-1,0)][Math.min(j+1,numCols-1)].isAlive) sum++
if (Arr[i][Math.max(j-1,0)].isAlive) sum++
if (Arr[i][Math.min(j+1,numCols-1)].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][Math.max(j-1,0)].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][j].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][Math.min(j+1,numCols-1)].isAlive) sum++
if ( Arr[i][j].isAlive && sum == 2 ) return true // remain alive if sum==2
if ( sum == 3 ) return true  // remain alive if sum==3; or spawn new life if sum==3
return false // die from lack of neighbors or from overcrowding; or just remain dead
}
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
x = colWidth * j                           // Calculate a X-coordinate
y = rowHeight * i                          // Calculate a Y-coordinate
Arr[i].push({isAlive:false, continueLiving: false}) // Create a cellular organism
Arr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle
Arr[i][j].rect.border('#f0f0f0')           // Light border on the rectangle
Arr[i][j].clicked = function() {           // Allow interaction with user
this.isAlive = !this.isAlive             // Toggles the state of isAlive
this.rect.fill( colors[this.isAlive*1] ) // Fill with color based on state
}
}
}
function render() {                            // Show the status of every organism
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].rect.fill(colors[Arr[i][j].isAlive*1])  // Fill with color (from array)
}
}
}
canvasDiv=document.getElementById('canvas')
window.onclick = function(event) {             // Will handle the clicks in the panel
let x = event.x - canvasDiv.offsetLeft        // Boxes are offset on left and top
j=floor(x/colWidth)                           // Calculate an index value for j (col)
let y = event.y - canvasDiv.offsetTop
i=floor(y/rowHeight)                          // Calculate an index value for i (row)
Arr[i][j].clicked()                           // Execute the object's click handler
}```

### Using Keyboard Events to Step Through Evolution

To process a step of evolution, the state of each cell will need to be checked to see if it should remain alive in the next generation. We will keep track of this status by setting a ".continueLiving" property to the results of the willLive() function.

After all of the cells have been checked, we will then update the .isAlive property by assigning it the value of the .continueLiving property.

Once all of those assignments have been made, then we will update the display using the render() function.

Example:
```window.onkeypress = function(e) {
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].continueLiving = willLive(i, j)// Set the continueLiving flag
}
}
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].isAlive = Arr[i][j].continueLiving // Set the isAlive status
}
}
render()                                     // Show the current state of the world
}```
The final version of the program should now appear as:

Example:
```numRows = 14
numCols = 28
rowHeight = maxy / numRows                     // Dimensions of rows
colWidth = maxx / numCols                      // Dimensions of columns
Arr = []                                       // Empty array
colors = ['white','green','blue','yellow','purple','black']
function willLive(i, j) {
let sum = 0                                  // Initialize a sum variable
// Check each of 8 neighboring cells
if (Arr[Math.max(i-1,0)][Math.max(j-1,0)].isAlive) sum++
if (Arr[Math.max(i-1,0)][j].isAlive) sum++
if (Arr[Math.max(i-1,0)][Math.min(j+1,numCols-1)].isAlive) sum++
if (Arr[i][Math.max(j-1,0)].isAlive) sum++
if (Arr[i][Math.min(j+1,numCols-1)].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][Math.max(j-1,0)].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][j].isAlive) sum++
if (Arr[Math.min(i+1,numRows-1)][Math.min(j+1,numCols-1)].isAlive) sum++
if ( Arr[i][j].isAlive && sum == 2 ) return true // remain alive if sum==2
if ( sum == 3 ) return true  // remain alive if sum==3; or spawn new life if sum==3
return false // die from lack of neighbors or from overcrowding; or just remain dead
}
for (i=0; i<numRows; i++) {                    // Create the cells
Arr.push( [] )                               // Each row has an array of columns
for (j=0; j<numCols; j++) {                  // For each column
x = colWidth * j                           // Calculate a X-coordinate
y = rowHeight * i                          // Calculate a Y-coordinate
Arr[i].push({isAlive:false, continueLiving: false}) // Create a cellular organism
Arr[i][j].clicked = function() {           // Allow interaction with user
this.isAlive = !this.isAlive             // Toggles the state of isAlive
this.rect.fill( colors[this.isAlive*1] ) // Fill with color based on state
}
Arr[i][j].rect = rectangle(x+1,y+1,colWidth-3,rowHeight-3) // Draw rectangle
Arr[i][j].rect.border('#f0f0f0')           // Light border on the rectangle
}
}
function render() {                            // Show the status of every organism
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].rect.fill(colors[Arr[i][j].isAlive*1])  // Fill with color (from array)
}
}
}
canvasDiv=document.getElementById('canvas')
window.onclick = function(event) {             // Will handle the clicks in the panel
let x = event.x - canvasDiv.offsetLeft        // Boxes are offset on left and top
j=floor(x/colWidth)                           // Calculate an index value for j (col)
let y = event.y - canvasDiv.offsetTop
i=floor(y/rowHeight)                          // Calculate an index value for i (row)
Arr[i][j].clicked()                           // Execute the object's click handler
}

window.onkeypress = function(e) {
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].continueLiving = willLive(i, j)// Set the continueLiving flag
}
}
for (i=0; i<numRows; i++) {                  // Each row
for (j=0; j<numCols; j++) {                // Each column
Arr[i][j].isAlive = Arr[i][j].continueLiving // Set the isAlive status
}
}
render()                                     // Show the current state of the world
}```

### Patterns to Explore

Try the following patters to see what happens.

### Bonus Exercises

#### Implementing Toroidal Topology

This means that opposing edges of the grid are connected. The rightmost column is the neighbor of the leftmost column and the topmost row is the neighbor of the bottommost row and vice versa. This allows the unrestricted transfer of state information across the boundaries.