Computer Science II Lab 2
Life, The UNIX, and Arrays
Introduction
=============
Welcome back! In this lab we are going to explore a classic in
Computer Science! This is Conway's Game of of life. It will be a
good practice for using arrays, as well as making use of our nice
ansi.h library.
Conway's game of life was created by John Conway, a British
mathematician, some time in the 1970's. It was an example of a
problem first proposed by John Von Neumann (creator of the famous
computer architecture). Von Neumann's problem was in the study of
self-replicating machines. This proposal led Conway to create this
little game, which is one of the first examples of a field called
cellular automata (CA).
The basic idea of a CA is to use a simple set of rules to create a
very complex pattern. Don't be fooled by the easiness of
understanding the rules. Conway's game of life, when played on an
infinite grid, is capable of simulating a Turing machine. This
means that the simple rules we are about to look at are capable of
universal computation. In fact, randomly generated rule sets have
a fairly high probability of being capable of universal
computation. Maybe the universe is geared toward forming computers!
The Game of Life
================
Conway's game of life is played on an orthogonal grid. Each element
in the grid is a cell, and the cell is either alive or dead. Each
grid arrangement is used to generate the next "generation" of cells.
The fate of each cell is determined by it's neighbors. Take for
instance, the cell 0. The X's are it's neighbors:
XXX
X0X
XXX
So each cell has 8 neighboring cells. The number of living
neighbors surrounding a cell are what determines what the cell does
in the next generation. The rules that the game follows are:
1. A living cell with fewer than 2 living neighbors dies. (Starvation)
2. A living cell with more than 3 living neighbors
dies. (Overcrowding)
3. A living cell with 2 or 3 living neighbors lives on.
(Stability)
4. A dead cell with exactly 3 living neighbors will become a live
cell (Reproduction)
So you can see that counting the cells around each cell, plus that
cell's state, determines what the cell does. Generally, this
results in weird and wonderful patterns. There are some patterns
that are interesting, however. Take for instance:
***
Following those rules, there are two possible iterations which this
oscillates through.
***
Followed by:
*
*
*
Then:
***
And so on. This is called a spinner. The next interesting one is
the glider. Use a sheet of paper and checkout what the glider does:
*
*
***
HINT: The glider moves! How cool is that?
There are some other interesting shapes, and I will post more to my
the gopher site. That way you can run them through your own
programs.
So now, we want to program this thing! I am going to get you
started, but you will have to code the actual rules yourself. So I
would recommend working out some of these games on paper!
Creating the Game of Life (Guided)
===================================
Alright, so let's set out to build this thing! I will guide you
through this one step at a time, but the final file will be up to
you. You will have to organize it correctly, and you will have to
provide appropriate function prototypes. We are going to use
our ansi.h library, as well as unistd.h to provide for timing. This
is, after all, an animation. To start things off, let's get our
include files and a few constants in place:
GRID_WIDTH and GRID_HEIGHT define our grid size. We are going to
play on an 80x24 grid, but it's best to not hard code constants into
a program. That way, if we change our minds later on, we can just
modify the constants at the top of the file.
DELAY is the time delay, in microseconds, between each frame. I've
found that 2 frames per second works pretty well (500,000
microsecond delay), but you can tweak this as you like.
Ok, so now that we have that, let me describe how I want to be able
to launch this program. If I launch it with no arguments, the
program should generate a randomized grid of living and dead cells.
If, on the other hand, I specify a filename then it should load the
grid from the file. That way we can save interesting grids, and
then run them.
So, we will run it as:
./life
for a random grid and
./life glider
to load the glider file and run the simulation.
Some other thoughts. How are we going to represent the grid? Well,
a 2d array should do the trick! But wait! There are really 2
grids. The current grid is used to generate the new grid. We can't
modify the original grid though, because if we do it will mess with
the rules. So, instead, what we do is we maintain 2 copies. We
just switch out which we are using as the current and which we are
using as the next grid. Putting that all together, this is what the
main function looks like:
-- Begin Code Segment --
int
main(int argc, char **argv) {
bool grid1[GRID_HEIGHT][GRID_WIDTH];
bool grid2[GRID_HEIGHT][GRID_WIDTH];
int generation = 1;
//run the generations, until the user presses Ctrl-C
while(true) {
//show the appropriate grid, and generate the next population
if(generation++ % 2) {
//odd numbered generation
renderGrid(grid1);
nextGeneration(grid1, grid2);
} else {
//even numbered generation
renderGrid(grid2);
nextGeneration(grid2, grid1);
}
//wait a while before doing it again!
usleep(DELAY);
}
return 0;
}
-- End Code Segment --
Look over the main function, and make sure you understand it. Type
this out into the correct place in your code file.
So now, we have a few functions to create! Let's start with the
initGrid function. This is an overloaded function, and there are
two versions of this:
-- Begin Code Segment --
//initialize the grid with random cells
void
initGrid(bool grid[][GRID_WIDTH]) {
//get the random number seeded with our present time
srand(time(0));
//loop through each row
for(int y=0; y<GRID_HEIGHT; y++) {
//loop through each column
for(int x=0; x<GRID_WIDTH; x++) {
//1/3 of the cells are alive
grid[y][x] = (rand() % 3) == 1;
}
}
}
//initialize the grid from a file
void
initGrid(const char* fileName, bool grid[][GRID_WIDTH]) {
ifstream file; //the file
char c; //character to be read
file.open(fileName);
//we are just going to assume that the file is valid
//this is bad, but in the interest of time, it's ok.
for(int y=0; y<GRID_HEIGHT; y++) {
for(int x=0; x<GRID_WIDTH; x++) {
c=file.get();
if(c=='\n')
c=file.get();
grid[y][x] = c == '*';
}
}
file.close();
}
-- End Code Segment --
The first function generates a random grid, the second loads a fie.
The format of the file is a space represents a dead cell and a *
represents a living cell. To save time, we just assume that the
file is correct. (I'll only test with correct files)
The last function I will provide for you is the render function.
Here it is:
-- Begin Code Segment --
//render the grid
void
renderGrid(bool grid[][GRID_WIDTH]) {
//loop through the grid, rendering as we go
for(int y=0; y<GRID_HEIGHT; y++) {
for(int x=0; x<GRID_WIDTH; x++) {
//go to the position
cout << cursorPosition(x+1,y+1);
//print the ' ' or '*'
cout << (grid[y][x] ? '*' : ' ');
}
}
}
-- End Code Segment --
I should note that your cursor might go a little nuts when you use
this. You can hide the cursor, but I'll leave it up to you to
figure out how!
Ok, so that leaves just one outstanding function. The one which
does the real magic, and generates the next generation. Just so you
can test the guided part, here is a placeholder version:
-- Begin Code Segment --
//create the next generation. The cur grid generates the next grid
void
nextGeneration(bool cur[][GRID_WIDTH], bool next[][GRID_WIDTH]) {
//placeholder, just copy the generation
for(int y=0; y<GRID_HEIGHT; y++) {
for(int x=0; x<GRID_WIDTH; x++) {
next[y][x]=cur[y][x];
}
}
}
-- End Code Segment --
The idea of nextGeneration is to take the grid cur, and use it to
populate the grid next. Here, I'm just copying it. This means,
when you run this program, what you will see is a steady image of
your grid. Well, that and a cursor that flies all over the place.
To exit the program, hit ctrl+c. Your terminal may end up in a
weird mode when you do this. If that happens, just type "reset" and
press enter. You can type the reset command even if your text is
hidden from view.
Ok that's all you get for free, now it's your turn to write some
code! Before you move on, you may want to look up a reference on
unistd.h. unistd.h is the header file which provides the interface
functions for the UNIX/POSIX environment. This contains the
function prototypes for talking to the kernel. (We used usleep from
this file).
NOW! On to bigger things!
Tinkering with Life (Challenge Lab)
===================================
Ok, so here's what I want you to do:
1. Modify the nextGeneration function so that it generates the next
grid according to the rules described in the introduction.
2. Modify the render function so that cells which will die in the
next generation are colored red, and cells which will live on
are colored green.
Of course, if you add other fancy things I will give you extra
credit. Enjoy!
HINT: I would strongly urge you to write a function which counts a
cell's living neighbors. Pay careful attention to the edges of the
grid, those are the ones which will give you trouble!
