CSC352 Game of Life Lab 2017

--D. Thiebaut (talk) 17:02, 8 February 2017 (EST)

---

Game of Life

In this lab you will write a multithreaded version of Conway's Game of Life.

Serial Game of Life

Wikipedia has a good page on Conway's game of life. Please read the first section containing the rules.
The program below is a serial version of the game of life taken from RosettaCode.org.

It displays the generation of cells using simply ascii characters on the console. Get a copy of it with the following command:

getcopy GameOfLife.java

If that doesn't work, just copy/paste it in a file called GameOfLife.java in your 352b-xx account.
Compile and run it as follows:

javac GameOfLife.java
java GameOfLife

and adjust the size of your terminal/console to make sure you can see the pattern evolving.

The game is coded so that the array wraps around horizontally, and vertically. So a pattern sliding on the array will reach the bottom and reappear at the top. Similarly, a pattern sliding off the left will reappear on the right.

The generations are stable for a few seconds, then one of the moving patterns (glider) hits the blinker, and the population of cells start growing until it freezes with just a few cells blinking.

/*  
 Game of life
 D. Thiebaut
 Heavily adapted from code found in java section at this
 URL:  https://rosettacode.org/wiki/Conway%27s_Game_of_Life#Java

 This code works in console mode, displaying successive generations
 of the game of life on the screen, and clearing the screen between
 each one.

 The initial pattern is defined in the array dish (as in petri dish).

 To compile and run:

 javac GameOfLife.java
 java GameOfLife


*/

public class GameOfLife{
    public static void main(String[] args){
	String[] dish2 = {
	    "     ",
	    "  #  ",
	    "  #  ",
	    "  #  ",
	    "     " 
	};
	String[] dish= {
	    "                                                                                  ",
	    "   #                                                                              ",
	    " # #                                            ###                               ",
	    "  ##                                                                              ",
	    "                                                                                  ",
	    "                                                      #                           ",
	    "                                                    # #                           ",
	    "                                                     ##                           ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "             #                                                                    ",
	    "           # #                                                                    ",
	    "            ##                                                                    ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  ",
	    "                                                                                  "
	};
	int gens= 30000;
	for (int i= 0;i < gens;i++) {
	    //System.out.println("Generation " + i + ":\n\n\n");
	    print(dish);
	    dish= life(dish);
	    
	    clearScreen();
	    // add a bit of a delay to better see the visualization
	    // remove this part to get full timing.
	    try {
		Thread.sleep(50);                
	    } catch(InterruptedException ex) {
		return;
	    }
	}
    }

    public static void clearScreen(){
        /* 
        brings the cursor home (top-left), so that the 
        next generation will be printed over the current one.
        */
	final String ANSI_CLS    = "\u001b[2J";
        final String ANSI_HOME = "\u001b[H";
        System.out.print( ANSI_HOME);
        System.out.flush();
    }
    
    public static String[] life(String[] dish){
        /*
        Given an array of string representing the current population of
        cells in a petri dish, computes the new generation of cells according
        to the rules of the game.
        A new array of strings is returned.
        */

	String[] newGen= new String[dish.length];

	for ( int row= 0; row < dish.length; row++ ) {//each row

	    newGen[row]= "";

	    for ( int i= 0; i < dish[row].length(); i++ ) {//each char in the row

		int neighbors = 0;
		char current = dish[row].charAt(i);

		// loop in a block that is 3x3 around the current cell
		// and count the number of '#' cells.  
		for ( int r=row-1; r<=row+1; r++ )  {

		    // make sure we wrap around from bottom to top
		    int realr = r;
		    if ( r==-1 )         realr = dish.length-1;
		    if ( r==dish.length) realr = 0;

		    for ( int j=i-1; j<=i+1; j++ ) {
			
			// make sure we wrap around from left to right
			int realj = j;
			if ( j==-1 )                 realj = dish[row].length()-1;
			if ( j==dish[row].length() ) realj = 0;

			if (r==row && j==i ) continue; // current cell is not its
			                               // neighbor
			if (dish[realr].charAt(realj) == '#' )
			    neighbors++;
		    }
		}

		if ( current=='#' ) 
		    if (neighbors < 2 || neighbors > 3) 
			newGen[row] +=  " "; 
		    else
			newGen[row] += "#";  

		if ( current==' ' )
		    if ( neighbors == 3 )
			newGen[row] += "#";
		    else
			newGen[row] += " ";
	    }
	}
	return newGen;
    }
        
    public static void print( String[] dish ) {
        /*
        just display all the lines of the array of strings.
        */
	for ( String s: dish )
	    System.out.println(s);
	
    }
}

Exploring the Serial Version

• Explore the code and make sure you get some reasonable understanding of it.
• Play with the Thread.sleep() delay to see how it influences the display.
• Create new patterns in the petri dish, and see how they evolve.

Part 1: Class discussion

Question #1:

How could we make this program parallel, and make it work faster with 2 threads? Think of what would constitute the contents of the run() method, and how you would split the data for the least amount of coding.

Question #2:

Think of what would constitute the contents of the run() method.

Question #3:

How should you split the data for the least amount of extra coding.

Question #4:

Playout your parallel sketch of an algorithm and see if there are some hidden complexity in the way the two threads should proceed so that the generations are computed correctly.

Part 2: Coding

Go for it and code a multithreaded version of the Game of Life!

• Recommendations:

• Do not make the threads display their arrays. They might interleave their System.out.println() outputs and it won't look good. We really should have a 3rd thread to display the different generations, but for now it's easier to have the main program display the final generation only.
• Code an application that just uses 2 threads, and do not worry about synchronizing them. Very likely the generations will not be correct, but, at least, you will have two threads running on computing the evolution of life in their two halves of the petri dish.
• When your code work and stops correctly, without errors, add the synchronization.
• Then, and only then, verify that your parallel program works correctly by comparing the last generation it creates to the one generated by the serial version.

• Feel free to work in pairs.