Пишем двоичный сумматор в игре «Жизнь» на JavaScript
После того, как я прочитал «Код» Петцольда, мне захотелось собрать какую-нибудь логическую схему руками. Но не просто собрать, а ещё и визуализировать её работу: как по ней проходят сигналы, как работают логические гейты, вот это всё.
Первое, о чём я вспомнил — это ролик Мэта Паркера (Matt Parker), в котором он с ребятами собирал компьютер из домино. В ролике он показывал, как работают логические схемы, построенные из домино — хотелось чего-то похожего. А потом я вспомнил, что я давно хотел написать игру «Жизнь». Потому что ведь все должны хоть раз написать игру «Жизнь», верно? Две идеи сошлись в одной точке, и появилась эта серия постов 😃
В эти трёх статьях мы с помощью JS реализуем двоичный калькулятор в правилах из игры «Жизнь» Конвея, который будет складывать два двубитовых числа.
- В первом посте реализуем правила игры, напишем модуль для рисования на canvas.
- Во втором посте познакомимся с распространёнными фигурами из игры, научимся генерировать «сигналы» и создадим логические схемы NOT, AND, OR и XOR.
- В третьем посте реализуем двоичный полусумматор и полный сумматор, которые и используем для создания калькулятора.
В результате получим приложение, которое будет принимать от пользователя два двубитовых числа и запускать «сигналы» из фигур игры «Жизнь», чтобы сложить их и получить ответ.
Ссылку на исходники я положу здесь и ещё в конце поста. А сейчас сосредоточимся на правилах игры и её отрисовке.
Правила игры «Жизнь»
Игра «Жизнь» (англ. Conway’s Game of Life) — это мир, поделённый на клетки, где каждая клетка может быть «живой» или «мёртвой».
У каждой клетки есть 8 соседей вокруг неё. Соседи также могут быть живыми или мёртвыми.
Живые и мёртвые клетки влияют на то, как мир будет «эволюционировать». Клетки «рождаются» и «умирают» по некоторым правилам, заданным в мире. Правила в общем случае могут быть разными, но в игре «Жизнь» приняты такие:
- клетка рождается, если вокруг неё есть ровно 3 живых соседа;
- клетка продолжает жить, если вокруг неё ровно 2 или 3 живых соседа;
- в остальных случаях клетка умирает от перенаселения, если клеток слишком много, или от одиночества, если клеток слишком мало.
Такие правила позволяют создавать стабильные и движущиеся фигуры, которые мы будем использовать для построения схем. Но фигуры и схемы — это в будущем, а сейчас приступим к реализации самой игры.
Клетки и соседи
Сперва определимся, как мы будем хранить «популяцию» клеток в мире игры. Мир двумерный, значит за расположение каждой клетки отвечают две координаты:
- x, положение по горизонтали,
- y, положение по вертикали.
Мы можем использовать для хранения популяции двумерный массив, в котором будем отмечать живые клетки значением 1, а мёртвые значением 0.
const population = [
[0, 0, 1],
[0, 1, 0],
[1, 1, 1]
];Это в принципе рабочий вариант, но для больших миров он нам не подойдёт. Дело в том, что чем больше будет схема (а сумматор получится очень большим), тем больше данных нам придётся хранить и обрабатывать на каждую перерисовку. Вместо этого мы будем запоминать только живые клетки.
Чтобы было удобнее к ним обращаться, будем хранить их не в массиве, а в объекте:
const population = {
'2:0': cell1,
'1:1': cell2,
'0:2': cell3,
'1:2': cell4,
'2:2': cell5
// …
};Каждая клетка будет объектом с двумя координатами. Объект занимает чуть больше памяти, но координаты внутри пригодятся нам в будущем для расчётов следующих шагов эволюций и отрисовки на экране.
Напишем фабрику для создания живых клеток:
// life/agent.js
export function createAgent(x, y) {
return { x, y };
}При перерисовке мы будем проверять каждую живую клетку и её соседей, чтобы понять, какие клетки доживут до следующей итерации:
// life/agent.js
export function isAlive(agent, population) {
return !!population[`${agent.x}:${agent.y}`];
}Если в популяции по заданным координатам есть объект, значит клетка живая. Если там пусто, значит клетка мёртвая:
const population = {
'5:5': { x: 5, y: 5 }
};
isAlive({ x: 5, y: 5 }, population); // true
isAlive({ x: 0, y: 5 }, population); // falseЧтобы посчитать количество живых соседей вокруг заданной клетки, нам потребуется их всех сперва найти:
// life/agent.js
export function neighborsOf({ x, y }) {
return [
// Соседи сверху:
{ x: x - 1, y: y - 1 },
{ x, y: y - 1 },
{ x: x + 1, y: y - 1 },
// ...С каждой стороны:
{ x: x - 1, y },
{ x: x + 1, y },
// ...И под указанной клеткой:
{ x: x - 1, y: y + 1 },
{ x, y: y + 1 },
{ x: x + 1, y: y + 1 }
];
}…А потом — посчитать, сколько из них в популяции существует, то есть — сколько из найденных живы:
// life/agent.js
export function countAliveAround(agent, population) {
return neighborsOf(agent).reduce((total, agent) => {
return total + (isAlive(agent, population) ? 1 : 0);
}, 0);
}Тогда, например, в такой популяции у клетки с координатами 1:1 будет 4 живых соседа:
// Alive Dead Alive
// Alive Current Dead
// Dead Alive Dead
const population = {
'0:0': { x: 0, y: 0 },
'2:0': { x: 2, y: 0 },
'0:1': { x: 0, y: 1 },
'1:1': { x: 1, y: 1 },
'1:2': { x: 1, y: 2 }
};
countAliveAround({ x: 1, y: 1 }, population);
// 4Когда главные функции для работы с клетками и определением соседей готовы, мы можем приступить к программированию мира игры и правил эволюции.
Эволюция клеток
Игра «Жизнь» — это клеточный автомат. Это значит, что эволюция в ней дискретна — то есть мы можем разбить весь процесс развития популяции на отдельные шаги, итерации.
Начальная популяция будет первым шагом эволюции. Чтобы получить следующий шаг мы должны применить правила игры ко всем клеткам одновременно. Результат применённых правил и будет следующим шагом эволюции.
Функция эволюции сама по себе — чистая, потому что зависит только от предыдущего состояния популяции и правил игры. Но чтобы было удобнее хранить текущую популяцию и свойства «мира», мы напишем класс World:
// life/world.js
export class World {
constructor(rows, columns, population) {
this.rows = rows;
this.columns = columns;
this.population = population;
}
}В конструктор будем передавать размер мира в клеточках и начальную популяцию. Для собственно эволюции напишем метод evolve. В нём заведём объект evolved, в котором будем хранить состояние популяции на следующем шаге. После всех преобразований мы заменим старую популяцию на evolved:
// life/world.js
export class World {
// …
evolve = () => {
const evolved = {};
const checked = {};
// TODO: Здесь будут преобразования…
this.population = evolved;
};
}Чтобы провести сами преобразования, нам понадобится пройтись по каждой живой клетке и проверить, останется ли она живой. Вспомним, что клетка остаётся живой, только если у неё 2 или 3 живых соседа:
// life/world.js
evolve = () => {
const evolved = {};
const checked = {};
Object.values(this.population).forEach((agent) => {
const alive = countAliveAround(agent, this.population);
if (alive === 2 || alive === 3) {
const { x, y } = agent;
evolved[`${x}:${y}`] = agent;
}
// TODO: Проверить соседей…
});
};Мы добавляем выжившие клетки в новую популяцию evolved, которая потом заменит текущую. Отдельный объект нам нужен, чтобы не изменять текущую популяцию по ходу её обработки.
Мы не можем менять текущую популяцию, потому что эти изменения отразятся на пересчёте других клеток, а этого происходить не должно. Нам необходимо применить правила сразу ко всем клеткам в текущей популяции. А если правила будут применяться, перезаписывая текущую популяцию, то это условие уже не выполнится.
Кроме самой клетки нам также необходимо проверить и её соседей. Если у соседней клетки 3 живых соседа, она рождается:
Object.values(this.population).forEach((agent) => {
// …
neighborsOf(agent).forEach((neighbor) => {
const { x, y } = neighbor;
if (checked[`${x}:${y}`]) return;
checked[`${x}:${y}`] = true;
if (countAliveAround(neighbor, this.population) !== 3) return;
evolved[`${x}:${y}`] = createAgent(x, y);
});
});Мы используем объект checked, чтобы не перепроверять уже проверенные ранее клетки. Так как соседи при проверке поменяться не могут, посчитанный ранее результат поменяться не должен, поэтому его можно не перепроверять.
Промежуточный результат
Метод для эволюции готов. Теперь мы можем проверить, как он работает, чтобы убедиться, что всё сделано правильно.
Проверить, что игра работает правильно, проще всего на каком-нибудь осцилляторе. Осцилляторы в игре «Жизнь» — это фигуры, которые превращаются за некоторое количество итераций в себя же.
Самый простой осциллятор — блинкер. Это фигура, которая осциллирует между горизонтальной полосой длиной в 3 клетки и вертикальной полосой высотой в 3 клетки:
Напишем такой блинкер и проверим, что наша реализация правильно преобразовывает эту фигуру. Для проверки создадим HTML-страницу, к которой подключим скрипт с типом module — это будет главный модуль:
<script type="module" src="./main.js"></script>Атрибут type="module" говорит браузеру, что мы собираемся использовать JS-модули. Внутри JS-модуля мы сможем использовать импорты, свежий синтаксис и всё такое. Это избавит нас от необходимости тащить сборку в проект: подключаем к странице скрипт и всё работает — как в старые добрые времена, только с шашечками и ехать проще.
Создадим мир и популяцию в виде горизонтальной полоски из 3 клеток:
// main.js
import { World } from './life/world.js';
const population = {
'0:1': { x: 0, y: 1 },
'1:1': { x: 1, y: 1 },
'2:1': { x: 2, y: 1 }
};
const world = new World(5, 5, population);А теперь пробуем провести несколько итераций эволюции и проверить, как изменяется популяция. У блинкера период равен 2 итерациям — это значит, что каждые 2 хода он возвращается к своей начальной форме. Проверим это:
// main.js
// …
world.evolve();
console.log(world.population);
// {1:0: {x: 1, y: 0}, 1:2: {x: 1, y: 2}, 1:1: {x: 1, y: 1}}
world.evolve();
console.log(world.population);
// {0:1: {x: 0, y: 1}, 2:1: {x: 2, y: 1}, 1:1: {x: 1, y: 1}}И правда, на втором шаге популяция вернулась к начальной. …Но смотреть на популяцию в таком виде совершенно неудобно. Хочется нормального отображения, графического интерфейса. Реализуем и его!
Отрисовка популяции
Мы будем использовать canvas для работы с графикой и отрисовки популяции в игре. Добавим элемент на страницу:
<canvas width="400" height="300" id="canvas"></canvas>
<script type="module" src="./main.js"></script>Для работы с канвасом мы создадим ещё один модуль, назовём его Drawer. Этот класс будет в конструкторе принимать размер сетки и готовить полотно к рисованию:
// dom/drawer.js
export class Drawer {
constructor(kernelSize) {
// Находим элемент:
const canvas = document.getElementById('canvas');
const context = canvas.getContext('2d');
const [width, height] = [canvas.offsetWidth, canvas.offsetHeight];
// Сохраняем ссылки на контекст и настройки:
this.context = context;
this.kernel = kernelSize;
this.width = width;
this.height = height;
// Рассчитываем количество колонок и рядов на поле:
this.rows = Math.floor(height / this.kernel);
this.columns = Math.floor(width / this.kernel);
// Нормализуем отображение на экранах с высокой плотностью пикселей:
this.normalizeScale();
}
}Чтобы рисунок не был мыльным на экранах с высокой плотностью пикселей, мы отмасштабируем физический и логический размер полотна, используя window.devicePixelRatio:
// dom/drawer.js
export class Drawer {
// …
normalizeScale = () => {
const { devicePixelRatio: pixelRatio } = window;
if (pixelRatio > 1) {
canvas.width = this.width * pixelRatio;
canvas.height = this.height * pixelRatio;
canvas.style.width = `${this.width}px`;
canvas.style.height = `${this.height}px`;
this.context.scale(pixelRatio, pixelRatio);
}
};
}Сетку мира нарисуем с помощью линий, которые добавим через lineTo. Расставим вертикальные и горизонтальные линии на расстоянии в kernelSize друг от друга:
// dom/drawer.js
export class Drawer {
// …
drawGrid = () => {
this.context.strokeStyle = 'rgba(0,0,0, 0.3)';
// Вертикальные линии:
for (let i = 0; i < this.width; i += this.kernel) {
this.context.beginPath();
this.context.moveTo(i, 0);
this.context.lineTo(i, this.height);
this.context.stroke();
}
// Горизонтальные линии:
for (let j = 0; j < this.height; j += this.kernel) {
this.context.beginPath();
this.context.moveTo(0, j);
this.context.lineTo(this.width, j);
this.context.stroke();
}
};
}Возьмём из популяции все живые клетки и нарисуем чёрные квадраты на месте их расположения с помощью fillRect:
// dom/drawer.js
export class Drawer {
// …
drawWorld = (world) => {
this.context.fillStyle = '#000000';
world.agents.forEach((agent) => {
this.context.fillRect(agent.x * this.kernel, agent.y * this.kernel, this.kernel, this.kernel);
});
};
}Сейчас в классе World нет свойства agents, через которое мы хотим получить список клеток. (Помним, что популяция — это объект.) Список для отрисовки будет использовать удобнее, поэтому добавим геттер для получения всех живых клеток:
// life/world.js
export class World {
// …
get agents() {
return Object.values(this.population);
}
}Теперь в главном модуле вызовем отрисовщик и посмотрим на результат:
// main.js
// …
const drawer = new Drawer(20);
const world = new World(5, 5, population);
function liveGeneration() {
drawer.drawGrid();
drawer.drawWorld(world);
}
liveGeneration();Получился блинкер в его начальном состоянии:
Проверим, как работает преобразование, добавим эволюцию:
// main.js
// …
function liveGeneration() {
world.evolve();
drawer.drawGrid();
drawer.drawWorld(world);
}
liveGeneration();Отлично, блинкер стал вертикальным — это именно то поведение, которое мы ожидали от него.
Понятно, что менять итерации руками — дело пустое, поэтому нам нужен механизм для автоматического запуска новых шагов эволюции. Для этого мы будем использовать игровой цикл.
Игровой цикл
Игровой цикл (англ. Game Loop) — это паттерн, который обычно используют в играх для повторяющейся обработки пользовательского ввода и перерисовки экрана. В нашем случае он пригодится для перезапуска эволюции.
Напишем в главном модуле самозапускающуюся функцию gameLoop:
// main.js
// …
(function gameLoop() {
liveGeneration();
window.requestAnimationFrame(gameLoop);
})();Эта функция сперва запускает пересчёт популяции (liveGeneration), а потом просит браузер запустить себя ещё раз перед следующей перерисовкой (repaint).
Но если мы запустим игру прямо сейчас, то полотно быстро станет чёрным, потому что мы не стираем то, что было нарисовано раньше 😃
Для очищения предыдущей итерации создадим метод reset в классе Drawer. Сперва очистим всё поле с помощью clearRect, а потом нарисуем сетку:
// dom/drawer.js
export class Drawer {
reset = () => {
this.context.clearRect(0, 0, this.width, this.height);
this.drawGrid();
};
}Теперь немного обновим функцию liveGeneration в главном модуле, чтобы полотно очищалось перед отрисовкой новой итерации:
// main.js
function liveGeneration() {
drawer.reset();
world.evolve();
drawer.drawWorld(world);
}
(function gameLoop() {
liveGeneration();
window.requestAnimationFrame(gameLoop);
})();Ну и чтобы можно было управлять тем, как быстро наступает новый шаг эволюции, добавим небольшой таймер перед перезапуском:
// main.js
(function gameLoop() {
liveGeneration();
setTimeout(() => window.requestAnimationFrame(gameLoop), 100);
})();Теперь мы можем запустить игру и посмотреть, как всё работает:
Случайная популяция
Смотреть на блинкер особого интереса не вызывает 😅
Давайте напишем функцию для наполнения популяции случайными клетками, тогда мы сможем увидеть, как фигуры превращаются друг в друга и как проходит эволюция на больших популяциях.
В функцию populateRandom передадим количество строк и колонок из мира, который надо населить. Далее пройдём по каждой клетке из сетки и запустим генератор случайных чисел, который будет возвращать случайное бинарное значение (true / false). Если вернулось true, добавим живую клетку в популяцию, если нет, ничего не будем делать:
// life/population/random.js
export function populateRandom(rows, columns) {
const population = {};
range(columns).forEach((_, i) => {
range(rows).forEach((_, j) => {
if (Math.random() <= 0.5) return;
population[`${i}:${j}`] = createAgent(i, j);
});
});
return population;
}Используем результат работы этой функции как значение по умолчанию в конструкторе класса World. Так, если ему не передали никакой начальной популяции, то он заселит мир случайными клетками:
// life/world.js
export class World {
constructor(rows, columns, population = populateRandom(rows, columns)) {
this.rows = rows;
this.columns = columns;
this.population = population;
}
// …
}Уберём из главного модуля лишний код и обновим размеры поля:
// main.js
const drawer = new Drawer(10);
const world = new World(30, 40);
function liveGeneration() {
drawer.reset();
world.evolve();
drawer.drawWorld(world);
}
(function gameLoop() {
liveGeneration();
setTimeout(() => window.requestAnimationFrame(gameLoop), 100);
})();…И получим результат — игра работает, мы всё сделали правильно 🥳
В следующих постах
Мы создали основу для построения сложных популяций, но пока что никак не можем создать и направить «сигнал» из живых клеток, чтобы использовать его для построения логических схем.
В следующем посте мы реализуем базовые фигуры из игры «Жизнь»: глайдер, пушку и отражатель. С помощью этих фигур мы сможем создать основу для бинарной логики — логические гейты NOT, OR, AND и XOR.
В последнем посте мы используем эти гейты для создания полусумматора, полного сумматора, а следом и калькулятора, который будет складывать два двубитовых значения.