Programming

Game of Life

Kemaren waktu nyari info tentang “map”nya Java di stackoverflow.com, di samping kanan websitenya ada bagian “Hot Network Questions” yg isinya adalah pertanyaan2 dari berbagai bidang (dan dari berbagai website), ada yg dari superuser.com, math.stackexchange.com, codegolf.stackexchange.com, english.stackexchange.com, codereview.stackexchange.com, dll (detailnya liat langsung aja di link ‘Hot Network Questions’ di atas).

Nah, dari code review, ada yg nanya tentang Conway’s Game of Life. Penasaran, akhirnya malah bikin sendiri deh, pake javascript aja yg gampang. Informasinya saya dapet dari wikipedia. Dunia dari game of life adalah sel kotak yang hidup dalam grid dua dimensi yang tak berhingga luasnya. Tiap sel dari grid cuma punya salah satu status, yaitu hidup atau mati. Tiap kali perubahan memiliki hukum seperti ini:

  1. Sel hidup yang punya tetangga hidup kurang dari 2 akan menjadi mati.
  2. Sel hidup yang punya tetangga hidup 2 atau 3 tetap akan hidup.
  3. Sel hidup yang punya tetangga hidup lebih dari 3 akan mati.
  4. Sel yang mati tapi punya 3 tetangga hidup akan menjadi sel hidup.

Langsung aja, ini source-code nya:

[code lang=”HTML” title=”Source-code: conways.html”]
<html>
<head>
<title>Conway’s Game of Life</title>
<style type="text/css">
table.cgol { border-collapse:collapse; border: 1px solid #333; border-spacing: 0px; }
table.cgol td { text-align:center; width:10px; height:10px; border: 1px solid #333; overflow: hidden; }
</style>
<script type="text/javascript" src="conways.js"></script>
<script type="text/javascript">
var gol;
var lop;
function $(id) { return document.getElementById(id); }
function getRandomInt(min, max) { return Math.floor(Math.random()*(max-min+1)+min); }
function isOdd(num) { return (num % 2) == 1; }

function draw() { $(‘output’).innerHTML = gol.draw(); $(‘stp’).innerHTML = gol.steps; }
function doCreate() {
if (typeof lop != "undefined") clearInterval(lop);
clearInterval(lop);
gol = new CGOL($(‘we’).value,$(‘ha’).value,"gol");
draw();
}
function doRandom() { gol.initRandom(); draw(); }
function doStep() { gol.step(); draw(); }
function doStepClick() { if (typeof lop != "undefined") clearInterval(lop); clearInterval(lop); doStep(); }
function doLoop() { if (typeof lop != "undefined") clearInterval(lop); lop = setInterval(doStep, 150); }
</script>
</head>
<body>
<h2>Conway’s Game of Life</h2>
<div>
Width <input type="text" id="we" value="50">
Height <input type="text" id="ha" value="50">
<input type="button" value="Create" onclick="doCreate()">
<input type="button" value="Random" onclick="doRandom()">
<input type="button" value="Step" onclick="doStepClick()">
<input type="button" value="Auto" onclick="doLoop()">
</div>
<br>
Steps : <span id="stp"></span>
<br>
<div id="output"></div>
</body>
</html>
[/code]

[code lang=”Javascript” title=”Source-code: conways.js”]
function CGOL (wid, hig, nam) {
this.width = wid;
this.height = hig;
this.cells = [];
this.varname = nam; // little hack for board designer
this.steps = 0;

this.init();
}

CGOL.prototype.alive = function(x,y) { return this.cells[(this.width*y)+x]; }
CGOL.prototype.toggle = function(x,y) { this.cells[(this.width*y)+x] = !this.alive(x,y); }

CGOL.prototype.countLiveNeighboursSimple = function(x,y) {
/*
* The simplest strategy is simply to assume that every cell outside the array
* is dead. This is easy to program, but leads to inaccurate results when the
* active area crosses the boundary.
*/
var live = 0;
var atas = false;
var bawa = false;
var kiri = false;
var kana = false;
if (x>0) kiri = true;
if (x<this.width-1) kana = true;
if (y>0) atas = true;
if (y<this.height-1) bawa = true;

if (kiri) {
if (this.alive(x-1,y)) live++;
if (atas) { if (this.alive(x-1,y-1)) live++; }
if (bawa) { if (this.alive(x-1,y+1)) live++; }
}
if (kana) {
if (this.alive(x+1,y)) live++;
if (atas) { if (this.alive(x+1,y-1)) live++; }
if (bawa) { if (this.alive(x+1,y+1)) live++; }
}
if (atas) { if (this.alive(x,y-1)) live++; }
if (bawa) { if (this.alive(x,y+1)) live++; }
return live;
}

CGOL.prototype.countLiveNeighbours = function(x,y) {
/*
* A more sophisticated trick is to consider the left and right edges of the
* field to be stitched together, and the top and bottom edges also, yielding
* a toroidal array. The result is that active areas that move across a field
* edge reappear at the opposite edge. Inaccuracy can still result if the
* pattern grows too large, but at least there are no pathological edge
* effects.
*/
var live = 0;
var atas = false;
var bawa = false;
var kiri = false;
var kana = false;
if (x>0) kiri = true;
if (x<this.width-1) kana = true;
if (y>0) atas = true;
if (y<this.height-1) bawa = true;

if (kiri) {
if (this.alive(x-1,y)) live++;
if (atas) { if (this.alive(x-1,y-1)) live++; } else { if (this.alive(x-1,this.height-1)) live++; }
if (bawa) { if (this.alive(x-1,y+1)) live++; } else { if (this.alive(x-1,0)) live++; }
} else {
if (this.alive(this.width-1,y)) live++;
if (atas) { if (this.alive(this.width-1,y-1)) live++; } else { if (this.alive(this.width-1,this.height-1)) live++; }
if (bawa) { if (this.alive(this.width-1,y+1)) live++; } else { if (this.alive(this.width-1,0)) live++; }
}
if (kana) {
if (this.alive(x+1,y)) live++;
if (atas) { if (this.alive(x+1,y-1)) live++; } else { if (this.alive(x+1,this.height-1)) live++; }
if (bawa) { if (this.alive(x+1,y+1)) live++; } else { if (this.alive(x+1,0)) live++; }
} else {
if (this.alive(0,y)) live++;
if (atas) { if (this.alive(0,y-1)) live++; } else { if (this.alive(0,this.height-1)) live++; }
if (bawa) { if (this.alive(0,y+1)) live++; } else { if (this.alive(0,0)) live++; }
}
if (atas) { if (this.alive(x,y-1)) live++; } else { if (this.alive(x,this.height-1)) live++; }
if (bawa) { if (this.alive(x,y+1)) live++; } else { if (this.alive(x,0)) live++; }
return live;
}

CGOL.prototype.step = function() {
var newcell = [];
for (var y=0; y<this.height; y++) {
for (var x=0; x<this.width; x++) {
var t = this.countLiveNeighbours(x,y);
newcell.push(this.alive(x,y));
var i = newcell.length-1;
//Any live cell with fewer than two live neighbours dies, as if caused by under-population.
if (this.alive(x,y) && (t<2)) newcell[i]=false;
//Any live cell with two or three live neighbours lives on to the next generation.
if (this.alive(x,y) && t>=2 && t<=3) newcell[i]=true;
//Any live cell with more than three live neighbours dies, as if by overcrowding.
if (t>3) newcell[i]=false;
//Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
if (!this.alive(x,y) && t==3) newcell[i]=true;
}
}
this.cells = [];
for (var z=0; z<newcell.length; z++) {
this.cells.push(newcell[z]);
}
this.steps++;
}

CGOL.prototype.init = function() {
this.cells = [];
for (var x=0; x<this.width*this.height; x++) {
this.cells.push(false);
}
this.steps = 0;
}

CGOL.prototype.initRandom = function() {
var min = 0;
var max = 9;
this.cells = [];
for (var x=0; x<this.width*this.height; x++) {
var c = (((Math.floor(Math.random() * (max – min + 1) + min)) % 4) == 1);
this.cells.push(c);
}
this.steps = 0;
}

CGOL.prototype.draw = function() {
var tbl = "<table class=’cgol’>";
for (var y=0; y<this.height; y++) {
tbl += "<tr>";
for (var x=0; x<this.width; x++) {
var warna = "#000";
if (this.alive(x,y)) warna = "#0f0";
tbl += "<td style=’background-color:" + warna + "; ‘ "+
"onclick=’"+this.varname+".toggle("+x+","+y+"); draw();’></td>";
}
tbl += "</tr>";
}
tbl += "</table>";
return tbl;
}
[/code]

Seperti keterangan pada wikipedia, ada metode paling simple untuk menghitung jumlah “tetangga hidup” yaitu dengan menganggap sel diluar array adalah sel mati. Metode ini dianggap sangat tidak akurat. Di conways.js, saya sertakan metode ini dengan nama “countLiveNeighboursSimple”.

Lalu ada metode lainnya yaitu yang menganggap bahwa bagian kiri dan kanan grid adalah menyatu, begitu pula bagian atas dan bawah. Kalau di visualisasikan, akan terbentuk torodial. Ini yang jadi default cara menghitung “tetangga hidup” dalam conways.js.