The Game of Life
Write a complete C program that implements Conway\'s Game of Life.
The rules for the Game of Life are simple. The universe consists of a two-dimensional matrix of cells with each cell being alive or dead. For each generation every cell determines its next phase of life as follows:
If the cell is alive:
it dies if it has 0, 1, 4 or more living neighbours (starvation), or
it lives if it has 2 or 3 living neighbours (balance).
If the cell is dead:
it springs to life if it has exactly 3 neighbours (procreation).
A cycle occurs as soon as the state of the universe of the latest generation is the same as a previous generation. You should be able to see that once this occurs the Game of Life will repeat the intermediate generations forever.
Implementation Requirements
All of the following conditions must be met by your solution.
Your program must read the initial state from standard input (redirecting files on the command line is the way to go!).You will be expected to adequately test your program All input will conform to the following format:
The input will consist of starting universes for multiple games. Play each game completely, in the order they appear in the file.
The first line of the game starts with an asterisk and contains the game title.
The second line of the game contains two numbers, separated by a space, which indicate the number of rows and columns for the 2-D matrix.
Then there is one line for each row in the matrix:
A blank character represents a dead cell.
An \'X\' represents an alive cell.
The next game starts on the next line, until EOF.
There are no errors in the input file format.
For each game, your program will first print the game title as read from the file. Print the starting universe as read in. Then, after each generation is calculated your program will print the current state of the universe. All printing goes to standard output, and each universe must be preceded by a label indicating the generation number (where the initial state is generation 0). You must include a border, use \'.\' for dead cells and \'*\' for alive cells.
Each game will run for 250 generations or until a cycle is detected, whichever comes first. If the game ends because of a cycle, print the numbers of the two generations that were duplicated.
Printing all generations is great for debugging purposes (and should prove mesmerizing). But the release version of your program, when compiled with -DNDEBUG, should only print the initial universe and the last 10 (or less) generations. The sample output above is produced by a release version.
Hints
The following should help point you in the right direction:
Store the universe in a two-dimensional array, but be careful that your program avoids subscripting your array \"out of bounds\". Not checking for array boundaries may lead to your program crashing, or worse, giving the wrong results.
You will need to store all previous generations in order to identify a cycle. To do this, consider using a struct to represent a generation. Then, you can employ an array of objects to track your universe\'s history.
You may assume file input lines are at most 80 characters, and a universe is at most 60x60 cells.
Here is a sample input file to use for testing.
#include
#include #include #include #include using namespace std; //Copies one array to another. void copy(int array1[52][102], int array2[52][102]) { for(int j = 0; j < 52; j++) { for(int i = 0; i < 102; i++) array2[j][i] = array1[j][i]; } } //The life function is the most important function in the program. //It counts the number of cells surrounding the center cell, and //determines whether it lives, dies, or stays the same. void life(int array[52][102], char choice) { //Copies the main array to a temp array so changes can be entered into a grid //without effecting the other cells and the calculations being performed on them. int temp[52][102]; copy(array, temp); for(int j = 1; j < 51; j++) { for(int i = 1; i < 101; i++) { if(choice == \'m\') { //The Moore neighborhood checks all 8 cells surrounding the current cell in the array. int count = 0; count = array[j-1][i] + array[j-1][i-1] + array[j][i-1] + array[j+1][i-1] + array[j+1][i] + array[j+1][i+1] + array[j][i+1] + array[j-1][i+1]; //The cell dies. if(count < 2 || count > 3) temp[j][i] = 0; //The cell stays the same. if(count == 2) temp[j][i] = array[j][i]; //The cell either stays alive, or is \"born\". if(count == 3) temp[j][i] = 1; } else if(choice == \'v\') { //The Von Neumann neighborhood checks only the 4 surrounding cells in the array, //(N, S, E, and W). int count = 0; count = array[j-1][i] + array[j][i-1] + array[j+1][i] + array[j][i+1]; //The cell dies. if(count < 2 || count > 3) temp[j][i] = 0; //The cell stays the same. if(count == 2) temp[j][i] = array[j][i]; //The cell either stays alive, or is \"born\". if(count == 3) temp[j][i] = 1; } } } //Copies the completed temp array back to the main array. copy(temp, array); } //Checks to see if two arrays are exactly the same. //This is used to end the simulation early, if it //becomes stable before the 100th generation. This //occurs fairly often in the Von Neumann neighborhood, //but almost never in the Moore neighborhood. bool compare(int array1[52][102], int array2[52][102]) { int count = 0; for(int j = 0; j < 52; j++) { for(int i = 0; i < 102; i++) { if(array1[j][i]==array2[j][i]) count++; } } //Since the count gets incremented every time the cells are exactly the same, //an easy way to check if the two arrays are equal is to compare the count to //the dimensions of the array multiplied together. if(count == 52*102) return true; else return false; } //This function prints the 50 x 100 part of the array, since that\'s the only //portion of the array that we\'re really interested in. A live cell is marked //by a \'*\', and a dead or vacant cell by a \' \'. void print(int array[52][102]) { for(int j = 1; j < 51; j++) { for(int i = 1; i < 101; i++) { if(array[j][i] == 1) cout << \'*\'; else cout << \' \'; } cout << endl; } } int main() { int gen0[52][102]; int todo[52][102]; int backup[52][102]; char neighborhood; char again; char cont; bool comparison; string decoration; //Instructions on how the program is used, along with the rules of the game. cout << endl << \"This program is a C++ implementation of John Conway\'s Game of Life.\" << endl << \"With it, you can simulate how \\\"cells\\\" interact with each other.\" << endl << endl << \"There are two types of neighborhoods you can choose, the\" << endl << \"Moore, and the Von Neumann. The Moore neighborhood checks\" << endl << \"all 8 surrounding cells, whereas the Von Neumann checks\" << endl << \"only the 4 cardinal directions: (N, S, E, and W).\" << endl << endl << \"The rules of the \\\"Game of Life\\\" are as follows:\" << endl << endl << \"1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.\" << endl << \"2. Any live cell with two or three live neighbors lives on to the next generation.\" << endl << \"3. Any live cell with more than three live neighbors dies, as if by overcrowding.\" << endl << \"4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.\" << endl << endl << \"The initial configuration (Generation 0) of the board is determined randomly.\" << endl << \"Every hundred Generations you will get the option to end or continue the simulation.\" << endl << \"If a system becomes \\\"stable\\\" (meaning the system does not change from one\" << endl << \"generation to the next), the simulation will end automatically.\" << endl << endl; //Loop to check if user wants to keep simulating. do { //Loop to check for proper inputs. do { cout << \"Which neighborhood would you like to use (m or v): \"; cin >> neighborhood; }while(neighborhood != \'m\' && neighborhood != \'v\'); //Clears the screen so the program can start fresh. system(\"clear\"); int i = 0; //Loop that does the bulk of the simulation. do { //Generates the initial random state of the game board. srand(time(NULL)); //The actual array is 102 x 52, but it\'s easier to just leave the surrounding part of //the array blank so it doesn\'t effect the calculations in the life function above. for(int j = 1; j < 51; j++) { for (int i = 1; i < 101; i++) gen0[j][i] = rand() % 2; } //Determines how big the decoration should be. if(i < 10) decoration = \"#############\"; else if(i >= 10 && i < 100) decoration = \"##############\"; else if(i >= 100 && i < 1000) decoration = \"###############\"; else if(i >= 1000 && i < 10000) decoration = \"################\"; else decoration = \"#################\"; //Prints the generation. If i == 0, the gen0 array is copied to the //todo array, and is printed before any functions act upon it. cout << decoration << endl << \"Generation \" << i << \":\" << endl << decoration << endl << endl; //Initializes the arrays by copying the gen0 array to the todo array. if(i == 0) copy(gen0, todo); copy(todo, backup); print(todo); life(todo, neighborhood); i++; //Pauses the system for 1/10 of a second in order to give the screen //time to refresh. system(\"sleep .1\"); //Checks whether the generation is a multiple of 100 to ask //the user if they want to continue the simulation. If they //wish to end, the program breaks out of the loop to ask if //the user wishes to run another simulation. if(i % 100 == 1 && i != 1) { cout << endl; //Loop to check for proper inputs. do { cout << \"Would you like to continue this simulation? (y/n): \"; cin >> cont; }while(cont != \'y\' && cont != \'n\'); if(cont == \'n\') break; } //Compares the current generation with a backup generation. //If they aren\'t the same (they usually aren\'t) the system //clears the screen and repeats the process until they are //the same or the user chooses to quit. comparison = compare(todo, backup); if(comparison == false) system(\"clear\"); if(comparison == true) cout << endl; }while(comparison == false); //Loop to check for proper inputs. do { cout << \"Would you like to run another simulation? (y/n): \"; cin >> again; }while(again != \'y\' && again != \'n\'); }while(again == \'y\'); return 0; }
Homework Sourse
