Conway Game of Life Implementation

This project implements the Conway Game of Life. Idea: The world consists of a 2D grid. Each cell in the grid can be "alive" or "dead". At each step the cells are updated according to the following rules:

  • A dead cell will become alive if it has exactly 3 live neighbors (each non-boundary cell has 8 neighbors in this grid).
  • A live cell will die unless it has 2 or 3 live neighbors.

We use a matrix to hold the grid. A cell is "alive" if the relevant matrix element is 1 and "dead" if 0. Several steps are needed:

  1. Figure out how many live neighbors each cell has.
  2. Update the grid.
  3. Plot the grid.

Homework 9. Implement the Conway Game of Life by iterating over all the grid cells and for each one counting the neighbors. You can either be careful not to access elements that are beyond the limits of the matrix, or make the matrix slightly larger and only iterate over the "middle" part of the matrix. Start with a small grid, as this is a very inefficient method upon which we will improve. To plot the grid use pcolor. Make sure you first calculate the number of neighbors and then update the grid, otherwise your update of early cells will interfere with the calculation of the later cells.

As you can easily see when trying to increase the size of the grid, this is a very inefficient method. We want to do all the tasks on a matrix-at-a-time basis, with no unneeded for loops.

The hardest part of the calculation is the neighbor-counting part. Here's one way to do this:

Noff_r= [-1, -1, 0, 1, 1,  1,  0, -1]; %the row offset of the 8 neighbors 
Noff_c=[ 0,  1, 1, 1, 0, -1, -1, -1]; %the column offset of the 8 neighbors
n N=numel(Noff_r); % the number of neighbors each element has
count = zeros(size(A)-[2 2]); %A is the grid with a border of zeros
for j j=1:n N       count=count + A(Noff_r(jj)+(2:end-1),Noff_c(jj)+(2:end-1)); %this is the heart
end %now count will have the correct number of alive neighbors.

Exercise 20. It takes time and practice to understand code. Explain to a friend, or a classmate how this code works.

Exercise 21. Here are various parts of the next step:

  • Given the matrix count find the logical expression that informs which elements of A(2:end-1,2:end-1) have 2 or 3 neighbors.
  • Find the truth matrix specifiying the elements that need to "die" according to the count.
  • Find the truth matrix specifiying the elements that need to be "born" according to the count.
  • Find the elements that are alive and need to remain so.
  • Update A according to the rules.
  • Show the grid using pcolor.

Homework 10. (Bonus) Counting neighbors can be done as a single linear algebra multiplication of A(:) by a large, mostly empty matrix. Figure out how this is possible, and implement it. Since the matrix is so large, use a sparse matrix.

Project 3. Now that we have all the parts (refer to Homework 9, Exercise 20, Exercise 21, and Homework 10), here's the project: Initialize the board using rand. Put the counting, updating, plotting parts of the game into a loop. When busy calculating MATLAB® avoids updating the plots. To force MATLAB to update the plots, place a pause(0.1) after pcolor.

Once you have the basic dynamics working, there are various directions for further study:

  • You will find that a large grid still requires too much memory and computation time. Since the matrices A and count are mostly zeros, it can be beneficial to use a sparse matrix for them. Figure out how to do it. To get a random sparse matrix use sprand.
  • What happens if you change the rules? You can change the birth/life/death rules, or you can change the definition of neighborhood, or both. Find an alternative dynamic with nice results.
  • A square grid is only one possibility. You could also consider a triangular or hexagonal grid. How would you implement them? Can you find nice game rules for them? How would you plot them? You cannot use pcolor any more.