---

Hra života vyzerá jednoducho, no vykresľovať milióny buniek v reálnom čase priamo v prehliadači už jednoduché nie je. Tento článok vychádza z mojej seminárnej prezentácie „Efficient rendering in HTML Canvas for cellular automaton simulations“ a prechádza viaceré CPU a GPU techniky, pričom porovnáva ich kompromisy a výkon.

TL;DR: Kľúčom k plynulým simuláciám na veľkých mriežkach je oddeliť výpočet od vykresľovania, vyhýbať sa zbytočnému kresleniu a presúvať prácu do viacerých vlákien alebo na GPU.

---

Motivácia a problém

Môj diplomový projekt Fuzzy Life rozširuje Conwayovu Hru života o fuzzy hodnoty buniek, čím sa okamžite zvyšujú náklady na výpočet aj vykresľovanie. Pri simulácii mriežok so stovkami tisíc až miliónmi buniek už úzkym miestom nie sú iba samotné pravidlá, ale aj to, ako často a ako efektívne sa celý svet vykresľuje.

Typické problémové miesta:

• Výpočet: Aktualizácia susedov a aplikovanie pravidiel pre každú bunku v každom kroku.
• Vykresľovanie: Počet volaní grafického API, prenosy bufferov, prekresľovanie a kreslenie mimo viditeľnej oblasti.
• Interakcia: Plynulé posúvanie a približovanie, displeje s vysokým DPI a veľké zobrazované oblasti.

Cieľom je nájsť architektúry vykresľovania, ktoré:

• Oddelia simulačný krok od samotného kreslenia.
• Aktualizujú iba viditeľné alebo zmenené oblasti.
• Škálujú od základného Canvas 2D až po GPU WebGL2.

---

Základy Canvas 2D

HTML <canvas> poskytuje bitmapovú plochu, do ktorej môže JavaScript kresliť pomocou 2D vykresľovacieho kontextu.

• Každý canvas má 2D kontext s funkciami ako clearRect, fillRect, drawImage, stroke alebo fillText.
• Canvas funguje v režime immediate mode: po nakreslení objektu si API neuchováva jeho štruktúru; ak sa stav zmení, všetko treba nakresliť znova.
• Canvas 2D sa často používa na vizualizácie, hry, simulácie a spracovanie obrazu, kde je užitočný priamy prístup k pixelom.

Pre Hru života to znamená, že naivný prístup spočíva v prejdení všetkých buniek a volaní fillRect pre každú živú bunku v každom snímku.

---

Demo prostredie a server

Všetky demá sú malé HTML súbory, ktoré zdieľajú spoločné jadro v JavaScripte a líšia sa tým, ako počítajú a vykresľujú jednotlivé snímky.

Demá sú servované cez minimálny Express server s potrebnými hlavičkami COOP/COEP:

// server.js
app.use((req, res, next) => {
res.setHeader('Cross-Origin-Opener-Policy', 'same-origin');
res.setHeader('Cross-Origin-Embedder-Policy', 'require-corp');
next();
});

app.use(express.static(__dirname));

app.get('/', (req, res) => {
res.sendFile('index1-full-redrawn.html', { root: __dirname });
});

Spustenie:

npm init -y
npm i express
node server.js

# open http://localhost:8080/

Dostupné demo stránky:

• index1-full-redrawn.html – základná verzia s úplným prekreslením.
• index2-dirty-rectangles.html – dirty rectangles.
• index3-vis-region-rendering.html – vykresľovanie viditeľnej oblasti.
• index4-static-web-workers.html – jeden web worker.
• index5-static-web-workers-n.html – viac workerov s kopírovaním.
• index6-sharedarray-multiworker.html – viac workerov so SharedArrayBuffer.
• index7-static-image-data.html – push vykresľovanie cez ImageData.
• index8-sharedarray-multiworker-imagedata.html – hybrid SAB + ImageData.
• index9-gpu-webgl.html – GPU verzia cez WebGL2.

---

CPU vykresľovanie: tri základné stratégie

Úplné prekreslenie každého snímku

Najjednoduchší model je prekresliť celý svet v každom kroku bez ohľadu na kameru alebo viditeľnosť.

Myšlienka

• Pre každý simulačný krok:
  • Vyčistiť pozadie.
  • Prejsť všetky bunky ROWS * COLS.
  • Pre každú živú bunku nakresliť obdĺžnik veľkosti 1×1 na jej súradniciach.

function drawAll(ctx) {
    ctx.fillStyle = '#fff';
    ctx.fillRect(camX, camY, visW, visH);

    ctx.fillStyle = '#000';
    // Full redraw of every cell
    for (let y = 0; y < ROWS; y++) {
        const off = y * COLS;
        for (let x = 0; x < COLS; x++) {
            if (filled[off + x]) {
                ctx.fillRect(x, y, 1, 1);
            }
        }
    }
}

Výhody

• Konceptuálne jednoduchý a spoľahlivý základ na meranie výkonu.
• Dobrý záťažový test pre CPU a Canvas API.

Nevýhody

• Mimoriadne veľa volaní fillRect, vrátane buniek mimo obrazovky.
• Náklady rastú s veľkosťou sveta, nie s veľkosťou viewportu, čo pri veľkých mriežkach výrazne znižuje výkon (v testoch približne 100–300 ms na krok).

---

Dirty rectangles

Technika dirty rectangles sleduje bunky, ktoré sa medzi snímkami zmenili, a prekresľuje iba tieto bunky nad predchádzajúcim snímkom.

Myšlienka

• Udržiavať dve polia: filled (aktuálny stav) a next (ďalšia generácia).
• Po výpočte ďalšieho stavu porovnať obe polia.
• Iba pre indexy, kde filled[i] !== next[i]:
  • Zvoliť správnu farbu (živá/mŕtva bunka).
  • Nakresliť obdĺžnik veľkosti 1×1 na danej bunke.

function drawDirtyGlobal() {
    for (let y = 0; y < ROWS; y++) {
        const off = y * COLS;
        for (let x = 0; x < COLS; x++) {
            const i = off + x;
            if (filled[i] !== next[i]) {
                ctx.fillStyle = next[i] ? '#000' : '#fff';
                ctx.fillRect(x, y, 1, 1);
            }
        }
    }
}

Charakteristika

• Prvý snímok stále vyžaduje úplné prekreslenie; nasledujúce snímky aktualizujú iba zmenené bunky.
• Čas jedného snímku sa stáva úmerný počtu zmenených buniek, nie celkovému počtu buniek.
• Práca je konzistentná a nezávislá od veľkosti viewportu, ale aktualizácie stále prebiehajú aj v oblastiach mimo obrazovky.

---

Vykresľovanie viditeľnej oblasti

Vykresľovanie viditeľnej oblasti oreže svet na časť, ktorú vidí kamera, a kreslí iba aktuálne viditeľnú časť.

Myšlienka

• Vypočítať obdĺžnik v súradniciach sveta, ktorý zodpovedá viewportu na základe pozície kamery a priblíženia.
• Orezať tento obdĺžnik podľa hraníc sveta.
• Prechádzať iba bunky vnútri tejto oblasti a kresliť živé bunky.

const W = canvas.width,
      H = canvas.height;
const left = camX,
      top = camY;
const right = camX + W * S;
const bottom = camY + H * S;

const cs = Math.max(0, Math.floor(left / CELL));
const ce = Math.min(COLS - 1, Math.ceil(right / CELL));
const rs = Math.max(0, Math.floor(top / CELL));
const re = Math.min(ROWS - 1, Math.ceil(bottom / CELL));

ctx.save();
ctx.scale(S, S);
ctx.translate(-camX, -camY);

ctx.fillStyle = '#fff';
ctx.fillRect(left, top, right - left, bottom - top);

ctx.fillStyle = '#000';
for (let y = rs; y <= re; y++) {
    const off = y * COLS;
    for (let x = cs; x <= ce; x++) {
        if (filled[off + x]) {
            ctx.fillRect(x, y, 1, 1);
        }
    }
}
ctx.restore();

Prečo je to dôležité

• Znižuje prekresľovanie a prístup do pamäte tým, že preskakuje bunky mimo viewportu.
• Najviac pomáha pri priblížení, keď viewport pokrýva iba malú časť sveta.
• Je základným stavebným prvkom ďalších optimalizácií (ImageData, SAB, GPU), ktoré sa opierajú o presne definovanú viditeľnú oblasť.

---

Paralelizácia na CPU

Jeden Web Worker

Aktualizácie susedov v Hre života sú lokálne a paralelizovateľné, preto presun simulačného kroku do Web Workera udrží hlavné UI vlákno responzívne.

Architektúra

Hlavné vlákno:

const worker = new Worker('worker.js');
worker.postMessage({
    init: true,
    COLS,
    ROWS
});

worker.onmessage = (e) => {
    const filled = new Uint8Array(e.data.buffer); // received world state
    draw(filled); // UI thread only draws
};

Worker:

onmessage = (e) => {
    if (e.data.init) {
        initWorld(e.data.COLS, e.data.ROWS);
        return;
    }

    // Compute next generation
    for (let y = 0; y < ROWS; y++) {
        for (let x = 0; x < COLS; x++) {
            const i = y * COLS + x;
            next[i] = rule(filled, x, y);
        }
    }

    // Swap buffers and transfer
    [filled, next] = [next, filled];
    postMessage({
        buffer: filled.buffer
    }, [filled.buffer]);
};

Výhody

• Simulácia pokračuje aj vtedy, keď UI dočasne zaťaží hlavné vlákno; posúvanie a približovanie pôsobia plynulo.
• Prenos ArrayBuffer ako transferable objektu zabraňuje dodatočným kópiám pri odosielaní.

Nevýhody

• Pri mriežke 2000×2000 trvá jeden krok približne 400 ms, takže úzkym miestom sa stáva samotný výpočet vo workeri.
• Plne sa využíva iba jedno CPU jadro.

---

Viac workerov s kopírovaním

Na využitie viacerých jadier možno svet rozdeliť na horizontálne pásy, z ktorých každý spracúva samostatný worker.

Problém je však v tom, že:

• Každý worker dostáva kópiu príslušnej časti sveta (pri mriežke 2000×2000 asi 4 MB na jeden pás).
• Hlavné vlákno tiež kopíruje buffery, napríklad cez filled.buffer.slice(...), v každom kroku.
• Odosielanie 16–44 MB dát cez postMessage v každom snímku stojí stovky milisekúnd.

Výsledok:

• Výpočet je síce paralelný, ale réžia prenosu dát dominuje; namerané časy sú približne 1000 ms na krok, čo je pomalšie než verzia s jedným workerom.

To motivuje úplné odstránenie dátových kópií.

---

SharedArrayBuffer: nulové kopírovanie

Koncept

SharedArrayBuffer umožňuje viacerým workerom a hlavnému vláknu zdieľať rovnakú podkladovú pamäť. Bez kópií, bez transfer listu, iba zdieľané typované polia a podľa potreby korektná synchronizácia.

Inicializácia

Hlavné vlákno:

const sabA = new SharedArrayBuffer(COLS * ROWS);
const sabB = new SharedArrayBuffer(COLS * ROWS);

const worldA = new Uint8Array(sabA);
const worldB = new Uint8Array(sabB);

// spawn workers and send SABs
for (const worker of workers) {
    worker.postMessage({
        init: true,
        COLS,
        ROWS,
        sabA,
        sabB
    });
}

Workeri používajú new Uint8Array(sabA) a new Uint8Array(sabB), aby z jedného buffera čítali a do druhého zapisovali ďalšiu generáciu.

Vzor

• Všetci workeri čítajú z buffera A a zapisujú do buffera B.
• Po každom kroku hlavné vlákno iba prehodí referencie: current = B; next = A (ping-pong).
• Nie je potrebné posielať dátové payloady cez postMessage; správy iba signalizujú „krok dokončený“.

Výkon

• Kritickou cestou sa stáva najpomalší worker, ktorý určuje celkový čas kroku.
• V meraniach znížila viacworkerová verzia so SharedArrayBuffer čas kroku z približne 1000 ms na približne 80–120 ms pre mriežku 2000×2000.

Požiadavky

Na použitie SharedArrayBuffer v prehliadači musí byť stránka cross-origin isolated, napríklad pomocou hlavičiek:

• Cross-Origin-Opener-Policy: same-origin
• Cross-Origin-Embedder-Policy: require-corp

---

Push vykresľovanie pomocou ImageData

Jeden veľký putImageData

Namiesto tisícov volaní fillRect vytvorí vykresľovanie cez ImageData pixelový buffer v pamäti a odošle ho do canvasu jedným volaním.

Myšlienka

• Pomocou ctx.createImageData(W, H) získať objekt ImageData pre veľkosť viewportu.
• Vyplniť jeho Uint8ClampedArray hodnotami odtieňov sivej alebo RGB podľa stavu buniek a priblíženia.
• Zavolať ctx.putImageData(img, 0, 0) raz za snímok.

const img  = ctx.createImageData(W, H);
const data = img.data;

for (let py = 0; py < H; py++) {
const wy = top + Math.floor(py * S);
if (wy >= bottom) break;

for (let px = 0; px < W; px++) {
const wx = left + Math.floor(px * S);
if (wx >= right) break;

    const alive = filled[wy * COLS + wx];
    const c = alive ? 0 : 255;

    const i = (py * W + px) * 4;
    data[i]     = c; // R
    data[i + 1] = c; // G
    data[i + 2] = c; // B
    data[i + 3] = 255; // A
    }
}

ctx.putImageData(img, 0, 0);

Výhody

• Minimalizuje počet prechodov z JS do natívnej grafickej vrstvy – iba jedno volanie na snímok.
• Funguje veľmi dobre pri veľkých úrovniach priblíženia, keď každá bunka pokrýva viac pixelov a viewport je veľký.

Nevýhody

• Kopírovanie veľkého bloku ImageData z JS do natívneho kontextu stále stojí niekoľko milisekúnd.
• Nie je ideálne pre malé inkrementálne zmeny, pretože sa vždy prenáša celý buffer.

---

SharedArrayBuffer a ImageData

Hybridný prístup používa:

• SharedArrayBuffer na paralelnú simuláciu vo viacerých workeroch bez kopírovania.
• ImageData na efektívne vykreslenie celého viewportu jedným push volaním.

Tým sa kombinuje:

• Paralelný výpočet.
• Zdieľanie stavu sveta bez kopírovania.
• Minimálny počet vykresľovacích volaní.

V praxi:

• Typické časy pre mriežku 2000×2000 boli 40–70 ms na krok (výpočet + vykresľovanie), čo z tejto verzie robilo najrýchlejšie CPU-only riešenie v testoch.

---

GPU implementácia cez WebGL2

Výpočtový model

GPU verzia presúva celý krok Hry života na grafickú kartu pomocou WebGL2.

Kľúčové myšlienky

• Svet je reprezentovaný ako dve 2D textúry A a B, pričom každá uchováva stavy buniek.
• Fragment shader pre každý pixel (bunku) číta jeho susedov z textúry A, aplikuje pravidlo Hry života a zapisuje výsledok do B.
• Používa sa ping-pong rendering: v každom kroku sa prehodia úlohy textúr A a B.

To znamená:

• Každý GPU priechod aktualizuje všetky bunky paralelne pomocou tisícov GPU jadier.
• Počas simulácie nie je potrebné kopírovať stav sveta späť na CPU; menia sa iba uniformy a väzby textúr.

Prečo je GPU také rýchle

• GPU sú navrhnuté na masívne paralelné rovnaké výpočty, napríklad na spustenie toho istého shaderu nad miliónmi pixelov.
• WebGL2 umožňuje ponechať všetky simulačné dáta v pamäti GPU, čím sa eliminuje prenos CPU–GPU v každom kroku.
• CPU iba spúšťa vykresľovacie volania a prehadzuje textúry; náročná práca zostáva na GPU.

V meraniach zvládala WebGL2 implementácia milióny buniek na snímok približne za 1 ms, teda výrazne rýchlejšie než kombinácia SAB + ImageData.

---

Zhrnutie

Nasledujúca tabuľka približne sumarizuje namerané časy a kvalitatívne poznámky zo seminára. Časy závisia od hardvéru, ale ukazujú relatívne poradie.

Technika	Čas (ms)	Poznámky
Canvas Full redraw	100–300	Veľmi jednoduché, ale škáluje s veľkosťou sveta
Dirty rectangles	70–200	Kreslí iba zmeny, stále pracuje aj mimo obrazu
Visible region	10–250	Iba viditeľná oblasť; závisí od priblíženia
Web Worker – 1 vlákno	~300	Oddeľuje výpočet od UI
Web Worker – 4 vlákna	500–1000	Paralelný výpočet, ale drahé kopírovanie bufferov
SAB – 4 workeri	80–120	Zdieľaná pamäť bez kópií, plynulé UI
ImageData	10–100	Jeden veľký putImageData, dobré pri veľkom priblížení
SAB + ImageData	40–70	Najlepšia CPU-side implementácia
WebGL2 GPU	~1	Milióny buniek v reálnom čase

Pozorovanie: výkon sa systematicky zlepšuje, keď sa viac práce paralelizuje a presúva bližšie ku GPU, najmä ak sa zároveň odstraňuje nadbytočné kreslenie a prenosy pamäte.

---

Záverečné poznámky

Efektívne vykresľovanie Hry života v prehliadači nie je ani tak o samotných pravidlách Hry života, ale skôr o pohybe dát a stratégii kreslenia. Od naivného úplného prekresľovania možno postupne prejsť cez dirty regions, orezávanie podľa kamery, viacvláknový výpočet, zdieľanú pamäť až po presun výpočtu na GPU, čo pri veľkých mriežkach vedie k zrýchleniam o celé rády.

Pre praktické simulácie v prehliadači poskytuje prístup SAB + ImageData veľmi dobrý kompromis medzi jednoduchosťou, výkonom a laditeľnosťou na CPU, zatiaľ čo implementácia vo WebGL2 zostáva najlepšou voľbou v prípade dostupnej GPU a akceptovateľnej mierne vyššej komplexity.

Zdrojový kód

Kompletný zdrojový kód všetkých dem je dostupný na GitHube:

👉 https://github.com/vasylkhorev/efficient-gol