Саша Беспоясов
Это я.

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

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

В этом посте познакомимся с распространёнными фигурами из игры, научимся генерировать «сигналы» и создадим логические схемы 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 ходов эволюции из пушки вылетает один глайдер.

Пушка стреляет глайдером каждые 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);

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

Каждые 30 ходов пушка стреляет глайдером

Пушка с периодом в 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);

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

Каждые 60 ходов пушка стреляет глайдером

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

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

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

// 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 таблица истинности будет такой:

ANOT A
01
10

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

Гейт 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 будет такой:

ABA AND B
000
010
100
111

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

// 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
Графическое обозначение функции AND

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

Схема OR

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

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

ABA OR B
000
011
101
111

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

Расположение сигналов и выхода на схеме OR
Расположение сигналов и выхода на схеме OR

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 обозначается как... ну... рыцарский шлем на боку?.. В общем, вот так выглядит:

Графическое обозначение функции OR
Графическое обозначение функции OR

Схема XOR

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

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

ABA XOR B
000
011
101
110

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

Если на входе 1 и 1, на выходе 0
Если на входе 1 и 1, на выходе 0

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

Если на входе 1 и 0, на выходе 1
Если на входе 1 и 0, на выходе 1

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

Если на входе 0 и 1, на выходе 1
Если на входе 0 и 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 только с чертой перед входами:

Графическое обозначение функции XOR
Графическое обозначение функции XOR

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

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

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

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

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

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

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

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

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

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

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

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

Допиливаем двоичный сумматор в игре «Жизнь» до концаПишем двоичный сумматор в игре «Жизнь» на JavaScript