GUIDE FILE FOR ASSIGNMENT 5 

by James Tam

Best viewed with Internet Explorer version 5+ and a computer with a sound card and speakers.  You can view a text-only version of the assignment guidelines in Unix under /home/231/assignments/assignment5/guidetoa5.  The pictures are drawn with ASCII and there is no sound but otherwise you pretty much get the same thing.  Also there is an executable file in that directory called "a5B".  It is essentially a B-level version of the assignment with a few extra things to make it look nice (e.g., there is a border and it keeps track of which turn you are currently on - which aren't mandatory for your assignment).  As usual you can either copy it back to your home directory or run it while in the assignment 5 directory by typing "./a5B" at the Unix prompt.

Introduction

The Game of Life is a biological simulation invented by Cambridge mathematician John Conway.   The simulation consists of a collection of cells, that live or die depending upon a simple set of rules. Depending on the initial pattern of life forms, the cells form various patterns throughout the course of the game.

Assignment description

Essentially what you are doing for assignment 5 is simulating a mini biosphere of finite size There is only one type of inhabitant in the biosphere which I will refer to as the "critter". The biosphere a two dimensional world that is divided up into squares.  Each square will either be occupied with a maximum of one critter or the square will be empty.

Example Biosphere

This world can be simulated by a two dimensional character array. In my online executable files, a "*" (star) represents the presence of a critter while a " " (space) represents an empty square. You can find the initial pattern of critters and spaces in the program a5a.p & a5b.p.   (The difference between these two starting programs depends upon whether you wish to complete the B-level assignment or if you wish to go further).   The source code in these programs is available for your use, just make sure that you reference where you got this source code from. Also note that all assignments must start with this initial pattern of critters in some form (see below) and must be run for the required number of turns.

This program simulates the births and deaths of the critters over time. Time will pass on a turn by turn basis. The user will signal the end of a turn by a key press (e.g., press (C) to continue or (Q) to quit the program). For each turn that passes your program must scan the entire biosphere:

1) For squares that contain an existing critter, the program must determine, which critters die and which critters are unaffected by the turn change. 

2) For squares that are currently empty the program must determine or if a new critter will be born into a square or not.

The births and deaths of critters is based solely upon the number of neighbors that a particular critter has. To make things simpler you can assume that all births and deaths occur simultaneously as a turn passes.

For your convenience I will again state under which conditions a critter will be born and under which conditions a critter will die.

1) There is already a critter in the square:

a) The critter will die :-( if: 

    i) It has 0 or 1 neighbors - it gets too lonely 

    ii) It has 4 to 8 neighbors - the critter is overcrowded.

b) It will go on living as is (won't die) :-) if: 

    i) It has 2 - 3 neighbors.

2) There currently is not a critter in the square - a critter will be born ;-) into an empty square if:

a) There are there are exactly three neighboring critters in the adjacent squares.

How do you determine what the neighbors for a particular critter are? Picture the following two dimensional array that is a subset of the biosphere array:

The square marked with an "X" is a place where we are trying to determine if a critter will be born there or if a resident critter will die there.  In the cases below I will use a "*" (star) to represent the neighboring critters.  The squares that you need to scan (to see if there are neighboring critters) will then be all the adjacent squares (above, below, left side, right side, and the four diagonals). Note: in the examples below I assume that the square to be scanned is an inner square, you will have to account for other cases (e.g., the top, bottom, left and right edges as well as the four corners - see below when I talk about different grade levels).

e.g., (critter already in square to be scanned) - Critter dies of loneliness (no neighbors or just one neighbor).

No neighbors                                                                              One neighbor

e.g., (critter already in square to be scanned) - Critter dies from overcrowding (four neighbors - also applies if there are more than four neighbors) 

Four neighbors

e.g., (critter already in square to be scanned) - No Change to the Critter (two or three neighbors)

Two neighbors

e.g., (empty square) - Critter will born into the square marked "B" (there is exactly 3 neighbors). 

Empty square (critter born)

What are the row and column coordinates for the 8 squares relative to the center square above? 

If the coordinates for the center square (X) is r, c then the neighboring squares are as follows:

How does all of this scanning relate to the 10 x 10 biosphere? You must perform all of the above scans for each of the 100 squares. If there is already a critter living in the square then you must determine if the number of neighbors that it has will allow it to continue living. If the square is currently empty, then you must determine if a critter will be born into the square or not.

How do you start the simulation? You must have a biosphere that starts out with a set number of critters in it and in set positions and you run the simulation to determine what happens to them. Although the A and A- versions of the assignment specifications requires that you to randomly generate the starting positions for the critters I don't recommend that you do so. Determining if your program is working or not can be difficult if you do this. Instead I suggest that you start with the 10 x 10 biosphere where the critters start out in fixed positions so that you can check your scanning algorithm (above). I suggest that you start by using the example biospheres provided and work your way up from the simplest ones to the more complex. However, in the version of the typescript that you hand in the biosphere that you run must show the program running the biosphere "required data for a5". This is even the case even if you complete a A- or A level assignment. Run this biosphere for about 20 turns or so.

Different grade levels for this assignment

B level assignment:  

The skeletal program a5a.p contains the starting data for a "B" level assignment. There are two ways to handle edges and corners. With the B-level assignment you essentially create a 10x10 array in your assignment but only use 9 x 9 squares. The outer border of squares will be filled with spaces and you use rows 2 - 9 and columns 2 - 9. Row 1 and 10 and column 1 & 10 will be filled with spaces.

i.e.,

The boxes labeled with SP (spaces) simulate a no-critters land that surrounds the biosphere. It is called that because no critters are allowed to live there. Because no critters live in any of these locations, they will have a value of zero (won't count when you do a critter count for adjacent squares).   This value will be used by it's neighbor squares when trying to determine births and deaths. The boxes labeled with a question mark are part of the biosphere (which may or may not contain a critter).

The reason why I suggest that you make the array bigger than the simulated biosphere is so that when apply the formula for critter births and deaths you don't have to make a special exception for the corners and edges (making it more efficient). But if do follow this suggestion, you must make sure that you don't traverse, the whole array when checking for births and deaths, just the part that is related to the simulated biosphere (squares that are capable of supporting life).

B+ Level assignment 

Fulfills all requirements of the B level assignment but you now use the entire 10x10 array. Critters can exist anywhere within it. This second way of handling the edges and corners employs the scanning algorithm above but must treat these situations as special cases. You will need several conditional statements to catch all of the cases. To fulfill the B+ requirements you must use the starting skeleton program a5b.p instead of the one above. This program utilizes all 100 squares (instead of the 81 used above). Run the required starting biosphere in a5b.p instead of a5a.p for 20 turns or so.

If you complete the assignment requirements for a B+ level assignment and above then annotate the beginning of your print out (write in ink or felt pen that this is the case).

A- Level assignment 

You must complete either of the 2 features listed below.

A Level assignment 

You must complete both of the features listed below.

Feature one:

It is the same as the B+ level assignment but the user can choose whether they wish to run the 10x10 or a 20x20 biosphere (without having to edit the source code and recompile the program).   I don't have a starting skeleton program for this version of the assignment - it is up to you will have to figure out how to adapt a5b.p to handle this case. (Hint: look back at some of the lecture notes when talked briefly about good programming style and why good programming style can make program maintenance easier).  To show the marker that your program works run the required biosphere for 20 turns at 10x10 size. Then rerun your program with the required biosphere for 20 turns but at 20x20 size.

Feature two:

Your assignment must show in the typescript that you have completed all the requirements for an B+ level assignment (i.e., by running the required cases in the typescript as indicated above).  In addition to the pre-generated biosphere, show in the typescript how your program can create a randomly generated biosphere. Run the program with a randomly created biosphere for 4 turns and stop the program. Rerun the program (which should produce another random biosphere) for another 4 turns.

Suggested Approaches to this Assignment:

1) Start early! If you found assignment 4 tough, you will find this one tougher. (For what it might be worth this was one that stumped me when I had to do it in first year - for a while at least :-)).

2) Take it in small steps 

a) Make sure you are manipulating the array properly - display the results to the screen just to make sure things are working. 

b) Start out with simple cases - you may want to work your way up the cases shown below.

Biospheres 

Biosphere1 (The Barren Realms) 

It's a 10x10 world that is completely empty. Run it thru a few turns. If you ever have a critter suddenly appear in this barren wasteland then you are doing something wrong. A good basic starting test.

Biosphere2 (I'm so-o-o-o-o lonely!) 

It has a single critter in it that should die in one turn :-(. If it doesn't go away then you again know that something is wrong. A good test to see if you "critter dies" algorithm works.

Biosphere3 (You make my head spin)

 The biosphere consists of 3 critters in a vertical line. From turn to turn this line should rotate from vertical to horizontal (and back again) endlessly. A very good test for your "critter is born" and "critter dies" algorithm.

Biosphere 4 (Four friends forever) 

A more advanced test - 4 critters in a solid cube. These critters should stay stable in this pattern no matter how many turns you run.

Biosphere 5 (Doomed for extinction) 

Another more advanced test. After several dozen turns or so all critters die out.

Biosphere 6 (The required test case that you must run in your typescript) 

And finally of course your assignment must be able to handle this case. If your program can handle this then you know you've made the cut folks.

(By the way if you find this assignment difficult and can't get it going you still might want to try and hand in something. If you use good coding style and document things well, try running as many of the example cases above that your program will handle. If it can't handle the final BIG one then at least do as many of the small ones as possible. Either run the simulation for as many turns as needed for it to stabilize (or for a minimum of 10 for each of the cases above).

3) You might want to apply some of what I talked about in my debugging lab here too. Try to isolate your test cases (e.g., . - test the "critter dies" and "critter is born" algorithm separately if you get really stuck). Make liberal use of "write's" and "writeln's" to view your happy little biosphere.

4) If you need help and can't seem to get any (e.g., .- my office hours really suck and you have a knack for catching me away from my desk then try email and I might be able to sit down with you some time). Of course I must warn you all that I am more of a night person that a more person though so those 8 AM appointments are kinda bad...

5) Have fun! Remember this is only one assignment folks and not the whole semester. 

Learning objectives: Applying the concepts learned with two-dimensional arrays (assigning values, extracting values, scanning different parts, checking boundaries).

Game of Life on the web (some web-based versions of the Game of Life that you can try out through your web browser):

There's probably dozens of web sites where you can try out the Game of Life through your web browser, here's two of the most straight-forward ones that I found:

1) http://www.students.cs.uu.nl/~smotterl/conway/

2) http://www.bitstorm.org/gameoflife/