Conway's Game of Life

Door Cyphax op zondag 16 januari 2011 15:19 - Reacties (6)
Categorie: -, Views: 5.054

Introductie
In 1970 bedacht John Conway een nul-spelerspel. Een spel zonder echte spelers. Hij noemde het spel The Game of Life. Conway's Game of Life is een soort simulatie van een bevolking die een oneindig aantal generaties "leeft". Die bevolking wordt vertegenwoordigd in cellen, zoals je die ziet op een schaak- of dambord. Cellulair
Omdat een spel altijd een verloop moet hebben, maar er geen spelers zijn die dat verloop dicteren, gaat de verloop van de generaties automatisch. Dat maakt van Conway's Game of Life een automaat.

Conway's Game of Life is een cellulaire automaat.

De cellulaire automaat
Een cellulaire automaat is een model dat wordt toegepast in onder meer de wiskunde. Zo'n model bestaat uit een n-dimensionaal (Life heeft 2 dimensies) raster dat is opgebouwd uit cellen. Elke cel heeft een bepaald aantal toestanden (afhankelijk van welke automaat je bekijkt - de cellen in Life hebben 2 toestanden). Het hele model "leeft" doordat de toestand van de cellen steeds verandert volgens de regels van het model. In het model van Conway zijn de cellen altijd dood of levend, en is de staat van elke cel afhankelijk van de buren: de aangrenzende cellen.

Of een cel bij de volgende generatie nog leeft, of gaat leven, wordt bepaald door enkele regels:
  • Een levende cel blijft leven als twee of drie van zijn buren leven (balans).
  • Een dode cel gaat leven als precies drie van zijn buren leven (voortplanting).
  • Een levende cel gaat dood als meer dan drie van zijn buren leven (overpopulatie).
  • Een levende cel gaat dood als minder dan twee van zijn buren leven (onderpopulatie).
Van elke generatie wordt van alle cellen tegelijk de staat van de huidige generatie bepaald. Vervolgens gaat de ene generatie over in de andere en sterven sommige cellen, worden andere "geboren" en blijven andere cellen in leven.

En dit is leuk, omdat...?
Het leuke ervan is dat je het verloop van je eigen populatie kunt volgen. Je ziet elke generatie evolueren, en omdat je er geen invloed op hebt kun je alleen maar toekijken. Met een voldoende groot bord en initiele opstelling weet je niet hoe je bord eruit gaat zien na tientallen, honderden of duizenden generaties, terwijl er pure logica achter zit. Er zijn interessante argumenten en achtergrondinformatie beschikbaar in het Wikipedia-artikel

Maar genoeg theorie, hoe gaan we dit doen? Voordat er computers waren moest dit met de hand. Een Go-bord is hier erg geschikt voor, evenals rasterpapier. Aan de andere kant; de meeste mensen hebben nog meer te doen, en handmatig ben je na 10 generaties op een beetje bord wel moe. En we hebben allemaal een computer die snel genoeg is om een leuke simulatie neer te zetten. Gelukkig is het niet zo vreselijk ingewikkeld om te maken. Dus gaan we de Game of Life implementeren. In Javascript!

De implementatie
We hebben twee klassen nodig voor deze implementatie: een bord (Board) en een cel (Cell). De relatie tussen die twee is eenvoudig: een Board bevat de Cells en de methoden die ervoor zorgen dat elke volgende generatie de juist toestand krijgt, uiteraard gebaseerd op de toestand van dit moment.
Daarnaast moeten we een eenvoudig HTML-documentje hebben en een paar stijlen voor de cellen. Aan het eind van deze post heb je alle code van een werkende Game of Life, met daarin een voldoende groot bord voor een mooie glider.

Laten met dat eenvoudige HTML-documentje beginnen, dan hebben we dat maar vast gehad.

HTML:
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
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
    <head>
        <style type="text/css">
            .cell
            {
                width: 10px;
                height: 10px;
                float: left;
                border: 1px solid black;
            }
            .alive
            {
                background-color: black;
            }
            .dead
            {
                background-color: white;
            }

        </style>
        <script type="text/javascript">

        </script>
    </head>
    <body onload="init();">
        <div id="life_container" style="width: 1px"/>
    </body>
</html>



De cel
De cel bevat de logica die nodig is om de toestand voor de volgende generatie uit te kunnen rekenen. In principe hoef je voor een cel alleen te weten welke plek 'ie op het bord inneemt (x- en y-coordinaten), wat de toestand is voor de huidige generatie, en hoeveel levende buurcellen er zijn. In de update()-method wordt de nieuwe toestand bepaald aan de hand van het aantal levende cellen. Het is eigenlijk een deel van de implementatie van de regels die Conway bedacht.


JavaScript:
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
38
39
40
41
42
43
44
45
46
47
function Cell(x, y)
    {
        this.x = x;
        this.y = y;
        this.state = 0; // 0 == dead, 1 == alive
        this.livingneighbours = 0;
        this.htmlelement = this.create();
    }

    Cell.prototype.create = function()
    {
        var newcell = document.createElement("div");
        newcell.setAttribute("id", this.y + "_" + this.x);
        newcell.setAttribute("class", "cell dead");
        return newcell;
    }

    Cell.prototype.raise = function()
    {
        this.state = 1;
        this.htmlelement.setAttribute("class", "cell alive");
    }

    Cell.prototype.kill = function()
    {
        this.state = 0;
        this.htmlelement.setAttribute("class", "cell dead");
    }

    Cell.prototype.update = function()
    {
        if (this.state === 0)
        {// De cel is dood
            if (this.livingneighbours === 3)
            {// Een dode cel met precies 3 levende buurcellen komt tot leven in de volgende generatie
                this.raise();
            }
        }
        else
        {// De cel leeft
            if (this.livingneighbours > 3 || this.livingneighbours < 2)
            {// Er is sprake van over- of onderpopulatie, waardoor de cel sterft in de volgende generatie
                this.kill();
            }
        }
        this.livingneighbours = 0;
    }



Het bord
In deze klasse worden de gegevens opgeslagen die voor het bord relevant zijn. Uiteraard de cellen die het bord bewonen, maar daarnaast de afmetingen en de leeftijd van elke generatie (in milliseconden).
Verder heeft deze klasse twee methoden die ervoor zorgen dat alle cellen worden geupdate. Met twee loops door alle cellen wordt eerst de toestand van het bord (eigenlijk van de cellen) voor de volgende generatie berekend (Board.tick()), waarna de tweede loop alle cellen update (Board.update()). De logica van de regels van Conway zit echter in Board.tick() verwerkt.

Board.tick()
Met de loop in deze methode wordt elke cel aangedaan. Van elke cel wordt elke buurcel (maximaal 8 in ons geval) bekeken en afhankelijk van de staat van die buurcellen wordt het aantal levende cellen van de huidige cel opgeslagen:

JavaScript:
1
2
3
4
5
6
7
8
this.cells[x][y].livingneighbours += x > 0 && y > 0 ? this.cells[x-1][y-1].state : 0;
    this.cells[x][y].livingneighbours += x > 0 ? this.cells[x-1][y].state : 0;
    this.cells[x][y].livingneighbours += x > 0 && y < this.height-1 ? this.cells[x-1][y+1].state : 0;
    this.cells[x][y].livingneighbours += y > 0 ? this.cells[x][y-1].state : 0;
    this.cells[x][y].livingneighbours += y < this.width-1 ? this.cells[x][y+1].state : 0;
    this.cells[x][y].livingneighbours += x < this.width-1 && y > 0 ? this.cells[x+1][y-1].state : 0;
    this.cells[x][y].livingneighbours += x < this.width-1 ? this.cells[x+1][y].state : 0;
    this.cells[x][y].livingneighbours += x < this.width-1 && y < this.height-1 ? this.cells[x+1][y+1].state : 0;



Board.update() en Cell.update()
Nadat het aantal levende cellen van elke cel is bepaald wordt er nog een keer door alle cellen geloopt. We weten nu van elke cel hoeveel levende buren er zijn. Elke cel had al ook een huidige toestand. Die informatie is genoeg om per cel de nieuwe generatie in te luiden, met misschien wel een nieuwe toestand:

JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (this.state === 0)
    {// De cel is dood
        if (this.livingneighbours === 3)
        {// Een dode cel met precies 3 levende buurcellen komt tot leven in de volgende generatie
            this.raise();
        }
    }
    else
    {// De cel leeft
        if (this.livingneighbours > 3 || this.livingneighbours < 2)
        {// Er is sprake van over- of onderpopulatie, waardoor de cel sterft in de volgende generatie
            this.kill();
        }
    }



De hele Board-klasse:

JavaScript:
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
function Board (width, height, update_frequency)
    {
        this.width = width;
        this.height = height;
        this.cells = new Array(width);
        this.update_frequency = update_frequency;
        var x = width - 1, y;
        while(x >= 0)
        {
            y = height - 1;
            this.cells[x] = new Array(this.width);
            while (y >= 0)
            {
                cell = new Cell(x, y);
                this.cells[x][y] = cell;
                y--;
            }
            x--;
        }
    }

    Board.prototype.start = function()
    {
        this.draw();
        this.tick();
    }

    Board.prototype.draw = function()
    {
        var x, y = 0;
        var life_container = document.getElementById("life_container");
        life_container.setAttribute("style", "width: " + 12 * this.width + "px");
        while(y < this.height)
        {
            x = 0;
            while (x < this.width)
            {
                life_container.appendChild(this.cells[x][y].htmlelement);
                x++;
            }
            y++;
        }
    }

    Board.prototype.tick = function()
    {
        var x, y = this.height - 1;
        while (y >= 0)
        {
            x = this.width - 1;
            while (x >= 0)
            {
                this.cells[x][y].livingneighbours += x > 0 && y > 0 ? this.cells[x-1][y-1].state : 0;
                this.cells[x][y].livingneighbours += x > 0 ? this.cells[x-1][y].state : 0;
                this.cells[x][y].livingneighbours += x > 0 && y < this.height-1 ? this.cells[x-1][y+1].state : 0;
                this.cells[x][y].livingneighbours += y > 0 ? this.cells[x][y-1].state : 0;
                this.cells[x][y].livingneighbours += y < this.width-1 ? this.cells[x][y+1].state : 0;
                this.cells[x][y].livingneighbours += x < this.width-1 && y > 0 ? this.cells[x+1][y-1].state : 0;
                this.cells[x][y].livingneighbours += x < this.width-1 ? this.cells[x+1][y].state : 0;
                this.cells[x][y].livingneighbours += x < this.width-1 && y < this.height-1 ? this.cells[x+1][y+1].state : 0;
                x--;
            }
            y--;
        }
        this.update();
        var self = this;
        var lifecycle = setTimeout(function() { self.tick() }, this.update_frequency);
    }

    Board.prototype.update = function()
    {
        var x = y = 0;
        while (y < this.height)
        {
            x = 0;
            while (x < this.width)
            {
                this.cells[x][y].update();
                x++;
            }
            y++;
        }
    }



Initialisatie
Alle logica is er, de laatste stap is een nieuw Board opzetten en daarin een paar cellen plaatsen: dat wordt onze initiele toestand, en het is die toestand die uit zal groeien tot... wie zal het zeggen! Ik had een glider beloofd, dus daar geldt voor dat we het in dit geval eigenlijk al wel weten, het is immers een bekend patroon:

JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function init()
    {
        var board_width = 60;
        var board_height = 60;
        var update_frequency = 500; // milliseconden
        
        var life = new Board(board_width, board_height, update_frequency);

        /* Cellen voor de glider tot leven wekken */
        life.cells[2][1].raise();
        life.cells[3][2].raise();
        life.cells[1][3].raise();
        life.cells[2][3].raise();
        life.cells[3][3].raise();
        /* Start de simulatie */
        life.start();
    }


Het resultaat is dan deze glider (maar met een frequency van 100ms).

Tot slot
De bovenstaande implementatie is toegespitst op een werkende Game of Life, in Firefox 3.6 en Chrome. Het werkt in IE8 ook, maar lijkt erg traag te zijn.

Als kleine bonus een alternatieve begintoestand die behoorlijk lang doorevolueert, maar niet volgens zo'n vast patroon als de glider:

JavaScript:
1
2
3
4
5
life.cells[40][40].raise();
    life.cells[41][40].raise();
    life.cells[39][41].raise();
    life.cells[40][41].raise();
    life.cells[40][42].raise();


Je moet de vijf regels voorde glider in init() hiervoor even vervangen door bovenstaande regels. (Of hier voor het directe resultaat met ook weer een frequency van 100ms)

Meer info
Wikipedia (EN)
Wikipedia (NL) (kort artikel)
Java-applet van de Game of Life

Updates
* Voorbeelden live gezet en linkjes toegevoegd voor de nieuwsgierigen!
* Foutje uit de regel hierboven gehaald, met dank aan afraca. :+