2008 Project 2 - Game of Life

This programming assignment is to be submitted by 5pm on Thursday October 30th. Your work must be submitted electronically via cssubmit. This assignment contributes to 15% of your assessment for the unit.

The School's policies on Late Submissions and on Plagiarism will be enforced. All submitted project work will be tested electronically for plagiarism.

The specification for the programming assignment is given below. You are required to build a simulator for cellular automata, specifically a general implementation of Conway's Game of Life.

Simulating cellular automata

Conway's "Game of Life" simulates the evolution of a colony of organisms that occupy a square 2D world of cells (a grid). Shown below are two examples of regions within Conway's world:

Each cell in the world is either occupied by an organism or it is unoccupied. A cell can only be occupied by one organism at a time.

Each cell has eight neighbouring cells (up, down, left, right, and the four diagonals), except for the cells located on the edges of the world (which have five neighbouring cells) and on the corners of the world (which have three neighbouring cells).

At regular time intervals, the colony evolves instantaneously from one generation to the next, according to the following rules:

1. An empty cell with precisely 3 occupied neighbours will result in the birth of an organism in the next generation.
2. An occupied cell with precisely 2 or 3 neighbours will survive to the next generation.
3. An occupied cell with fewer than 2 or more than 3 occupied neighbours will die from loneliness or over-crowding.

Evolves instantaneously in the above description means that the state of a cell in one generation depends entirely on the number of neighbours in the previous generation. In other words, all updates to the world are assumed to happen in parallel.

In the above figures, we can see how the right-hand colony has evolved from the left-hand colony. Conway's Game of Life is just one instance of a class of problems called "Life" cellular automata (CA).

We can denote the above described version of Conway's Game of Life with the shorthand notation S23/B3, which signifies that an occupied cell survives (the S) if it has two or three living neighbours (the 23) and that an organism is born (the B) into an unoccupied cell if it has three living neighbours (the 3).

Conway's Game of Life is a famous class of cellular automata, and other variations including S23/B36, S5678/B35678, and S34678/B3678 produce interesting results. We say the survival rule for Conway's game is 23, while the birth rule is simply 3.

The execution of a Life cellular automata requires a seed configuration to start the simulation from. We can imagine reading the entire specification for a simulation from one text file.

Consider the following sample "CA datafile":

Survival        2 3
Birth           3
Size            10 6
Generation      20
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 5 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0

This file fully specifies a Life cellular automata simulation and consists of four lines of parameters and a block of lines to specify the initial world configuration.

The first two lines of the data file specify the survival and birth rules. The survival rule is specified with the keyword Survival in any mixture of case followed by a list of whitespace-separated integers that specify the allowable number of neighbouring cells that must be occupied for an organism to survive into the next generation.

The birth rule is specified with the keyword Birth in any mixture of case followed by a list of whitespace-separated integers that denote the number of occupied neighbouring cells that results in a birth in an unoccupied cell.

Note that the list of integers specifying the survival and birth rules may be empty, but the keywords Survival and Birth must appear in the CA datafile on separate lines. Note also that the list of integers should not contain an integer greater than eight. If it does, the CA datafile is deemed invalid and should be rejected.

The third line of the data file specifies the size of the world that the organisms will reside in. This line begins with the keyword Size in any mixture of case and is followed by two whitespace-separated integers that denote the number of rows and columns in the world respectively.

The fourth line specifies how many generations have passed to produce the state specified by the file. This is not the number of iterations to be run in the simulation - it is the number of iterations that have been run to produce the cellular automata state as specified by the CA datafile. This line begins with the keyword Generation in any mixture of case and is followed by one integer.

A CA datafile must contain the four initialisation commands on separate lines, but theys can appear in any order. Note however, the four lines must appear before the specification of the organisms in the world. Also note that blank lines are allowed in the CA datafile.

All subsequent lines in the data file represent a block of data that specifies the location of all the organisms in the world. Treating the world as a grid of size NxM (as specified by the Size parameter), this block of data must contain NM separate integers. Integers on separate lines represent different rows in the world. Integers on the same line separated by whitespace represent different columns in the world.

Each integer in this block of data represents one cell in our world. A value of zero indicates that no organism resides in that corresponding cell. Conversely, a non-zero value indicates that an organism does reside in that cell. The value in the cell indicates the age (the number of generations) that organism survived.

The data represented in a CA datafile is best collected together into one Matlab structure that we will call a simulation structure.

The fields of the simulation structure are:

• survival - a (possibly empty) row vector of integers specifying the survival rule.

• birth - a (possibly empty) row vector of integers specifying the birth rule.
• size - a 1x2 row vector of integers specifying the size of the world (rows and then columns respectively).
• generation - an integer specifying the number of generations passed to produce the cellular automata specified by the CA datafile.
• world - a NxM matrix of integers specifying the age of each organism in the world. An age of zero indicates no organism is present in the corresponding cell.

For example, we could imagine reading the above CA datafile into a single structure variable game:

game = 
      survival: [2 3]
         birth: 3
          size: [10 6]
    generation: 20
         world: [10x6 double]

Your task for this assignment is to write a function called simulateCA with the following specification:

simulateCA(datafilename, noi, delay, outputfilename)

Your function should read the CA datafile specified by the datafilename string, perform noi iterations of the simulation, and write the resultant cellular automata state to the CA datafile specified by the outputfilename string.

Your function should report any errors encountered in reading the CA datafile and exit gracefully. You can assume the values following the keywords on each simulation initialisation line are integers.

The outputfilename is an optional parameter. If outputfilename does not exist, the cellular automata state should not be written to a file.

Should the file specified by outputfilename already exist, be sure to prompt the user to find out whether to overwrite the file or not. If the user does not want to overwrite the file, your function should exit without modifying the existing file.

You should ensure the columns of numbers in the output file form neat, lined-up, easy-to-read columns. Extra spaces should be added where necessary.

After each iteration of the simulation, your function should also display the state of the cellular automata visually on the screen.

Unfortunately, if you have a plotting command within a loop, Matlab tends to only do all the plotting in a rush after the loop has finished. A way around this is to incorporate a pause statement in the loop, which seems to flush the graphics operations of each step of the loop. The delay parameter specifies how long you should pause for each iteration. If delay is less than zero, your function should wait for the user to press a key before proceeding.

Be sure to incorporate the age of organisms in your visualisation, but note that (for the purposes of the visualisation only) you may want to cap the age of all organisms to some maximum to ensure long surviving sub-populations do not distort the display.

The simulateCA function should check the validity of its arguments, reporting an error if any of the arguments are invalid.

To help decompose the problem, you are required to write three separate sub-functions as specified below. You are welcome to create any additional sub-functions you desire, provided it makes sense to do so.

1. game = readCADataFile(datafilename)
   

   This function reads the CA datafile specified by the string datafilename returning a "simulation structure" that holds the information read from the file.

2. writeCADataFile(game, filename)
   

   This function writes the information contained within the "simulation structure" s to the text file specified by the string filename.

3. numberOfNeighbours = neighbours(game, r, c)
   

   This function returns the number of neighbouring cells around the cell specified by row number r and column number c that are occupied.

Hints:

• Use the fscanf function to read the block data of organism ages.
• Use the sscanf function to read the numerical values associated with each simulation initialisation line. The sscanf function behaves exactly like the fscanf function except it operates on strings rather than files. Equally you can use the tokenising code presented in Lectures 19 and 20.
• Use the isempty function to determine if a survival rule is empty or not.
• Use the pause function to create a delay between iterations of the simulation.
• Use the exist function to determine if a file exists or not.

Assessment

The project will be assessed on four criteria:

Late submissions will have marks deducted at a rate of 10% for each day late. Extensions to the deadline will be granted only for significant medical reasons. Applications for extensions should be made to the lecturer as soon as possible.

Help

This project extends the concepts introduced in the past labsheets. You will need to have completed and understood these labsheets in order to successfully complete this project. You may ask for help from the laboratory demonstrators, and the lecturers, but you must demonstrate that you have made a reasonable attempt at the labsheets in order to receive help with the project.

Remember, the help message board is a great source of information. Project clarifications and answers to commonly asked questions will be posted there.

Submission details

Your final project effort is due at 5:00pm, Thursday 30th October.

Your submission for this question will be in the form of one file:

1. A file called simulateCA.m which forms your solution to this project.

   Any sub-functions you write to help complete this question must appear within the simulateCA.m file.

Make sure that the name of your file and function (including spaces and case) match the specification exactly.

The file you submit should start with the following lines of comment:

% CITS1005 Project 2
% Name: 
% Student number: 
% Date: 

Sample files

Test CA datafiles are available for download here:

• datafile1
• datafile2
• datafile3
• datafile4

Good luck!