Тетрис для DCPU-16

Как уже писали на Хабре, разработчик широко известного в узких кругах Minecraft'а Маркус «Notch» Перссон в данный момент занят разработкой новой игры, действие которой будет происходит в космосе в 281 474 976 712 644 году.

Как и Майнкрафт, игра будет нестандартной: главная «фишка» — полностью эмулируемый процессор, под управлением которого космические корабли и будут бороздить просторы Большого… э, Вселенной. Поскольку персонажи игры в год 0x10^c (игра, собственно, так и называется) попали прямиком из 1980 года, то и процессор DCPU-16 по своим характеристикам примерно соответствует той эпохе: 128 килобайт оперативной памяти, 100 мегагерц, нехитрый набор команд.

Несмотря на то, что игра находится еще в очень ранней стадии разработки, спецификация процессора уже доступна для ознакомления — и уже формируются сообщества, участники которых разрабатывают множество всяких интересных штук под несуществующую платформу. Ваш покорный слуга — в числе этих людей, и в этом посте я хочу рассказать об одной из таких вещей: реализации Тетриса для DCPU-16.

Подробно о «внутренностях» DCPU-16

Итак, о чем говорит спецификация? О том, что процессор будет 16-битным (про байты можно забыть — обращение производится только к двухбайтовым словам), в нашем распоряжении 12 регистров (3 из них — SP, PC и O — служебного рода), памяти ровно 65535 слов (то есть 128 килобайт), 15 базовых и 1 дополнительный опкод, инструкции занимают от 1 до 3 слов, все это будет эмулироваться с частотой порядка 100 тысяч тактов в секунду (число тактов, как положено, зависит от опкода и того, делается ли обращение к памяти).

Базовые опкоды нехитры — присвоение, арифметика (дробные числа представляются только с фиксированной точностью, 16 бит после запятой — они попадают при делении в регистр переполнения, O), битовые операции, проверки условий. Нет переходов, обратите внимание: они делаются с помощью непосредственно присвоения значений регистру PC (как нетрудно догадаться, он указывает, на инструкцию, которая будет выполнена следующей). Проверки условий просто пропускают следующую инструкцию, если условие не выполняется — условные переходы делаются совмещением проверки и обычного перехода. Единственный не-базовый опкод — для вызова подпроцедур, кладет адрес возврата на вершину стэка и делает переход на указанный адрес.

С операндами интересно: кроме обычных регистров, памяти по заданному адресу, памяти по адресу + значению регистра и непосредственно заданных значений, есть специальные значения POP, PEEK и PUSH (да — это не операции, а операнды!), которые во-первых позволяют обращаться к вершине стека (вообще говоря, напрямую обратиться к памяти, на которую указывает служебный регистр, нельзя), и, во-вторых, при этом уменьшать или увеличивать значение SP на единицу. В результате с помощью SET PUSH, X можно положить значение в стэк, SET X, POP — забрать его оттуда, и SET X, PEEK — скопировать значение, не забирая его со стэка. Правда, становятся допустимы странные конструкции типа SET X, PUSH; SET POP, X и даже SET POP, PUSH. Понять, что они делают, уже не очень тривиально.

Наконец, о памяти. Выше уже упоминался стэк — поскольку при инициализации все регистры равны 0, он начинается с 0xFFFF (первый PUSH сначала уменьшит SP на единицу, а только затем запишет значение) и растет вниз. Кроме того, стало известно, что по адресу 0x8000 находится видеобуфер — дисплей содержит 12 строк по 32 символа, в памяти он лежат построчно, каждое слово соответствует одному символу. Правда, к сожалению, из 16 бит всего 7 младших ушли на код символа — 8-й бит отвечает за мигание, следующие 4 — за цвет фона и самые старшие 4 — за цвет символа. Цветов 24, используется палитра CGA (RGBI).

Кроме доступа к дисплею, есть и возможность читать символы с клавиатуры: для этого предназначен циклический буфер по адресу 0x9000 размером в 16 байт. Чтобы буфер работал, нужно хранить указатель на следующий символ — как только значение в памяти станет отличным от нуля, его нужно считать, записать 0 и увеличить указатель на 1 (при достижении 0x9010 сбросить его на 0x9000). Нотч привел собственный пример, иллюстрирующий все это.

Наконец, по последним данным, для вывода на экран можно задать собственный набор символов — он находится по адресу 0x8180 (сразу после видеобуфера), каждое слово описывает одну литеру размером 4x8 пикселей, каждый байт соответствует одному столбцу.

Эмулятор на JavaScript

Устройство DCPU-16 довольно незамысловато, да и производительность его невысока — поэтому я решил написать для него онлайновый эмулятор на JavaScript. Конечно, в этой задумке я не был одинок — сейчас таких эмуляторов уже огромный ворох, но какого ненормального программиста это останавливало?

В результате получилась вот такая штука:

http://dcpu.ru/

Собственно, это не просто эмулятор, а шампунь «три в одном» — ассемблер, эмулятор и в довесок дизассемблер. Умеет почти все из описанного выше, кроме собственной таблицы символов. Зато при отладке красиво подсвечивает текущую строчку, а при ассемблировании умеет такую забавную штуку, как вычисление выражений. Думаю прикрутить еще макросы, в ассемблере от Нотча это есть.

Ну да не о нем речь. Заканчиваю лирические отступления, перехожу к теме статьи.

Тетрис

Как все знают, Тетрис был изобретен Алексеем Пажитновым в 1984 году. Создатель — мой соотечественник, игра создана практически для компьютеров того же уровня, что и DCPU-16 — что могло лучше подойти для реализации?

Вкратце о коде. Про возможность переопределения символов я еще не знал, поэтому решил рисовать обычными символами: два закрашенных пробела подряд — одна клетка. Каждую фигуру (в любом из 4 поворотов) можно вписать в квадрат 4x4 клетки, всего фигур 7 — итого 28 состояний по 16 слов (я решил хранить непосредственно те коды, которые будут записываться на экран, но удваивать их только при выводе). Все это свалено в кучу в конце программы.

Написал несколько подпроцедур. Например, для вывода строчек на экран (их там немного, «Score:», «Level:», «GAME OVER»), для чтения символа с клавиатуры, или вот — генератор псевдослучайных чисел:

:next_rand                ; takes no arguments, returns random word in A
  MUL [rand_seed], 10061
  ADD [rand_seed], 1
  SET A, [rand_seed]
  SET PC, POP
:rand_seed
  DAT 0xC00F

В общем-то стандартная реализация линейного конгруэнтного метода (LCG). Простое число 10061 взял наугад — готов принять поправки, если у кого-то есть лучшая кандидатура. В любом случае, у нас тут никакой криптографии нет, заботиться об особой «рандомности» не нужно. Вроде выкидывает разные фигурки, и слава богу. Начальное зерно rand_seed инициализируется следующим образом: при запуске в цикле значение увеличивается до тех пор, пока пользователь не нажмет какую-нибудь клавишу. Говорят, в старых играх «Press any key» тоже было как раз для этого, кстати.

Наконец, самая хитрая подпроцедура, которая умеет и стирать с экрана фигурку, и отрисовывать её, и проверять возможность её размещения:

:show_cur_piece           ; display/clear/check current piece (A=0 - clear, A=1 - display, A=2 - check), if A=2 doesn't actually place anything, return B=1 is position is valid, 0 otherwise
  SET X, [piece_pos]      ; place block at [X] (display)
  SET Y, [cur_piece]      ; ...from [Y] (pieces array)
  SHL Y, 2
  BOR Y, [cur_rot]
  SHL Y, 4
  ADD Y, pieces
  SET I, 0                ; index
:piece_cyc1
  SET B, [Y]
  IFE B, 0
    SET PC, piece_jmp1
  IFG 2, A
    SET PC, piece_jmp2
    IFG X, 0x8000 + 32*12
      ADD PC, 3
    IFE [X], 0
      SET PC, piece_jmp1
    SET B, 0
    SET PC, POP
:piece_jmp2
  IFE A, 0
    SET B, 0
  SET [X], B
  SET [X + 1], B
:piece_jmp1
  ADD I, 1
  ADD X, 2
  ADD Y, 1
  SET B, 1
  IFE I, 16
    SET PC, POP
  IFB I, 3
    SET PC, piece_cyc1
  ADD X, 32 - 8
  SET PC, piece_cyc1

Как видно, все проверки делаются прямо «на месте» — в видеобуфере. Это, конечно, имеет небольшой негативный эффект — при смещении фигурки, её нужно сначала стереть, затем попытаться поставить на новом месте и если это не удалось сделать — отрисовать снова на старом. Из-за стирания происходит небольшое смаргивание, но скорость работы получилась достаточной, чтобы оно было малозаметным. Собственно, прежде чем фигурка сдвинется на одну клетку ниже, успевает отработать порядка 2500 итераций (на каждой проверяется наличие клавиши в буфере и фигура поворачивается или смещается влево/вправо) на первом уровне, 2000 на втором, 1500 на третьем — и так далее.

Про самый вложенный цикл я упомянул, но он обернут в еще два — если фигурку уже не удается сдвинуть вниз под действием гравитации, делается проверка на наличие полностью заполненных рядов, они уничтожаются, выбирается новая фигура (на самом деле, она выбирается заранее и рисуется в поле «Next:», а тут делается выбор «на шаг вперед») и бросается в стакан сверху. Если бросить не удается — завершается и внешний цикл, и рисуется красивая мигающая надпись «Game Over».

Проверка заполненных рядов идет снизу вверх, используются два указателя на текущую «записываемую» и текущую «читаемую» строчки. Сначала поднимается «читаемая» до тех пор, пока не дойдет до самого верха или не встретит незаполненный ряд. Затем из «читаемой» клетки копируются в «записываемую» и обе увеличиваются на 1. Пара оптимизаций: копирование не происходит, если оба указателя соответствуют одной строке, попытки поднять «читаемую» строчку прекращаются, если она уже на самом верху или если количество уже стертых строк стало равно 4 (за один раз больше уничтожить нельзя). В результате работает довольно быстро, жить можно.

:scan_lines                   ; search for complete lines, remove them and move all other down; update score & level
  SET A, 0x8000 + 32*11 + 11  ; start of next line to fill
  SET B, A                    ; start of next line to check
  SET J, 0                    ; num of lines skipped
:scan_cyc2
  SET I, 0                    ; horizontal index
  SET X, B
:scan_cyc1
  IFE [X], 0
    SET PC, scan_jmp1
  ADD X, 2
  ADD I, 1
  IFG 10, I
    SET PC, scan_cyc1
  ADD J, 1                    ; no gaps found, increase num of complete rows
  SUB B, 32
  IFE J, 4
    SET PC, scan_jmp1
  IFG B, 0x8000
    SET PC, scan_cyc2
:scan_jmp1                    ; found a gap, or no more gaps can be found
  IFE A, B
    SET PC, scan_jmp2         ; no need to move anything, continue
  SET I, 0
:scan_cyc3
  SET [A], [B]
  ADD I, 1
  ADD A, 1
  ADD B, 1
  IFG 20, I
    SET PC, scan_cyc3
  SUB A, 20
  SUB B, 20
:scan_jmp2
  SUB A, 32
  IFG 0x8000, A
    SET PC, scan_end
  SUB B, 32
  IFE J, 4
    SET PC, scan_jmp1
  IFG 0x8000, B
    SET PC, scan_jmp1
  SET PC, scan_cyc2
:scan_end
  IFE J, 0
    SET PC, POP
  ADD [lines], J
  SET J, [lines_score + J]
  MUL J, [level]
  ADD [score], J
  JSR update_score
  IFG 10, [lines]
    SET PC, POP
  SET [lines], 0
  ADD [level], 1
  JSR update_level
  SET PC, POP

Полностью исходник доступен тут, чтобы запустить его — найдите кнопку "Run in the dcpu.ru emulator", а уже там — кнопку "Run".

Ссылки

• Официальный сайт игры
• Официальная спецификация DCPU-16
• Подреддит, посвященный игре 0x10^C, а также посвященный DCPU-16
• Официальный форум, посвященный игре
• Вики, посвященная игре
• Каталог ассемблеров, эмуляторов, дизассемблеров и прочих инструментов
• Каталог программ для DCPU-16
• Мой эмулятор/ассемблер/дизассемблер DCPU-16
• Исходник моего «Тетриса» для DCPU-16

Автор: deNULL