11 января 2015 в 17:55

Делаем тетрис под FPGA

Всем привет!

imageНа этих долгих новогодних выходных я задался вопросом: насколько легко написать какую-то простенькую игрушку на FPGA с выводом на дисплей и управлением с клавиатуры. Так родилась еще одна реализация тетриса на ПЛИС: yafpgatetris.


Конечно, игры на FPGA делаются больше для фана и обучения, чем для каких-то реальных “продакшен” задач, да и от “разработки” игр я очень далек, можно сказать, для меня это новый опыт.


Если интересно, как можно запускать игру без операционной системы, реализуя её на самом низком уровне, с помощью триггеров и комбинационной логики, добро пожаловать под кат.


О девките


Нам надо «что-то», где наша игра запустится. Один из самых простых способов — взять девкит, где есть FPGA и какая-то периферия для ввода/вывода. В моем распоряжении оказалась платка от Terasic с названием DE1-SoC.





Ну что сказать?
Девкит, как девкит. Много периферии: нам из неё будет интересны разьемы PS/2 и VGA. Для обучения (в школах, либо университетах) самое то. Для своих целей мы его закупили как раз для того, чтобы поиграться (и для обучения студентов), чем для реализации каких-то своих «продакшен» идей.
Если вдруг DE1-SoC (либо похожие платы) вы используете в своих реальных приборах (а не просто поморгать светодиодом) — поделитесь в комментариях, будет интересно.

SoC в названии чипа обозначает то, что в чипе есть и обычная FPGA-логика, и ARM-процессор. Забегая вперед, скажу, что для своей задачи я не использовал ни ARM, ни какой-то софтварный процессор, так что мой проект вы сможете запустить на своих платах с другими FPGA-чипами. Если интересно почитать про поднятие связки FPGA + ARM, и какие бонусы из этого можно получить, советую обратиться к статье моего коллеги Des333.

Что хотим получить


В понятие тетрис можно вкладывать различные вещи, поэтому я набросал примерное ТЗ, чего хотел получить:
  • Стандартный набор фигурок. Их поведение должно быть максимально похожим на привычное.
  • Игра разноцветная. За каждой фигуркой закреплен свой цвет.
  • Фигурки генерируется случайно с равномерным распределением.
  • Должно быть окно, в котором отображается следующая фигурка.
  • Должна быть информация о состоянии игры: количество очков, количество убранных линий, текущий уровень.
  • Очки начисляются по “прогрессивной” шкале: чем больше за раз убрал линий, тем больше очков.
  • Чем выше уровень, тем больше скорость падения фигурок.
  • Корректно детектируется “конец игры”, есть возможность начать новую игру.
  • Ввод действий пользователя осуществляется с клавиатуры (PS/2).
  • Отображение состояния поля и прочего происходит на обычном дисплее через VGA интерфейс.


Схема проекта




Можно выделить три основные части:
  • Ввод пользователем. Принимаем данные от клавиатуры и “воздействуем” на систему.
  • Всё, что относится к самой игре. По факту FSM (finite-state machine), которая принимает “запросы” от игрока, и “делает всё”: генерирует новые фигурки, их двигает, убирает линии, и прочее.
  • Отображение состояния игры. Отрисовываем на дисплей через интерфейс VGA.


PS/2


Если честно, сначала думал обойтись без клавиатуры и использовать клавиши на самом ките, но на удивление никаких проблем с клавиатурой не возникло: всё заработало из коробки.

Для приёма команд с клавиатуры нужен PS/2 контроллер. Я использовал вот этот.

Если чуть обратиться к теории, то для каждой клавиши определен набор кодов, которые посылает клавиатура при её нажатии или отпускании.

Возьмем клавишу “Enter”:
  • Make: 5A
  • Break: F0, 5A.

Посмотрим, как это выглядит внутри FPGA:

Обычное нажатие клавиши:

Как видим, действительно:
  • Нажимаем на клавишу, приходит 5A.
  • Отпускаем: приходит F0, после нее 5A.
  • Снова нажимаем: приходит 5A и так далее.


Если зажмем клавишу, то получим вот это:

Просто приходит команда 5A с какой-то периодичностью.

Нам нужен небольшой набор клавиш:
  • обычные стрелки — для управления фигуркой.
  • n — для начала новой игры.

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

После детектирования интересующего нас “события” кладем его в FIFO, откуда его заберет “прикладная логика” игры. Если у вас не оказалось PS/2 на своей плате, но есть какие-то ключи, тумблеры, то достаточно будет написать логику которая нажатия этих кнопок переведет в “события”, и игра ничего не заметит.

Этот контроллер позволяет подключить мышь, но я не пробовал.

Основная логика игры



С одной стороны, логика тривиальна, и описывается следующей FSM:


(Если честно, не знаю, использует кто-нибудь в продакшене “State Machine Viewer”, если да, поделитесь в комментариях для чего. За всё время разработки под FPGA я его открывал пару раз, да и то в рамках обучения).

FSM «общается» со следующими блоками/модулями:
  • gen_sys_event — таймер, который отсчитывает время, через которое надо автоматически двинуть фигурку вниз.
  • gen_next_block — генератор новой фигурки.
  • check_move — проверка, можно ли выполнить текущий «ход».
  • tetris_stat — накопление «статистики».
  • user_input — считывает событие, которое «произвел» пользователь.

Всё очень похоже на «обычную» реализацию Тетриса, которые написаны на C++/Java/etc: различные модули выполняют роль функций в тех языках. Да и проблемы возникают такие же: дольше всего сидел над переворотом фигурки, ответ подсмотрел в коде quadrapassel. Один из вариантов является то, что можно хранить хранить таблицу всех возможных разворотов (для каждой фигурки четыре варианта).

Весь код написан на Verilog, а если быть более точным — на SystemVerilog. С одной стороны SystemVerilog намного гибче, чем Verilog, а с другой стороны это приводит к тому, что ты не ограничен, и хочешь всё больше и больше различных рюшечек реализовать :).

Я упростил себе жизнь: текущее состояния поля хранится на регистрах (вместо внутренней памяти), и из-за этого (а так же того, что некоторые вещи сделаны неоптимально) образуется много логики, и проект занимает немало ресурсов (около 3.2k ALM из 32k). Если переехать на память, то придется делать некоторые вещи последовательно (например, сдвиг вниз всего поля, когда надо убирать линию, которая заполнилась). Скорее всего я не буду переделывать на использование памяти.

В тестовых целях я собрал я проект под платы DE0/DE1 (братья той платы, которая у меня, но с бюджетными чипами: у них меньше ресурсов, и они более «младшего поколения»): проект по ресурсам влезает. Однако…
Скрытый текст
… прям из коробки не заработает:
  • Квартус будет ругаться на некоторые вещи в qsf файле, т.к. я собирал для 14-м квартусом, где нет Cyclone II/III. Ранние версии квартуса этих вещей не знают: придёться ручками удалить в qsf файле эти строчки, а потом по смыслу такие же галки поставить в GUI квартуса.
  • Не укладывается по частоте: «главная» частота в этом проекте 108 МГц (на нем работает сам main_game_logic и отрисовка на VGA). Чуть забегая вперед, частота 108 МГц — потому что используется разрешение 1280x1024, если использовать 640x480, то там будет частота 25 МГц, и уложится.
  • Возможно, придется перегенерировать мегафункции для PLL и FIFO, т.к. они были созданы для Cyclone V.
  • Вывод на дисплей, возможно, надо чуть подредактировать (выбрать другие цвета), т.к. там на каждый цвет только четыре бита выделено (как я понял), против восьми, как в этой плате.



Отображение на дисплей


Информации о том, как с помощью ПЛИС выводить изображение на дисплей через VGA можно найти немало, например на хабре, поэтому на этом подробно останавливаться не буду.

В этом ките вывод на VGA сделан следующим образом:


Каждый такт VGA_CLK необходимо выставлять новое значения цвета в модели RGB, а затем ЦАП эти значения преобразует в необходимый уровень сигнала.

В качестве контроллера VGA сигналов я взял модуль из демопримеров, которые есть на CD для этого кита. Забавно, что есть понятие CD, но в комплекте с платой никакого CD нет: необходимо скачивать архив из интернета.

Этот «контроллер» Terasic использует и в других китах: он легко гуглится по имени «vga_time_generator». Он удобен тем, что можно настроить его на любой режим работы (640x480, 800x600, etc), и тем, что выдает координаты (pixel_x, pixel_y) текущего пикселя для отображения. Наша задача сводится к тому, чтобы в зависимости от этих координат подставить нужное значения цвета.



Я решил, что 640x480 на большом мониторе смотрится не очень и переехал на 1280x1024, просто передав в модуль нужные значения из стандарта. Дополнительно пришлось изменить значение VGA_CLK: вместо 25.175 МГц стало 108 МГц. Правда, я потом немного жалел об этом, но красота требует жертв.

Рассмотрим, как выводить какие-то примитивные объекты.

Например:
`define RGB_BLACK   24'h00_00_00
`define RGB_ORANGE  24'hFF_A5_00

logic [23:0] vga_data;

localparam START_X = 100;
localparam START_Y = 100;
localparam END_X   = START_X + 200 - 1;
localparam END_Y   = START_Y + 300 - 1;

always_comb
  begin
    vga_data = `RGB_BLACK;

    if( ( pixel_x >= START_X ) && ( pixel_x <= END_X ) &&
        ( pixel_y >= START_Y ) && ( pixel_y <= END_Y ) )
        vga_data = `RGB_ORANGE;
  end

assign { r, g, b } = vga_data;


Выведется оранжевый квадрат размером 200x300 пикселей, причем верхний левый угол будет расположен в точке (100, 100).

Или:
`define RGB_BLACK   24'h00_00_00
`define RGB_ORANGE  24'hFF_A5_00

logic [23:0] vga_data;

localparam MSG_X = 56;
localparam MSG_Y = 5;

logic [0:MSG_Y-1][0:MSG_X-1] msg;

assign msg[0] = 56'b10010011110010000010000001100000001001000110001110001110;
assign msg[1] = 56'b10010010000010000010000010010000001001001001001001001001;
assign msg[2] = 56'b11110011110010000010000010010000001111001111001111001111;
assign msg[3] = 56'b10010010000010000010000010010000001001001001001001001110;
assign msg[4] = 56'b10010011110011110011110001100000001001001001001110001001;

logic [$clog2(MSG_X)-1:0] msg_pix_x;
logic [$clog2(MSG_Y)-1:0] msg_pix_y;

localparam START_MSG_X = 100;
localparam START_MSG_Y = 100;
localparam END_MSG_X   = START_MSG_X + MSG_X - 1;
localparam END_MSG_Y   = START_MSG_Y + MSG_Y - 1;

assign msg_pix_x = pixel_x - START_MSG_X;
assign msg_pix_y = pixel_y - START_MSG_Y;

always_comb
  begin
    vga_data = `RGB_BLACK;

    if( ( pixel_x >= START_MSG_X ) && ( pixel_x <= END_MSG_X ) &&
        ( pixel_y >= START_MSG_Y ) && ( pixel_y <= END_MSG_Y ) )
      begin
        if( msg[ msg_pix_y ][ msg_pix_x ] )
          begin
            vga_data = `RGB_ORANGE;
          end
      end
  end

assign { r, g, b } = vga_data;


Выведется HELLO HABR шрифтом c высотой в 5 пикселей оранжевым цветом на черном фоне. (Приглядитесь к единицам в массиве msg).

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

Выводим строчки


Для отображения статистики (строк «Score», «Lines», «Level» и их значений) я решил пойти по “классическому” пути. Его можно посмотреть, например, тут.

Допустим, какая-то логика уже определила, какой какой символ (читай, букву или цифру) мы хотим выводить #прямосейчас (в зависимости от pixel_x, pixel_y). Для его отображения используем готовую таблицу шрифта, где единицами будет отмечено какой пиксель необходимо красить цветом шрифта, а нулем — цветом фона, типа:
  "00000000", -- 0
  "00000000", -- 1
  "00010000", -- 2    *
  "00111000", -- 3   ***
  "01101100", -- 4  ** **
  "11000110", -- 5 **   **
  "11000110", -- 6 **   **
  "11111110", -- 7 *******
  "11000110", -- 8 **   **
  "11000110", -- 9 **   **
  "11000110", -- a **   **
  "11000110", -- b **   **
  "00000000", -- c
  "00000000", -- d
  "00000000", -- e
  "00000000", -- f


Во многих проектах (что можно найти в сети) с VGA используется такая таблица (Font ROM), но они рассчитаны на дисплей 640x480: для 1280x1024 это получается мелковато, поэтому необходимо подготовить похожую таблицу, но с “большим” шрифтом.

В этом мне помогла утилита nafe. На входе принимает psf файл, на выходе — текстовый файл с X, в тех пикселях, которые надо отрисовать. С помощью любимого языка (либо чуть переделываем вывод оригинальной программы) меняем X на “1”, а пробелы на “0”, и добавляем заголовок, чтобы сделать mif файл (который потом используется для инициализации ROM).

Самый большой шрифт, что я нашел у себя в формате psf, был 32x16, и, в принципе, для этой задачи его хватило, но я хотел бы чуть больше его сделать. Насколько я понимаю, каких-то ограничений нет, и с помощью этой утилиты можно подготовить ROM с любыми символами (например, русскими буквами).

Однако, для заголовка yafpgatetris и сообщения GAMEOVER этот размер мне показался маленьким, и я решил выводить эти сообщения аналогично строчке HELLO HABR в примере выше. Единственный вопрос — как подготовить msg, т.к. ручками это делать уж очень не хотелось.

Сразу пришло в голову относительно простое велосипедное(?) решение:
  • Набираем текст нужного шрифта и размера в Paint/GIMP.
  • Сохраняем в PNG без сжатия и сглаживания.
  • Используем какую-то готовую библиотеку, чтобы прочитать PNG файл и для каждого пикселя вывести 0, если “цвет белый”, 1 если “цвет черный”.

Получившийся набор нулей и единиц тоже можно положить в ROM (в другую, чем шрифт, конечно).

Немного фотографий


Пара фотографий из серии “разработка в процессе”:
Скрытый текст
Научились выводить поле: фигурки просто падают вниз и все одного цвета.


Добавили статистику и разные цвета. Цвета вырвиглазные :)


Ну, а окончательный вариант — в начале статьи :)

P.S.
Если честно, не знаю, почему при фотографировании такие «разводы» на дисплее, может какую-то настройку не включил в VGA-корке, либо просто не повезло…


Итоги


Исходники:
https://github.com/johan92/yafpgatetris

Видео:


Я попытался сделать проект максимально параметризируемым, и логически разделил на части, поэтому, если захотите на базе моего проекта сделать «гоночки», где надо уворачиваться от других машин, либо змейку, достаточно написать свою main_game_logic и чуть-чуть поправить вывод (если надо).

На разработку ушло где-то около 5 дней, если считать «чистое время»: пришлось повозиться с переворотом фигурки (фактически два раза переписывать алгоритм), много времени ушло на подбор цветов, размеров, выравнивания и расположения сообщений. Внутренний перфекционист всё время требовал от внутреннего дизайнера что-то сдвинуть, что-то увеличить/уменьшить и пр. Для себя я усвоил, что разработка GUI это не моё) В итоге, цвета для фигурок я взял из приложения Тетрис в Вконтакте.

Если вы купили кит и хотите обучиться разработке под FPGA, не рекомендую делать тетрис прям в качестве первого проекта. Начините со светодиодиков, сегментных индикторов, часов, и прочих классических вещей. Когда это пройдете, то можно попробовать тетрис, либо какую-то другую простенькую игру. Надеюсь, мой проект поможет в этом начинании.

Спасибо за внимание! Если появились вопросы, задавайте без сомнений.
Автор: @ishevchuk
НТЦ Метротек
рейтинг 166,43
Компания прекратила активность на сайте
Похожие публикации

Комментарии (22)

  • +2
    Теперь надо GTA V портировать ;)
    • 0
      Хе-хе)
      Не, вся видеомагия от меня слишком далека)

      Можно попробовать написать какой-нибудь экшен, типа пакмана (на чистом Verilog'e без процессора), но я не знаю трюков для видеоотображения, которые применяли разработчики того времени.

      Здесь фактически я отрисовываю статичную картинку, т.к. меняется очень редко, а в экшене немного не так)
      • 0
        А если добавить процессор общего назначения, вообще хорошо получается andybrown.me.uk/wk/2014/06/01/ase/
        • 0
          Вы правы, процессор может помочь в «запуске» более серьезных игр.
          В некоторых реализациях того же тетриса используют «софтовый» процессор (NIOS) внутри самой FPGA. Я намеренно отказался от такого, т.к. мне было интересно сделать без процессора)
        • +2
          На используемый в отладке Cortex-A9 можно накатать Linux или Android и ставить игрушки из Play market, но публикация получится о другом.
    • 0
      Мой коллега попросил прокомментировать пост (пока у него нет возможности оставлять комментарии):

      «Спасибо за статью, отличный пример под популярный кит!
      По поводу „разводов“ на фотографиях экрана. Настройки тут не при чем,
      это муаров эффект — по сути нарушение теоремы Котельникова в
      пространственной области. А неравномерность узора по экрану скорее всего
      обусловлена дисторсией объектива фотоаппарата.»
  • –1
    А я надеялся, что автор возьмет китайский тетрис, выдернет с платы черную бескорпусную «соплю» и заменит на свой FPGA-чип. Ну или что-то в этом роде.
    • 0
      Хех)
      В принципе, если там интерфейс с дисплеем не сложный, почему бы и нет?
      • 0
        Я думаю, что в плане управления он должен быть проще чем VGA. поле X*Y + несколько семисигментных индикаторов. Вот только разъём чуть сложнее припаивается.
  • +1
    Черт, это круто. Вы мотивировали меня купить этот KIT и попробовать свои силы
  • +1
    По поводу размеров шрифта, если увеличивать букву нужно кратно двум, то это реализуемой с помощью автомата. При чтении из памяти нужно каждый пиксель считывать N раз, и повторять при выводе N строк. это самое простое увеличение без сглаживания. При этом не нужно хранить несколько разных шрифтов (ресурсы не бесконечны). Полная таблица шрифтов 11*7 займёт меньше ячеек чем 32*16. хотя последние будут рисоваться более красиво.
  • 0
    Быстро управились — 5 дней на реализацию такого проекта на ПЛИС — это круто!

    Я так понял никакого фреймбуфера вы не использовали при выводе на экран, а непосредственно генерировали цвета текущих пикселей?

    Поясните, чем на ваш взгляд SystemVerilog отличается от Verilog, и как эти отличия помогли вам в этой проекте.
    • 0
      Спасибо.

      Да, фреймбуфера не было. Просто генерировал цвета в зависимости от pixel_x, pixel_y. см. файлы draw_*

      Я не думаю, что мой взгляд на разницу Verilog от Systemverilog'a отличается от общепринятого :)
      Из того, что я использовал в этом проекте:
      • В стандарте 2001 года не было struct и enum.
      • always_comb — не надо думать о списке чувствительности когда описываешь комбинационку. always_ff — это триггер.
      • logic — не надо думать о reg/wire.

      В других проектах использую и интерфейсы, и package.

      Как отличия помогли в проекте?

      Ну, например, если бы не было структуры game_data_t, то мне было бы лень тащить сигнал game_over_state, а так добавил в структуру — она появилась в модуле draw_strings. Либо например структура block_info_t — содержит информацию о блоке. Удобно — вместо пяти строчек обьявления сигналов — получается одна.

      Либо move_t — сначала их было всего четыре, и в классической ситуации надо было бы заводить 2-х битную переменную и делать типа `define MOVE_DOWN 2'b00 и т.п. Потом добавился MOVE_APPEAR — и пришлось бы делать 3-х битную переменную, а так это всё автоматически.

      ИМХО, упрощение в разработке и красота :)
      • 0
        Похоже мне надо бросать VHDL и переходить сразу на SystemVerilog =)
        • 0
          Ну, это холиварная тема)
          Кому как удобнее.

          Xilinx ISE вроде SystemVerilog не поддерживает, а Synplify должен.

          Если знакомы с конструкциями Veriloga, то посмотрите «SystemVerilog for Design»)
          • 0
            Да посмотрю! Я в ISE не работаю, только с новыми кристаллами в Vivado, а он вроде поддерживает SystemVerilog…
  • 0
    Если переехать на память, то придется делать некоторые вещи последовательно

    Хех. 'Какая досада', все параллельно выполняется… Везде бы так.

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

    Как жаль что производители потребительских компьютеров (не важно soc или нет) старательно обходят добавление открытой для использования FPGA логики, готовых реализаций по пальцам пересчитать можно. А ведь даже закрыв глаза на аппаратные гибкие возможности по управлению периферией, FPGA дают огромные возможности по оптимизации/ускорению программ, особенно когда речь идет об экономии электроэнергии. Понятно что вхождение программирование FPGA заметно труднее, но я думаю доступность и повсеместное внедрение сделало бы развитие языков программирование в этом направлении еще быстрее, и кто знает, вполне возможно FPGA могут стать следующим качественным скачком в повышении скорости железа, с момента появления видеокарт с GPGPU и появления OpenCL.

    p.s. вот пример, не совсем в тему FPGA (там на плате дополнительно еще 16-ядерный чип parallela) но до недавнего времени платы снабжались Zynq-Z7010/Z7020 с модулем FPGA (да, маленьких, всего на 30-60к вентилей, но если игра с поддержкой ввода вывода требует каких то жалких несколько тысяч....)
    • 0
      У Intel и Altera были идеи на этот счёт. Ну и сами производители FPGA встраивают ARM ядра в свои чипы. До этого были PowerPC и другие аппаратные реализации встроенные в ПЛИС.
  • 0
    Интересный проект. Спасибо. Сам хотел сделать нечто подобное, но не на видеовыход, а в ANSI-терминал. Проблема проявилась в отсутствии компилятора. То есть на ПЛИС я реализовал оригинальный процессор, а компилятора к нему нет. Можно было бы переписать Си код на ассемблере, но есть дела и поважнее.

    Собственно, мой комментарий не для того чтобы похвастаться или похвалить автора, а в надежде узнать название двух самых популярных в мире плат с FPGA — самую популярную с Altera на борту и самую популярную с Xilinx.

    Требования к устройству:
    • не менее 10000 Altera LE
    • не менее 400 Кбит внутренней памяти (встроенная в ПЛИС)
    • желательно от 4 мбайт SDRAM на борту платы
    • частота не менее 100 Мгц
    • бюджет от $100 до $150


    Чем популярнее плата у разработчиков, тем лучше. Кажется, что название Terasic DE1 слышал уже неоднократно. Возможно одна из самых популярных? Но $250 уже нормальные деньги, которые вот так просто из семейного бюджета не вытащишь.
    • +1
      Увы, данных про самые популярные в мире платы у меня нет :) Платы от Терасика для Альтеры, да, на слуху. Но являются ли они самыми популярными — не знаю.

      Замечу, что у Терасика есть кит DE1 c Cyclone II, а тот кит, который использовал я (DE1-SoC) использует Cyclone V.

    • +1
      Посмотрите на DE-0 Nano на Cyclone-IV или DE0 на Cyclone-III.
      Первый дешевле по деньгам, второй побогаче на интерфейсы.

      Кстати, те отладки что советует ishevchuk можно было заполучить в рамках конкурса Altera’s Innovate Europe Design Contest. Но там есть ограничения по степени студенчества и инновационности.

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

Самое читаемое Разработка