Conway's Game of Life in JavaScript

Question

I made Conway's Game of Life in JavaScript and was hoping someone could give me some pointers regarding my logic of checking adjacent cells. I know there must be a better way, but at the same time, it works.

JS:

var board = [["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""],
            ["","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""]];

//boolean to tell if cell is alive
var alive = new Boolean(null);

//counter will be used to see how many cells are alive
var counter;



//number of initial alive cells
var number = Math.floor((Math.random()*900)+5);

//coordinates for alive cells
var xcor;
var ycor;

//make table and assign ID to all cells
var idAssign;
document.write("<table border='1px>'");
for (var x = 0; x < 30; x++ ) {
    document.write("<tr>");

    for (var y = 0; y < 30; y ++) {
        idAssign = x.toString() + y.toString();
        document.write("<td id='" + idAssign + "'>oo</td>");
    }
    document.write("</tr>");
}
document.write("</table>");

//generate coordinates for the cells that are alive
for (var i=0; i < number; i++) {
    xcor = Math.floor((Math.random()*29)+0);
    ycor = Math.floor((Math.random()*29)+0);

    board[xcor][ycor] = "x";

}
function run(){

    //loop to check all cells
    for (var x=0; x != 30; x++) {
        for (var y=29; y != -1; y--) {

            //reset counter and boolean after every iteration
            counter = 0;
            alive = null;

            //evaluation of cells
            var check;
            check = x.toString() + y.toString();

            //check current cell
            if(board[x][y] == "x") {
                alive = true;
            }
            else{
                alive = false;
            }

            //BOUNDS
            //Handle left bound
            if (y == 0) {
                if (board[x ][(y + 1)] == "x"){
                    counter ++;
                }
                //Left bottom corner
                if (x == 29) {
                    if (board[(x - 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y + 1)] == "x") {
                        counter ++;
                    }
                }
                //Left top corner
                else if (x == 0) {
                    if (board[(x + 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][(y + 1)] == "x") {
                        counter ++;
                    }
                }
                else{
                    if (board[(x - 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[x][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][(y + 1)] == "x") {
                        counter ++;
                    }
                }
            }
            //handle right bound
            else if (y == 29) {
                if (board[(x)][(y - 1)] == "x"){
                    counter ++;
                }
                //right bottom corner
                if (x == 29) {
                    if (board[(x - 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y - 1)] == "x") {
                        counter ++;
                    }
                }
                //right top corner
                else if (x == 0) {
                    if (board[x + 1][y] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][(y - 1)] == "x") {
                        counter ++;
                    }
                }
                else{
                    if (board[(x - 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y - 1)] == "x") {
                        counter ++;
                    }
                    if (board[x][(y - 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][(x - 1)] == "x") {
                        counter ++;
                    }
                }
            }
            else{
                //Top bounds
                if (x == 0) {
                    if (board[x][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[x][(y - 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][y + 1] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][y - 1] == "x") {
                        counter ++;
                    }

                }
                //Bottom bounds
                else if (x == 29) {
                    if (board[x][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[x][(y - 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y - 1)] == "x") {
                        counter ++;
                    }
                }
                else{
                    //center of board
                    if (board[x][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[x][(y - 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][y] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x - 1)][(y - 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][(y + 1)] == "x") {
                        counter ++;
                    }
                    if (board[(x + 1)][(y - 1)] == "x") {
                        counter ++;
                    }
                }
            } //end board checking

            //apply rules to cell
            if (alive == true) {
                if (counter < 2) {
                    board[x][y] = "";
                }
                if (counter > 3) {
                    board[x][y] = "";
                }
            }
            else if (alive == false) {
                if (counter == 3) {
                    board[x][y] = "x";
                }
                else if (counter != 3){
                    board[x][y] = "";
                }
            }


        }//Inner FOR

    }// Outer FOR

    var IDcheck;
        for (var x= 0; x < 30; x ++) {
            for (var y = 0; y <30; y ++) {
                IDcheck = x.toString() + y.toString();
                if (board[x][y] == "x" ) {
                    document.getElementById(IDcheck).className = 'active';
                }
                else{
                    document.getElementById(IDcheck).className = 'NotActive';
                }
            }
        }

}//WHILE

HTML:

<html>
    <head>
        <!-- Author:           Justin Murphy     >
        <--- Start Date:       November 27, 2013 >
        <--- File:             Display.html      >
        <--- Supporting Files: Life.js         -->
        <title>Conway's Game Of Life</title>
        <link rel='stylesheet' type='text/css' href='style.css'>
        <script src='Life.js'></script>

    </head>
    <body onload='setInterval(function(){run();},100)'>

    </body>

</html>

The reason I have all spaces set to the array manually is because, instead of randomly generating the starting plots for the bacteria, one could comment out that code and place them manually to see that sort of patterns they can make.

Answer 1

There is a major bug/issue, and also stringing together three very different recommendations here.

Bug/issue

in the Game-Of-Life you are supposed to scan the entire board, and only then apply the changes. You are applying changes part-way through the process (as you check each cell, you change its state). So, if you change the cell in one location, when you check it's neighbour it will affect the results).

You need to 'store' the counter for each cell until you have completed the scan, and then re-set each block in the board. Essentially you need the following:

var counter[];
//loop to check all cells
for (var x=0; x < DIMENSION; x++) {
    for (var y=0; y < DIMENSION; y++) {
        counter[x][y] = 0;
        // check all cells and update counter[x][y]
    }
}
// loop to update board....
for (var x=0; x < DIMENSION; x++) {
    for (var y=0; y < DIMENSION; y++) {
        // check whether we are alive or dead....
        if (counter[x][y] == 2 || counter[x][y] == 3) {
            board[x][y] = "x";
        } else {
            board[x][y] = "";
        }
    }
}

Code style:

Seriously, you manually create the blank board? Wasn't that sore on the wrists? Lazy programmers are a good thing, consider the following:

var DIMENSION= 30;
var board = [];
for (var y = 0; y < DIMENSION; y++) {
    for (var x = 0; x < DIMENSION; x++) {
        board[y][x] = "";
    }
}

Note, this declares the dimension for the game. This is a single constant. Your use of 30 and 29 in a lot of places is called using Magic Numbers, and this is a bad thing... You need to replace those with a dimension

OK, that gets rid of the copy/paste board initializer.

Math.random()

To initialize the 'alive' cells you use:

xcor = Math.floor((Math.random()*29)+0);
ycor = Math.floor((Math.random()*29)+0);

This is never going to generate the value 29... It is a common mistake to make when using Math.random() which is to forget that Math.random() returns a value from 0.0 (inclusive) to 1.0 (EXCLUSIVE). In other words, it will never generate 1.0 and you will thus never get the value 29.

The right approach is:

xcor = Math.floor(Math.random()*DIMENSION);
ycor = Math.floor(Math.random()*DIMENSION);

Using Buddy-table

In the Game-of-life, each cell has a buddy. The buddy cells are:

• above me (or nothing if we are at the top) - to the left, immediate, and to the right
• left of me (or nothing if we are at the left)
• right of me (or nothing if we are at the right)
• below me (or nothing if we are at the bottom) - to the left, immediate and to the right.

We can represent these buddies as:

var BUDDIES = [
      [-1, -1], [0, -1], [1, -1],  // above
      [-1,  0],          [1,  0],  // our row
      [-1,  1], [0,  1], [1,  1]]; // below

Those arrays are what we have to add to our (x,y) co-ordinate to get the surrounding buddies.... but, the table does not help (yet) with cells at the margins.

But, there is a modulo trick for that. Consider the function:

function buddy(dim, pos, direction) {
    return (pos + direction + dim) % dim;
}

Since your version of the game does not 'wrap' at the margins, use this function instead:

function buddy(maxdim, pos, direction) {
    var newpos = pos + direction;
    if (newpos >= maxdim) {
       newpos = -1;
    }
    return newpos;
}

This function takes the dimension of the board, the position (in one dimension), and which way we want to look for our buddy. So, consider we want to find the position of our 'left' buddy:

var left = buddy(DIMENSION, x, -1);

If x is 5 for example, it will add the -1, and 5 together to get 4.

If x is 0, it will return -1

If we want to find the right buddy at position 29, the math will be: 29 + 1, which is 30, and that will be translated to -1.

Now, all the 'duplicate' code you have for your neighbour checks can be reduced to a loop:

# Using the buddies array above
for (var i = 0; i < buddies.length; i++) {
    var budx = buddy(DIMENSION, x, BUDDIES[i][0]);
    var budy = buddy(DIMENSION, y, BUDDIES[i][1]);
    if (budx >= 0 && budy >= 0 && "x" == board[budx][budy]) {
        counter++;
    }
} 

Conclusion

Between these three (.5) suggestions (board initialization (and dimension magic number), Random, and Buddies) you should be able to reduce your code size massively.

Answer 2

I see several issues with the initialization, aside from the obvious gigantic literal array.

• Ambiguous element IDs: You concatenate x.toString() + y.toString() for the element IDs. When you refer to ID 121, is that (12, 1) or (1, 21)?

• Namespace pollution (global variables): alive, counter, xcor, ycor, and idAssign do not need to be in the global scope. The simple fix is to initialize the board using an Immediately Invoked Function Expression (IIFE):

  var board = (function(dim, min) {
      var b = new Array(dim);
      // TODO: initialize b
      return b;
  })(30, 5);
  

  I would go a step further and change it to a constructor (see below).

• Underpopulation: You use the following code to generate the initial alive cells:

  //number of initial alive cells
  var number = Math.floor((Math.random()*900)+5);
  
  /* Some code here which should not have been placed
     in an intervening position */
  
  //generate coordinates for the cells that are alive
  for (var i=0; i < number; i++) {
      xcor = Math.floor((Math.random()*29)+0);
      ycor = Math.floor((Math.random()*29)+0);
  
      board[xcor][ycor] = "x";
  }
  

  You'll be breathing life into some cells twice, so number is actually an upper bound, not an exact count, of the number of cells that are initially alive. Perhaps you don't care about the exact count, since it's random anyway, but at least the "number of initial alive cells" comment should be made more accurate.

  To get an exact count, populate the first n cells, then do a shuffle.

• "x" as a boolean: You use "x" to basically serve as a boolean value; true would be more conventional.

Here's how I would write it:

function Board(dim, min) {
    var b = new Array(dim);
    for (var i = 0; i < b.length; i++) {
        b[i] = new Array(dim);
    }

    // Give life to a random number of cells
    var initPopulation = min + Math.floor((dim * dim + 1 - min) * Math.random());
    for (var i = 0; i < initPopulation; i++) {
        b[i / dim >> 0][i % dim] = true;
    }
    // Two-dimensional Fisher-Yates shuffle
    for (var i = dim * dim - 1; i > 0; i--) {
        var j = Math.floor((i + 1) * Math.random());
        var swap = b[i / dim >> 0][i % dim]; 
        b[j / dim >> 0][j % dim] = b[i / dim >> 0][i % dim]; 
        b[i / dim >> 0][i % dim] = swap; 
    }
    this.array = b;
}

var board = new Board(30, 5);

Answer 3

To reduce memory usage and increase performance I recommend you consider a sparse matrix approach. Instead of having an entire array of mostly empty cells, you can just keep a list of cells that are live. As a cell changes state, you update the display for that cell and the list for the surrounding cells.

---

Edit: I will describe it in more detail as I have time.

---

To do this, create a cell object that has attributes for x, y coordinates for each live cell you want to represent:

function cell(x, y) {
    this.x = x;
    this.y = y;
}

Also create a grid object that is just an array of cells, and has the following methods:

grid.isLive(x,y) \\ return true if cell(x, y) is found in grid array.
grid.liveNeighbors(x,y) \\ returns number of live neighbors around any grid coordinate

To create the new grid state, test each (x,y) coordinate of the entire grid space with grid.liveNeighbors(x,y) and add live cells to the next grid object.

This can be further optimized by using the existing grid to eliminate large dead areas from the test. For example, you could find out the min and max x and y values and only test that region.

Or could add a boolean live and int liveNeighbors attribute to the cell object to keep track of the liveNeighbors value in nearby dead cells, then switch them live when the value is within the life threshold. This will allow you to only iterate through the grid list, not the entire grid space, providing much better performance in many cases.

---

Edit: I created a short, simple Python example version here, converting to JavaScript will make it a little longer.

---

Answer 4

In addition to @rolfl suggestion you could create a separate LifeBoard class and keep the array private and have a second count array. Then provide get, set and remove methods. Whenever square is set, increment it's neighbors in the count array, whenever one is removed, decrement them.

That way it saves you always double counting squares as you move over the board.