Conway's game of life - suggest code improvements

edited January 2018 in Questions about Code

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();
      }
    }
  }
}
Tagged:

Comments

  • 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.

  • edited January 2018

    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;
    
  • edited January 2018

    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

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

  • 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 ;)

  • edited January 2018

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

    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).

  • 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;
        }
      }
    }
    
Sign In or Register to comment.