February 03, 2022

Conway's Game of Life

edit

In a previous post, The Simulation Pattern, I mentioned Conway’s Game of Life. In this post, we’re going to implement it using the simulation pattern.

The Game of Life is about cellular automata, that is, how do individuals governed by a set of rules interact in a system. In this case, the individuals are the cells that make up a 2-dimensional grid.

The game is a simulation because it advances in discrete increments. During each tick, our cells may or may not change their state. Let’s go over those states and the rules that govern the cellular behavior.

Each cell can be in one of two states: alive or dead. Cells die or reanimate based on a set of conditions. Those are:

  • An alive cell with fewer than 2 neighbors dies
  • An alive cell with 2 or 3 neighbors lives
  • An alive cell with 4 or more neighbors dies
  • A dead cell with exactly 3 neighbors reanimates

Given those rules, we can start to write the code that meets that criteria. I’m going to use JavaScript & React, but I encourage you to try and write this in all sorts of languages and frameworks. It can be a lot of fun to explore a familiar problem in different ways.

Let’s create the shell of our simulation’s factory function. Our initial state will be a 2-dimensional array of 10 rows and 10 columns, and every value will be false.

// Creates a 10 x 10 2d array of falses
const initialState = Array(10)
  .fill()
  .map(() => Array(10).fill(false))

function createGameOfLifeSim() {
  let state = initialState

  return {
    tick() {},
    getState() {
      return state
    },
  }
}

Next, we need to encode the Game of Life rule’s inside our tick method. Because we frequently need to get a cell’s neighbors, let’s write a function that manages that functionality. Since this function needs access to the current state, we can write it in the closure of our factory function:

function createGameOfLifeSim() {
  let state = initialState

  function getNumberOfNeighbors(rowIdx, colIdx) {
    const neighborIndices = [
      [rowIdx - 1, colIdx - 1],
      [rowIdx - 1, colIdx],
      [rowIdx - 1, colIdx + 1],
      [rowIdx, colIdx - 1],
      [rowIdx, colIdx + 1],
      [rowIdx + 1, colIdx - 1],
      [rowIdx + 1, colIdx],
      [rowIdx + 1, colIdx + 1],
    ]

    const neighbors = neighborIndices
      .map(([row, col]) => state?.[row]?.[col])
      .filter(Boolean).length

    return neighbors.length
  }

  return {
    tick() {},
    getState() {
      return state
    },
  }
}

I think it’s worth examining this function briefly. To start, we create an array of neighborIndices. These are the row and column indexes we will use to retrieve the neighbor values from the state grid.

Next, we want to determine how many neighbors have the value true. To do this, we map over the neighborIndices. Cells that are on the edge of our grid will create neighborIndices outside the bounds of our grid, and so we use optional chaining, the ?. you see there, to avoid errors that come from trying to access non-existent values.

After that, it’s your basic filter(Boolean), making use of pointfree programming, to only get trues and then the length.

Now that we can efficiently get the number of alive neighbors a cell has, we can write the conditional logic to determine the next state.

return {
  tick() {
    const nextState = state.map((row, rowIdx) => {
      return row.map((cell, colIdx) => {
        const neighbors = getNumberOfNeighbors(rowIdx, colIdx)

        // A dead cell only reanimates with exactly 3 neighbors
        if (!cell) return neighbors === 3

        // An alive cell only stays alive with 2 or 3 neighbors
        switch (neighbors) {
          case 2:
          case 3:
            return true
          default:
            return false
        }
      })
    })

    state = nextState

    // Will allow us to chain .getState() after a call to .tick()
    return this
  },
}

I’ve divided the logic into two sections: a guard and early return when the cell is dead, and a small switch when the cell is alive. I often prefer to use switches because they are similar to pattern matching, and in this case, the fallthrough works to our benefit.

This is the crux of our simulation. The full code should look like this so far:

// Creates a 10 x 10 2d array of falses
const initialState = Array(10)
  .fill()
  .map(() => Array(10).fill(false))

function createGameOfLifeSim() {
  let state = initialState

  function getNumberOfNeighbors(rowIdx, colIdx) {
    const neighborIndices = [
      [rowIdx - 1, colIdx - 1],
      [rowIdx - 1, colIdx],
      [rowIdx - 1, colIdx + 1],
      [rowIdx, colIdx - 1],
      [rowIdx, colIdx + 1],
      [rowIdx + 1, colIdx - 1],
      [rowIdx + 1, colIdx],
      [rowIdx + 1, colIdx + 1],
    ]

    const neighbors = neighborIndices
      .map(([row, col]) => state?.[row]?.[col])
      .filter(Boolean).length

    return neighbors.length
  }

  return {
    tick() {
      const nextState = state.map((row, rowIdx) => {
        return row.map((cell, colIdx) => {
          const neighbors = getNumberOfNeighbors(rowIdx, colIdx)

          // A dead cell only reanimates with exactly 3 neighbors
          if (!cell) return neighbors === 3

          // An alive cell only stays alive with 2 or 3 neighbors
          switch (neighbors) {
            case 2:
            case 3:
              return true
            default:
              return false
          }
        })
      })

      state = nextState

      return this
    },
    getState() {
      return state
    },
  }
}

I want to add two more methods that will be useful for us when we build our UI: a randomize method and a toggleCell method. First, randomize:

const randomBool = () => Boolean(Math.round(Math.random()))

//... inside our factory function
return {
  //... the return of our sim
  randomize() {
    state = state.map(row => row.map(randomBool))
    return this
  },
}

With randomize, we generate a completely random grid of trues and falses. Next, let’s write toggleCell. This will allow a user to click on a cell and toggle its state.

return {
  //... the return of our sim
  toggleCell(rowIdx, colIdx) {
    state[rowIdx][colIdx] = !state[rowIdx][colIdx]
    /**
     * Because React requires immutable changes to know that
     * state has updated, we're going to clone the current state
     * in order to create an immutable update
     *
     * It's a pain in the butt, but it's what we gotta do
     *
     * Alternatives would be creating/using a clone util or
     * a package like Immer
     */
    state = state.map(row => row.map(x => x))
    return this
  },
}

Now with those extra methods in place, we can build our UI. Because we’ve built our sim as a plain object with state held in closure, we can use it with whatever framework (or lack thereof) that we want. We just have to adapt it to the framework. That said, adapting it can result in some strange patterns. We’ll see that as we make this work with React.

Let’s start with our basic markup and build up the functionality of our UI. I’m going to use inline styles for the sake of simplicity, but use whatever styling method you prefer:

function GameOfLife() {
  const grid = [] // just a placeholder, will eventually be stateful

  return (
    <div style={{ display: 'flex', justifyContent: 'center' }}>
      {/* Our grid */}
      <div>
        {grid.map((row, rowIdx) => {
          return (
            <div key={rowIdx} style={{ display: 'flex' }}>
              {row.map((cell, colIdx) => {
                return <button key={colIdx} onClick={() => {}} type="button" />
              })}
            </div>
          )
        })}
      </div>
      {/* Our actions */}
      <div style={{ display: 'flex', justifyContent: 'space-between' }}>
        <button onClick={() => {}} type="button">
          Start
        </button>
        <button onClick={() => {}} type="button">
          Randomize
        </button>
      </div>
    </div>
  )
}

Now that we have our basic UI, let’s add our simulation to the component. We want to have a single simulation for the lifetime of our component. The simplest way to do this is with useRef. However, as I’ve written about before in Comparing useRef and useState, changes to a ref will not cause our component to update, so we’ll need a useState as well. Here’s how we’re going to make that happen:

function GameOfLife() {
  const simRef = React.useRef(createGameOfLifeSim())
  const [grid, setGrid] = React.useState(simRef.current.getState())

  //... the rest of the component
}

Now, whenever we make an update to our sim, we’ll have to use setGrid on the new state to update our UI. Bit of a pain, but manageable.

Let’s build out some of the UI functionality next. The primary function we need to add next is the button that starts and stops our simulation. What good is the Game of Life if it never ticks?

To do this, we’re going to use an effect that will call tick on an interval while the game is running, and stop when the game is paused. We can set that up like this:

const INTERVAL = 150

function GameOfLife() {
  const simRef = React.useRef(createGameOfLifeSim())
  const [grid, setGrid] = React.useState(simRef.current.getState())
  const [gameState, setGameState] = React.useState('paused')

  React.useEffect(() => {
    // If the game is paused, the effect should do nothing
    if (gameState === 'paused') return

    // Otherwise, setup the interval...
    const intervalId = setInterval(() => {
      // Because refs and state setters are stable across renders,
      // none of these need to be included as dependencies of the effect
      setGrid(simRef.current.tick().getState())
    }, INTERVAL)

    // ...and clean it up
    return () => {
      clearInterval(intervalId)
    }
  }, [gameState])

  // Our handling function for toggling the state of the game
  const handleGameStateToggle = React.useCallback(() => {
    setGameState(s => (s === 'paused' ? 'running' : 'paused'))
  }, [])

  return (
    //... most of the UI
    <button onClick={handleGameStateToggle} type="button">
      {gameState === 'paused' ? 'Start' : 'Stop'}
    </button>
    //... the rest of the UI
  )
}

Our game is ready to run, but all the cells are dead so nothing will happen. Let’s make use of our randomize and toggleCell methods from before so we can change the state of our cells.

function GameOfLife() {
  //...
  const handleRandomize = React.useCallback(() => {
    setGrid(simRef.current.randomize().getState())
  }, [])

  // Pay attention here, we're going to use a higher order function so that
  // we can partially apply the rowIdx and colIdx values
  const handleToggleCell = React.useCallback(
    (rowIdx, colIdx) => () => {
      setGrid(simRef.current.toggleCell(rowIdx, colIdx).getState())
    },
    [],
  )

  return (
    <div>
      //...then in the cell button UI
      <button
        key={colIdx}
        onClick={handleToggleCell(rowIdx, colIdx)}
        type="button"
      />
      //...then in our actions UI
      <button onClick={handleRandomize} type="button">
        Randomize
      </button>
    </div>
  )
}

Now we have all the pieces for our Game of Life. Your component code should look something like this:

const INTERVAL = 150

function GameOfLife() {
  const simRef = React.useRef(createGameOfLifeSim())
  const [grid, setGrid] = React.useState(simRef.current.getState())
  const [gameState, setGameState] = React.useState('paused')

  React.useEffect(() => {
    if (gameState === 'paused') return

    const intervalId = setInterval(() => {
      setGrid(simRef.current.tick().getState())
    }, INTERVAL)

    return () => {
      clearInterval(intervalId)
    }
  }, [gameState])

  const handleGameStateToggle = React.useCallback(() => {
    setGameState(s => (s === 'paused' ? 'running' : 'paused'))
  }, [])

  const handleRandomize = React.useCallback(() => {
    setGrid(simRef.current.randomize().getState())
  }, [])

  const handleToggleCell = React.useCallback(
    (rowIdx, colIdx) => () => {
      setGrid(simRef.current.toggleCell(rowIdx, colIdx).getState())
    },
    [],
  )

  return (
    <div style={{ display: 'flex', justifyContent: 'center' }}>
      <div>
        {grid.map((row, rowIdx) => {
          return (
            <div key={rowIdx} style={{ display: 'flex' }}>
              {row.map((cell, colIdx) => {
                return (
                  <button
                    key={colIdx}
                    onClick={handleToggleCell(rowIdx, colIdx)}
                    type="button"
                  />
                )
              })}
            </div>
          )
        })}
      </div>
      <div style={{ display: 'flex', justifyContent: 'space-between' }}>
        <button onClick={handleGameStateToggle} type="button">
          {gameState === 'paused' ? 'Start' : 'Stop'}
        </button>
        <button onClick={handleRandomize} type="button">
          Randomize
        </button>
      </div>
    </div>
  )
}

The only thing left for you to do is tweak some styles. Specifically, you should play around with the buttons for each cell. Style them based on their current state. Have fun with it and see what you come up with.

Here’s a version of our game right here. Click randomize and get the simulation started:

Recap

The Game of Life is an interesting exercise that can use the simulation pattern. It’s a great starting point for learning cellular automata. Change the rules, build it in other languages and frameworks, explore to your heart’s content.


Liked the post?
Give the author a dopamine boost with a few "beard strokes". Click the beard up to 50 times to show your appreciation.
Kyle Shevlin's face, which is mostly a beard with eyes

Kyle Shevlin is the founder & lead software engineer of Agathist, a software development firm with a mission to build good software with good people.

Logo for Data Structures and Algorithms
Data Structures and Algorithms
Check out my courses!
If you enjoy my posts, you might enjoy my courses, too. Click the button to view the course or go to Courses for more information.
Sign up for my newsletter
Let's chat some more about TypeScript, React, and frontend web development. Unsubscribe at any time.