V22.0101 Homework Assignment 4 Fall 1997
The Game of Life
Assigned: Tue Nov 4
Due: Thu Nov 20
Final Exam: Tue Dec 16 at 2:00-3:50.
Note: there will be one more homework assignment, due the last week of classes.
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 diagonals). 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:
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 XXThen 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 two nested while loops, 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.
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 neighboring cells 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 (organisms in neighboring cells) 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.
You can see how the game, as described so far, works by connecting to the web page and running the program there. However, your program is not supposed to work interactively with the web like this: it should be a stand-alone Pascal program as usual.
Once your program is working, also terminate if the world is the same as the world before last. For example, if the world consists of
XXXthen next time it will be
X X Xand next time it will be
XXXsame as the time before last, so stop, since from now on the game will cycle back and forth between these two states. Display an informative message when this happens. In order to implement this, you will need to use THREE arrays, not just two: it should be clear why. Use a function which compares two worlds to see if they are equal.