Conway’s Game of Life

| Comments

My javascript demo.
Naive implementation of Conway’s life game.


You can try click the black screen to toggle cell’s life, create some patterns and then click play.

Game of Life maybe is, as far as I know, the most simple cellular automaton. The cell life is ruled by its neighbors. The cell will not survive if there is more than 3 or less than 2 adjacent cells alive. And a new cell will born if there is exactly 3 adjacent cells alive.

The original concept for game of life mentioned that the field is infinite, so we can always check how the n-th generation’s doing. I implement finite field above since it’s way more simple.

Now let’s see the source.

1
2
3
function und(a) {
    return (typeof a === "undefined");
}

Since I used finite field for this implementation, we should check for unbounded cell, from function above we can check the cell whether it is actually defined or not.

Next, we calculate the cell’s neighbour. Game of life using cartessian lookalike field in which the coordinate system is orthogonal. Naturally, I use 2 dimensions array for this. To calculate the neighbours number, we can traverse through all adjacent cells and check if that cell is dead or alive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function count_neighbour(f, x, y) {
    var num = 0;
    if (!und(f[x - 1])) {
        if (!und(f[x - 1][y - 1]) && f[x - 1][y - 1] === 1) num += 1;
        if (!und(f[x - 1][y]) && f[x - 1][y] === 1) num += 1;
        if (!und(f[x - 1][y + 1]) && f[x - 1][y + 1] === 1) num += 1;
    }
    if (!und(f[x])) {
        if (!und(f[x][y - 1]) && f[x][y - 1] === 1) num += 1;
        if (!und(f[x][y + 1]) && f[x][y + 1] === 1) num += 1;
    }
    if (!und(f[x + 1])) {
        if (!und(f[x + 1][y - 1]) && f[x + 1][y - 1] === 1) num += 1;
        if (!und(f[x + 1][y]) && f[x + 1][y] === 1) num += 1;
        if (!und(f[x + 1][y + 1]) && f[x + 1][y + 1] === 1) num += 1;
    }
    return num;
}

That is the most simple algorithm I can think of, not really clever I know… ^_^;

Of course we should initiate our field first. Here I’m using typed array for a slight performance boost.

1
2
3
4
5
function init_field(field, h, w) {
    for (j = 0; j < h; j++) {
        field[j] = new Uint8Array(w);
    }
}

Uint8Array will generate array of 8bit unsigned integer, which we can access like ordinary array later.

Now let’s initiate the DOM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function init_field_dom(h, w) {
    for (j = 0; j < h; j++) {
        for (i = 0; i < w; i++) {
            cell = $("<div id =\"cell_"+ i +"_"+ j +"\"></div>").addClass("cell");
            cell.addClass("clickable");
            cell.appendTo("#life_field");
        }
    }
}

function toggleOnOff(field, x, y) {
    if (field[x][y] === 0) {
        field[x][y] = 1;
    }
    else {
        field[x][y] = 0;
    }
}

Those functions will generate all the small cells. The toggleOnOff function will just alternate the cell’s state.

And here is the life rule.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var dead_cell_fn = function (field, n_field, x, y) {
    n = count_neighbour(field, x, y);
    if (n == 3) {
        n_field[x][y] = 1;
    }
    else {
        n_field[x][y] = 0;
    }
}

var alive_cell_fn = function (field, n_field, x, y) {
    n = count_neighbour(field, x, y);
    if (n <= 1 || n >= 4) {
        n_field[x][y] = 0;
    }
    else {
        n_field[x][y] = 1;
    }
}

function next_gen(field, n_field, h, w) {
    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++) {
            if (field[x][y] === 0) {
                dead_cell_fn(field, n_field, x, y);
            }
            else {
                alive_cell_fn(field, n_field, x, y);
            }
        }
    }
}

You see I’m cheating above. I use 2 fields to calculate the next generation, so we can maintain the current field state as we create our next generation, but this also mean we have to alternate between this 2 fields while playing. And that nasty nested for-loop made the algorithm grow in exponential.

For the rule itself. You can change the rule as you like. For example you may want a new cell to born if there is 5 adjacent cells alive, etc…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function play_this_life(field, temp, h, w) {
    var swap = true;
    play = function() {
        if (swap) {
            next_gen(field, temp, h, w);
            update_field(temp, h, w);
            swap = false;
        }
        else {
            next_gen(temp, field, h, w);
            update_field(field, h, w);
            swap = true;
        }
    };
    return play;
}

You can say the overall game is controlled by this function above. I made closure to do some currying with all of those parameters. Closure is sort of like an object constructor, but work with function. Above, we check for the swap value since we should alternate between field and tmp.

The last is our main entry.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
$(function() {
    var _field = [];
    var temp   = [];
    var rgx    = /cell_(\d+)_(\d+)$/;
    var dw = 64 ,dh = 64;

    init_field(_field, dw, dh);
    init_field(temp, dw, dh);
    init_field_dom(dw, dh);

    $(".cell").click(function(){
        getto = rgx.exec(this.id);
        x = parseInt(getto[1]);
        y = parseInt(getto[2]);
        toggleOnOff(_field, x, y);
        toggleOnOff(temp, x, y);
        $("#cell_" + x + "_" + y).toggleClass("cell_on");
    });

    update_field(_field, dw, dh);
    lets_play = play_this_life(_field, temp, dw, dh);

    var intId = null;
    var play  = false;
    $("#play").click(function() {
        if (!play) {
            intId = setInterval(lets_play, 85);
            play  = true;
        }
    });
    $("#stop").click(function() {
        if (play) {
            clearInterval(intId);
            play = false;
        }
    });
});

We bind the click event to our cell. To turn the cell alive or dead I should find which cell actually get clicked. I implement this by using regular expression to catch current cell index.

After calling play_this_life, we get our closure and we just have to call it over and over to run the game. I use setInterval to do this.

And that’s it.
I omit the Gosper Gun Glider function, but you can always see the full source code from right click ;)

Comments