Implementing Conway’s game of life.

#react #redux #computerscience #javascript

We just completed Build Week at Lambda school. What it is, in a nutshell, is a week without lectures, coding challenges, or instructions. All there is to do is apply all the knowledge garnered in the previous three weeks learning algorithms and Data Structures to build an implementation of Conway’s game of life. Exciting, no?

Usually, build weeks in Lambda school would be in teams of about five to six students from different cohorts forming some sort of Voltron to constitute a product team. However, we were required to work solo this time due to the scope of the project.

About the project

Conway’s game of life is a zero player game which means its evolution is determined by its initial input and no further interaction is required.

The game was invented by Cambridge mathematician, John Horton Conway. It became very popular when it was mentioned in an article published by Scientific American in 1970.

Also, the algorithm which the game is based on is Turing complete, which means that it is a system able to recognize or decide other data manipulation sets.

Fundamentally, Conway’s game of life is a grid featuring a collection of cells which can live, die or multiply, depending on the initial input configurations. These cells form various patterns as the grid evolves. These patterns are formed by the individual cells responding to the rules of the game.

The Rules

The rules examine each cell in the grid. For each cell, it counts the active neighbors. That is, the eight surrounding cells (up, down, left, right, and diagonals), and then acts on that result.

If the cell is alive and has 2 or 3 neighbors, then it remains alive. Else it dies.
Else, if the cell is dead and has exactly 3 neighbors, then it comes to life. Else, it remains dead.

Any number of different possible configurations can be used as the initial input, but one thing to note is that after a time, there might be nothing left on the grid, or as in some cases, the configuration lives forever.

There is no algorithmic way of telling if the configuration will last forever or fade away completely. If there is a configuration on the grid and you follow it for a thousand moves and it doesn’t die off, it could die-off on the thousand and first move, or the billionth. Following the progress gives you no clue, regardless of whether you track the cells for a hundred or a billion moves.

One would assume that if a thing is governed by rules as clear and simple as this, there would be a way of predicting future outcomes, but it turns out there isn’t. It is what makes the game astonishing.

My Implementation

The specs for the minimum viable product given to us by Lambda School stated that the 2d grid could be any size above 25 by 25. I chose to build mine with a 40 by 40 grid for no reason other than the fact that 1600 sounds to me like a very respectable number.

The next and probably the most important decision was what data structure to use in designing the grid. Here I chose to go with arrays in an object. That is, 40 arrays each containing 40 values in an object. These values will be either 0 or 1 representing the two possible cell states, alive and dead. Obviously, there are a plethora of options when it comes to possible data structures, each with their pros and cons, but I chose to opt for arrays and objects because of how relatively easy they are to manipulate, and also the size of data I was working with.

Since this implementation was created using React and Redux, what followed was architecting the Component and state structures. Nothing too complicated here, just decisions to be made on what components would be reused and what slices of state need to be managed globally.

Another important consideration was what behavior I wanted from the cells when they got to the end of the grid. I chose to design it such that that the cells that are off the edge of the grid wrap around to the far side. Another possible implementation would be to have every cell at the end of the grid to be in the ‘dead’ state. Obviously various implementations will have different effects on the lifecycle of the cells in the grid.

...some code

A helper function to create the actual grid.

const buildBoard = (height, width, random = false) => {
  let board = {};
  for (let i = 0; i < height; i++) {
    let row = [];
    for (var j = 0; j < width; j++) {
      if (random) {
        row.push(Math.round(Math.random()));
      } else {
        row.push(0);
      }
    }
    board[i] = row;
  }
  return board;
};

This buildGrid function takes in the height, width, and a boolean as inputs. The boolean is responsible for deciding whether or not the grid is made up of all dead cells or seeded with random living cells. Ergo, to build a 40 by 40 grid with random living cells, I will call the function like so.

buildGrid(40, 40, true)

Next, another function to implement the algorithm that sets the rules for the game.

export const nextSlide = (board = {}) => {
  // height is number of keys in object
  // width is length of each nested array
  let boardHeight = Object.keys(board).length;
  let boardWidth = board[0].length;

  const activeNeighbours = (x, y) => {
    const topRow = x - 1 < 0 ? boardHeight - 1 : x - 1;
    const bottomRow = x + 1 === boardHeight ? 0 : x + 1;
    const leftColumn = y - 1 < 0 ? boardWidth - 1 : y - 1;
    const rightColumn = y + 1 === boardHeight ? 0 : y + 1;

    let neighbours =
      board[topRow][leftColumn] +
      board[topRow][y] +
      board[topRow][rightColumn] +
      board[x][leftColumn] +
      board[x][rightColumn] +
      board[bottomRow][leftColumn] +
      board[bottomRow][y] +
      board[bottomRow][rightColumn];
    return neighbours;
  };

  let newSlide = {};
  for (let i = 0; i < boardHeight; i++) {
    let row = [];
    for (let j = 0; j < boardWidth; j++) {
      let isActive = board[i][j];
      let neighbours = activeNeighbours(i, j);
      if (isActive === 1) {
        if (neighbours < 2) {
          row.push(0);
        } else if (neighbours > 3) {
          row.push(0);
        } else {
          row.push(1);
        }
      }
      if (isActive === 0) {
        if (neighbours === 3) {
          row.push(1);
        } else {
          row.push(0);
        }
      }
    }
    newSlide[i] = row;
  }
  return newSlide;
};

This function takes in the grid object as its input, then calculates the height and width of the grid by checking how many keys are in the object and checking the length of the nested arrays. Since all the arrays are of the same size, it makes sense to check the length of just one.

Nested in the nextSlide function is a function to calculate the living neighbors of every cell passed to it. This function takes the x and y coordinates of the cell as input.

After that, I am passing every cell in the grid through the newSlide function to calculate the neighbors and then make sure that each cell lives or dies based on the rules of the algorithm. Pass each array into a new object, and then return that new object. Whew!

Fast-forward to creating a few popular presets (cell configurations), making play, fast forward, and random buttons. The game was almost complete with all the major features nailed down. All in three days of work.

Finally, I added a bit of copy and styled using just CSS. No CSS framework as I thought it'd be overkill.

You can find the repo on github, and the deployed site.

Moving forward

Working on this project was a great way to end the first half of my Computer Science section at Lambda School. Next week, we’ll be covering Hash tables. I don’t know very much about them at the moment so I’ll be reviewing the materials in the Training kit before then just so I don’t get stumped.

Also, and just as important, I’ll try to finish reading Joseph Heller’s Catch-22!