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

then the next step is

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[4][3] = 1;
board[4][4] = 1;
board[4][5] = 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;}
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 += '.';
result += 'X';}
result += '\n';}
return result;}

//Unit testing
public static void main(String[] argc){
TwoDCell life = new TwoDCell(8);

No comments: