Lab7Kenyon < SCMP118/Fall2016

Tags: %TAGME{ tpaction="" web="SCMP118/Fall2016" tag="" }% view all tags
<table border="1" cellpadding="0" cellspacing="1"> <tbody> <tr> <td>
---+ Lab 7 - Game of Life
---+++ Due: November 19, 11:55pm

[[https://moodle.kenyon.edu/mod/assign/view.php?id=6223][Moodle Link]]</td> <td><img alt="1280px-Game_of_life_glider_gun.svg.png" height="90" src="%ATTACHURLPATH%/1280px-Game_of_life_glider_gun.svg.png" width="320" /></td> </tr> </tbody> </table>
---+++ Alternate Graphics Oriented Lab

If you wish, you can try this [[IntroGraphicLab8][alternate lab]] involving Allegro Graphics. You will need to install Alegro on you own computer, Allegro is not on the lab computers.

---+++ Instructions

   * Turn in the code (a cpp file), and the run outputs as requested below.
   * Remember to format the code as described and the book and text, and to include comments including complete commetns at the beginning of the program.
---+++ Grading Table
| *Requirement* | *Grading Comments* | *Points* | *Score* |
| Easy to use user interface | | 10 | |
| C++ code includes comments, with project information at top, pre and post conditions for each functions and other cmments as needed. | | 10 | |
| The C++ code has good formatting, indentation, and organization. | | 10 | |
| Good variable and function names, appropriate use of constants rather then literal numbers. | | 10 | |
| Functions: Logic divided up into cohesive functions with a single purpose | | 20 | |
| Runs: Run examples from trials with correct output | | 40 | |
| Total | | 100 | |
---+++ Conway's Game of Life
---+++ <img alt="population-dynamics-in-conways-game-of-life-and-its-variants-9-728.jpg" height="436" src="%ATTACHURLPATH%/population-dynamics-in-conways-game-of-life-and-its-variants-9-728.jpg" width="600" />
---+++ Problem

The mathematician John Horton Conway invented the “Game of Life.” Though not a “game” in any traditional sense, it provides interesting behav- ior that is specified with only a few rules. This Project 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 array to 80 characters wide by 20 character positions high. If you have access to a larger screen, by all means use it. This world is an array 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.
   * 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 newborn 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.

---+++ Notes

Some configurations grow from relatively small starting configurations. Others move across the region. It is recommended that for text output you use a rectangular array of char with 22 rows and 82 columns (the world is actually 20,80, see for why we add the extra two rows nd columns) to store the LIFE world’s successive generations. (*char world[22][82];*) Use an asterisk * to indicate a living cell, and use a blank (or space) to indicate an empty (or dead) cell. If you have a screen with more rows than that, by all means make use of the whole screen.

Also, it would be best if you used constants for the row number and column number, e.g.:
<sticky>
%CODE{"c++"}%
    int const rows=22;
    int const columns = 80;
    char world[rows][columns];
%ENDCODE%</sticky>

---+++ Examples:
| Step 1 | Step 2 | Step 3 | Step 4 |
| <img alt="Screen_Shot_2016-09-30_at_10.25.25_PM.png" height="250" src="%ATTACHURLPATH%/Screen_Shot_2016-09-30_at_10.25.25_PM.png" width="246" /> | <img alt="Screen_Shot_2016-09-30_at_10.28.44_PM.png" height="242" src="%ATTACHURLPATH%/Screen_Shot_2016-09-30_at_10.28.44_PM.png" width="240" /> | <img alt="Screen_Shot_2016-09-30_at_10.25.25_PM.png" height="250" src="%ATTACHURLPATH%/Screen_Shot_2016-09-30_at_10.25.25_PM.png" width="246" /> | ??? |
again, and so on.

What happens with this?

<img alt="Screen_Shot_2016-09-30_at_10.33.02_PM.png" height="260" src="%ATTACHURLPATH%/Screen_Shot_2016-09-30_at_10.33.02_PM.png" width="270" />

---+++ Input

On startup have the program ask for coordinates of where to put *'s:
<pre>Welcom to LIFE.  Enter row and column coordinates where 1&lt;=row&lt;=20 and 1&lt;=column&lt;=80.  Enter row of -1 to end.
Enter coordinate 1: 10 10
coordinate 2: 10 11
coordinate 3: 10 12
coordinate 4: -1

        * * *
Enter to 'Y' continue:Y
           *
           *
           *
Enter to 'Y' continue:Y

        * * *

Enter to 'Y' continue:N!
Bye!
</pre>

---+++ 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 *nextGenWorld* that takes the array we call *world*, a 80-column by 22-row *array of char*, which contains the initial configuration. This would be defined by *world[22][80]*. The function scans the array 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. *nextGenWorld* will need to have a local array ( *newWorld*) of the same type and size, and it will compute the next generation status of each cell from *world* into *newWorld*.<strong>nextGenWorld</strong> will then copy *newWorld* back into *world* and return.

So, the life of a cell [r,c] where __r__ is the row, and __c__ is the column, depends on surrounding cells:
| [r-1,c-1] | [r-1,c] | [r-1,c+1] |
| [r,c-1] | [r, c] | [r,c+1] |
| [r+1,c-1] | [r+1,c] | [r+1,c+1] |
Given each cell, you will write a to examine the surrounding cells to determine what happens to that cell.

One trick is dealing with the boundary conditions, that is when something is on the edge of the array. A neat trick is to make the array one bigger in every direction, and then use this as boundary space. So if we make *world[22][82]*, the first index *r* goes (top to bottom) from 0 to 21, or 22 total rows, and the other index *c* goes (left to right) from 00 to 81. Start by making every element a space. Use these boundary cells while computing next generations, but never change or print the boundary cells. Then a boundary is really not an exception, it is just considered a dead cell with no chance for life. The boundary cells should never be displayed (they are for internal use only).

Example:
| | *0* | *...* | *c-1* |  *c* |  *c+1* | *...* | *81* |
| *0* | space | ... | space | space | space | ... | space |
| *...* | space | ... | ... | ... | ... | ... | space |
| *r-1* | space | ... | [r-1,c-1] | [r-1,c] | [r-1,c+1] | ... | space |
| *r* | space | ... | [r,c-1] | [r, c] | [r,c+1] | ... | space |
| *r+1* | space | ... | [r+1,c-1] | [r+1,c] | [r+1,c+1] | ... | space |
| *...* | space | ... | ... | ... | ... | ...  | space |
| *23* | space  | ... | space | space | space | ... | space |
There should also be a function *display* that accepts the array world and displays the array on the screen. Is should merely display the contents of each row right to left.
---+++ Design - the following routines might be useful:

   * *int alive(char cell*) - return a <b>1 </b>for *alive('*')*, and *0* otherwise. Used to check if a *cell* is alive.
   * *int neighborsAlive(car world [][82], int r, int c)* - Return the number of neightbors of cell (r,c) that are alive. Simply add the <b>Alive </b>valuefor all the neigbors<b>.</b>
   * *char nextGenCell(char world[][82], int row, int column)* - return a '*' if the cell at this location should be alive in the next generation. Otherwise return a space.
   * *void nextGenWorld(char current[ ][82])* - Given the *current* world, compute the *next* generation for the world. Note this changes the current world to a new world, so internally it will need to have some sort of temporary world to compute into, then it will need to copy that new world back over the current world.
   * You find a LOT of interesting patterns here: [[http://www.conwaylife.com/wiki/Main_Page][conwaylife]]
   * *void copyWorld(* *char from[ ][82], char to[ ][82])* - Copy world *from* to world *to*. <p> </p>
---+++ Using Classes

You should consider using classes to do the game. What I would suggest the following class:
| World |
| char board[22][82];<br />char tempBoard[22][82]; |
| <span style="background-color: transparent;">World() // Constructor<br /></span><span style="background-color: transparent;">void inputBoard() // Ask user for positions of life<br /></span><span style="background-color: transparent;">void display() // Display the board<br /></span><span style="background-color: transparent;">void nextGen(); // move to the next generation</span> |
The functions described in the design above should be private helper functions inside the class. The main can be something like:
<sticky>
%CODE{"c++"}%

int main()
{
  char done;
  World w;   // create the board
  w.inputBoard();   // fill board with life;
  do {
     w.Display();       // show the board
     w.nextGen();      // go to next generation
     cout << "Hit D if done:";
     cin >> done;
  } while (done != "D");
}

%ENDCODE%</sticky>

---+++ Examples

There is a cool online version to play with [[http://pmav.eu/stuff/javascript-game-of-life-v3.1.1/][here]] and [[http://www.bitstorm.org/gameoflife/][here]].

---+++ Turn In:

Runs of the following cases. Run until they are either stable, or 10 steps, whichever come first. Turn in the results.

   * <img alt="boat.png" height="67" src="%ATTACHURLPATH%/boat.png" width="68" /> (10,10), (11, 10), (10, 11), (12, 11), (11, 12)
   * <img alt="glider.png" height="67" src="%ATTACHURLPATH%/glider.png" width="68" /> (10,10),(10,11),(10,12),(11,10),(12,11)
   * <img alt="f.png" height="65" src="%ATTACHURLPATH%/f.png" width="67" /> (10,11),(10,12),(11,10),(11,11),(12,11) <p> [[SsdSolutions][Solutions]]</p>
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who
png	boat.png	r1	manage	4.1 K	2016-08-24 - 20:22	JimSkon
png	f.png	r1	manage	4.1 K	2016-08-24 - 20:22	JimSkon
png	glider.png	r1	manage	4.1 K	2016-08-24 - 20:22	JimSkon
png	Screen_Shot_2016-09-30_at_10.25.25_PM.png	r1	manage	7.1 K	2016-10-01 - 02:29	JimSkon
png	Screen_Shot_2016-09-30_at_10.28.44_PM.png	r1	manage	7.6 K	2016-10-01 - 02:29	JimSkon
png	Screen_Shot_2016-09-30_at_10.33.02_PM.png	r1	manage	8.4 K	2016-10-01 - 02:33	JimSkon
png	1280px-Game_of_life_glider_gun.svg.png	r1	manage	12.0 K	2016-09-30 - 18:54	JimSkon
jpg	population-dynamics-in-conways-game-of-life-and-its-variants-9-728.jpg	r1	manage	131.4 K	2016-09-30 - 18:54	JimSkon
Topic revision: r28 - 2019-11-12 - JimSkon