Homework 3
From the book, page 440, question 13.
Due Apr 25, 11pm (Wed).
Skills needed to complete this assignment:
Using conditionals and loops
Writing functions
Storing values in vectors, and representing 2D matrices in 1D vectors
The mathematician John Horton Conway invented the "Game of Life" (not the board game). Though not a "game" in any traditional sense, it provides interesting behavior that is specified with only a few rules. This homework asks you to write a program that allows you to specify an initial configuration. The program follows the rules of LIFE to show the continuing behavior of the configuration.
LIFE is an organism that lives in a discrete, two-dimensional world. While this world is actually unlimited, we don't have that luxury, so we restrict the world to 80 characters wide by 22 character positions high. If you have access to a larger screen, by all means use it. It is your choice to make the edges "wrap around" or not.
This world is a 1D or 2D vector (of char or bool perhaps) with
each cell capable of holding one LIFE cell. Generations mark the
passing of time. Each generation brings births and deaths to the LIFE
community. The births and deaths follow the following set of rules.
We define each cell to have eight neighbor cells. The neighbors of a cell are the cells directly above, below, to the right, to the left, diagonally above to the right and left, and diagonally below to the right and left. Be careful when checking for neighbors on the edges; you can decide whether an edge cell has alive or dead neighbors beyond the edge.
If an occupied cell has zero or one neighbors, it dies of loneliness. If an occupied cell has more than three neighbors, it dies of overcrowding.
If an empty cell has exactly three occupied neighbor cells, there is a birth of a new cell to replace the empty cell.
Births and deaths are instantaneous and occur at the changes of generation. A cell dying for whatever reason may help cause birth, but a new born cell cannot resurrect a cell that is dying, nor will a cell's death prevent the death of another, say, by reducing the local population.
Examples available from the article Scientific American 223 (October 1970): p. 120-123
These examples are stolen from Wikipedia.
|
|
||||||||||||||||||||
|
|||||||||||||||||||||
These may prove interesting starting conditions (see Wikipedia for more options).
F-pentomino
|
Diehard
|
Acorn
|
You will "hard code" a starting configuration. The user need not be able to provide a different starting configuration (that would just complicate your program).
Suggestions: Look for stable configurations. That is, look for communities that repeat patterns continually. The number of configurations in the repetition is called the period. There are configurations that are fixed, which continue without change. A possible project is to find such configurations.
Hints: Define a void function named generation that takes the
vector we call world (call-by-reference or using a pointer), which
contains the current (or initial) configuration. The function scans
the vector and modifies the cells, marking the cells with births and
deaths in accord with the rules listed earlier. This involves
examining each cell in turn, either killing the cell, letting it live,
or if the cell is empty, deciding whether a cell should be born. Note
that the game will not work if your code counts neighbors in the same
vector it is modifying. A copy of the world vector must be created
before it is modified, and this copy is used to count neighbors, while
cells are turned on or off in the original vector.
There should be a function display that accepts the vector world
and displays the grid on the screen. Some sort of time delay is
appropriate between calls to generation and display. To do this,
your program should generate and display the next generation when you
press Return/Enter. You are at liberty to automate this (put in a real
time delay, and not wait for the user to press a key), but automation
is not necessary for the program.
If you want to "delay" the display of your grid, rather than wait for the user to type something and press enter before displaying the next grid, then you will need to pause or "sleep" your program somehow. If you are using Microsoft Windows, do this:
#include <windows.h>
// ...
Sleep(800); // pause 800 ms
On Linux or Mac OS X, do this:
#include <unistd.h>
// ...
usleep(800000); // pause 800 ms
Go to http://www.qotile.net/blog/wp/?p=600 to see some cool 3D visualizations of the game over time. A ridiculous amount of further information is available here: http://www.conwaylife.com/wiki/index.php?title=Main_Page
Download Golly (for Windows, Mac, Linux) to play with cellular automata and some amazing creations by researchers.
Here is an app that generates music based on cellular automata principles: Otmata.
Cellular automata is serious research; see a list of journals that publish articles about cellular automata.
Code template for the homework using vectors (to be precise, a vector of vector of char). This is an outline
for just one of the many possible ways of tackling this problem. You are, of course, free to use any method you
are comfortable with, so long as the program simulates Conway's Game of Life.
#include<iostream>
#include<vector>
#include<unistd.h> // linux / Mac OS X
// #include<windows.h> // Windows
#include<cstdlib>
using namespace std;
// You can change the size of your world matrix in your entire code
// just by changing the values of ROWS and COLS here.
#define ROWS 21
#define COLS 80
// You can change the characters used to represent DEAD and ALIVE cells here
#define DEAD ' '
#define ALIVE '*'
void generation(vector< vector<char> > &world,
vector< vector<char> > &world_copy)
{
// copy the contents of world into world_copy
//for(int i = 0; i < ROWS; i++) {
// for(int j = 0; j < COLS; j++) {
// look at world_copy[i][j]'s neighbors and count ones that are alive
// update world[i][j] based on it
// Be careful when dealing with cells on the boundary since they
// do not have eight neighbors
// }
//}
}
void display(vector< vector<char> > &world)
{
// display the 2D matrix
// You can add more code to 'beautify' the display of the matrix
for(int i = 0; i < ROWS; i++)
{
for(int j = 0; j < COLS; j++)
{
cout << world[i][j];
}
cout << endl;
}
}
int main()
{
vector< vector<char> > world(ROWS, vector<char>(COLS, DEAD));
vector< vector<char> > copy(ROWS, vector<char>(COLS, DEAD));
// set some cells of world to ALIVE for initial configuration
world[1][1] = world[1][2] = world[1][3] = ALIVE;
while(true)
{
// clear the screen and display the world
system("clear"); // linux / Mac OS X
// system("cls"); // Windows
display(world);
// wait for some time
usleep(800000); // linux / Mac OS X
// Sleep(800); // Windows
// update the world
generation(world, copy);
}
return 0;
}