Nicholas A. Yager


Creating Cellular Automata: Life-like Cellular Automata

01 Jun 2014

In a continuation of understanding models of life, one of the most interesting cellular automatons is a two dimensional "life-like" automaton. The first life-like automaton was created by John Conway in 1970, and was published in the October 1970 release of Scientific American. The intrigue that surrounds the automaton comes from the emergence and self-organization of highly complex patterns as the simulation evolves. As a result, these automata have attracted the interest of computer scientists, mathematicians, biologists, and physicists.

Figure 1: An example of life-like cellular automata. This simulation is represented as Unicode characters from an automaton implemented in python. White characters represent cells that are alive. As the simulation progresses, it approaches a state of stability and order. Some patches of complexity remain and migrate through the world.

Let's examine the rules of Conway's cellular automaton and see if we can implement a simple life-like cellular automaton in python.

Four basic rules define the spatial interactions that determine how life in the world evolve:

  1. Any live cell with fewer than two live neighbors dies.
  2. Any live cell with two or three live neighbors lives.
  3. Any live cell with more than three live neighbors dies.
  4. Any dead cell with exactly three live neighbors becomes a live cell.

Based on these rules, underpopulated and overpopulated cells die, existing communities survive, and cells can be populated through migration. In our implementation, we are going to use a Moore neighborhood to examine relationships, and all cells will be evaluated simultaneously each tick of discrete time.

We can start by defining how we want our simulation to work. In general, we must create a world, populate the world with life, and then let the world evolve and output its new state each tick. In the abstract, this only requires a world and functions to manipulate the world. We can take these basic steps and implement them as classes and functions.

def main():

    # Create the world
    world = World()

    # Populate it with life
    world.populate()

    # Simulate the world
    while True:

        world.show()       # Write the current state to the terminal
        world.simulate()   # Simulate the next tick

Now we can flesh out exactly what the world is. In our case, the world is a two-dimensional array with width and height that stores if a cell is dead or alive. Additionally, we don't want to lose information as out cells migrate across borders, so we must treat the world as a torus, which we will get to in a bit.

First, let's define our world object, and specify what happens when we make a new one. We must determine the width and height of the terminal, and then create a multidimensional array to fit the dimensions.

class World():

   def __init__(self):
       """
       Initial creation of a world. Determine the dimensions of the
       world and populate it accordingy.
       """

       # Create the world
       self.height, self.width = get_terminal_size();

       self.matrix = [[0 for x in range(self.width)] for x in
                        range(self.height)]

We can then take the world that we created, and populate it with life. For our purposes we are not interested in testing specific geometries, so we can instead pseudo-randomly assign life to each cell. For the sake of simplicity a uniform distribution can be applied.

def populate(self, p = 0.5):
    """
    Iterate through the world randomly placing life in positions
    based on a probability p.
    """
    for row in range(self.height):
        for col in range(self.width):
            # If the odds are in the position's favor
            if random.uniform(0,1) <= p:
                # The cell is alive.
                self.matrix[row][col] = "█"
            else:
                # The cell is dead.
                self.matrix[row][col] = " "

We now have the simple task of outputting the current state of the world. To that end all we need to do is iterate through each row and concatenate the characters into a string.

def show(self):
    """
    Print the current world to the console.
    """
    #os.system('cls' if os.name=='nt' else 'clear')
    for row in range(self.height):
        print("".join(self.matrix[row]))

Last but certainly not least, we must evaluate the cells and generate the state of the world for the next tick. For each tick, we must evaluate each cell by counting its neighbors, and following Conway's rules determine if the cell will survive into the next generation. The next generation cannot interfere with the current state of the world, and each cell must remain within our torus world.

def simulate(self):
    """
    Examine the number of neighbors for each cell and determine if a
    future lifeform will occupy the same space.

    Algorithm:
        1. Choose a cell.
        2. Count its neighbors.
        3. If the cell has 3 neighbors, it lives regardless of
           current state. If the cell is alive and has 2 neighbors,
           it lives. Otherwise, the cell is dead. All changes to the
           world are saved in the next generation matrix "NGM".
        4. Once completed, replace the world with the NGM.
    """

    # Create a temporary matrix to hold the next generation.
    self.NGM = [[0 for x in range(self.width)] for x in
                    range(self.height)]

    # Iterate through the next generation
    for row in range(self.height):
        for col in range(self.width):

            # We must account for a Moore neighborhood.
            # Setup a basic template for neighbor coordinates.
            neighbors = [ (row - 1, col - 1), (row - 1, col),
                          (row - 1, col + 1), (row, col + 1),
                          (row + 1, col + 1), (row + 1, col),
                          (row + 1, col - 1), (row, col - 1) ]

            n_neighbors = 0 # Keep track of the number of neighbors

            # Iterate through each of the neighbors and increment
            # for each living neighbor found.
            for n_row, n_col in neighbors:

                # Check for out-of-bound cells and reposition in
                # the torus if necessary.

                if n_row < 0:
                    n_row = self.height - 1
                elif n_row == self.height:
                    n_row = 0

                if n_col < 0:
                    n_col = self.width - 1
                elif n_col == self.width:
                    n_col = 0

                if self.matrix[n_row][n_col] == "█":
                    n_neighbors += 1

            # Determine if there will be life in that cell on the
            # next tick
            if n_neighbors == 3:
                self.NGM[row][col] = "█"
            elif n_neighbors == 2 and self.matrix[row][col] == "█":
                self.NGM[row][col] = "█"
            else:
                self.NGM[row][col] = " "

    # Replace the existing world with the next generation.
    self.matrix = self.NGM

With our class and functions defined, we can put all of our code together and run our own life-like cellular automaton. Due to the initial stochastic distribution of life, each run will be unique with its own still lifes, oscillators, and spaceships.

The complete script is freely available on github. Happy simulating!

Return to home...