Ефективне рендерення Гри життя в HTML Canvas

Гра життя виглядає простою, але рендерити мільйони клітин у реальному часі безпосередньо в браузері — зовсім не проста задача. Цей допис базується на моїй семінарній презентації «Efficient rendering in HTML Canvas for cellular automaton simulations» і розглядає кілька CPU- та GPU-технік, порівнюючи їхні компроміси й продуктивність.

TL;DR: Для плавних симуляцій на великих ґратках ключовими є відокремлення обчислення від рендерення, уникнення зайвого малювання та перенесення роботи в кілька потоків або на GPU.

Мотивація і проблема

Мій дипломний проєкт Fuzzy Life розширює Conway’s Game of Life нечіткими значеннями клітин, що одразу збільшує витрати як на обчислення, так і на рендерення. Під час симуляції ґраток із сотнями тисяч або мільйонами клітин вузьким місцем стають уже не лише правила, а й те, як часто та наскільки ефективно відмальовується світ.

Типові проблемні місця:

Обчислення: Оновлення сусідів і застосування правил для кожної клітини на кожному кроці.
Рендерення: Кількість викликів графічного API, передавання буферів, надмірне перемальовування та малювання поза екраном.
Взаємодія: Плавне панорамування й масштабування, дисплеї з високою DPI та великі viewport-и.

Мета полягає в тому, щоб знайти архітектури рендерення, які:

Відокремлюють крок симуляції від малювання.
Оновлюють лише видимі або змінені області.
Масштабуються від базового Canvas 2D до GPU WebGL2.

Основи Canvas 2D

HTML <canvas> надає бітмапову поверхню, у яку JavaScript може малювати за допомогою 2D-контексту рендерення.

Кожен canvas має 2D-контекст із функціями на кшталт clearRect, fillRect, drawImage, stroke або fillText.
Canvas працює в режимі immediate mode: після малювання API не зберігає об’єкти; якщо стан змінюється, усе потрібно намалювати знову.
Canvas 2D широко використовується для візуалізацій, ігор, симуляцій та обробки зображень, коли корисний прямий доступ до пікселів.

Для Гри життя це означає, що наївний підхід полягає в проходженні всіх клітин і виклику fillRect для кожної живої клітини на кожному кадрі.

Демо-середовище і сервер

Усі демо — це невеликі HTML-файли, які мають спільне JavaScript-ядро та відрізняються тим, як вони обчислюють і малюють кадри.

Демо подаються через мінімальний Express-сервер із необхідними заголовками 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 });
});

Запуск:

npm init -y
npm i express
node server.js

# open http://localhost:8080/

Доступні демо-сторінки:

index1-full-redrawn.html – базовий варіант із повним перемальовуванням.
index2-dirty-rectangles.html – dirty rectangles.
index3-vis-region-rendering.html – рендерення видимої області.
index4-static-web-workers.html – один web worker.
index5-static-web-workers-n.html – кілька worker-ів із копіюванням.
index6-sharedarray-multiworker.html – кілька worker-ів зі SharedArrayBuffer.
index7-static-image-data.html – push-рендерення через ImageData.
index8-sharedarray-multiworker-imagedata.html – гібрид SAB + ImageData.
index9-gpu-webgl.html – GPU-версія через WebGL2.

CPU-рендерення: три базові стратегії

Повне перемальовування кожного кадру

Найпростіша модель — перемальовувати весь світ на кожному кроці, ігноруючи камеру та видимість.

Ідея

Для кожного кроку симуляції:
- Очистити фон.
- Пройти всі клітини ROWS * COLS.
- Для кожної живої клітини намалювати прямокутник 1×1 у її координатах.

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);
            }
        }
    }
}

Переваги

Концептуально простий і надійний базовий варіант для вимірювання продуктивності.
Добрий стрес-тест для CPU та Canvas API.

Недоліки

Надзвичайно багато викликів fillRect, зокрема для клітин поза екраном.
Вартість зростає з розміром світу, а не з розміром viewport-а, що руйнує продуктивність на великих ґратках (у тестах приблизно 100–300 мс на крок).

Dirty rectangles

Техніка dirty rectangles відстежує клітини, які змінилися між кадрами, і перемальовує лише їх поверх попереднього кадру.

Ідея

Тримати два масиви: filled (поточний стан) і next (наступне покоління).
Після обчислення наступного стану порівняти обидва масиви.
Лише для індексів, де filled[i] !== next[i]:
- Вибрати правильний колір (жива/мертва клітина).
- Намалювати прямокутник 1×1 у цій клітині.

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);
            }
        }
    }
}

Характеристики

Перший кадр усе ще потребує повного перемальовування; наступні кадри оновлюють лише змінені клітини.
Час на кадр стає пропорційним кількості змінених клітин, а не загальній кількості клітин.
Обсяг роботи стабільний і не залежить від розміру viewport-а, але оновлення все одно виконуються і для областей поза екраном.

Рендерення видимої області

Рендерення видимої області обрізає світ до того, що бачить камера, і малює лише поточну видиму частину.

Ідея

Обчислити прямокутник у координатах світу, який відповідає viewport-у, з урахуванням позиції камери та масштабу.
Обрізати цей прямокутник межами світу.
Проходити лише клітини всередині цієї області й малювати живі клітини.

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();

Чому це важливо

Зменшує надмірне перемальовування й доступ до пам’яті завдяки пропуску клітин поза viewport-ом.
Найбільш корисне під час наближення, коли viewport покриває лише частину світу.
Це базовий будівельний блок для наступних оптимізацій (ImageData, SAB, GPU), які спираються на чітко визначену видиму область.

Паралелізація на CPU

Один Web Worker

Оновлення сусідів у Грі життя є локальними й паралелізовними, тому перенесення симуляційного кроку в Web Worker зберігає чутливість UI-потоку.

Архітектура

Основний потік:

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]);
};

Переваги

Симуляція продовжується навіть тоді, коли UI тимчасово навантажує основний потік; панорамування й масштабування відчуваються плавними.
Передавання ArrayBuffer як transferable об’єкта уникає додаткових копій під час надсилання.

Недоліки

Для ґратки 2000×2000 один крок триває приблизно 400 мс, тому вузьким місцем стає саме обчислення у worker-і.
Повністю використовується лише одне CPU-ядро.

Кілька worker-ів із копіюванням

Щоб використати кілька ядер, світ можна розбити на горизонтальні смуги, кожну з яких обробляє окремий worker.

Однак:

Кожен worker отримує копію своєї частини світу (приблизно 4 MB на смугу для 2000×2000).
Основний потік також копіює буфери, наприклад через filled.buffer.slice(...), на кожному кроці.
Надсилання 16–44 MB даних через postMessage на кожному кадрі коштує сотні мілісекунд.

Результат:

Обчислення є паралельним, але накладні витрати на передавання даних домінують; виміряні часи становлять приблизно 1000 мс на крок, що повільніше за версію з одним worker-ом.

Це мотивує повністю усунути копіювання даних.

SharedArrayBuffer: нульове копіювання

Концепт

SharedArrayBuffer дозволяє кільком worker-ам і основному потоку спільно використовувати ту саму базову пам’ять. Без копій, без transfer list — лише спільні типізовані масиви й належна синхронізація там, де вона потрібна.

Ініціалізація

Основний потік:

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
    });
}

Worker-и використовують new Uint8Array(sabA) і new Uint8Array(sabB), щоб читати з одного буфера й записувати наступне покоління в інший.

Шаблон

Усі worker-и читають із буфера A і записують у буфер B.
Після кожного кроку основний потік просто міняє посилання: current = B; next = A (ping-pong).
Не потрібно передавати дані через postMessage; повідомлення лише сигналізують, що «крок завершено».

Продуктивність

Критичним шляхом стає найповільніший worker, який визначає загальний час кроку.
У вимірюваннях багатопотокова версія зі SharedArrayBuffer зменшила час кроку з приблизно 1000 мс до 80–120 мс для ґратки 2000×2000.

Вимоги

Щоб використовувати SharedArrayBuffer у браузері, сторінка має бути cross-origin isolated, наприклад через заголовки:

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

Push-рендерення через ImageData

Один великий `putImageData`

Замість тисяч викликів fillRect рендерення через ImageData формує піксельний буфер у пам’яті й надсилає його до canvas одним викликом.

Ідея

Використати ctx.createImageData(W, H), щоб отримати об’єкт ImageData розміру viewport-а.
Заповнити його Uint8ClampedArray значеннями grayscale або RGB на основі стану клітини й масштабу.
Викликати ctx.putImageData(img, 0, 0) один раз на кадр.

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);

Переваги

Мінімізує кількість переходів із JS до нативного графічного шару — лише один виклик на кадр.
Дуже добре працює для великих рівнів масштабування, коли кожна клітина покриває кілька пікселів і viewport є великим.

Недоліки

Копіювання великого блоку ImageData з JS у нативний контекст усе ще коштує кілька мілісекунд.
Не ідеально підходить для малих інкрементальних змін, бо весь буфер завжди передається цілком.

SharedArrayBuffer і ImageData

Гібридний підхід використовує:

SharedArrayBuffer для паралельної симуляції в кількох worker-ах без копіювання.
ImageData для ефективного рендерення всього viewport-а одним push-викликом.

Це поєднує:

Паралельне обчислення.
Спільний стан світу без копіювання.
Мінімальну кількість викликів рендерення.

На практиці:

Типові часи для ґратки 2000×2000 становили 40–70 мс на крок (обчислення + рендерення), що робило цей підхід найшвидшим CPU-only варіантом у тестах.

GPU-реалізація через WebGL2

Обчислювальна модель

GPU-версія переносить увесь крок Гри життя на графічну карту за допомогою WebGL2.

Ключові ідеї

Світ представлений двома 2D-текстурами A і B, кожна з яких зберігає стани клітин.
Fragment shader для кожного пікселя (клітини) читає сусідів із текстури A, застосовує правило Life і записує результат у B.
Використовується ping-pong rendering: ролі A і B міняються місцями на кожному кроці.

Це означає:

Кожен GPU-прохід оновлює всі клітини паралельно за допомогою тисяч GPU-ядер.
Під час симуляції не потрібно копіювати стан світу назад на CPU; змінюються лише uniforms і прив’язки текстур.

Чому GPU настільки швидке

GPU створені для масово паралельних однотипних обчислень, наприклад для запуску одного й того самого shader-а над мільйонами пікселів.
WebGL2 дозволяє тримати всі симуляційні дані в пам’яті GPU, уникаючи передавання CPU–GPU на кожному кроці.
CPU лише запускає draw calls і міняє текстури місцями; важка робота залишається на GPU.

У вимірюваннях WebGL2-реалізація обробляла мільйони клітин на кадр приблизно за 1 мс, тобто значно швидше навіть за комбінацію SAB + ImageData.

Підсумок

Наведена нижче таблиця приблизно підсумовує виміряні часи та якісні спостереження із семінару. Часи залежать від апаратного забезпечення, але показують відносний порядок.

Техніка	Час (мс)	Примітки
Canvas Full redraw	100–300	Дуже просто, але масштабується з розміром світу
Dirty rectangles	70–200	Малює лише зміни, але все ще працює поза екраном
Visible region	10–250	Лише видима область; залежить від масштабу
Web Worker – 1 потік	~300	Відокремлює обчислення від UI
Web Worker – 4 потоки	500–1000	Паралельне обчислення, але дорогі копії буферів
SAB – 4 worker-и	80–120	Спільна пам’ять без копій, плавний UI
ImageData	10–100	Один великий `putImageData`, добре при великому масштабі
SAB + ImageData	40–70	Найкраща CPU-side реалізація
WebGL2 GPU	~1	Мільйони клітин у реальному часі

Спостереження: продуктивність систематично зростає тоді, коли більше роботи паралелізується й переноситься ближче до GPU, особливо якщо водночас усуваються зайве малювання та передавання пам’яті.

Завершальні думки

Ефективне рендерення Гри життя в браузері стосується не стільки самих правил Life, скільки руху даних і стратегії малювання. Починаючи з наївного повного перемальовування, можна поступово додавати dirty regions, обрізання за камерою, багатопотокове обчислення, спільну пам’ять і GPU-offloading, що для великих ґраток дає прискорення на порядки.

Для практичних браузерних симуляцій підхід SAB + ImageData забезпечує чудовий баланс між простотою, продуктивністю та зручністю налагодження на CPU, тоді як реалізація через WebGL2 залишається найкращим вибором, якщо доступна GPU і прийнятна дещо вища складність.

Вихідний код

Повний вихідний код усіх демо доступний на GitHub:

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

Мотивація і проблема

Основи Canvas 2D

Демо-середовище і сервер

CPU-рендерення: три базові стратегії

Повне перемальовування кожного кадру

Dirty rectangles

Рендерення видимої області

Паралелізація на CPU

Один Web Worker

Кілька worker-ів із копіюванням

SharedArrayBuffer: нульове копіювання

Концепт

Push-рендерення через ImageData

Один великий putImageData

SharedArrayBuffer і ImageData

GPU-реалізація через WebGL2

Обчислювальна модель

Чому GPU настільки швидке

Підсумок

Завершальні думки

Вихідний код

Один великий `putImageData`