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

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

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

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

    (и сразу дисклеймер: музыка в ролике наложена отдельно для художественной, так сказать, выразительности; DCPU пока выводить звук, увы, не позволяет)


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


    Итак, о чем говорит спецификация? О том, что процессор будет 16-битным (про байты можно забыть — обращение производится только к двухбайтовым словам), в нашем распоряжении 12 регистров (3 из них — SP, PC и O — служебного рода), памяти ровно 65536 слов (то есть 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 — за цвет символа. Цветов 16, используется палитра 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".

    Ссылки




    P. S. Да, не могу не похвастаться — сам Notch положительно оценил результат всех вышеописанных стараний :)
    Поддержать автора
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 43

      +4
      Музыку в ролик вставлять — читерство.
      Ай-ай-ай.
        +3
        Ну кому бы было интересно смотреть ролик в неловкой тишине :)

        А как DCPU начнет поддерживать вывод звука — можно будет попробовать и мелодию в игру добавить.
          +2
          Я инстинктивно дернулся читать код, как выводится музыка.
          После запуска игры на двух эмуляторах успокоился.
          Нельзя так, люди ж читают, интересуются.
            +1
            Ох. Добавил пояснение в пост, чтобы больше никого не обескураживать :)
        +7
        Чувствую лет через 10 можно будет в резюме писать «прокачал программиста 80 лвл в 0x10c»
          0
          Почему до сих пор поделки для DCPU-16 делаются на ассемблере?
          Ни у кого руки не дошли до компилятора С, например?
            –1
            Тут наверно лучше подойдёт Forth, нежели чем C.
              +1
              не объясните человеку несведущему в forth чем он так хорош?
                0
                Простота написания форт-машины по сравнению с компилятором C, производительность, расширяемость. Например, вкратце можно почитать тут или вот эту статью на хабре.
                Сам я тоже спецом не являюсь, всего лишь учу потихоньку, так что аргументированно отстаивать позиции форта не смогу.
                  0
                  Я тоже мало знаком с Forth, но он же вроде как стэковый, нет? Его можно действительно эффективно компилировать в код, работающий в первую очередь с регистрами?
                    0
                    Вот тут, к сожалению, не могу ничего сказать конкретного. Но попытки написать форт-машину под DCPU-16 тем не менее уже имеются, что наверно говорит о том что с производительностью у неё в теории всё нормально.
                      +1
                      ; использование аппаратного стэка для данных - 6 циклов (почему-то операции со стэком стоят 0 циклов  по спеке, хотя логично должно быть 2 минимум для PUSH и POP и 1 для PEEK)
                          SET A, POP   ;1+1+0
                          DIV PEEK, A ;3+0+1
                      
                      ; использование "виртуального" стэка, Z - указатель, 8 циклов
                          DIV [1+Z], [Z] ; 3+1+1
                          ADD Z,1 ; 1+1+1
                      
                      ; использование переменных в памяти - 5 циклов
                          DIV [0x1000], [0x1001] ;3+1+1
                      


                      Проигрыш минимален и вполне допустим, имхо. А в каких-то ситуациях будет выигрыш, например умножение на 2: ADD PEEK, PEEK — 1 цикл, ADD [0x1000], [0x1000] — 3 цикла
                        0
                        ADD стоит столько же, сколько MUL и SHL — 2 цикла. 1 цикл — только на битовые операции и на SET. Но со стеком будет заметный проигрыш при обращении к «глубоким» ячейкам: SET [1+X],[2+X] занимает 3 такта, поскольку смещения записаны в отдельных словах программы.

                        SET A, POP ;1
                        DIV PEEK, A; 3 ;;; 4 такта, 2 слова

                        DIV [1+Z], [Z]; 4
                        ADD Z,1; 2 ;;; 6 тактов, 3 слова

                        DIV [0x1000], [0x1001]; 5 тактов, 3 слова

                          0
                          Упс, невнимательно спеки читал. Но всё равно, по-моему, качественного преимущества нет у «классического» подхода.
                      0
                      Вы привели ссылки по истории языка, а хотелось бы видеть ссылки на учебники, туториалы и т.п. Впрочем, лично я весьма скептически отношусь к Forth. Многие ругают Perl, называя его write-only языком — они ещё код на Forth не читали. Аргументы фортеров про простоту написания компилятора смехотворны: говоря метафорично, программисту обычно нужен рабочий парашют, а не возможность шить парашют в процессе падения. Делать компиляторы — удел спецов, нормальным людям нужно задачи решать. А выразительные средства Forth (если такие есть) этому не способствуют.

                      Я бы очень хотел увидеть пример чистого и понятного кода на Forth, но никто из встречавшихся в сети фортеров так мне его и не дал. Честно говоря, код на ассемблере мне кажется более понятным и приятным глазу.
                        +1
                        Вопрос был почему по моему мнению форт лучше C подходит для создания «высокоуровневого» языка на DCPU-16, посему и были даны ссылки на описания языка, а не учебники. Если же вам интересно введение в язык, то можете например начать отсюда. Там же приведены примеры читаемого кода, например мы можем оперировать размерностями словно у нас естественный язык:
                        254 10        UNITS INCHES
                        254 12 *  10  UNITS FEET
                        254 36 *  10  UNITS YARDS
                        10  1         UNITS CENTIMETERS
                        1000  1       UNITS METERS
                        
                        10 FEET 3 METERS + 
                        

                        Выдаст результат в миллиметрах сложения 10 футов и 3 метров, кроме того мы можем преобразовывать величины обратно:
                        3048 AS FEET

                        Или например код управления роботом может иметь вид:
                         2 TIMES   LEFT EYE  WINK


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

                    We heard you like compilers so we put a compiler in your compiler so you can compile while you compiling!
                      0
                      А может ли кто-нибудь с абсолютной точностью сказать, что всё происходящее — реально?
                      Что, например, этот комментарий написан не только в моём сознании?
                        0
                        Все происходящее — результат симуляции на суперкомпьютере, которого вообще не существует — ни в этой Вселенной, ни в другой, ни самого по себе. Так что все реально :)
                          0
                          физики вроде как считают что нет ничего настоящего.
                          0
                          Тут скорее надо кросскомпиляцию — оперативки маловато, внизу в комментах про llvm пишут, для gcc я думаю тоже кто-нибудь бэкенд сделает ;)
                          0
                          Есть lisp-dcpu с ограничениями.
                            +2
                            Работы ведутся, как говорится.

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

                            Знаю, что вот тут другим нашим соотечественником ведется разработка LLVM для DCPU.
                              0
                              По-моему даже неоптимизирующая компиляция Си или Си-подобного языка (все переменные «статические», никаких куч и прочей динамики) не сильно хуже ассемблера будет для данной архитектуры, где нет разницы по времени доступа к регистру, памяти им адресуемой, литералу, памяти, адресуемой литералом. Всё один цикл.
                                0
                                Да, но памяти очень мало. И скорость почти пропорциональна длине исполняемого кода. А любое обращение к переменной в глубине стека или в общей памяти — лишний такт.
                                По Z80 я помню, что какой-то C-компилятор (единственный, который был доступен — не помню, чей) давал код в 3 раза длиннее, чем результат ручной компиляции. Хотя, конечно, времена изменились, и компилятор может работать на заметно более мощной машине :)
                                  0
                                  Я специально написал «неоптимизирующий», имея в виду кросскомпиляцию на каком-нибудь i5 :)
                                    0
                                    Насчет «скорость пропорциональна длине, я, конечно, неправ. И постоянно стоит вопрос, что сейчас важнее — слова или такты. Какой-нибудь memset можно написать так, что он займет 7 слов и 7 тактов на элемент массива, а можно — в 21 слово и 1.4 такта на элемент. И иногда память важнее (например, в boot-секторе, если будет такое понятие).
                                +1
                                По моему, по приведенной в статье ссылке на девелопертулзы куча компиляторов Це, Це-решеток и даже куВасик есть.
                                +4
                                Знаете, я вам завидую. Судя по всему у вас просто дохрена времени.
                                  0
                                  А Вы не планируете добавить макросы? Эмулятор и ассемблер у Вас хороший, только макросов очень не хватает.
                                    0
                                    Я, в общем-то, даже в статье упомянул, что определенно планирую :)
                                      0
                                      sorry, сразу полез в эмулятор свои программы пробовать :-)
                                        +1
                                        Пять, пожалуй, основных вещей, которые собираюсь реализовать:

                                        • Более «правильный» вывод на экран (цвета, шрифты)
                                        • Макросы
                                        • Сохранение/загрузку исходников и скомпилированного кода (хотел быстро это сделать, но понял, что придется прикручивать флэш, чтобы все работало только на клиенте, и немного притормозил)
                                        • Какую-никакую подсветку синтаксиса (наверняка легко прикрутить готовое решение, но хочется самому с этим поразбираться)
                                        • В эмуляторе — более комфортную работу с текущим содержимым памяти (сейчас там очень печальная прокрутка, а еще хочется сделать возможность посмотреть содержимое ячеек в разных системах счисления и менять их)

                                        Ну и, конечно, когда Нотч обновит спецификации (а он вроде обещался прислушаться ко всем отзывам сообщества) — адаптироваться к ним.
                                          0
                                          Сохранение/загрузку исходников и скомпилированного кода (хотел быстро это сделать, но понял, что придется прикручивать флэш, чтобы все работало только на клиенте, и немного притормозил)


                                          Пока вполне достаточно и localStorage обойтись. Но такими темпами на за горами тот день, когда на одном из подобных сайтов прикрутят git-репозитории для приложений и github hooks: )
                                            0
                                            Кстати, github уже включил DCPU-16 asm в список официальных языков, недавно здесь писали :)
                                            +1
                                            Кстати, Вы чистые скан-коды шлете в программу? Судя по тому, что при нажатии на точку (0x2E) приходит 0xBE… Может, правильнее было бы слать проинтерпретированные ascii-коды, чтобы uppercase/lowercase работали и так далее?
                                              0
                                              Шлю значение event.keyCode, с небольшими заменами, которые подглядел в программах (написанных, по всей видимости, для других ассемблеров): Enter — 0x0a, стрелка влево — 0x01, вправо — 0x02, вверх — 0x03, вниз — 0x04.

                                              Нормальной спецификации по вводу с клавиатуры пока нет, а Нотч писал, что будет его менять (можно будет в том числе ловить события keydown/keyup) — поэтому пока так.
                                        0
                                        Теперь макросы должны работать. Синтаксис такой же, как в примерах Нотча:

                                        #macro push(a) {
                                        	set PUSH,a
                                        } 
                                        
                                        #macro push(a,b) {
                                        	set PUSH,b
                                        	set PUSH,a
                                        }
                                        
                                        push(x, 1)
                                          0
                                          вроде работает, спасибо. Может, в режиме single-step debugging прыгать внутрь макроса, показывать строки, или это слишком много?

                                          но, кажется, Вам теперь много надо переписывать в связи со вчерашними событиями — www.reddit.com/r/dcpu16/comments/sqfre/rfe_dcpu16_11/
                                            0
                                            Ну это было вполне ожидаемое событие :)

                                            Над запрыгиванием внутрь макросов подумаю, вроде бы в моей нынешней реализации это должно быть не очень трудно сделать.
                                              0
                                              По-моему, есть небольшой баг.

                                              Код не работает (test_ptr не видит в качестве аргумента dat метки, назначенные позже)

                                              set a, test
                                              :test_ptr dat test
                                              :test dat 1

                                              А вот это работает:

                                              :test dat 1
                                              :test_ptr dat test
                                              set a, [test_ptr]
                                        0
                                        можно идти еще глубже — например Dwarf Fortress и машина Тьюринга или калькулятор

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                        Самое читаемое