CS 99

Summer 2002: Final Project                                                      07.25

The game of Life

Due date:   08.01

 

1.    Objectives
Completing all tasks in this assignment will help you:


First skim, and then, carefully read the entire assignment before starting any tasks!

2.    About the game
The game of Life (or Life) was invented by the mathematician John Conway in 1970.  It is not a ‘game’ in the conventional sense—there are no players, and no one wins or loses. Once the pieces are placed in their starting positions, the rules determine everything that happens later.

Life is played on a grid of square cells extending infinitely in every direction (we imitate infinity by allowing our grid to ‘wrap around’: leaving the left edge starts you again on the right, and the same goes for the right, top, and bottom edges).  A cell can be live or dead. A live cell has value 1; a dead cell, value 0.  Each cell in the grid has a neighborhood consisting of the eight cells in every direction (including the diagonals).

To apply the rules, we count the number of live neighbors for each cell. What happens to a particular cell depends on the number of its neighbors (see Section 4 below).


3.    Why Life is interesting
Conway chose his rules carefully, after trying many possibilities. Some caused the cells to die too fast, others caused too many cells to be born. Life balances these tendencies, making it hard to tell whether a pattern will die, form a stable population, or grow forever*. There are entire Web sites devoted to collecting interesting patterns (http://radicaleye.com/lifepage/ is one).

Life is known in the trade as a cellular automaton, which is any system in which rules are applied to cells and their neighbors.  It is also one of the simplest examples of  “emergent complexity”. This subject area has captured the attention of scientists and mathematicians from a variety of fields, for it is the study of how elaborate patterns and behaviors can emerge from simple rules. A recent book on this very subject is A New Kind of Science, by Stephen Wolfram.

Such self-organizing systems may help us understand how the petals on a rose, the flying formations of flocks of birds, the construction of ant hills, or the stripes on a zebra, arise.

*One pattern, called the ‘Spacefiller’, grows at an explosive quadratic rate and quickly fills the
grid half with live cells.  It was discovered in 1993; there are still things to discover with this
30 year-old game.




4.    The rules
The ‘board’ for the game is an n-by-n grid of cells, each of which can be active (
1) or inactive (0).  The board develops according to the following rules:

 


The neighbors of a cell are the eight cells that share an edge or vertex with it. The top, bottom, left, and right edges ‘wrap around’—so the cells on the top row have neighbors on the bottom row, and so on.

Note that number of live neighbors is always based on the cells
before the rule is applied! So we must first find all of the cells that change before changing any of them.

 

5.     Goals and specifications
You will write a collection of M-files to work in concert to play Life.  There will be 6 such files: One will be a script file, the other five will be function files.  They will have these features:

GameOfLife.m

 
neighbors.m

 
shiftDown.m


shiftUp.m


shiftRight.m


shiftLeft.m

 

 

6.    Experiment!
If you get your program and functions to work, you should consider that quite an accomplishment. Now have some fun!  See what sorts of interesting patterns you can create or find (on the Web).

7.     Do something interesting
For full credit on this assignment, do at least one interesting thing to the basic program: modify the rules, make the patterns colorful, output the stage of the generation—you name it.

Then write a paragraph about the modifications you made.

8.     Submitting your work
Type your name, student ID, and the date at the top of each file. Hand the signed documents to a staff member in lab on Friday, 02 August 2002 between the hours of 10AM to 12:30PM (you may also hand in your assignment earlier).