Наверняка всем вам знаком бессмертный хит мобильных телефонов — игра «Змейка». В наш век процессоров и микроконтроллеров любой, даже начинающий программист сможет моментально написать эту игру на своём любимом языке/платформе. А что, если у нас есть пачка логических элементов и никаких микропроцессоров? Можно ли создать такую игру, используя только логические элементы?
Конечно, да! На помощь к нам придут конечные автоматы, минимирование логики, смекалка и программа-симулятор Logisim.

Вот такой вот интересный монстр получился. Давайте разберёмся как оно работает: у нас есть экран, подключённый к специальному массиву памяти, где за каждым пискселем стоит 1 бит состояния (памяти) — пиксель или горит, или нет.
Особенность этого массива в том, что мы можем с помощью специальных входов адресации (ROW,COL) выбрать нужный нам пиксел и сделать следующее: считать его значение(Out), зажечь(Set) и погасить(Reset).
Внутри эта «видеопамять» выглядит так (конечно же всё «размножено» 8х8):


Выход RS-защёлки напрямую подключен к пикселу, а три управляющих сигнала(o,s,r) «подключаются» тогда, когда линия выбора ряда и столбца сойдутся вместе.

Ещё раз схема, теперь с обозначенными областями:


Для нашего алгоритма важны 3 игровых элемента — голова змеи, хвост и еда. Все эти положения хранятся в специальных кольцевых сдвиговых регистрах (красная область), которые к началу игры инциализируются со значением 10000000. При подаче сигнала «clk» — значение единица в регистре сдвигается вправо. Если подать 2 сигнала «clr» и «dir» одновременно, то единица сдвинется налево.
Таким образом, положение ячеек управляющий автомат может изменять достаточно просто — управляя контрольными сигналами. В жёлтой области находится логика сравнения — когда значение регистров от еды и головы совпадают — на вход автомата подаётся 1, это означает, что голова «наехала» на еду, т.е змейке пора расти. Как конкретно работает алгоритм, разобраться нам поможет следующая диаграмма состояний/переходов.
Синим обозначены входы в автомат, в нашем случае 2 бита: левый — значение пиксела(Out) и правый — змейка съела еду.



Начинает система с состояния 1. К этому моменту экран чист, а все 3 регистра указывают на одну ячейку.
В этом состоянии следующие сигналы подаются на систему:
1. Подключить указатель головы к экрану.
2. Сохранить текущее направление.
3. Зажечь пиксел.
4. Заблокировать управление (зачем надо, разберёмся позже).

Т.к в начальном цикле состояния регистров были одинаковые, мы переходим к состоянию 2. Тут система генерирует положение новой еды до тех пор, пока не попадёт на свободную ячейку. Выходы:
1. Подключить указатель еды к экрану.
2. Сгенерировать новое значение (фиолетовый блок: генератор случайных чисел — напрямик подключён к сигналам clr,dir,clk,dir указателей столбца и строки для еды).

Если мы нашли пустую ячейку, то на входе автомата будет 00, и мы перейдём в состояние 3:
1. Подключить указатель еды к экрану.
2. Зажечь пиксел.

Далее входы системы нас не волнуют (dc — don't care), и мы переходим к состоянию 4:
1. Подключить указатель головы к экрану.
2. Заблокировать управление (так как в следующем состоянии мы должны сохранить направление, оно не должно поменяться за время перехода состояний. Чтобы избежать ошибочной ситуации, управлние блокируется).
3. Поднять указатель памяти для головы, зачем это — расскажу позже.
4. Обновить положение головы. К сдвиговым регистрам головы подключается определённая комбинация из сигналов (clk,dir,clk,dir), чтобы новая ячейка головы указывала на следующую по текущему направлению:
шина с номером направления идёт прямиком от блока управления игрока (тёмно-розовый) и декодируется в нужную комбинацию простой комбинаторной логикой (верхний розовый блок).
Блок управления очень прост: двухразрядный счётчик с кнопками +1 (налево) и -1 (направо). Вверх 00, Влево: 01, Вниз: 10, Направо: 11.

Если новое положение головы попало на тело змейки, то вход в автомат будет 10 и система перейдёт в состояние 7, в котором просто ничего не будет происходить (вы проиграли).
Если нет — мы переходим в положение 1, так как змейка, допустим, ничего не ела, то вход в систему будет 10 -> переходим в состояние 5.
Выходы:
1. Подключить указатель хвоста к экрану.
2. Убрать пиксел.
3. Поднять указатель памяти для хвоста. Вот тут самое интересное: алгоритм построен так, что мы при движении змейки ставим голову и убираем хвост. Затем мы назначем хвостом новую ячейку тела.
Но чтобы знать, в каком направлении эта ячейка находится, мы сохраняем каждый раз направление движения. Выходит, каждый элемент змейки «указывает» на следующий.

Переход в состояние 6:
1. Подключить указатель памяти для хвоста к самой памяти, и отключить указатель для головы (по умолчанию всегда подключен указатель для головы).
2. Обновить положение хвоста — сохранённое направление будет считано из памяти и с помощью аналогичного блока комбинаторной логики (розовый) и будет декодировано в комбинацию из clk,dir,clk,dir для хвоста.
И мы возвращаемся в состояние 4.

Зачем писалась эта статья? Мне хотелось показать, что как и в любом другом деле, ограничения подталкивают к креативности мышления. Именно поэтому, допустим, полезно кодить на эзотерических языках программирования или ассемблере. Удачи.

Видео в студию:

Источник