Friday, April 11, 2008

2D Cellular Automata

A two-dimensional cellular automata implements the same idea but in a two-dimensional array. The most famous one is Conway's game of life which uses the following rules:

1. Any live cell with fewer than two live neighbours dies, as if by loneliness.

2. Any live cell with more than three live neighbours dies, as if by overcrowding.

3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.

4. Any dead cell with exactly three live neighbours comes to life.

Where the neighbors of a cell are those which immediately surround it. Thus, if you start with
`.......................XXX................`

then the next step is
`.................X......X......X..........`

Write a class which implements and displays Conway's game of life. This time, try to make the cells on the edge (border) neighbors of those at the other side, that is, make the space wrap around.

This program is too long to fit on a whiteboard (at least, in Java) but a good programmer should be able to write out the basic functions in a piece of paper, but getting all the details correct (such as the module arithmetic and the update function) will likely require testing. It is a good test of your debugging abilities as well as your matrix manipulation capabilities.

`public class TwoDCell {  private int[][] board;  /**Creates a square board */  public TwoDCell(int length){    board = new int[length][length];    for (int i = 0; i < board.length; i++)      for (int j=0; j < board[i].length; j++)        board[i][j] = 0;  }  /** Ugly hack, just for testing. Its a flipper. */  public void setup(){    board = 1;    board = 1;    board = 1;}  /** A true modulo function for the board. Negative numbers get     wrapped around, as well as numbers bigger than the size of the     board. Only works if n >= -board.length.*/  private int mod(int n){    if (n < 0) return board.length + n;    return n % board.length;  }  /** Return the number of neighbors, assumes that x,y are not on the     border of the board. This works out because I set 0 to be a dead     cell and 1 to be a live cell...sneaky me.*/  public int getNumNeighbors(int x, int y){    return //picture this      board[mod(x-1)][mod(y-1)] + board[x][mod(y-1)] + board[mod(x+1)][mod(y-1)] +       board[mod(x-1)][y]                             + board[mod(x+1)][y] +      board[mod(x-1)][mod(y+1)] + board[x][mod(y+1)] + board[mod(x+1)][mod(y+1)];  }    /** Take a step in Conway's Game of Life */  public void step(){    int[][] newBoard = new int[board.length][board.length];    //Apply the rule of Life    for (int i = 0; i < board.length; i++)      for (int j=0; j < board[i].length; j++){        int neighbors = getNumNeighbors(i,j);        if (board[i][j] == 1) {          if (neighbors < 2) {            newBoard[i][j] = 0;}          else if (neighbors < 4) {            newBoard[i][j] = 1;}          else { //5 or more             newBoard[i][j] = 0;}}        else {//dead cell          if (neighbors == 3) {            newBoard[i][j] = 1;}          else             newBoard[i][j] = 0;}};    board = newBoard;  }  /**The Obvious visualization */  public String toString(){    String result = "";    for (int i=0; i< board.length; i++){      for (int j=1; j < board.length; j++){        if (board[i][j] == 0)           result += '.';        else          result += 'X';}      result += '\n';}    return result;}  //Unit testing  public static void main(String[] argc){    TwoDCell life = new TwoDCell(8);    life.setup();    System.out.println(life);    life.step();    System.out.println(life);    life.step();    System.out.println(life);  }`