Conway's game of life - suggest code improvements

Tsskyx

After like half a year of not programming with Processing at all, I got back into it to see if I'm still good at it.

I tried to make Conway's game of life. Look at the code and suggest improvements. I'm really not happy with a few things in it, for example the code that checks the state of neighboring cells for each one:

class Cell {
  PVector dim, pos;
  boolean state, change;
  int[] id = new int[2];

  Cell(int x, int y) {
    id[0] = x;
    id[1] = y;
    dim = new PVector(width/float(cols), height/float(rows));
    pos = new PVector(x*dim.x, y*dim.y);
  }

  boolean mouseInside() {
    return mouseX > pos.x && mouseX < pos.x+dim.x && mouseY > pos.y && mouseY < pos.y+dim.y;
  }

  void iterate() {
    int count = 0;
    if (id[0]-1 > -1 && id[1]-1 > -1 && grid[id[0]-1][id[1]-1].state) {
      count++;
    }
    if (id[1]-1 > -1 && grid[id[0]][id[1]-1].state) {
      count++;
    }
    if (id[0]+1 < rows && id[1]-1 > -1 && grid[id[0]+1][id[1]-1].state) {
      count++;
    }
    if (id[0]-1 > -1 && grid[id[0]-1][id[1]].state) {
      count++;
    }
    if (id[0]+1 < rows && grid[id[0]+1][id[1]].state) {
      count++;
    }
    if (id[0]-1 > -1 && id[1]+1 < cols && grid[id[0]-1][id[1]+1].state) {
      count++;
    }
    if (id[1]+1 < cols && grid[id[0]][id[1]+1].state) {
      count++;
    }
    if (id[0]+1 < rows && id[1]+1 < cols && grid[id[0]+1][id[1]+1].state) {
      count++;
    }
    if (state && (count < 2 || count > 3) || !state && count == 3) {
      change = true;
    }
  }

  void display() {
    if (change) {
      state = !state;
      change = false;
    }
    fill(state? color(255, 255, 0) : 200);
    stroke(175);
    rect(pos.x, pos.y, dim.x, dim.y);
  }
}

int rows = 40;
int cols = 40;
boolean drawMode;

Cell[][] grid = new Cell[cols][rows];

void setup() {
  size(800, 800);
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      grid[i][j] = new Cell(i, j);
    }
  }
}

void draw() {
  background(0);
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      if (mousePressed && mouseButton != CENTER && grid[i][j].mouseInside()) {
        grid[i][j].state = drawMode;
      }
      grid[i][j].display();
    }
  }
}

void mousePressed() {
  switch (mouseButton) {
  case LEFT:
    drawMode = true;
    break;
  case RIGHT:
    drawMode = false;
    break;
  case CENTER:
    for (int i = 0; i < cols; i++) {
      for (int j = 0; j < rows; j++) {
        grid[i][j].state = false;
      }
    }
  }
}

void keyPressed() {
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      if (key == ' ') {
        grid[i][j].iterate();
      }
    }
  }
}

koogs

id[0] = x;
id[1] = y;

Code would be a lot more readable, and much less typing, if you didn't use an array to store the class's x and y.

Chrisir

Well this

return mouseX > pos.x && mouseX < pos.x+dim.x && mouseY > pos.y && mouseY < pos.y+dim.y;

can be written as

  return 
   mouseX > pos.x && 
   mouseX < pos.x+dim.x && 
   mouseY > pos.y && 
   mouseY < pos.y+dim.y;

Chrisir

your whole iterate() method could be a nested for loop, both from -1 to 1

if not both are 0, hand it over to a function that performs the checks

jeremydouglass

Recent very concise Conway's Game of Life example, possibly of interest:

• https://forum.processing.org/two/discussion/comment/114488/#Comment_114488

quark

for example the code that checks the state of neighboring cells for each one:

In the game of life this is the most time consuming bit. The problem is not so much how to code it but how to avoid doing it at all ;)

jeremydouglass

Two in-depth code review discussions about optimizing Conway's Game of Life in Java:

• https://codereview.stackexchange.com/questions/62160/checking-for-neighbours-more-elegantly-in-conways-game-of-life
• https://codereview.stackexchange.com/questions/42718/optimize-conways-game-of-life

These include some good tips for refactoring (an array of offsets), optimization (an empty border and no special bounds checking), and advanced algorithms for high-performance life computing, if you are going in that direction (like hashlife, which uses quadtrees).

quark

These articles are OK but the first is still counting neighbours (every frame) :( and the second is using a 3D boolean array to buffer the intermediate calculations :(

The first is expensive in CPU time and the second in memory.

A much better solution would to have a single 2D byte array for the grid and never have to count neighbours and avoid array bounds checking. All these are easily achievable allowing large boards with good frame rates.

The trick here is in the design of the life board. Assume that we want a board size [w, h] we use a byte array byte[w+2][h+2] with the usable/displayable elements being [1-w][1-h]. The extra 2 columns and 2 rows mean we don't have to do array bounds checking when we are stepping the animation.

NOTE we still need to check the x,y coordinates fit inside the usable part of the array when we are setting up the initial board.

Now we come to the cell, there are only two things we need to know
1) Does the cell contain life?
2) How many neighbouring cells contain life?

The second has a value in the range 0-8 so can be encoded in 4 bits, the first is a simple boolean so can be encoded with one bit. The code below uses the four least significant bits (0-3) for the number of neighbours (this simplifies and speeds up the code) and the next bit (4) to say if there is life or not. So the following bytes mean

00010010 has life and 3 neighbours - will survive
00010101 has life and 5 neighbours - will die
00000011 empty and 3 neighbours - will create life
00000001 empty 1 neighbour - will remain empty

Now consider what happens when a cell gets new life, all the neighbouring cells have an extra neighbour at the next step. If a cell empties then all the neighbouring cells have one less neighbour at the next step. So what happens is that as we iterate over the board and note the positions of any changes i.e. 'lifr > empty' and 'empty > life`. At the end of the iteration we simply process the changes by incrementing or decrementing the number of neighbours for neighbouring celss.

Anyway the sketch below demonstrates what I mean and shows a 160x120 grid with a Gosper Gun running in it. If any of the code needs further explanation just ask.

Grid board;

void setup() {
  size(800, 600);
  board = new Grid(160, 120, 4);
  addGosperGun(4, 4);
  addGosperGun(40, 9);
  addGosperGun(76, 14);
  addGosperGun(112, 19);
  noStroke();
  // We have to slow the framerate otherwise the 
  // animation looks blury
  frameRate(10);
}

void draw() {
  background(0);
  board.step();
  board.display();
}

void addGosperGun(int px, int py) {
  board.addLife(px + 2, py + 6);
  board.addLife(px + 2, py + 7);
  board.addLife(px + 3, py + 6);
  board.addLife(px + 3, py + 7);
  board.addLife(px + 12, py + 6);
  board.addLife(px + 12, py + 7);
  board.addLife(px + 12, py + 8);
  board.addLife(px + 13, py + 5);
  board.addLife(px + 13, py + 9);
  board.addLife(px + 14, py + 4);
  board.addLife(px + 14, py + 10);
  board.addLife(px + 15, py + 4);
  board.addLife(px + 15, py + 10);
  board.addLife(px + 16, py + 7);
  board.addLife(px + 17, py + 5);
  board.addLife(px + 17, py + 9);
  board.addLife(px + 18, py + 6);
  board.addLife(px + 18, py + 7);
  board.addLife(px + 18, py + 8);
  board.addLife(px + 19, py + 7);
  board.addLife(px + 22, py + 4);
  board.addLife(px + 22, py + 5);
  board.addLife(px + 22, py + 6);
  board.addLife(px + 23, py + 4);
  board.addLife(px + 23, py + 5);
  board.addLife(px + 23, py + 6);
  board.addLife(px + 24, py + 3);
  board.addLife(px + 24, py + 7);
  board.addLife(px + 26, py + 2);
  board.addLife(px + 26, py + 3);
  board.addLife(px + 26, py + 7);
  board.addLife(px + 26, py + 8);
  board.addLife(px + 36, py + 4);
  board.addLife(px + 36, py + 5);
  board.addLife(px + 37, py + 4);
  board.addLife(px + 37, py + 5);
}

class Grid {
  ArrayList<Change> changes = new ArrayList<Change>();

  int lifeColor = color(255, 255, 0); // cell containing life
  int emptyColor = color(64, 64, 64); // cell with no life

  int w; // number of cells horizontally
  int h; // number of cells vertically
  int gs; // Physical space needed for cell
  int s; // cell size
  boolean wrap; // Wrap the interation as if on a torus
  byte[][] grid;

  Grid(int w, int h, int s) {
    this.w = w;
    this.h = h;
    this.s = s;
    this.gs = s + 1; // Give a cell separation effect
    grid = new byte[w + 2][h + 2]; // Will be initialised to zero
  }

  void display() {
    int px = 0, py = 0;
    for (int iy = 1; iy <= h; iy++) {
      px = 0;
      for (int ix = 1; ix <= w; ix++) {
        int col = (grid[ix][iy] & 16) == 16 ? lifeColor : emptyColor;
        fill(col);
        rect(px, py, s, s);
        px += gs;
      }
      py += gs;
    }
  }

  void step() {
    // Iterate across the grid and calculate changes
    for (int iy = 1; iy <= h; iy++) {
      for (int ix = 1; ix <= w; ix++) {
        byte cell = grid[ix][iy];
        boolean alive = (cell & 16) == 16;
        int nn = cell & 15; // number of neighbours
        if ( (alive && (nn < 2 || nn > 3)) || (!alive && nn == 3) ) {
          changes.add(new Change(ix, iy));
        }
      }
    }
    // Apply changes
    for (Change change : changes) {
      boolean alive = (grid[change.x][change.y] & 16) == 16; 
      if (alive) {
        clearLife(change.x, change.y);
      } else {
        addLife(change.x, change.y);
      }
    }
    changes.clear();
  }

  void addLife(int x, int y) {
    if (x >= 1 && x <= w && y >=1 && y <= h && grid[x][y] < 16) {
      addLifeImpl(x, y);
    }
  }

  // Only to be used by the step() method
  private void addLifeImpl(int x, int y) {
    grid[x - 1][y - 1]++;    // NE
    grid[x][y - 1]++;        // N
    grid[x + 1][y - 1]++;    // NW
    grid[x - 1][y]++;        // W
    grid[x + 1][y]++;        // E
    grid[x - 1][y + 1]++;    // SW
    grid[x][y + 1]++;        // S
    grid[x + 1][y + 1]++;    // SE
    grid[x][y] |= 16;        // add life
  }

  void clearLife(int x, int y) {
    if (x >= 1 && x <= w && y >=1 && y <= h && grid[x][y] >= 16) {
      clearLifeImpl(x, y);
    }
  }

  // Only to be used by the step() method
  private void clearLifeImpl(int x, int y) {
    grid[x - 1][y - 1]--;    // NE
    grid[x][y - 1]--;        // N
    grid[x + 1][y - 1]--;    // NW
    grid[x - 1][y]--;        // W
    grid[x + 1][y]--;        // E
    grid[x - 1][y + 1]--;    // SW
    grid[x][y + 1]--;        // S
    grid[x + 1][y + 1]--;    // SE
    grid[x][y] &= 15;        // remove life
  }

  private class Change {
    final int x;
    final int y;

    Change(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}