[Из песочницы] Игра «Жизнь» на логических элементах
Заранее предупрежу: довольно много картинок.
В данной статье речь пойдёт о реализации игры «Жизнь» на логических элементах в симуляторе «Atanua».
Игра «Жизнь» является, пожалуй, одним из самых узнаваемых клеточных автоматов. Про неё написано не одна статья, в том числе и на Хабрахабре. Когда-то тоже заинтересовался ей, но как-то надолго не хватило.
- Клетка оживает, если в её окрестности имеются 3 живые клетки.
- Клетка продолжает жить, если в ёе окрестности живы 2 или 3 клетки.
- В иных случаях клетка умирает.
Окрестностью клетки считаются 8 окружающих её клеток (см. двумерная окрестность Мура порядка 1).
Подробнее о «Жизне» можно узнать в Википедии.
Позже услышал где-то, что современные компьютеры имеют ограничение в скорости вызванное, в том числе и наличием некоторого канала связи между памятью и вычислительным ядром. В качестве решения предлагалось собрать считающую память. Я уже точно не помню, то ли я сам вспомнил про «Жизнь», то ли она упоминалась в той статье, но я захотел смоделировать её в логической схеме (если быть точным, то в матрице одинаковых схем). Почему именно «Жизнь»? Основными причинами были её распространённость и известность, а также тот факт, что «вселенные» в ней полны по Тьюрингу, что позволяет производить на ней любые вычисления и решать разнообразные задачи. Получается, на основе данного клеточного автомата можно создать компьютер.
В качестве инструмента был выбран симулятор Atanua (официальный сайт), так как довольно лёгкий в освоении и отображает состояние всех линий. В конечном итоге получилось следующее:
Одной удобной особенностью симулятора «Atanua» является то, что можно подключать схемы как, своего рода, микросхемы в другие проекты. Этим я и воспользовался, собрав матрицу для отладки и экспериментов.
Для более подробного рассмотрения левый верхний угол:
Кнопка «r» используется для сброса схемы. Кнопки, подписанные как »0», используются для установки ячейки в живое состояние. Хочу заметить, сброс повторным нажатием пока не реализован. 3 нижних заземления используются как ограничители схемы, чтобы не появлялось разнообразных артефактов. В Atanua провод может иметь 4 состояния:
- тёмно-зелёный: лог. 0;
- светло-зелёный: лог. 1;
- красный: не правильно подключён;
- белый: не подключён (неопределённое состояние).
При этом, если на вход логического элемента подано неопределённое состояние, то некоторые могут распознать его как 0, а некоторые как 1. Для этого и были поставлены ограничители в виде установки неиспользуемых выводов в 0.
На верхнее заземление не обращайте внимания. Первоначальный вариант схемы требовал инициализации, для чего этот выход и использовался. В настоящее время — это рудимент (чтобы не переделывать матрицу), и его состояние может быть любым. Ещё один провод, уходящий за край рисунка — это вывод тактового сигнала. Он идёт к набору генераторов, на которых тестировал максимальную скорость.
Теперь поподробнее о схеме ячейки. Из-за проблем с качеством скриншотов, я буду давать рисунки отдельных узлов.
Регистр
На рисунке выше представлен 2-х разрядный зацикленный сдвиговый регистр на D триггерах, который выступает в роли памяти. С ним связан один не хороший момент, который мне ещё предстоит поправить: во время работы схема как бы мигает, так как в активном состоянии (когда в данный регистр записана информация, то есть в состоянии живой клетки) триггеры обмениваются между собой 0 и 1 и получается, что на выходе F (выход на индикацию состояния, на светодиод например) имеем то 0, то 1 (это заметно на видео в конце статьи). RST — это вход сброса. SET — вход установки ячейки в состояние живой клетки. Как уже упоминалось, сброс отдельной ячейки пока не предусмотрен. Слева сверху подходит тактовый сигнал. О соседних двух проводах далее.
Блок проверки
В блоке проверки осуществляется проверка на условие игры. Сверху на рождение, снизу на выживание. Особенность данного блока состоит в том, что его можно подстроить и под другие правила, тем самым организовав аналогичные клеточные автоматы. Слева подходят выходы с сумматоров, снизу — те самые два провода, которые идут к регистру. Они, по сути, подсоединяются в разрез одной из передаточных линий регистра.
Сумматоры
Пожалуй, самой большой и противоречивой частью схемы являются параллельно-последовательно подключенные сумматоры. Реализовав его, я решил проблему проверки необходимых условий «в лоб», просуммировав все входы A0-A7 от соседних ячеек и проверив результат на соответствие условиям. В данном случае суммируются сначала входы A0+A1+A2, A5+A6+A7, потом результат второй суммы выводы A3 и A4 и так далее. В конечном итоге получилось в конечном итоге 6 сумматоров и 1 полусумматор. Стоит отметить один из сумматоров можно также заменить на полусумматор, т.к. один из его входов не используется. Зачем я сделал один заземлённый вход (слева снизу тёмно-зелёный уходящий за пределы рисунка) — не помню. Изначально хотел её упростить при помощи ДНФ или КНФ, но решать карту Карно 8×8 желания пока не возникает. Так что не исключаю, того момента, что этот модуль может иметь альтернативный вид.
C — это вход таковой частоты, к схеме сумматоров отношения не имеет, идёт к регистру. Про Init я писал выше — рудимент от прошлого варианта.
Итог
Я не считаю игру «Жизнь» достойным клеточным автоматом для реализации считающей памяти, так как «программа» для такого компьютера займёт довольно много места и сложна в реализации. Но всё же схема позволяет по мечтать о микросхеме с реализацией ячеек этой игры. Думаю это было бы довольно интересно, увидеть аппаратную реализацию данного клеточного автомата. Причём я имею ввиду не микроконтроллеры с программой, а исключительно на ячейках из логических элементов.
Что же касается схемы, в ней конечно хватает недоработок, но для экспериментов вполне хватает. Буду ли её дорабатывать? Честно говоря, не знаю, как душа ляжет.
Напоследок несколько видео с работой:
Планер:
Малый корабль:
Уместился и пентадекатлон:
Файлы с проектом на Google Drive.
Некоторое пояснение по содержимому:
live.atanua — ячейка;
LiveFieldM.atanua — матрица;
LiveField.atanua — небольшой элемент матрицы (8×8) из которых создавался LiveFieldM. Края не заземлены.
Для обнаружения сложить в одну папку. Если не поможет, отредактируйте файлы в любом текстовом редакторе (по структуре, обычные XML).
