Cellular Automata: Building the Game of Life

As Lambda School is winding to a close, the format of the weekly sprint challenges testing our knowledge has quickly changed. There are no more heavily commented repos, no more step-by-step README.md files that lay out our path for the three hours of the challenge. Instead, the challenges pose a problem and give us free reign in interpreting it and writing code to solve it.

This week’s challenge was four and a half days long, and it’s the best example yet of this open-ended approach. On Monday, we forked and cloned the repo describing Conway’s Game of Life with instructions to build a visual representation of that game using our primary language, including a couple of functional requirements. For me, this meant javaScript and React. In the next few sections, I’ll lay out how I applied Polya’s Problem Solving Technique to build an app that represents Conway’s Game of Life.

STEP 1: Understand the Problem

It seemed like there were two main pieces of the problem to dissect. First, what even is Conway’s Game of Life?

Turns out, it’s a grid-based simulation, in which cells in the grid can be either alive or dead. Their status is determined by a set of rules, which measure the status of each cell’s 8 neighbors (N, E, S, W, NE, NW, SE, SW), and make a wholesale change to every cell in the grid based on the following rules:

1. The cell is living and has fewer than 2 live neighbors. In the next generation, this cell is dead. (Loneliness?)
2. The cell is living and has 2 or 3 live neighbors. In the next generation, this cell lives. (Goldilocks.)
3. The cell is living and has greater than 3 live neighbors. In the next generation, this cell dies. (Overcrowding.)
4. The cell is dead and has 3 live neighbors. In the next generation, this cell lives. (Lazarus!)

So, the rules are four simple conditional statements. One generation is observed, the rules are applied, and cells’ statuses are changed accordingly when the next generation is displayed. I felt confident that I could write the logic for that, and put it on the back burner.

The second piece of the problem was more operational:

• I’d have to build an app that ran the simulation, and had multiple functions that would operate on the simulation. It also needed to display the generation — i.e. how many times cells had been evaluated and their fates decided.
• I’d have to deploy that app to production somewhere

STEP 2: Devising a Plan

So, how to display this thing? What even is React? I broke down my planning into a couple of steps.

1. Figure out how to display a Grid. Then, how do you change the status of a cell in that Grid and re-render appropriately
2. Plan a double-buffer function to measure every cell in that grid against Conway’s rules, create a new Grid accordingly, then replace the old Grid with the new one.
3. What functionality does the Grid (and every component within it) need?
4. How do I deploy?

For the first step, I started to think in terms of React components. Going from largest to smallest, I figured I would need three. A Grid, which was made up of Rows, which were each composed of Cells. The child components would be represented by an array (of arrays filled with boolean values)in Grid’s state. All functions would be held in the Grid Class component and passed down as props to the Row and Cell functional components. At this early stage, I imagined rendering each component as a <div>, the color of which would change based on whether it was alive or dead.

Next, I created a list of functions I thought I’d need:

• toggleCell — change the value of a cell from alive to dead manually
• createGrid — take an integer (n) and create a grid array full of (n) row arrays full of (n) cell values (boolean false). This helper would come in handy in a couple of places
• findNeighbors — evaluate each cell in an existing grid, find the number of live neighbors. This is O(1) — it gets called on a cell, then accesses 8 distinct cells to increment a count variable. It returns that count variable, and updateGrid measures the conditional statements against it.
• updateGrid — Loop through the existing Grid and create a new Grid based on the evaluation of each cell in the existing grid. My first pass of this is O(n²). I have to loop through the outer array and consider each Row, and then loop through each Row, where I call findNeighbors on each cell. Based on the determination (i.e. this live cell has four live neighbors, kill it), I update the corresponding cell in the new blank grid. When every cell has been evaluated, I call setState on the Grid component to replace the old grid with the new one, and to increment the generation. All components then re-render based on the change to the props they’ve been passed. Nested loops, n² re-renders: I acknowledge this is a hacky first pass.
• startGame — after a few cells have been toggled, call updateGrid on an interval of 25 ms
• endGame — stop that interval
• resetGrid — replace the existing grid, whatever’s in state, with a blank grid. Reset the generation counter to 0.-

(Note: this is definitely not the fastest way to do this. I wanted to get an ugly version done and iterate from there.)

Finally — I decided to deploy using Firebase, and to stick this on a route in my portfolio page (that at the moment you can’t get to from anywhere but direct URL entry).

STEP 3: Carrying Out the Plan

I… re-learned React. I like to think I kept things pretty tight. One class component, two functional components, a bunch of CSS. (Note, I do NOT like CSS. I might write about why later).

STEP 4: Looking Back

Three main notes:

My updateGrid algo is not especially performant (though it does work alright on grids < 50 squares) for two reasons. My initial inclination is that it’s actually the React re-render calls that are slowing it down. My next step is refactoring with the html Canvas component, which I opted out of for the sake of job interviews this week. I believe that’ll speed things up immensely.

My next step will be honing the algo in search of the mythical O(n) solution. I started the week playing with a solution that used hash tables, which I might revisit.

Finally, I want to implement a randomizer to start the Game. At the moment you have to choose which squares are alive and which are dead. While I personally don’t mind playing cell god, it’s not immediately intuitive. I’ve actually got this partially built, so it’ll probably be the next iteration.