48
\$\begingroup\$

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.

Jamal
35.2k13 gold badges134 silver badges238 bronze badges
asked Jan 7, 2014 at 13:01
\$\endgroup\$
4
  • 2
    \$\begingroup\$ About a year ago I created a Game of Life in Javascript, as an excercise. I used html5 canvas to render, but you can see how I solved some things. jsfiddle.net/mgvd/a2tVe \$\endgroup\$ Commented Jan 7, 2014 at 15:58
  • 3
    \$\begingroup\$ The jsfiddle link doesn't work in my browser, so I have no idea how you solved anything. You should post the details on this site, with a link solely for reference. \$\endgroup\$ Commented Jan 7, 2014 at 16:44
  • 2
    \$\begingroup\$ Thanks to all who answered. I am not going to lable a correct answer yet, but I do plan to. I just want to see give it a day or 2 to see if any one else can come with anything. Thanks for your help! \$\endgroup\$ Commented Jan 7, 2014 at 18:55
  • \$\begingroup\$ Not worth a whole answer, but function(){run();} in your setInterval call can be more succinctly written run - since run is already a function taking no arguments, there's no reason I can think of to wrap it in an anonymous function with no arguments. Also, remember that var only scopes to the current function (including code written above the var declaration), not current {} pair; so for (var x=0; x != 30; x++) gives a misleading impression of the scope of x. \$\endgroup\$ Commented Jan 8, 2014 at 0:08

4 Answers 4

70
\$\begingroup\$

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.

answered Jan 7, 2014 at 13:52
\$\endgroup\$
11
  • 1
    \$\begingroup\$ You don't have to actually process the entire board before writing the values back; There's a way to do it where you store a row's values in an array and use that array to get the old values when computing the next row. \$\endgroup\$ Commented Jan 7, 2014 at 16:29
  • 1
    \$\begingroup\$ Also, why is there a +0 in Math.floor((Math.random()*dimension)+0);? \$\endgroup\$ Commented Jan 7, 2014 at 16:31
  • \$\begingroup\$ @AJMansfield - copy-paste from the OP's code. There is no other reason... will edit. \$\endgroup\$ Commented Jan 7, 2014 at 16:32
  • 2
    \$\begingroup\$ @DaveJarvis that is correct, and it is not supposed to. DIMENSION is 30, and since the array index is 0-based, the largest value we ever want is 29. We want to generate values from 0 to 29 inclusive, so Math.floor(Math.random() * 30) is what we want to do (Note DIMENSION is 30, and not 29 like you have in your JFiddle) \$\endgroup\$ Commented Jan 7, 2014 at 19:19
  • 1
    \$\begingroup\$ @David, Google's Javascript style guide recommends against it (not supported in IE). \$\endgroup\$ Commented Jan 8, 2014 at 0:02
10
\$\begingroup\$

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);
answered Jan 7, 2014 at 21:11
\$\endgroup\$
8
\$\begingroup\$

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.

answered Jan 7, 2014 at 16:11
\$\endgroup\$
3
  • 8
    \$\begingroup\$ That's a good idea, but you should give some more info on how to actually implement this in JS. It's not something that will be obvious to the OP. \$\endgroup\$ Commented Jan 7, 2014 at 16:48
  • 1
    \$\begingroup\$ Could you provide a small scale example of this? you have peaked my interest \$\endgroup\$ Commented Jan 7, 2014 at 18:52
  • 4
    \$\begingroup\$ 'Piqued'. :) english.stackexchange.com/questions/101450/… \$\endgroup\$ Commented Jan 8, 2014 at 0:04
5
\$\begingroup\$

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.

answered Jan 7, 2014 at 14:27
\$\endgroup\$
3
  • \$\begingroup\$ Since this is JavaScript, there is no such thing as a "class". I guess what you mean is to have an object, or possibly a constructor for multiple similar objects, with the "private" data scoped to the constructor or an IIFE. The distinctions are worth keeping in mind, as I think a lot of JS code gets over-complex because people are trying to emulate OO as they know it from another language, rather than using the JS OO facilities to solve their actual problem. \$\endgroup\$ Commented Jan 8, 2014 at 0:02
  • \$\begingroup\$ Yea, my bad. I see everything in Java terms these days ;) \$\endgroup\$ Commented Jan 8, 2014 at 8:48
  • \$\begingroup\$ For posterity, ECMAScript 6 became a standard on 17 June 2015 which includes Classes and while it took a few years, mainstream browsers added support for Private properties. \$\endgroup\$ Commented Feb 28 at 16:42

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.