Реализуем логические гейты в игре «Жизнь»

Продолжаем писать двоичный калькулятор, который складывает два двубитовых числа. В прошлом посте мы остановились на том, что написали саму игру «Жизнь» и модуль для отрисовки эволюции клеток на экране.

В этом посте познакомимся с распространёнными фигурами из игры, научимся генерировать «сигналы» и создадим логические схемы NOT, AND, OR и XOR. Эти схемы мы используем в следующем посте, чтобы создать схему полусумматора и полного сумматора.

Фигуры в игре и работа с ними

Вообще, идея создать комплюктер в игре «Жизнь» — не нова. Об этом есть и видео на Ютубе, и научные статьи. Дело в том, что правила «Жизни» делают игру Тьюринг-полной — то есть такой, что внутри неё можно реализовать любую вычислимую функцию. Ну а раз так, то почему бы не написать компьютер в компьютере, да?

Как и в случае с настоящими вычислителями, работа логических схем будет зависеть от сигналов. В «Жизни» в качестве сигналов мы можем использовать особые фигуры, которые умеют перемещаться по полю — космические корабли.

Глайдер

Самый маленький по размеру космический корабль — это глайдер или планёр (англ. glider). Он перемещается по полю по диагонали со скоростью в одну клетку за 4 хода. То есть каждые 4 шага эволюции глайдер смещается на одну клетку по диагонали по своему направлению.

Мы можем использовать поток таких глайдеров как «напряжение на входе схемы». Есть поток — есть сигнал, нет потока — нет сигнала.

Попробуем создать первый глайдер в нашей реализации. Добавим популяцию из клеток глайдера в главном модуле:

// main.js

// .O.
// ..O
// OOO

const population = {
	'0:1': createAgent(0, 1),
	'1:2': createAgent(1, 2),
	'2:0': createAgent(2, 0),
	'2:1': createAgent(2, 1),
	'2:2': createAgent(2, 2)
};

const drawer = new Drawer(10);
const world = new World(30, 40, population);

И посмотрим, сработает ли:

Отлично! Глайдер работает. Но мы снова сталкиваемся с неудобным видом начальной популяции. Пришлось даже добавить сверху комментарий, в котором нарисовать псевдографикой глайдер, чтобы было понятно, что это за фигура.

Вместо этого лучше напишем функцию, которая будет принимать такую псевдографику и возвращать — популяцию, которая там описана. Это нам пригодится и в будущем, когда мы будем работать с большими фигурами.

Фигуры из псевдографики

Псевдографика, которую я использовал в комментариях — это часть принятой нотации паттернов игры. В ней живые клетки записываются через прописную O, а мёртвые клетки — через точки. Например, библиотека фигур Life Lexicon использует такой именно способ записи. Глайдер она описывает так:

OOO
O..
.O.

Кроме простого текста ещё иногда используют формат RLE (Run Length Encoded), но он не такой наглядный, поэтому мы будем использовать не его, а простой текст.

# В формате RLE глайдер будет записан так:
x = 3, y = 3, rule = B3/S23
bob$2bo$3o!

# Не так наглядно, как с записью через точки и O.

Для того, чтобы из псевдографики получить популяцию клеток, мы напишем функцию fromPseudoGraphics.

Как аргумент будем передавать ей строку псевдографики, которую разобьём на строки, а каждую строку — на символы. На месте каждого символа O создадим живую слетку и наполним объект популяции, который затем вернём из функции как результат:

// composition/from-pseudo-graphics.js
export const LINE_BREAK = '\n';
export const LIVE_AGENT = 'O';
export const EMPTY_STRING = '';

export function fromPseudoGraphics(source) {
	const population = {};

	// Разбиваем на строки:
	const rows = source.split(LINE_BREAK).filter(exists);

	rows.forEach((row, j) => {
		// Каждую строку — на символы:
		const characters = row.split(EMPTY_STRING);

		characters.forEach((character, i) => {
			if (character !== LIVE_AGENT) return;

			// Если символ отвечает за живую клетку, создаём её
			// и добавляем в популяцию на указанное место:
			population[`${i}:${j}`] = createAgent(i, j);
		});
	});

	return population;
}

Теперь мы можем сохранить исходник паттерна в константе, передать его как аргумент в функцию fromPseudoGraphics и получить начальную популяцию:

// main.js

const glider = `
.O.
..O
OOO`;

const population = fromPseudoGraphics(glider);
const drawer = new Drawer(10);
const world = new World(30, 40, population);

Всё продолжает работать, можем двигаться к следующим фигурам.

Глайдерная пушка Госпера

Глайдеры мы создавать научились, но этого пока недостаточно, чтобы создать устойчивый и постоянный сигнал на входе будущих схем. Сейчас мы можем отправить лишь столько глайдеров, сколько создадим заранее. Нам нужен какой-то «генератор» сигналов, который будет создавать устойчивые потоки глайдеров без нашего участия.

Такие фигуры тоже есть, и они называются ружьями или пушками. Пушки «стреляют» глайдерами в указанном направлении с некоторой периодичностью.

Самая простая пушка — это глайдерная пушка Госпера. Она стреляет глайдерами с периодом 30, то есть каждые 30 ходов эволюции из пушки вылетает один глайдер.

Мы можем подсмотреть паттерн пушки в библиотеке паттернов и использовать его у себя:

// main.js

export const gliderGun = `
........................O...........
......................O.O...........
............OO......OO............OO
...........O...O....OO............OO
OO........O.....O...OO..............
OO........O...O.OO....O.O...........
..........O.....O.......O...........
...........O...O....................
............OO......................`;

const population = fromPseudoGraphics(gliderGun);
const drawer = new Drawer(10);
const world = new World(30, 40, population);

Проверим, работает ли пушка:

Пушка с периодом в 60

Обычная глайдерная пушка стреляет каждые 30 ходов. С этим уже можно работать, но нам лучше немного проредить потоки глайдеров.

Чем чаще стреляет пушка, тем больше глайдеров у нас будет на экране, и тем больше клеток нам придётся пересчитывать на каждый ход. На больших схемах (а сумматор будет большим) это может сильно ударить по производительности.

Мы можем решить проблему с плотностью глайдеров, если используем пушку с периодом в 60. То есть пушку, которая будет стрелять глайдером каждые 60 ходов. Добавим паттерн для пушки с периодом 60 и немного уменьшим масштаб клеток, чтобы всё вместилось:

// main.js

export const gliderGunP60 = `
............................O..........
............................O.O........
...........OO..................OO......
.........O...O.................OO....OO
...OO...O.....O................OO....OO
...OO..OO.O...O.............O.O........
........O.....O.............O..........
.........O...O.........................
...........OO..........................
.......................................
.......................................
.......................................
.......................................
.......................................
.......................................
.......................................
..........O.O..........................
.........O..O...OO.....................
OO......OO.....OOO.OO..OO..............
OO....OO...O...O...O...O.O.............
........OO.....O.O........O............
.........O..O..OO......O..O............
..........O.O.............O............
.......................O.O.......OO....
.......................OO........O.O...
...................................O...
...................................OO..`;

const population = fromPseudoGraphics(gliderGunP60);
const drawer = new Drawer(10);
const world = new World(60, 80, population);

Проверим, как пушка работает:

Отражатель и склеивание паттернов

Иногда нам будет нужно перенаправлять сигналы из глайдеров, поэтому ещё одна фигура, которая нам понадобится, — это рефлектор или отражатель.

Отражатель — это осциллятор, при столкновении с которым глайдер меняет своё направление. Добавим его на поле:

// main.js

export const reflector = `
........O
......OOO
.....O...
.....OO..
.........
.........
.........
.........
.........
.........
.........
OO.O.OO..
.........
O.....O..
.........
.OO.OO...
...O.....
.........
.........
.........
.........
...OO....
...OO....
`;

Теперь на поле хочется добавить также и глайдерную пушку, чтобы проверить, отражаются ли появляющиеся из пушки глайдеры. Проблема только в том, что функция fromPseudoGraphics сейчас принимает лишь один паттерн.

Чтобы решить задачу композиции паттернов, я написал отдельный модуль. Приводить полностью его код здесь не буду, исходники всегда можно найти на Гитхабе.

Суть этого модуля в том, что он проводит аффинные преобразования над фигурами с помощью функции withSettings. Эти преобразования помогают настроить расположение фигур на поле и направление сигналов пушек. Например, функция withSettings:

• перемещает фигуры по вертикали и горизонтали;
• вращает их относительно собственного центра;
• отражает относительно вертикальной оси.

А после применения преобразований этот модуль склеивает паттерны друг с другом с помощью функции composePatterns. Именно эту функцию мы и используем, чтобы совместить на поле отражатель и пушку:

// main.js

// Импортируем нужные фигуры:
import { gliderGunP60 } from './life/population/patterns/glider-gun-p60.js';
import { reflector } from './life/population/patterns/reflector.js';

// Импортируем композер и преобразователь:
import { composePatterns } from './composition/composer.js';
import { withSettings } from './composition/with-settings.js';

// Вращаем пушку на 270 градусов,
// зеркально отражаем рефлектор и «проматываем» его до 13-го хода.
const gun = withSettings(gliderGunP60, { rotate: 270 });
const reflect = withSettings(reflector, {
	reflect: true,
	phase: 13
});

// Составляем паттерны с некоторыми отступами от левого верхнего угла:
const population = composePatterns([
	{ pattern: gun, offset: { x: 38, y: 1 } },
	{ pattern: reflect, offset: { x: 9, y: 62 } }
]);

// Слегка уменьшаем масштаб:
const drawer = new Drawer(2);
const world = new World(200, 600, population);

Параметр phase функции withSettings указывает, с какого шага надо запустить фигуру. Чтобы глайдер влетел в отражатель и сменил направление, а не вызвал «взрыв», он должен влететь в нужное время и нужное место:

Если мы ошибёмся хотя бы на одну клетку или один ход эволюции:

// main.js

// Пусть отражатель работает не с 13-го хода, а с начала:
const reflect = withSettings(reflector, {
	reflect: true
	// phase: 13,
});

…Всё взорвётся:

Синхронизация по фазе и положению — вот что отняло у меня больше всего времени при подготовке в этому посту. Сперва приходилось вычислять значения перебором, потом — пытаться найти хоть какие-нибудь закономерности 😃

Я до сих пор не уверен, что точно понял, как именно надо располагать фигуры относительно друг друга в пространстве и времени, но часть объяснений оставил в исходниках на Гитхабе. Там же на Гитхабе можно посмотреть и другие паттерны и поиграться с ними.

Ну а теперь — к логическим гейтам!

Логические гейты

Логический гейт — это устройство, которое реализует логическую функцию. Такие функции принимают один или более входных сигналов и выдают в результате 0 (ложь) или 1 (истину).

Логические гейты будут основой более сложных схем типа полусумматора и сумматора. Мы создадим 4 базовые схемы: NOT, AND, OR и XOR.

Схема NOT

Самая простая схема — это схема функции отрицания NOT. Она преобразует входной 0 в выходную 1 и наоборот.

У любой логической функции есть таблица истинности. Такие таблицы содержат все возможные сочетания входных сигналов и соответствующие им результаты. Например, для функции NOT таблица истинности будет такой:

Мы будем использовать таблицы истинности, чтобы проверять правильность работы гейтов, которые напишем.

Гейт NOT — это инвертер. Если на входе есть сигнал, NOT его «нейтрализует», а если нет — то «сгенерирует». Мы можем для имитации этого поведения использовать пушку, которая будет стрелять глайдерами во входной сигнал.

Столкновение глайдеров может приводить к разным результатам, но нас интересуют те, которые уничтожают два столкнувшихся глайдера. Настроим «пушку-тактовый-генератор» так, чтобы она уничтожала входной сигнал, если он есть. Сигнал будет проходить слева, а пушка будет стоять справа:

// gates/not.js

const clockGun = withSettings(gliderGunP60, {
	rotate: 270
});

const signalGun = withSettings(gliderGunP60, {
	rotate: 270,
	reflect: true
});

const signal = { pattern: signalGun };
const clock = { pattern: clockGun, offset: { x: 38, y: 1 } };
export const not = composePatterns([clock, signal]);

Проверим, будут ли глайдеры сталкиваясь пропадать:

Если входного сигнала нет, то отразим поток из пушки. Отражённый поток и будет выходным сигналом:

// gates/not.js

const clockGun = withSettings(gliderGunP60, {
	rotate: 270
});

const redirection = withSettings(reflector, {
	reflect: true,
	phase: 13
});

const clock = { pattern: clockGun, offset: { x: 38, y: 1 } };
const router = { pattern: redirection, offset: { x: 9, y: 62 } };
export const not = composePatterns([clock, signal, router]);

Проверим, отражает ли рефлектор поток глайдеров:

Теперь если на входе 0, глайдеры из пушки не сталкиваются с входным сигналом, отражаются рефлектором и выходят как результат. А если на входе 1, глайдеры сталкиваются с входным сигналом и до выхода не доходят.

Нам осталось лишь сделать схему функцией, чтобы она могла принимать входной сигнал как аргумент:

// gates/not.js

export function not(input = 0) {
	// Если на входе 1, слева появится пушка входного сигнала,
	// если на входе 0, слева будет пусто:
	const signal = input ? { pattern: signalGun } : null;

	// Пушка «тактового генератора»:
	const clock = { pattern: clockGun, offset: { x: 38, y: 1 } };

	// Отражатель, который превратит
	// глайдеры из пушки справа в выходной сигнал:
	const router = { pattern: redirection, offset: { x: 9, y: 62 } };

	// Собираем всё вместе в начальную популяцию:
	return composePatterns([clock, signal, router]);
}

Полный код гейта NOT вы сможете найти на Гитхабе.

Схема AND

Следующий гейт — это логическое умножение AND. Эта функция принимает 2 входных сигнала и выдаёт на выходе 1, только если оба сигнала равны 1.

Таблица истинности функции AND будет такой:

Раз у нас два входа, то функция будет принимать два аргумента:

// gates/and.js

export function and(a = 0, b = 0) {
	const signalA = null;
	const signalB = null;
}

Для этой схемы нам нужно придумать такое расположение пушек, чтобы глайдеры доходили до выхода, только если два входных сигнала активны.

Я покумекал и придумал вот такую схему. Сигнал A стоит слева, сигнал B — правее, «тактовый генератор» самый правый на схеме. Они все настроены так, что столкновение глайдеров между ними приводит к уничтожению.

Если есть сигнал B, он уничтожает поток глайдеров из Clk, и на выходе будет то же, что и в сигнале A. Если сигнала B нет, то A уничтожится потоком из Clk. Таким образом выходной сигнал активен, только если оба входных сигнала активны.

Расположим элементы, чтобы собрать гейт:

// gates/and.js

const gunA = withSettings(gliderGunP60, {
	rotate: 270,
	reflect: true
});

const gunB = withSettings(gliderGunP60, {
	rotate: 270,
	reflect: true
});

const clockGun = withSettings(gliderGunP60, { rotate: 270 });
const collectorEater = withSettings(eater, { rotate: 270 });

export function and(a = 0, b = 0) {
	const signalA = a ? { pattern: gunA } : null;
	const signalB = b ? { pattern: gunB, offset: { x: 128 } } : null;

	const clock = { pattern: clockGun, offset: { x: 208, y: 1 } };
	const collector = { pattern: collectorEater, offset: { x: 76, y: 173 } };
	return composePatterns([clock, collector, signalA, signalB]);
}

Полный код гейта AND вы сможете найти на Гитхабе.

Графически схема AND обозначается как половинка скруглённого прямоугольника, в который входят два сигнала 😅

Мы будем пользоваться такими обозначениями при построении более сложных схем в будущем. Пока запомним, что это AND.

Схема OR

Следующий гейт — это логическое сложение OR. Эта функция также принимает два аргумента, но возвращает 1, если хотя бы один из аргументов равен 1.

Таблица истинности функции OR будет такой:

Расположение элементов для схемы OR я предлагаю сделать таким: за основу берём схему AND, но добавляем ещё один генератор — он будет создавать выходной сигнал. Его будет перебивать сигнал Clk, но только если ни A, ни B не активны.

Collector будет встречать глайдеры сигнала A и поглощать их, так как они сами по себе будут не нужны.

// gates/or.js

export function or(a = 0, b = 0) {
	const signalA = a ? { pattern: gunA } : null;
	const signalB = b ? { pattern: gunB, offset: { x: 128 } } : null;

	const clock = { pattern: clockGun, offset: { x: 208, y: 1 } };
	const output = { pattern: outputGun, offset: { x: 1, y: 45 } };

	const signalCollector = { pattern: collectorEater, offset: { x: 145, y: 161 } };
	const outputCollector = { pattern: collectorEater, offset: { x: 146, y: 206 } };
	return composePatterns([clock, output, signalA, signalB, signalCollector, outputCollector]);
}

Полный код гейта OR вы сможете найти на Гитхабе.

Графически OR обозначается как… ну… рыцарский шлем на боку?.. В общем, вот так выглядит:

Схема XOR

Последняя схема, которая нам понадобится — это исключительное (exclusive) сложение XOR. Эта функция работает, как OR, но возвращает 0, если оба сигнала равны 1.

Таблица истинности функции XOR будет такой:

Схема функции будет немного посложнее. Распишем разные сочетания сигналов, чтобы понять, как она работает. Когда на вход поданы 1 и 1, нам нужно уничтожить выходной сигнал. Расставим входные сигналы так, чтобы они друг друга уничтожали, а тактовый генератор — чтобы он уничтожал выход:

Когда на вход подан только первый сигнал, он уничтожает поток из тактового генератора, и выходной сигнал беспрепятственно проходит:

Когда на вход подан только второй сигнал, он отражается от рефлектора и уничтожает поток из тактового генератора. Выходной сигнал также беспрепятственно проходит к выходу:

Ну и если на входах 0 и 0, то тактовый генератор уничтожит выходной сигнал.

Реализуем схему:

// gates/xor.js

export function xor(a = 0, b = 0) {
	const signalA = a ? { pattern: gunA, offset: { x: 48, y: 2 } } : null;
	const signalB = b ? { pattern: gunB, offset: { x: 128, y: 1 } } : null;

	const clock = { pattern: clockGun, offset: { x: 168, y: 44 } };
	const router = { pattern: redirection, offset: { x: 56, y: 105 } };
	const output = { pattern: outputGun, offset: { x: 1, y: 87 } };
	return composePatterns([clock, router, signalA, signalB, output]);
}

Полный код гейта XOR вы сможете найти на Гитхабе.

Графически XOR обозначается как OR только с чертой перед входами:

И готово! Все логические гейты собраны. Я подготовил отдельные страницы на каждый гейт, чтобы можно было удобно посмотреть работу каждого в отдельности. Введите в поля входные сигналы, чтобы построить схему и посмотреть, как она работает:

• NOT
• AND
• OR
• XOR

В следующем посте

В этот раз мы реализовали 4 логические функции: NOT, AND, OR, XOR — которые будут строительными блоками для сложных схем.

В следующий раз из этих схем мы составим сперва двоичный полусумматор, полный сумматор, а потом и калькулятор, который будет складывать два двубитовых числа.

Ссылки и ресурсы

• Исходники
• «Калькулятор» двух бит
• Создание схемы по шагам

Другие посты из серии

• Первая часть: пишем основы игры «Жизнь»
• Третья часть: реализуем схемы сумматоров

Бинарная логика, CS

• Let’s BUILD a COMPUTER in CONWAY’s GAME of LIFE
• The 10,000 Domino Computer
• Код. Тайный язык информатики. Чарльз Петцольд
• Аффинные преобразования

Бинарная логика в игре «Жизнь»

• Conway’s Game of Life, PDF
• Turing machine in the Game of Life
• Digital Logic Gates on Conway’s Game of Life

Библиотеки паттернов

• RLE, Run Length Encoded
• Life Lexicon

Глайдеры, столкновения

• Глайдер
• Глайдер на Life Lexicon
• Глайдер на Conwaylife.com
• Глайдер в формате RLE
• Столкновение глайдеров

Другие фигуры

• Космические корабли
• Пушки
• Глайдерная пушка Госпера
• Пушка Госпера на Conwaylife.com
• Пушка с периодом 60 на Life Lexicon
• Отражатель на Life Lexicon

Логические гейты в Википедии

• Таблица истинности
• NOT
• AND
• OR
• XOR