Next: About this document

V22.0101 Homework Assignment 4 Fall 1996
The Game of Life

Assigned: Thu Oct 31
First Draft Due: Tue Nov 12 at 11 p.m.
Final Exam: Mon Dec 16 at 2:00-3:50pm.
Note: there will be one more homework assignment, with a first draft due before Thanksgiving and a final draft due after.

Consider a two dimensional array with M rows and N columns. This represents the world in which some organisms live. Each of the M by N cells in this array is either occupied (if an organism lives there) or is vacant. No more than one organism can live in any one cell at any time. Each cell, except those on the boundaries (the edge of the world), has exactly eight neighboring cells (above, below, left, right, and four diagonal neighbors). The cells on the boundaries have less than eight neighboring cells.

Initially, there is a given population of organisms occupying certain of the cells. At each succeeding generation, the organisms reproduce and die as follows:

• Each organism of the current generation survives to the next generation if, and only if, it has 2 or 3 neighbors (a neighbor is an organism that lives in a neighboring cell). Otherwise, it dies and its cell becomes empty in the next generation. Note: it dies if it is ``lonely'' or ``overcrowded''.

• Each vacant cell in the current generation becomes occupied by a new organism in the next generation if, and only if, it has exactly 3 neighbors. Otherwise, it remains vacant in the next generation.

For example, suppose the initial world (the ``zero"th generation) is as follows, using X to indicate the occupied cells and blanks for the vacant cells:

```                  X X
XXX                XX       XXXX
X X       XX
```
Then the next generation is
```          X                           XX
X                 XX        XX
X                 XX        XX
```

Write a program to play this Game of Life. Your program should read the initial world from a file (see below) and repeatedly generate new generations, prompting the user each time to see if he or she wants to see the next generation or terminate the program. Also, the program should terminate automatically if the world becomes empty, displaying a message accordingly.

Use two-dimensional arrays (either type Boolean or type char) to store the old and new generations respectively. To keep things simple, assume that M=20 and N=75, i.e. the world has 20 rows and 75 columns, and define these in a const statement before declaring your array variables.

Data files for testing your program will be provided on the home page. You should make sure your program works correctly on all these files, and you should also try your own test data. The program should prompt the user for the name of the input file (use a string variable). Empty cells are represented with blanks and occupied cells with X's. Read the data using a nested while loop, testing for EOLN and EOF. Do not assume that the lines of the file are ``padded'' with blanks. The lines may be only long enough to contain the last X on the line. Likewise, there may be less than 20 lines in the file; if the last lines of the world are empty, they may not be given in the file. You need to ensure that the cells in the world not explicitly given in the file are initialized to be empty.

Programming Details

You need two 2-dimensional arrays---the new generation should be created based on information from the old generation. If you use only one array, you will find that your old generation is overwritten by the new one before you have finished using all the information you need from it.

You should create a ``border'' of cells that always stay empty by declaring your arrays from 0 to M+1 and from 0 to N+1. This way, the cells on the edge will also have eight neighbors and won't need special treatment.

Include at least two functions. One should take a world and the coordinates of a cell and return the number of neighbors that the cell has. The other should take a generation array and return a Boolean value that tells whether or not the world represented by the array is empty.

Write all generations to the screen (don't forget the generation numbers), with a prompt to the user to type a key when ready to see the next one.

Also create one input file you make up yourself (different from other students!). Try to be creative and generate an interesting pattern. Send this file to your e-tutor as well as your source code.

Once again: avoid using global variables! This can be done by declaring variables after procedures, instead of before them. For example, if you need a variable in your main program, declare it after all the procedures, just before the begin keyword of the main program and not at the top of the program, which makes it available to all subsequent procedures. This way, procedures will only be able to access variables which are passed to them as parameters or declared locally. However, the constant values M and N (which are needed to define the type of your array variables) should appear at the top of the program, so that they are available globally.

This assignment is substantially less complicated than the previous two, so do your best to make the first draft good enough to be the final version.

Next: About this document

Sam Marateck
Wed Nov 6 13:09:50 EST 1996