Conway's game of life - Optimizing the code

Question

I have just finished my first iteration of conway's game of life as a codeing excercise. I have little experience with coding, so I think my code could use some refactoring. What i am curios about is the drivers for having a more efficient code. My code is based on a cell object:

//Defining the cells --------------------------------------------
function Cell (x,y,id, num) {
 this.id = id;
 this.num = num;
 this.isAlive = false;
 this.x = x;
 this.y = y;
 this.nextIsAlive = false;
 this.cellChange = false;
 this.cellTop = function() {
 if (this.y === 0) {
 return false;
 }
 return getCell(this.x, this.y-OFFS-RECH/2).isAlive;
 };
 this.cellRight = function() {
 if (this.x+RECW >= canvas.width) {
 return false;
 }
 return getCell(this.x+RECW+OFFS+RECW/2, this.y).isAlive;
 };
 this.cellBottom = function() {
 if (this.y+RECH >= canvas.height) {
 return false;
 }
 return getCell(this.x, this.y+RECH+OFFS+RECH/2).isAlive;
 };
 this.cellLeft = function() {
 if (this.x === 0) {
 return false;
 }
 return getCell(this.x-OFFS-RECW/2, this.y).isAlive;
 };
 this.cellUpperLeft = function() {
 if (this.x === 0 || this.y === 0) {
 return false;
 }
 return getCell(this.x-OFFS-RECW/2, this.y-OFFS-RECH/2).isAlive;
 };
 this.cellUpperRight = function() {
 if (this.x+RECW >= canvas.width || this.y === 0) {
 return false;
 }
 return getCell(this.x+RECW+OFFS+RECW/2, this.y-OFFS-RECH/2).isAlive;
 };
 this.cellBottomLeft = function() {
 if (this.x === 0 || this.y+RECH >= canvas.height) {
 return false;
 }
 return getCell(this.x-OFFS-RECW/2, this.y+RECH+OFFS+RECH/2).isAlive;
 };
 this.cellBottomRight = function() {
 if (this.x+RECW >= canvas.width || this.y+RECH >= canvas.height) {
 return false;
 }
 return getCell(this.x+RECW+OFFS+RECW/2, this.y+RECH+OFFS+RECH/2).isAlive;
 };
 this.numOfLiveNeighbour = function() {
 var i = 0;
 if (this.cellTop()) {
 i++;
 }
 if (this.cellRight()) {
 i++;
 }
 if (this.cellBottom()) {
 i++;
 }
 if (this.cellLeft()) {
 i++;
 }
 if (this.cellUpperLeft()) {
 i++;
 }
 if (this.cellUpperRight()) {
 i++;
 }
 if (this.cellBottomLeft()) {
 i++;
 }
 if (this.cellBottomRight()) {
 i++;
 }
 return i;
 };
}
Cell.prototype = {
 constructor: Cell,
 //Function where cell draws itself
 drawCell: function() {
 if (this.isAlive) {
 ctx.fillRect(this.x,this.y,RECW,RECH);
 } else {
 ctx.clearRect(this.x,this.y,RECW,RECH);
 }
 },
 //Function for killing a cell during animation
 killCell: function () {
 this.nextIsAlive = false;
 },
 //Function for reviving a cell during animation
 reviveCell: function () {
 this.nextIsAlive = true;
 },
 //function for turning on & off a cell when animation is not going.
 toggle: function() {
 if (this.isAlive) {
 this.isAlive = false;
 } else {
 this.isAlive = true;
 }
 }
};
// Cell finished -----------------------------------------------

As you can see i am trying to use a constructor/prototype pattern, but i think i have too many function definitions in the constructor, is that correct to assume? Is it a better way to do this?

I also have a suspicion that my functions for getting cells, determining next steps etc are not optimal:

//Function for finding a cell based on x & y coordinates ------------
function getCell(x,y) {
 for (var cell in cells) {
 var currCell = cells[cell];
 if (x >=currCell.x && x <= currCell.x+RECW && y >=currCell.y && y <= currCell.y+RECH) {
 return currCell;
 }
 }
}
//Function for drawing next step
function cellsNextStep() {
 var currCell;
 for (var cellNext in cells) {
 currCell = cells[cellNext];
 determineNextStep(currCell);
 }
 for (var cellDraw in cells) {
 currCell = cells[cellDraw];
 if (currCell.cellChange) {
 currCell.isAlive = currCell.nextIsAlive;
 }
 currCell.drawCell();
 currCell.cellChange = false;
 currCell.nextIsAlive = false;
 }
}
//Function for determining next value for each cell
function determineNextStep(cell) {
 var neighbours = cell.numOfLiveNeighbour();
 if (cell.isAlive) {
 if (neighbours < 2 || neighbours > 3) {
 cell.killCell();
 cell.cellChange = true;
 }
 } else {
 if (neighbours === 3) {
 cell.reviveCell();
 cell.cellChange = true;
 }
 }
}

My main problem is that when i try to increase the canvas size (number of cells are increased) the animation comes to a stand still. It is currently working ok with a canvas ov width 300, height 150 and cellsize of 7 (RECH and RECW) and offset between cells of 1 (OFFS).

I also have three different handlers, one for turning cells on and off before animation, one to start animation and one to stop. I guess I also should use one click handler on the document and make use of the bubble feature to only have one event handler (but i dont think that is my main performance issue here).

Any feedback would be appreciated!

• Pointy: It's a bad idea to use for ... in loops on arrays in JavaScript. Use a numeric index and a plain for loop. Besides that, your performance problem stems from the fact that you have to search to find your cells. Keep track of them with an array of arrays (a 2-dimensional array, in other words) and your "getCell()" function will be much faster.
• Bergi: Yes, you can put all your methods on the prototype since they're using only properties of your objects, not the local variables (parameters) in your constructor.
• djechlin: For starters, run this through jslint or jshint.
• Øyvind: @Pointy: thanks, the for ... in change helped alot. I also moved the functions to the prototype, but i didn't quite understand the change of the getCell() function. This function is based on the event from a mouseclick (using the x and y coordinates to determine the cell). Maybe it is smart to have one functions for this task and one "internal" getCell that keeps track of the cells?
• Pointy: @Øyvind well if you kept track of your cells in a data structure that allowed a direct lookup instead of a search, you'd save a huge amount of overhead.

Answer 1

Your code could indeed probably use some tuning.

The three major points are:

• A cell should know it's neighbors, you should only once determine the neighbors for each cell and place them in an array in that Cell. This will speed up your code tremendously.

• Only living cells and their neighbors can change, tracking the living cells in a queue ( array ) will speed up your code. You would check the cells in that queue and the neighbors within the cells for changes.

• Checking all cells for life status changes in status slows the code down, you should have a queue ( array ) where you add all cells that change status. This way you only draw what changes.

Then there are some minor things you can consider:

1.

drawCell: function() {
 if (this.isAlive) {
 ctx.fillRect(this.x,this.y,RECW,RECH);
 } else {
 ctx.clearRect(this.x,this.y,RECW,RECH);
 }

this could be a little DRYer since the parameters are the same.

drawCell: function() {
 var action = this.isAlive ? ctx.fillRect : ctx.clearRect;
 action(this.x,this.y,RECW,RECH);
}

2.

toggle: function() {
 if (this.isAlive) {
 this.isAlive = false;
 } else {
 this.isAlive = true;
 }
}

could use some Boolean magic:

toggle: function() {
 this.isAlive = !this.isAlive;
}

Finally, determineNextStep should really be part of the prototype of Cell.