Conway's Game of Life

Sun Dec 22 2024

In October 1970, John Horton Conway's Game of Life made its first appearance in Scientific American. Since then, it has become widely known in the world of computer science. Despite its simple zero-player design, it is quite entertaining to observe.

The game is based on a 2-dimensional grid. Each cell represents either a living (black) or a dead cell (white). In each iteration the state of the cells will be calculated by the following rules.

The rules

  1. Living cells survive with 2-3 neighbors.
  2. Living cells die with less then 2 or more then 3 neighbors.
  3. Dead cells revive with exactly 3 neighbors.

Implementation

It is important to understand that while calculating the next state of each cell, the calculation must be separated from the data. This means that we have to first calculate each cell before we start overwriting for the next state.

Let's first see whats happen if you just loop over every cell and update each cell individually. Use the interactive grid to get an visual explanation.

Legend

  • Alive
  • Dead
  • Selected
  • Mark for deletion

    • Caution

    In this investigation we will only investigate the behavior of the alive cells to reduce the amount of cells to check in the example.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

    If we compare this to what happens if we just mark the cells to deletion and only delete them at the end.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

    However, if we simply mark the element in our current grid, we would need to iterate over each cell again to delete the marked cells. To avoid this, a common technique is the dual buffer approach. By writing the result of our calculations directly into the second buffer, we ensure that we don't interfere with our data while calculating the next step.

    Dealing with infinity

    Some patterns can grow to infinity, which is a problem when implementing them.
    We could either:

    1. Keep track where living cells are and dynamically adjust the size of our universe.
    2. Limit our universe to a fix size.

    In the following I will use the second option with an universe with a fix size with an wraparound.

    Interesting patterns

    The game has no fix start point. But in order to see some action on the screen we need to set an initial pattern. While the game can look random at first glance, many patterns exhibit stable or predictable behavior.

    Spaceships

    A pattern is declared a spaceships when it travels continuously through the space.
    They can be uses to transmit information trough the space.

    Glider

    LWSS - Light weight spaceship

    MWSS - Middle weight spaceship

    HWSS - Heavy weight spaceship

    Infinity pattern

    Gosper glider gun

    Initially, it was unclear whether a pattern existed that could grow infinitely. To resolve this uncertainty, Conway offered a prize to anyone who could prove that such a pattern was possible. A team from the Massachusetts Institute of Technology, led by Bill Gosper, successfully collected the prize with their development of the Gosper Glider Gun.

    If you watch long enough, you will see how the gun eventually shoots itself due to the wraparound of space.

    Garden of Eden

    Another kind of pattern worth mentioning is the Garden of Eden patterns. These patterns cannot be achieved during the game. It's only possible to obtain them if they are the starting pattern of the game.

    If you want to know more about of the game of life I can recommend the following resources: