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:

  -- Begin Code Segment --
  #include <iostream>
  #include <iomanip>
  #include <fstream>
  #include <stdlib.h>
  #include <unistd.h>
  #include <time.h>
  #include "ansi.h"

  using namespace std;

  #define GRID_WIDTH  80
  #define GRID_HEIGHT 24
  #define DELAY 500000
  -- End Code Segment --

  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;
  
   //initialize the grid
   if(argc==2) {
     initGrid(argv[1], grid1);
   } else {
     initGrid(grid1);
   }
  
   //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!