Conway’s Game of Life 👾

Në një botë diskrete, të pafundme, zhvillohet një jetë në qelizat katrore të sistemit koordinativ. Qeliza është gjallë kur është e ndezur dhe e vdekur kur shuhet. Secila qelizë është në luftë konstante për mbijetesë me 8 qelizat e tjera fqinje rreth e rreth vetes.

Në fillim, qelizat e gjalla vendosen në çfarëdo konfigurimi dhe pastaj, në çdo hap diskret të kohës, jeta zhvillohet sipas këtyre katër rregullave:

1. Një qelizë vdes nëse ka 0 ose 1 fqinj (nga vetmia)
2. Një qelizë vdes nëse ka më shumë se 3 fqinj (nga mbipopullimi)
3. Një qelizë jeton nëse ka 2 ose 3 fqinj
4. Një qelizë e vdekur ngjallet nëse ka saktësisht 3 fqinj

John Conway i sajoi këto rregulla dhe studioi se si evulon jeta në një botë kaq të thjeshtë dhe, siç do të shohim, shumë interesante dhe të paparashikueshme.

Në këtë artikull do diskutojmë se si implementohet ky simulim me JavaScript. Nëse doni të shihni kodin dhe të mos e lexoni artikullin gjeni kodin në GitHub, ndërsa nëse doni të provoni rezultatin final klikoni këtu Game Of Life.

Rrjeti i pafundëm

Hapi i parë në zhvillimin e simulimit është të krijojmë “botën”. Në rastin tonë bota është një rrjet (grid) dydimensional i pafundëm. Do e ndërtojmë atë hap pas hapi duke përdorur Canvas API. Për fillestarët, në HTML mund të vendosim një element canvas në të cilin mund të vizatojmë viza e harqe me JavaScript.

//HTML
<canvas width="300" height="300" id="game"></canvas>

//JS
let canvas = document.getElementById("game");
let ctx = canvas.getContext("2d");

//vizatojmë
ctx.lineTo(10, 20);
ctx.fillRect(0, 0, 100, 200);

Në rastin tonë, ne do krijojmë një variabël për madhësinë e katrorit dhe do vizatojmë aq viza sa për të mbuluar gjerësinë dhe gjatësinë e kanvasit. Shikojmë se si vizatohen vizat horizontale:

let i = 0;
while (i <= height){
    ctx.beginPath();
    ctx.moveTo(0, i);
    ctx.lineTo(width, i);
    ctx.stroke();
    i += gridSize;
}

Në çdo hap lëvizim një njësi më poshtë dhe vizatojmë vijën horizontale derisa të arrijmë fundin. Ngjashëm do vizatohen edhe vizat vertikale. Normalisht, mund ti japim pak stil kontekstit paraprakisht:

ctx.strokeStyle = 'rgb(200 200 200 / 10%)';
ctx.shadowColor = '#66FF66A0';
ctx.fillStyle = '#66FF66A0';
ctx.shadowBlur = 30;

Ky rrjet nuk është i pafundëm, dhe normalisht që nuk do krijojmë asgjë të pafundme. Qëllimi është që përdoruesit t’i japim iluzionin e të pafundmes. Rrjeti jonë do mund të zhvendoset në drejtimin X dhe drejtimin Y. Madhësinë e zhvendosjes do e llogarisim sipas lëvizjes së miut (ose gishtit) në ekran:

let dragging = false;
let prevPosition = {};

//në fillim të 'dragging' llogarisim koordinatat ku ka filluar ndërveprimi
canvas.onmousedown = (e) => {
    const rect = canvas.getBoundingClientRect();

    const x = e.clientX - rect.left;
    const y = e.clientY - rect.top;

    prevPosition = {x: x, y: y};
    dragging = true;
    draw();
}

//sa herë që lëviz miu, llogaritim distancën nga pozicioni paraprak, 
//dhe zhvendosim rrjetin
canvas.onmousemove = (e) => {
    if (!dragging || !prevPosition)
        return;

    const rect = canvas.getBoundingClientRect();

    const currentX = e.clientX - rect.left;
    const currentY = e.clientY - rect.top;

    translate(currentX - prevPosition.x, currentY - prevPosition.y);
    draw();
    prevPosition = {x: currentX, y: currentY};
}

//cleanup
canvas.onmouseup = (e) => {
    dragging = false;
    prevPosition = {};
    draw();
}

Ndërveprimi është në rregull, mirëpo si ndodh ‘zhvendosja’. Zgjidhja, në fakt, është shumë e thjeshtë:

//tani 'i' nuk fillon nga 0 por varet nga zhvendosja
let i = Math.floor(translateY % gridSize);
while (i <= height){
    ctx.beginPath();
    ctx.moveTo(0, i);
    ctx.lineTo(width, i);
    ctx.stroke();
    i += gridSize;
}

Qelizat

Tani do të vizatojmë qelizat në rrjetin tonë. Hapi i parë është të zgjedhim një strukturë të të dhënave ku do ruajmë qelizat. Mendimi i parë fillestar është të përdorim një listë dy-dimensionale me booleans, mirëpo për shkak të lojës së pafundme dhe numrit të madh të qelizave të vdekura, kjo nuk i’a vlen në rastin tonë.

Do të përdorim një bashkësi ku do ruajmë vetëm koordinatat e qelizave të gjalla si strings. Për shembull, nëse qeliza (3, 7) është e gjallë, do e ruajmë si “[3, 7]”. Në JavaScript, bashkësia krijohet kështu:

let entries = new Set();

Ne duhet të lejojmë përdoruesin që të konfigurojë qelizat para se të fillojë loja, pra cilindo katror që ai e prek e ndezim ose e shuajmë. Por si ta dijmë cili katror është shtypur? Me pak matematikë:

canvas.onclick = (e) => {
    const rect = canvas.getBoundingClientRect();

    const x = e.clientX - rect.left;
    const y = e.clientY - rect.top;
    
    //llogaritja e koordinatave të katrorit
    let squareX = Math.floor((-translateX + x) / gridSize);
    let squareY = Math.floor((-translateY + y) / gridSize);
    
    //krijimi i string që reprezenton koordinatat
    let key = JSON.stringify([squareX, squareY]);
    
    //nëse nuk është prezent e shtojmë, përndryshe e largojmë
    if (entries.has(key)){
        entries.delete(key);
    }
    else{
        entries.add(key);
    }

    draw();
}

Bukur, tani kemi gjithçka në vend që t’i vizatojmë qelizat. Edhe vizatimi i tyre don pak matematikë. Së pari le të llogarisim se cilat qeliza janë të dukshme në ekran për momentin.

  let startSqX = Math.floor(-translateX / gridSize);
  let endSqX = startSqX + Math.floor(width / gridSize) + 1;

  let startSqY = Math.floor(-translateY / gridSize);
  let endSqY = startSqY + Math.floor(height / gridSize) + 1;

Qasja e parë është të iterojmë nëpër të gjithë qelizat e dukshme, të shohim se a janë të ndezura, dhe t’i vizatojmë në ekran, kësi soji:

//Qasja 1
for (let i = startSqX; i <= endSqX; i++){
    for (let j = startSqY; j <= endSqY; j++){
        if (entries.has(JSON.stringify([i, j]))){
            let startX = Math.floor(translateX + (gridSize * i));
            let startY = Math.floor(translateY + (gridSize * j));

            ctx.fillRect(startX, startY, gridSize, gridSize);
        }
    }
}

Por çka nëse përdoruesi bën zoom-out (të cilën se kemi implementuar ende) dhe në ekran duken me qindra qeliza? Ky kod nuk do ishte shumë performant. Në atë rast mund të iterojmë nëpër të gjithë qelizat e gjalla, të shohim a duken në ekran, dhe ti vizatojmë:

//Qasja 2
for (let entry of entries){
    let [x, y] = JSON.parse(entry);

    if (x >= startSqX && x <= endSqX && y >= startSqY && y <= endSqY){
        let startX = Math.floor(translateX + (gridSize * x));
        let startY = Math.floor(translateY + (gridSize * y));

        this.ctx.fillRect(startX, startY, gridSize, gridSize);
    }
}

Që të përfitojmë nga të dyja këto qasje, mund të bëjmë një logjikë ku shohim se sa qeliza janë në ekran dhe të vendosim në bazë të asaj:

let numCells = (endSqX - startSqX) * (endSqY - startSqY);

if (numCells < entries.size)
    //Qasja 1
else
    //Qasja 2

Logjika e Game Of Life

Më në fund, pas rregullimit të gjithçkaje, erdhëm tek logjika e Game of Life. Këtu do implementojmë rregullat e lojës. Ideja është të krijojmë një interval i cili e avancon lojën për një hap çdo x sekonda:

setInterval(animationStep, 250);

function animationStep(){
  //një hap i lojës
}

Në vend se të shikojmë të gjitha qelizat, të gjalla dhe të vdekura, do iterojmë nëpër qelizat e gjalla dhe do analizojmë fqinjët e tyre. Do mbajmë në mend qelizat që duhet të vdesin por edhe numrin e fqinjëve të qelizave të vdekura. Logjika kryesore është kjo:

let deadNeighbors = new Map();
let markedForDeletion = new Set();

for (let entry of entries){
    let [x, y] = JSON.parse(entry);
    
    let numOfNeighbors = 0;
    
    //iterojmë nëpër 8 fqinjët
    for (let i = x - 1; i <= x + 1; i++){
        for (let j = y - 1; j <= y + 1; j++){
            if (i == x && j == y)
                continue;

            let key = JSON.stringify([i, j]);
            
            if (entries.has(key)){
                //nëse fqinji është i gjallë, e rrisim variablën
                numOfNeighbors++;
            }
            else{
                //nëse është i vdekur, e rrisim për 1 numrin e
                //fqinjëve të gjallë të kësaj qelize
                if (deadNeighbors.has(key)){
                    deadNeighbors.set(key, deadNeighbors.get(key) + 1);
                }
                else{
                    deadNeighbors.set(key, 1);
                }
            }

        }
    }
    //nënpopullimi ose mbipopullimi
    if (numOfNeighbors < 2 || numOfNeighbors > 3){
        markedForDeletion.add(entry);
    }
}

//ringjallja
for (let [neigh, numNeighbors] of deadNeighbors){
    if (numNeighbors === 3){
        entries.add(neigh);
    }
}
//largojmë qelizat që duhet të vdesin
entries = entries.difference(markedForDeletion);

Me kaq përfundon implementimi, normalisht shumë i thjeshtëzuar, me JavaScript. Në GitHub mund të gjeni kodin e plotë me shumë funksionalitete të shtuara.

Demonstrimi

Game Of Life është studiuar shumë dhe ka shumë teori rreth saj. Çka mund të jetë interesant për ju është të se në lojë ka 3 lloje të ‘jetëve’. E para është jeta e qetë, e cila nuk ndryshon fare nga hapi në hap:

E dyta, më e gjallë, është jeta periodike e palëvizshme (oscillators). Këto lloje të jetës kalojnë nëpër disa gjendje dhe kthehen në gjendjen fillestare vazhdimisht:

Tipi i fundit dhe më interesante janë anijet kozmike (spaceships) të cilat janë gjithashtu periodike por lëvizin nëpër botë:

Konkluzion

Gjatë zhvillimit të kësaj loje në një pasdite të së dieles, mësova diçka për JavaScript, për Cavas, për Game Of Life, e pak edhe për jetën. Shpresoj që keni mësuar diçka edhe ju. Nëse ju pëlqen ky format i artikujve, dhe ju pëlqen JavaScript, mund të lexoni edhe ndonjë artikull tjetër si Stacks and the Undo feature.