Due : 6 p.m., Wednesday, February 11
This assignment is worth 10 marks towards your grade in this course.
The game of life
The game of Life was developed in 1970 by John Conway at the University
of Cambridge. It is meant to demonstrate that some simple local
rules can lead to interesting large scale behaviour.
The game is played on a two-dimensional grid of cells. Each cell has eight neighbouring cells. (Diagonal neighbouring locations are included.) Each cell can either be occupied by an organism or unoccupied. The game begins with a selection of occupied cells. From this initial generation, the next generation is calculated using the following rules:
For example, on the left below
is an initial grid of cells, with the organisms represented by
black squares.
Given this grid, the next generation would be as shown on the right:
Click here for the illustration.
This process of evolution continues until either of two things happens:
Notice that this is not a ``game'' as we usually think of it --
a set of rules specifying a competition between active, human players.
We have a program that ``plays'' the Game of Life.
It differs from the description above in two general ways.
First,
our program runs for a number of generations specified in the input;
it does not check for either of the stopping conditions mentioned above.
Second,
because we don't have until the heat death of the universe to wait for
the next generation to be calculated, our program uses a finite
grid of cells (rather than an infinite one, as the game was originally
meant to be played). With a finite grid, however, organisms at the
edge will tend to die since they don't have as many potential
neighbours to keep them alive. To remedy this, we act as though
the grid is wrapped around a torus (a donut shape). If we think of
the grid this way, there are no more edges, and each cell will have 8
neighbours.
For example, for a cell at the left hand edge,
the neighbour to its ``left'' is on the right hand edge of the grid.
We have implemented this using the % operator, which computes integer
remainders. (Some languages call this ``mod''.) For example,
28%5
has the value 3.
Input and output specifications for our program
The input to the program must be in a file called LifeInput
and must consist of the following:
:
9
6 6
1 1
1 2
1 3
2 1
The output from your program will be a representation
of each generation, from the initial configuration specified in
the input to the final generation computed.
Two kinds of output are simultaneously produced: text-based
and graphical.
In the text-based output,
empty cells are indicated by `-' and
live cells by `X'.
Each generation's output is preceded by a message indicating
which generation it is.
For example, below is possible output for one generation:
Generation number: 12
------
-XX---
XX---X
-----X
-X----
-X----
In the graphical output, empty cells are white and live cells are
coloured.
The age of an organism is indicated by its colour: organisms are
born white, and their colour becomes darker as they age.
Sometimes you may not want both kinds of output.
If you wish the program
to produce only text-based output, run the program
with the argument `text'; if you wish only graphical output,
run it with the argument `pretty'.
The default is that both types of output are produced.
This occurs when no argument is given.
Your first task
Your first task is to
improve the performance of the life program.
Our program
looks at every single cell in the grid, whether or not the cells are
occupied.
In fact, there may be large empty regions where no cell can die or be born
in the next generation.
Your task is to modify our program so that it
will be able to
ignore large empty sections when computing the next generation. This
should speed up the game.
The data structure in the original program
The grid is stored in an instance variable called theGrid.
It is a two-dimensional array in which each location
contains a Cell, which is either a LiveCell or an
EmptyCell. To
compute a new generation, a new, empty array called
nextGrid is created. Each
location in the old array is examined, the number of neighbours is
counted, and if that number is appropriate a LiveCell is placed at
that location in the new array. Then theGrid is set to the new
array, nextGrid.
Note that the second array is required -- as we compute the new generation,
we cannot store it into the old array directly.
Thought exercise: Why not?
Your revised data structure
As before, the current grid is stored in an instance variable called
theGrid.
What's new is that
you will be
keeping track of some extra information that will prove to be very
helpful in increasing speed.
You must add an additional instance variable -- another grid (we'll call it theInfoGrid), which is exactly the same size as theGrid, but which contains different information. Each location in theInfoGrid will point to a CellInfoNode if there is a LiveCell in theGrid at that location. Each CellInfoNode contains:
Because the CellInfoNodes are in a linked list,
there are two ways to find a specific CellInfoNode:
either traverse the theInfoList linked list,
or use theInfoGrid.
This is what will allow us to write a faster algorithm.
An illustration of this data structure can be
found in the
Assignments
area of the course web pages.
Overview of the revised program
When the program begins,
Life.java
reads the locations of the initial cells; as it reads each
location, it tells class Grid to add a cell at that location.
When it is asked to add a cell at a particular location,
class Grid
creates a LiveCell at that location in theGrid, and adds a
CellInfoNode
to theInfoList and theInfoGrid.
When the end of the input is reached, each cell in theGrid has
either a
LiveCell or EmptyCell, depending on whether that cell is
occupied or not.
Variable theInfoGrid contains a CellInfoNode
for each occupied cell,
and these CellInfoNodes are hooked together into a linked list,
whose front node is referenced by theInfoList.
All of this has been implemented for you.
Then the program calls the nextGeneration method repeatedly, for the desired number of generations. Your job is to rewrite nextGeneration to use the new data structure. An algorithm is provided on the following page.
Algorithm for computing the next generation
construct a new cell information grid called nextInfoGrid
declare a variable nextInfoList and set it to null
// Build nextInfoGrid and nextInfoList so that they contain
// both occupied cells and neighbours of occupied cells.
for each CellInfoNode c in the theInfoList of occupied cells
// Make sure this occupied cell appears in nextInfoGrid and nextInfoList.
let loc be c's location
if there is already a CellInfoNode c1 in nextInfoGrid[loc]
mark c1 as occupied
else
create a new CellInfoNode c1 in nextInfoGrid[loc]
set c1's coordinates
set c1's number of neighbours to 0
mark c1 as occupied
add c1 to nextInfoList
end if
// Now make sure its neighbouring cells also appear.
for each of c's eight neighbouring locations
let loc be this neighbour's location
if there is already a CellInfoNode c2 in nextInfoGrid[loc]
increment the number of neighbours of c2 by 1
else
create a new CellInfoNode c2 in nextInfoGrid[loc]
set c2's coordinates
set c2's number of neighbours to 1
mark c2 as unoccupied
add c2 to nextInfoList
end if
end for
end for
// Now that the list contains all cells that may be live in the next generation,
// remove any that are not actually live in the next generation.
// At the same time, update theGrid to contain the right pattern of live and empty cells.
for each CellInfoNode c in nextInfoList
if c is occupied but does not have the appropriate number of neighbours to be a LiveCell
remove c from nextInfoList
update theGrid accordingly
else if c is unoccupied but has the appropriate number of neighbours to be a LiveCell
mark c as occupied
update theGrid accordingly
end if
end for
// Store the revised information grid and list into our instance variables.
set theInfoList to nextInfoList
set theInfoGrid to nextInfoGrid
Hint: The first two if statements in the algorithm look
remarkably similar.
As you know, duplicate code is bad, so this is a good
opportunity for a method -- and it's things like this that might affect
your modularity marks.
After the algorithm finishes, theGrid contains the next
generation of occupied cells; and the linked list of CellInfoNodes,
whose front node is referenced by
theInfoList,
contains nodes only for the
occupied cells in the next generation.
The algorithm can thus be applied repeatedly to compute many generations.
What you need to do
We have begun to write a new version of the Grid class, that uses the new data structure and algorithms described above. It already includes a CellInfoNode class, declarations of the extra instance variables that are needed for the new data structure in class Grid, and code to initialize those instance variables. Your task is to complete the revised program. This includes:
Your new version of class Grid should not
affect any other classes in the program we provided. In particular,
the interface to Grid must remain unchanged.
Download our code
from the course web page using your web browser.
This includes the original, slow program, and the beginnings of
the revised, faster one.
You must use our code (the revised, faster version) as your starting point.
You will also find on the web an example of an input file
and the output that it should produce.
Your second task
Your second task is to
experimentally compare the running time of our original version of the program
against your new version and report your findings.
Use the extended version of the Life.java class,
called TimeOfYourLife.java,
which is available from the course web page.
It is the same as Life.java,
except that it prints timing information after the last generation.
There are also two new options for the command-line
argument (in addition to text and pretty) to make the timing less tedious.
The first is `nodelay'. It
works just like `pretty' except that there is not a one-second delay
between generations. The other option is `none', which will give you
no output other than the number of milliseconds it takes to run the
program.
To get meaningful results, make sure you have no other applications
running when performing your experiments.
Note that, depending on how fast your computer is, you may need to run
the program with a really large Grid or for lots of generations in
order to notice any differences in time between versions.
Also, your program may actually perform worse than the original
did, especially if the grid size is small or you have lots and lots of
cells that survive a long time.
Thought exercise: Why?
Your report
In your report, include only the following sections:
What to hand in
Hand in:
Tentative Grading scheme
Below is the tentative grading scheme.
Although we reserve the right to change it somewhat,
it should give you an idea of where to focus your efforts.
Organization of the materials handed in deduction of up to 5
Code
correctness 40
modularity and programming style 10
comments 10
Report
testing section
choice of test cases 5
annotated test runs 5
explanation of testing strategy 5
method section 10
bugs and missing features section deduction of up to 5
experiments section
choice of experiments 5
discussion 5
Overall quality of writing 5
TOTAL 100