Conways Game of Life in Java

Question

I created a program in Java that showcases Conway's Game of Life, in 4 days. Created the algorithm from scratch. However I got a scathing review and left me scratching my head. This was for a job application, the guy didn't say anything more, other than: "Kevin – we are going to pass. He has good documentation and coding hygiene, but his algorithms and design choices are questionable. It really does not make sense based on his background." I submitted it to Codacity and got a B based on style and such, I mean given the short time I had, I chose having more features, than elegant code. Could someone help me to understand what I did that was so bad.

You can see the whole bit here

/* (non-Javadoc)
 * @see Cells#step()
 * Calculate next generation of cells
 * Algorithm:
 *  - get both cells from the two buffers, both have the exact same location
 *  - count live neighbors, regardless of state, somewhat optimal depending on state
 *  - apply game rules: liveCell (2 or 3 liveNeighbors) = live, deadCell (3 liveNeighbors) = live
 *  - clear cell buffer, by killing all cells
 *  - swap buffers, readying for next step
 */
@Override
public void step() {
    for (int i = 0; i < this.cells.size(); ++i) {
        Cell cp = this.cells.get(i);
        Cell bcp = this.cellsBuffer.get(i);
        // count neighbor states, location is cached as adjacent cells contain references
        int liveNeighborsCount = getNeighborCount(cp);
        if (cp.isAlive()) {
            if (liveNeighborsCount == 2 || liveNeighborsCount == 3) {
                bcp.revive();
            }
        } else if (cp.isDead()) {
            if (liveNeighborsCount == 3) {
                bcp.revive();
            }
        }
    }
    // clear grid = kill all cells
    // we don't kill them before, since it would cause neighbor miscalculations
    for (Cell cp : this.cells) {
        cp.kill();
    }
    // swap arrays for next iteration
    ArrayList<Cell> tmp = this.cellsBuffer;
    this.cellsBuffer = this.cells;
    this.cells = tmp;
}

/**
 * Recalculate engine cell grid
 * use double buffer, so as to avoid unnecessary memory allocation and deallocation
 * Algorithm:
 *   - save current alive cells into array
 *   - resize cell buffer and add cells set to dead initially
 *   - for each cell save neighbor locations
 *   - clone array, both contain only dead cells
 *   - copy saved alive cells into cell array
 *   - save current dimensions
 *   - restored saved cells into resized array
 */
private void recalculate() {
    // save alive cells
    ArrayList<Cell> alive = new ArrayList<>(0);
    for (Cell nc : this.cells) {
        if (nc.isAlive()) {
            alive.add(nc);
        }
    }

    int c = this.dimensions.width;
    int r = this.dimensions.height;
    this.cellsBuffer = new ArrayList<>(c * r);
    // initialize array, identity is set to dead, so first step is recalculated
    Cell cp = null;
    Point p = null;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            p = new Point(i, j);
            cp = new Cell(p);
            this.cellsBuffer.add(cp);
        }
    }
    // calculate and set neighbors
    if (this.teleport) {
        calculateNeighborsStiched();
    } else {
        calculateNeighbors();
    }

    //clone cell array
    this.cells = new ArrayList<>(c * r);
    for (Cell bcp : this.cellsBuffer) {
        this.cells.add(new Cell(bcp));
    }

    this.columns = c;
    this.rows = r;
    // copy old to current
    for (Cell ocp : alive) {
        Point op = ocp.getLocation();
        cp = this.cells.get((op.x * this.columns) + op.y);
        cp.revive();
    }
}


//cells are confined to the grid without teleporting capability
private void calculateNeighbors() {
    int c = this.dimensions.width;
    int r = this.dimensions.height;
    int col = 0;
    int row = 0;
    for (Cell ncp : this.cellsBuffer) {
        Point np = ncp.getLocation();
        int i = np.x;
        int j = np.y;

        ArrayList<Point> neighbors = new ArrayList<>(8);
        // go around the cell...
        // top
        row = i - 1;
        col = j;
        if (row >= 0) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        // bottom
        row = i + 1;
        col = j;
        if (row < r) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        // top left
        row = i - 1;
        col = j - 1;
        if (col >= 0 && row >= 0) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        // top right
        row = i - 1;
        col = j + 1;
        if (col < c && row >= 0) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        // bottom left
        row = i + 1;
        col = j - 1;
        if (col >= 0 && row < r) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        // bottom right
        row = i + 1;
        col = j + 1;
        if (col < c && row < r) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        // left
        row = i;
        col = j - 1;
        if (col >= 0) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        // right
        row = i;
        col = j + 1;
        if (col < c) {
            addNeighbor(ncp, row, col, c, neighbors);
        }
        ncp.setNeighbors(neighbors);
    }
}

Answer 1

What I like:

• There is documentation, for nearly everything, which is great! Just for my curiosity's sake, what's the point of writing (non-Javadoc) at the beginning of your commentaries? Is it for human or for automatized tools? First time I see it, I'm genuinely curious.
• While looking quickly at your Github repo, I see you have tests, HOWTO, a README etc, I can tell you took a bit of extra time helping people wanting to look at your code and this is marvelous! Really I mean it.

What I liked less:

• Naming. I really don't like reading one letter variables. i or j is acceptable in a loop because people know what they stand for, I feel r and c are not, in a loop or outside.
• The naming of Cell and Cells for the class and the interface, that might be just personal taste but I find it confusing. One convention I learned a while ago is to put an I before the name if it's an interface, like ICell for interface and Cell for the class. I don't like this convention either but I find it less confusing. As always, naming is a hard thing.
• ArrayList<Cell> alive = new ArrayList<>(0); in the function recalculate(), maybe I'm missing the point but you initialize a 0 sized ArrayList, and then you try to put stuff in it, not a big deal but why not giving it no argument or an argument > 0 to initialize it with some room at first? That might be just a personal thing.

• Very long methods like calculateNeighbors(), which can be refactored easily. This is your code

  //cells are confined to the grid without teleporting capability
  private void calculateNeighbors() {
      int c = this.dimensions.width;
      int r = this.dimensions.height;
      int col = 0;
      int row = 0;
      for (Cell ncp : this.cellsBuffer) {
          Point np = ncp.getLocation();
          int i = np.x;
          int j = np.y;
  
          ArrayList<Point> neighbors = new ArrayList<>(8);
          // go around the cell...
          // top
          row = i - 1;
          col = j;
          if (row >= 0) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          // bottom
          row = i + 1;
          col = j;
          if (row < r) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          // top left
          row = i - 1;
          col = j - 1;
          if (col >= 0 && row >= 0) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          // top right
          row = i - 1;
          col = j + 1;
          if (col < c && row >= 0) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          // bottom left
          row = i + 1;
          col = j - 1;
          if (col >= 0 && row < r) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          // bottom right
          row = i + 1;
          col = j + 1;
          if (col < c && row < r) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          // left
          row = i;
          col = j - 1;
          if (col >= 0) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          // right
          row = i;
          col = j + 1;
          if (col < c) {
              addNeighbor(ncp, row, col, c, neighbors);
          }
          ncp.setNeighbors(neighbors);
      }
  }
  

That you could have written like:

//cells are confined to the grid without teleporting capability
private void calculateNeighbors() {
    int c = this.dimensions.width; //name it height or gridHeight?
    int r = this.dimensions.height; /name it width or gridWidth?
    int col = 0;
    int row = 0;
    for (Cell ncp : this.cellsBuffer) {
        Point np = ncp.getLocation();

        ArrayList<Point> neighbors = new ArrayList<>(8);
        // go around the cell...

        for(int col=np.x-1; col<=np.x+1; col++)
        {
            for(int row=np.y-1; row<=np.y+1; row++)
            {
                if(row!=np.y and col!=np.x and isInsideGrid(col,row))
                    addNeighbor(ncp, row, col, c, neighbors);
            }
        }
        ncp.setNeighbors(neighbors);
    }
 }

/*
* function to test if a position is inside the grid
* Documentation...
*/
private bool isInsideGrid(int x, int y)
{
    return (x>=0 and x<this.dimension.width and y>=0 and y<this.dimension.height);
}

Which in my opinion is shorter, clearer and less error prone.

Of course you had little time for this project, and quite frankly this is really impressive. Good luck for your future interviews!

Answer 2

Thanks for sharing your code.

I generally agree with the answer of @JulienRousé. I'd like to add some points:

Comments

I disagree that so much comments are something good.

Comments should explain why the code is like it is. You comment almost all only repeat what the code should express itself by proper naming and smaller methods.

E.g.: you have comments that "split" bigger methods into logical sections. This logical sections should live in their own methods names after the comments you used to separate them:

  private void recalculate() {
     ArrayList<Cell> alive =  saveAliveCells();
     initializeArrayWithDeadCells();
     calculateAndSetNeighbors();
     cloneCellArray(); 
     copyOldToCurrent(alive); 
  }

-

  private ArrayList<Cell> saveAliveCells() {
    // save alive cells
    ArrayList<Cell> alive = new ArrayList<>(0);
    for (Cell nc : this.cells) {
        if (nc.isAlive()) {
            alive.add(nc);
        }
    }
    return alife;
  }

-

  private void initializeArrayWithDeadCells() {
    int c = this.dimensions.width;
    int r = this.dimensions.height;
    this.cellsBuffer = new ArrayList<>(c * r);
    // initialize array, identity is set to dead, so first step is recalculated
    Cell cp = null;
    Point p = null;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            p = new Point(i, j);
            cp = new Cell(p);
            this.cellsBuffer.add(cp);
        }
    }
  }

-

private void  calculateAndSetNeighbors() {
    // calculate and set neighbors
    if (this.teleport) {
        calculateNeighborsStiched();
    } else {
        calculateNeighbors();
    }
}

-

private void cloneCellArray() {
    //clone cell array
    this.cells = new ArrayList<>(c * r);
    for (Cell bcp : this.cellsBuffer) {
        this.cells.add(new Cell(bcp));
    }
}

-

private void copyOldToCurrent(ArrayList<Cell> alive) {
    this.columns = c;
    this.rows = r;
    // copy old to current
    for (Cell ocp : alive) {
        Point op = ocp.getLocation();
        cp = this.cells.get((op.x * this.columns) + op.y);
        cp.revive();
    }
}

Now your recalculate() method "tells a story" and no extra comment is needed to understand what it does.

general approach

Your code is a procedural approach to the problem.

There is nothing wrong with procedural approaches in general, but Java is an object oriented (OO) programming language and if you want to become a good Java programmer then you should start solving problems in an OO way.

What I mean is: what if a cell is not just an element in an array or a dump data object but knows its neighbors?

Why could this be important?

Because the fastest way to do something is not to do it.

How many of the cells do change from one iteration to another? Wouldn't it be clever to recalculate only for those cells that might change because any of its neighbors changed and skip calculation for all the rest?

If Cells had knowledge about their neighbors and how to calculate the next state we could collect all the neighbors of changed cells and do calculation only for those few cells instead of all the cells of the complete field.

// Game class, main loop
List<Cell> allCells = initializeGameFieldAndSetCellNeigbours();
Set<Cell> affectedCells = new HashSet<>(allCells); // removes duplicates
do {
  Set<Cell> affectedCellsNextGen = new HashSet<>();
  for(Cell currentCell : affectedCells)
    currentCell.changeState(affectedCellsNextGen);
  displayGame();
  affectedCells.clear();
  affectedCells.addAll(affectedCellsNextGen);
} while(isGameRunning());

-

class Cell {
  Map<Cell,Boolean> currentGenerationNeighborStates = new HashMap<>(); 
  private boolean state;

  public void addNeighbor(Cell neighbor){
    currentGenerationNeighborStates.put(neighbor, neighbor.getState());
  }

  public boolean getState(){
     return state;
  }

  private saveOldState(Cell neighbor){
    currentGenerationNeighborStates.put(neighbor, neighbor.getState());
  }

  public calculate nextState(Set<Cell> affectedCellsNextGen){
     pushOldStateToNeigbours();
     if(calculateNewState()) {
        reportNeighborsAsPossibleChangingInNexGeneration(affectedCellsNextGen)
     }
  }

  private void reportNeighborsAsPossibleChangingInNexGeneration(Set<Cell> affectedCellsNextGen){
     affectedCellsNextGen.addAll(neighbors);
  }

  private void pushPoldStateToNeigbours(){
     for(Cell neighbor : currentGenerationNeighborStates.keySet())
        neighbor.saveOldState(this);
  }

  private boolean calculateNewState(){   
    boolean oldState = state;
    int alifeNeigborsCount = countAlifeNeigbours();
    state = state 
            ? isAlifeCellSurviving(alifeNeigborsCount) 
            : isDeadCellBorn(alifeNeigborsCount);
    return  oldState ^ state;         
  }

  private boolean isAlifeCellSurviving(int alifeNeigborsCount){
     return 3 == alifeNeigborsCount || 2 == alifeNeigborsCount;
  }
  private boolean isDeadCellBorn(int alifeNeigborsCount){
     return 3 == alifeNeigborsCount;
  }

  private int countAlifeNeigbours();
    int alifeNeighborsCount = 
          currentGenerationNeighborStates
              .stream()
              .map(mapEntry-> mapEntry.value())
              .filter(isAlife->isAlife)
              .count();
     return alifeNeighborsCount;
  }
}

This is the complete algorithm.

Please notice that there is no reference to the actual geometry of the game field. It is completely moved to the initialization phase (not shown) and during runtime no corner check or edge check is needed. _{I don't even need to create a 2-dimensional array to find neighbors (Of cause this will help for display...). I could do this with a simple logic on a list of cells (but not on a Set since it does not keep order of elements).}