Home | David Nicholas

Inspiration

Every now and again I find myself getting engrossed with certain ideas or tid bits of information. When that happens, I like to build something that allows me to explore the concept further. My current obsession is Jon Conway's Game of Life. At some point, I came across a Veritasim video that explores Math's incompleteness and undecidibility.

Although not the main focus of the video, John Conway's Game of Life and its Turing completeness were the highlights. They pulled off a classic "Turing complete move" — demonstrating Turing completeness using the mechanism itself. In other words, they showcased the Game of Life being powered by the Game of Life.

I had always found the Game of Life intriguing, but after seeing that, I knew I had to build it. Nothing as complex as the Game of Life powering itself, just a single random game along with some of the well-known configurations and structures.

The Game of Life

The Game of Life, developed by John Conway in the 1970s, is a cellular automaton — a mathematical model that simulates complex processes using a grid of cells governed by simple rules. Conway's Game of Life, as the name suggests, mimics life, where cells on the grid either live or die based on four key rules:

Any live cell with fewer than two live neighbors dies.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies.
Any dead cell with exactly three live neighbors becomes a live cell.

These foundational rules give rise to a surprisingly complex universe within Conway's Game of Life. Amidst this complexity, researchers have identified and categorized several popular structures, each exhibiting well-defined behaviors. Some interesting ones are:

Still Lifes - Stable structures that don't change
Oscillators - Structures that return to their starting point after some period
Spaceships - Structures that travel across the grid

These structures highlight the diversity of Conway's Game of Life and set the stage for building our own simulator to experiment with these behaviors firsthand. Let's get building.

The Build

Building the Game of Life is a fairly straightforward endeavor. There are four key components we need to address:

The Grid / Game State
The Game Logic
Rendering the Game

The first two can (and should) be done without relying on a framework or library like Angular or React. The fourth is a matter of personal preference — in this post, we'll use React.

The Grid

Conway's Game of Life is traditionally played on an infinite grid, which would be interesting to implement. However, to keep things simple, we will use a finite grid and apply wrapping. There are several ways to wrap a grid, including:

Toroidal Grids - A toroidal grid stitches together the left and right edges as well as the top and bottom edges.
Cylindrical Grids - A cylindrical grid wraps only one pair of opposite edges, typically the vertical edges, forming a cylinder.
Möbius Strip Grids - A Möbius strip grid has one pair of opposite edges that wrap around with a twist, creating a non-orientable surface.

There are a couple of other grid types as well, and while it would be fun to get into the specifics of each, for the sake of this post, we'll be implementing a toroidal grid. In my opinion, this is the one that makes the most sense, making our implementation more straightforward.

Just like the several ways to implement a grid wrap, there are various ways to actually implement our grid. Our cells need to store whether or not they are alive. With this in mind, there are a few popular approaches we can use, including:

A multi-dimensional array
A one-dimensional array
A binary Number

Each of these has its own pros and cons. The multi-dimensional array closely matches our mental grid model, but creating and maintaining a multi-dimensional array can be complex. A one-dimensional array is easier to create and maintain but requires more effort to figure out neighboring cells, increasing the complexity of our game logic. A binary number is arguably easier to create and maintain, but it also has pronounced issues similar to those of a one-dimensional array regarding calculating neighbors.

Something else that might influence your choice of grid implementation is what information you want to store about each cell. Currently, we're just focusing on whether the cell is alive or dead. However, if you want to store additional information, such as how many generations a cell has been alive, some of these options become less viable.

It's been a while since I've worked with binary, so for this post, I'm going with the binary number implementation. As mentioned above, this means our game logic will be more complex since most of it will involve bit twiddling.

Using a binary number also requires access to very large numbers. In JavaScript/TypeScript, the primitive number type only goes up to 2^31 - 1, which means we will be using a more recently added primitive: bigint. The main benefit of using a binary number for the grid is the implmentation is a bigint which means there actually isn't any implmentation to discuss here beyond declaring a variable, however, since we are going to be moving between one and two dimensions and using a torodial grid, we will need a couple helper functions which will help out our game logic implmentation.

Converting Bit Position to Grid Coordinates

We need to know the size of the grid we're creating to convert a binary number to a grid. A board of size N x M requires a binary number that is N x M bits long. To simplify, I'll make my grid square, so M and N will be the same. To avoid confusion, let's call it gridLength instead of N

The basic idea for converting anything one dimensional to two dimension is to break it up into slices of size gridLength and stack them on top of each other. To calculate "x" coordinate of our bit we can modulo the position of the bit with the gridLength. This will tell us how far over the given cell is. This works because the modulo operation effectively resets the count after reaching the end of each row, aligning the bit positions with their respective "x" coordinates in the grid.

export const getX = (position: bigint, gridLength: bigint): bigint => {
  return position % gridLength;
};

To figure out our "y" coordinate, rather than using modulo, we can use integer division to count how many "stacks" of the slices we are in. This works because integer division effectively counts the number of complete rows above the current cell, aligning the bit positions with their respective "y" coordinates in the grid.

export const getY = (position: bigint, gridLength: bigint): bigint => {
  return position / gridLength;
};

Last thing we'll need is a way to get back. We can recalculate the position using some math.

export const toPosition = (
  x: bitint,
  y: bitint,
  sideLength: bitint
): bigint => {
  return y * sideLength + x;
};

Getting Neighbor Bit Positions

The Game of Life's rules require us to know how many of any given cell's neighbors are alive. Since we want the grid to be toroidal, there will be some extra complexity. If we were to ignore the edges of the grid, a cell's neighbors can be calculated by adding and subtracting one from the cell's x and y coordinates.

If you want to be "math-y" we can describe the neighbors of a cell as the product of two sets dx and dy where dx and dy aren't both 0.

dx = {-1, 0, 1}
dy = {-1, 0, 1}

neighbors = {(dx x dy) | dxi ∈ dx, dyj ∈ dy ,dxi,dyj != 0}

If you don't want to be "math-y", you can be "program-y" and calculate the neighbors given a position with the following function.

export const getNeighborPositionNoWrap = (
  x: bigint,
  y: bigint,
  dx: bigint,
  dy: bigint,
  gridLength: bigint
) => {
  const nx = x + dx;
  const ny = y + dy;

  return toPosition(nx, ny, gridLength);
};

Now we can address the elephant in the room — handling the wrap. Luckily, this is more straightforward than it initially sounds. We'll take our current nx/ny, add the gridLength, and modulo by the gridLength. This will wrap our edges around.

The wrap function works the same for both nx and ny because the grid is square. If the grid were not square, the wrap function for ny would need to use the other side's length.

export const wrap = (value: bigint, gridLength: bigint): bigint => {
  return (value + gridLength) % gridLength;
};

export const getNeighborPosition = (
  x: bitint,
  y: bitint,
  dx: bitint,
  dy: bitint,
  gridLength: bitint
) => {
  const nx = wrap(x + dx, gridLength);
  const ny = wrap(y + dy, gridLength);

  return toPosition(nx, ny, boardSideLength);
};

Putting this all together, we've created our grid! you can see how the toroidal grid wrapping works by moving your mouse around over the grid, or by tapping on a cell if you're on your phone.

Everything we've discussed in this section isn't unique to the "binary implmentation" of a grid. It applies for any array implementation as well!

The Game Logic

The game logic itself will be a function that accepts the current game state and returns the next. To do this, we'll need to walk through each cell and...

Determine whether or not the cell is alive
Count the number of live neighbors
Apply the rules of the game which will potentially change the cell's state

Starting with the easy bit, to walk through the cell state, we'll need to create a loop that goes from 0 to gridLength * gridLength.

const playGame = (cells: bigint, gridLength: bigint): bigint => {
  let newCells = cells;

  for (
    let bitPosition = 0n;
    bitPosition < gridLength * gridLength;
    bitPosition++
  ) {
    /**
     * Determine whether or not the cell is alive
     *
     * Count the number of live neighbors
     *
     * Apply the rules of the game which will potentially
     * change the cell's state
     */
  }
};

A Crash Course in Bit Twiddling

Getting the cell state introduces the first bit of bit twiddling we'll use. If you are unfamilar with bit twiddling, heres a crash course. Bit twiddling is the intentional manipulation of individual bits (1s and 0s of a binary number). There are six fundamental operators most languages provide for developers to manipulate bits.

Bitwise AND (&) - Gives you the "and" of the bits provided. You can think of this as the logical &&, it works the same way. Notably, the identity of & is 1 meaning x & 1 is x (in math terms the identity of & is 1).
Bitwise OR (|) - Gives you the "or" of the bits provided. Like & you can think of this as the logical || and notably x | 1 is always 1 (or 1 is |'s annihilator).
Bitwise Negation (~) - Gives you the negation of whatever succeeds it - think of ! with logical operators. We wont be using this in this project due to two's complement reasons I don't want to get into.
Bitwise XOR (^) - Gives you a 1 if bits are different and 0 otherwise.
Left Shift (<<) - Shifts the lefthand side value to the left by the right hand side amount.
Right Shift (>>) - Shifts the lefthand side value to the right by the right hand side amount.

A friend of mine once said, a good rule of thumb when working with bits is to "read" with &, "write" with |, and toggle with ^, which spoilers, is exactly how we will be using them.

Back to Game State

Ok so where were we? Right - game state. Let's start with determining if a cell is alive. A cell is alive if the bit at the cell's position is a 1. It's dead if its a 0. We can determine the state of the cell by shifting the grid over by the bit position (grid >> bitPosition) and &-ing (and-ing) it with 1. The shifting will give us either a 0 or a 1 , and the & tells us if its a 1 or not. Again, this works because 1 is the identity of of & meaning that x & 1 is x. If you don't like thinking about bits/ones and zeros the same applies for booleans and && where x && true is x.

const getCellState = (grid: bigint, bitPosition: bigint): bigint => {
  return (grid >> bitPosition) & 1n;
};

// ...

const isAlive = getCellState(grid, bitPosition) === 1n;

Next, we need to count the number of live neighbors. We already have most of the tools needed to accomplish this task. What we now need to do is loop over all combinations of dx and dy and apply our getNeighborPosition function to get the position of each of the neighbors.

export const getNeighborPositions = (
  bitPosition: bigint,
  gridLength: bigint
): bigint[] => {
  const neighborPositions = [];

  const dx = [-1n, 0n, 1n];
  const dy = [-1n, 0n, 1n];

  const x = getX(bitPosition, gridLength);
  const y = getY(bitPosition, gridLength);

  for (let i = 0; i < dx.length; i++) {
    for (let j = 0; j < dy.length; j++) {
      if (dx[i] === 0n && dy[j] === 0n) {
        // skip the current cell
        continue;
      }

      const neighborBitPosition = getNeighborPosition(
        x,
        y,
        dx[i],
        dy[j],
        gridLength
      );

      neighborPositions.push(neighborBitPosition);
    }
  }

  return neighborPositions;
};

From there, we just need to count the number of live neighbors using the getCellState function.

export const countLiveNeighbors = (
  cells: bigint,
  bitPosition: bigint,
  gridLength: bigint
): number => {
  return getNeighborPositions(bitPosition, gridLength).reduce(
    (liveNeighbors, position) => {
      const toAdd = getCellState(cells, position) === 1n ? 1 : 0;

      return liveNeighbors + toAdd;
    },
    0
  );
};

Now all we need to do is apply the rules of the game to our binary number. Since it's been a while, let's refresh ourselves on the rules:

Any live cell with fewer than two live neighbors dies.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies.
Any dead cell with exactly three live neighbors becomes a live cell.

To make our bit logic simpler, we can also think about this as:

if the cell is alive and has less than 2 or more than 3 alive neighbors, kill it.
if the cell is dead and has exactly 3 neighbors, bring it to life.

Both of these could be written with ^ (xor) to toggle the current position, but for the sake of doing more twiddling techniques, we'll use | (or) to bring the cell back to life. The general approach is the same for both: shift and apply the operator. All together our playGame logic looks like this.

export const playGame = (cells: bigint, gridLength: bigint): bigint => {
  let newCells = cells;

  for (
    let bitPosition = 0n;
    bitPosition < gridLength * gridLength;
    bitPosition++
  ) {
    const neighbors = countLiveNeighbors(cells, bitPosition, gridLength);
    const isAlive = getCellState(cells, bitPosition) === 1n;

    if (isAlive) {
      if (neighbors < 2 || neighbors > 3) {
        newCells ^= 1n << bitPosition;
      }
    } else {
      if (neighbors === 3) {
        newCells |= 1n << bitPosition;
      }
    }
  }

  return newCells;
};

With our game logic in place and the rules of Conway's Game of Life applied, it's time to bring our grid to life visually. Let's move on to rendering.

Rendering

This is both the most important and yet most boring section of this build. Without rendering, the game can't be seen - however to actually render it is a fairly trival matter. As previously mentioned, we'll be using react to render this out, so we will need to put our grid into react state; and to lay the game run the playGame function on our cells updating state afterwards.

const GameOfLife = () => {
  const [grid, setGrid] = useState(initialGrid);

  const step = () => {
    setGrid((previousGrid) => playGame(previousGrid));
  };

  // ... rest of component
};

Now that our game logic is complete and the rules can be applied, we just need to render the grid visually. For each cell, we'll check if it's alive, and if so, we'll change its background color. The same looping approach from the game logic will work here, iterating over gridLength * gridLength. To render it as a grid instead of a list, we'll leverage CSS by setting display: grid; and specifying the number of columns using the gridLength.

interface GameOfLifeProps {
  gridLength: bigint;
  initialGrid: bigint;
}

const GameOfLife = ({ gridLength, initialGrid }: GameOfLifeProps) => {
  const [grid, setGrid] = useState(initialGrid);
  const renderable = useMemo(
    () =>
      [...Array.from({ length: gridLength * gridLength }).keys()].map(BigInt),
    [gridLength]
  );

  const step = () => {
    setGrid((previousGrid) => playGame(previousGrid, gridLength));
  };

  return (
    <div
      style={{
        display: "grid",
        gridTemplateColumns: `repeat(${gridLength}, 1fr)`,
        width: "500px",
        height: "500px",
      }}
    >
      {renderable.map((position, index) => (
        <div
          key={index}
          style={{
            background:
              getCellState(position, gridLength) === 1n
                ? "green"
                : "transparent",
          }}
        />
      ))}
    </div>
  );
};

That's really all there is to it; by applying everything we've discussed, and we get a working game.

There are a bunch of different ways you can create a grid to render from creating a random binary number to loading pre-created binary. The original reason I wanted to build this out was to explore some of the well known structures that a game can create -- so I'm going to use the latter.

Looking at Presets

There are three main structures that appear commonly in the game:

Still Lifes - Stable structures that don't change
Oscillators - Structures that return to their starting point after some period
Spaceships - Structures that travel across the grid

Still Lifes are pretty mundane looking, and although its interesting that there are stable patterns that arise within the chaos of a game like the game of life, I didn't build a simulator to see things not moveBy, so we'll omit this one.

Oscillators

Oscillators are fascinating structures in the Game of Life. After several generations, they periodically return to their original state, creating a rhythmic pattern. Here are a few interesting examples.

Beacon

A smaller oscillator with a period of 2. It consists of two blocks that "blink" in and out of existence, mimicking a beacon's signal.

Toad

Another simple oscillator with a period of 2. It features a set of six cells that alternate between two distinct shapes, resembling a toad hopping back and forth (Full disclaimer, I'm not sure that's what inspired the name, but it makes sense in my head and I like it).

Pulsar

One of the most well-known oscillators, the pulsar has a period of 3. It consists of a central block surrounded by three arms on each side that oscillate in sync. This one is my favorite, primarily because it looks like something out of space invaders.

Pentadecathlon

This oscillator has a period of 15 and resembles a repeating pattern of vertical lines.

These oscillators showcase the intriguing periodic behaviors that can emerge from Conway's simple rules as well as demonstrate the predictable periodic behavior that can emerge from simple rules. Oscillators also provide valuable insights into the stability and repetition within chaotic systems, making them key elements in studying the complexity of cellular automata.

Spaceships

Spaceships are another captivating category of structures in the Game of Life. Unlike oscillators, spaceships travel across the grid while maintaining shape, creating an illusion of movement. They highlight the potential for mobility and interaction in the Game of Life. They are particularly interesting for their ability to move through the grid, interact with other patterns, and demonstrate how information can propagate in cellular automata. Here are a couple of notable examples

Lightweight Space Ship (LWSS)

The LWSS is a small and fast-moving spaceship with a period of 4. It's known for its compact size and efficiency, making it a popular example in many simulations (like this one haha).

Glider

The glider is one of the most famous spaceships in the Game of Life. It has a period of 4 and moves diagonally across the grid. The glider has become an iconic symbol of the Game of Life.

These spaceships illustrate the fascinating possibilities of movement and interaction within the cellular automaton.

Wrapping Things Up

Conway's Game of Life is more than just a simple cellular automaton; it's a window into the rich and complex world of emergent behavior from simple rules. Through this journey, we've explored the fundamental concepts of the Game of Life, from setting up the grid and understanding bitwise operations to implementing game logic and rendering the results. We've also delved into the intriguing patterns that arise, such as oscillators and spaceships, each offering unique insights into the stability, repetition, and mobility within this system.

Building a simulator for the Game of Life enhances our understanding of these mathematical phenomena. It provides a hands-on way to witness the beauty and complexity that can emerge from simplicity.

I encourage you to experiment with different configurations and see what new patterns you can discover. The world of cellular automata is vast and full of surprises, and Conway's Game of Life is just the beginning. Happy simulating!