CS 4: Lecture 12 Wednesday, March 1, 2006 THE GAME OF LIFE ================ In 1970, the mathematician John Conway invented a "game" played on a grid of square cells--like a chess board, except that it extends infinitely far in all directions. Each cell is in one of two states: it is either _live_ or _dead_. We represent a live cell by putting a marker on the square. Dead cells are empty. Each cell has eight _neighbors_, the other cells that touch it (including the diagonally connected cells). Life runs one timestep at a time, just like our numerical simulations. After each timestep, each cell's state--live or dead--depends solely on the state of that cell and its neighbors just before the timestep. If a live cell has only one or zero live neighbors at the start of a timestep, it dies of loneliness during the timestep. If a live cell has four or more live neighbors at the beginning of a timestep, it dies of overcrowding during the timestep. ------- ------- |X| | | |?|?|?| ------- ------- | |X| | --> |?| |?| ------- ------- | | | | |?|?|?| ------- ------- If a live cell has two or three neighbors, it survives the timestep. ------- ------- | |X| | |?|?|?| ------- ------- | |X| | --> |?|X|?| ------- ------- | | |X| |?|?|?| ------- ------- If a dead cell has _exactly_ three neighbors, a new life is magically created in the cell during the timestep. Otherwise, it stays dead. ------- ------- | |X|X| |?|?|?| ------- ------- |X| | | --> |?|X|?| ------- ------- | | | | |?|?|?| ------- ------- All of the cells change from their old states to their new states simultaneously. The new state of each cell depends _only_ on the states before the timestep took place. You can't decide the new state for one cell based on the new state for its neighbor--if you do that, you'll get it wrong. Here's an example of a timestep. ------------- ------------- | | | | | | | | | |X|X| | | ------------- ------------- | |X|X|X|X| | | | |X| |X| | ------------- ------------- | | | |X|X| | --> | | | | |X| | ------------- ------------- | |X|X| | | | | | |X|X| | | ------------- ------------- | | | | | | | | | | | | | | ------------- ------------- Those are all the rules. Life is one example of a _cellular_automaton_. You can invent other cellular automata simply by changing the rules--for example, you could decide that a life is also born if seven of its neighbors are live; or you could decide that each cell has one of four different states, with rules as fancy as you like for deciding a cell's state after a timestep. The reason Life is famous, though, is because it exhibits very rich behavior from very simple rules. By choosing your starting state carefully, it's even possible to make the Game of Life simulate a computer. Cellular automata are sometimes applied to scientific problems. In particular, the Ising model of ferromagnetic materials is effectively a cellular automaton in which each electron has one of two spins. Electrons have a tendency to align their spins with their neighbors, but their spins can also toggle randomly, especially if the material is hot. Cellular automata have also been used to study forest fire propagation and the percolation of fluids through porous materials. Implementing Life ----------------- How could you implement the Game of Life? Well, a computer can't truly represent an infinite game board, so we're going to compromise a bit and use a finite game board. For example, we might create the game board like this. int[][] board = new int[150][50]; Each array element will be zero if the corresponding cell is dead, and one if the cell is live. We use special names to define these constants. public class Automaton { private final static int DEAD = 0; private final static int LIVE = 1; Java's "final" keyword declares a value that can never be changed. Because DEAD is "final", it's illegal to assign anything to it (except in the initializer). If you try, you'll get a compiler error. We could have used booleans instead of ints, but we'd like our code to generalize to more complicated automata, where each cell might have more than two states. Life isn't interesting if we start with all the cells dead, so we need to come up with an interesting starting state. Recall from lab that Java allows you to construct a Random object, which you can use to generate random numbers. Random r = new Random(new Date().getTime()); final double LIVING_PROBABILITY = 0.40; // initialize the array for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { if (r.nextDouble() < LIVING_PROBABILITY) { board[i][j] = LIVE; } else { board[i][j] = DEAD; } } } What's going on here? - A Random object generates random numbers for us. However, a random number generator needs a "seed" number to get it started. If it always starts with the same seed, you'll always get the same random numbers, so you'll watch the same Game of Life each time you run it, and that's not very interesting. So we use the time of day to initialize the random number generator when we construct the Random object. That way, we get a different game every time. - We initialize each cell to be live with 40% probability, and dead with 60% probability. Next, we implement a "step" method that performs one timestep. public static int[][] step (int[][] in) { Observe that step takes in a two-dimensional array, and also returns one. The array it returns is _not_ the same array object as the input parameter. The "step" method constructs a new array, writes the updated state in it, and returns the new array. Why a _new_ array? Suppose we tried to write the new state in the same array as the old state. To determine the new state of a cell, you need to know the _old_ state of all its neighbors. But if you update a cell in the same array, then you erase its old state--so you can't update its neighbors. This is a common programming error. You'll write the "step" method in lab. You'll need to figure out how to find a cell and its neighbors, determine their states, and figure out the cell's new state. CONSTANTS ========= If you find yourself repeatedly using a numerical value with some "meaning" in your code, you should probably turn it into a "final" constant. BAD: if (month == 2) { GOOD: public final static int FEBRUARY = 2; // Usually near top of class. ... if (month == FEBRUARY) { Why? Because if you ever need to change the numerical value assigned to February, you'll only have to change one line of code, rather than hundreds. The custom of rendering constants in all-caps is long-established and was inherited from C. The "final" keyword ensures that a programmer can't accidentally write code that changes the value during program execution. For any array x, "x.length" is a "final" field.