Minesweeper на FPGA

Привет всем!

Прочитав статью «Делаем тетрис под FPGA», я вспомнил, что у меня завалялся похожий проект, который я когда-то использовал для своеобразного предложения «руки и сердца» своей девушке.

А почему бы не сделать нечто подобное самому?

Откопав исходники, возобновил утерянные знания и решил на базе старого проекта на скорую руку написать простую версию игры «Сапёр» на старенькой ПЛИС Spartan3E. Собственно, о реализации игры «Сапёр» на уровне логических вентилей и основных особенностях разработки на FPGA фирмы Xilinx и пойдет речь в данной статье.

Отладочная плата


Несколько лет назад я искал бюджетный вариант отладочной платы с ПЛИС и простейшей обвязкой разными интерфейсами типа VGA, PS/2, наличием светодиодов и LED-дисплеем, а также триггеров-переключателей. Тогда я остановился на простейшем китайском ките, который проще всего было заказать с ebay за $135,00 с учетом доставки. Кстати, комплект пришел неполный, поэтому я оставил гневный отзыв, за что продавец вернул ~20$. Так что плата обошлась мне в ~4000р по старым ценам.


Официальный сайт производителя кита.

Основные особенности девкита:
  • ПЛИС Spartan3E (XC3S500E-4PQ208C) — 500К логических вентилей,
  • Источник тактовой частоты CLK = 50 MHz,
  • Внешняя память 64M SDRAM,
  • SPI Flash (M25P80) для хранения прошивки ПЛИС,
  • Матрица светодиодов 8х8, линейка светодиодов 8 шт.,
  • 8 переключателей и 5 кнопок,
  • Разъемы для подключения LED-дисплеев,
  • Разъем VGA для подключения дисплея,
  • Разъемы PS/2, и т. д.

Ресурсы кристалла Spartan3E XC3S500E приведены в таблице:



Из всего разнообразия, для реализации игры «Сапёр» необходимы VGA и PS/2 разъемы. Помимо них я использовал переключатель для глобального сброса (reset) логики внутри ПЛИС.

Основная концепция игры


Что было?
В старом проекте реализованы следующие штуки:
— ввод команд с клавиатуры (управление ШИМ-модулятором и дисплеем);
— самописный интерфейс VGA разрешением 640х480;
— мигающее сердечко на матрице светодиодов 8х8 на базе ШИМ.

Первые два пункта существенно ускорили время разработки игры, поэтому я не стал изобретать велосипед.

Правила для игры:
  • Управление с клавиатуры:
    "WSAD" — кнопки-стрелки для перемещения по экрану;
    "Enter" — проверка поля на наличие/отсутствие мины;
    "Space" — начать новую игру;
    "Esc" — завершить текущую игру;
    "Y/N" — для начала новой игры;
  • Поле 8х8, всего 8 мин на поле;
  • Остальные правила как в обычной игре сапёр;

Язык программирования ПЛИС: VHDL.

Вот так выглядит готовый проект в программе «PlanAhead» после стадий синтеза и трассировки. Блоки в фиолетовых рамках — занимаемые ресурсы кристалла.



Большой блок: основная логика игры;
Средний блок: контроллер PS/2 клавиатуры;
Маленький блок: контроллер VGA дисплея.

Иерархия проекта:
На одном из первых этапов проектирования необходимо прикинуть, а как же будет выглядеть проект и сколькими компонентами его удобнее описать. Я придумал следующую структуру:

--> Верхний уровень
----> Контроллер PS/2
----> Контроллер VGA 640x480
----> Контроллер игры
-------> Блок отрисовки границ прямоугольника,
-------> Блок для отрисовки закрашенных полей 8х8
-------> Блок для отрисовки мин и цифр на поле
-----------> Память для расстановки мин
-----------> Память для символов
-------> Блок для отрисовки текста и диалоговых сообщений
-----------> Память для символов

Так это выглядит в среде «PlanAhead» от Xilinx.



Верхний уровень
Он описывает основные порты ввода-вывода, содержит блок синтеза частоты DCM для преобразования входной частоты с 50 МГц в 25 МГц. Код верхнего уровня выглядит следующим образом:

entity top_minesweeper is
	port(
		-- PS/2 IO --
		PS2_CLK		:  in  std_logic; -- CLK from PS/2 keyboard
		PS2_DATA	:  in  std_logic; -- DATA from PS/2 keyboard
		-- CLOCK 50 MHz --
		CLK		:  in  std_logic; -- MAIN CLOCK 50 MHz
		-- VGA SYNC --
		VGA_HSYNC	:  out std_logic; -- Horizontal sync
		VGA_VSYNC	:  out std_logic; -- Vertical sync
		VGA_R		:  out std_logic; -- RED
		VGA_G		:  out std_logic; -- GREEN
		VGA_B		:  out std_logic; -- BLUE
		-- SWITCHES --
		RESET		:  in  std_logic -- Asynchronous reset: SW(0)
	);
end top_minesweeper;


Контроллер PS/2
За основу взят этот проект. Заработало сразу. Интерфейс последовательной передачи достаточно примитивный: две линии: PS2_CLK и PS2_DATA, по которым идут команды от клавиатуры.
Подводный камень — изначально с помощью «Make» кода я генерировал единичный импульс (по фронту), который бы сигнализировал «нажатие» клавиши. Это приводило к имитации повторного нажатия, когда происходило нажатие другой клавиши. Так как байт «Make» и «Break» кодов совпадают, то пришлось сделать условие более явным, учитывая «Break» код.
Таблица кодов для PS/2 контроллера приведена по ссылке выше.

Контроллер VGA
Когда-то в целях обучения написал самостоятельно, но алгоритм его работы точно такой же, как и у всех VGA-контроллеров. На Хабре тоже есть такой.



Основные особенности:
— Частота работы контроллера: 25.175 MHz
— Разрешение экрана: 640х480
— Частота обновления: 60Hz
— Доступная палитра: RGB

К сожалению, отладочная плата не обладает встроенными микросхемами дешифрации цветовой палитры, поэтому доступно всего 3 основных цвета (красный, зеленый, синий) и 5 комбинаций (желтый, пурпурный, голубой, белый и черный). Но это не мешает придумать цветовую схему и даже вывести мигающие изображения! (см. видео в конце)

Контроллер игры
Самый простой способ описания контроллера игры «Сапер» строится на базе конечного автомата (FSM). Необходимо придумать условия автомата, в которых будут обрабатываться те или иные события.

В моем проекте используется 5 основных комбинаций автомата:
  1. WAIT_START (обнуление всех управляющих сигналов, счетчика мин, запуск генератора случайной игры;
  2. PLAY (процесс игры: управление кнопками с клавиатуры, поиск мин);
  3. CHECK (проверка, если найдена мина — переход в конец игры);
  4. GAME_OVER (определяет событие победы или поражения, выводит дополнительные сообщения на дисплей);
  5. RST (необязательная стадия — очищает экран, сбрасывает все управляющие сигналы, без возможности запуска новой игры).

Память символов
Найдена на просторах Интернета. Размеры одного символа 8х16. Пример для символа «1»:

	"00000000", -- 0
	"00000000", -- 1
	"00011000", -- 2
	"00111000", -- 3
	"01111000", -- 4    **
	"00011000", -- 5   ***
	"00011000", -- 6  ****
	"00011000", -- 7    **
	"00011000", -- 8    **
	"00011000", -- 9    **
	"00011000", -- a    **
	"01111110", -- b    **
	"00000000", -- c    **
	"00000000", -- d  ******
	"00000000", -- e
	"00000000", -- f

Все символы укладываются в одну ячейку блочной памяти RAMB16 кристалла. Память устроена так, что символ состоит из 16 векторов разрядностью 8. Для вывода символов на дисплей необходимо 4 младших разряда шины адреса подключить к вектору координаты Y. Логическая '1' — окрашивает символ в цвет, '0' — цвет фона (черный).

Память для расстановки мин на поле
Эту часть проекта я модифицировал дольше всего, изобретая различные изощренные решения. В итоге решил сделать следующий компонент в виде ROM-памяти, который выбирает игру.

Кусок кода:

constant N8x8	: integer:=8; -- константа поля 8х8
constant Ngames	: integer:=1; -- количество игр

type round_array_3x64xN is array (Ngames*N8x8*N8x8-1 downto 0) of integer range 0 to 7;

constant mem_init0:	round_array_3x64xN:=(
	-- game 0:
	1,1,1,0,0,0,0,0,
	1,7,1,1,1,1,0,0,
	1,1,1,1,7,2,1,0,
	0,0,0,1,2,7,1,0,
	0,1,1,1,1,1,1,0,
	0,1,7,2,7,1,1,1,
	0,1,1,2,2,2,2,7,
	0,0,0,0,1,7,2,1);

Константы N8x8 и Ngames задают размер поля и количество игр. Цифра на поле соответствует мине или количеству мин вокруг нее. Правила очень простые:
  • Цифры 0-6 — определяют количество мин,
  • Цифра 7 — зарезервирована и определяет мину на поле.

Почему так?
Я не стал придумывать ситуацию, когда вокруг точки могут находиться сразу 7 или 8 мин. Для 8 мин и поля 8х8 это слишком неинтересные решения. К тому же числа от 0 до 7 занимают всего 3 бита, тогда как комбинации от 0 до 8, и 9 для мины занимают уже 4 бита. В этом плане я большой любитель сэкономить внутреннюю логику и трассировочные ресурсы кристалла, даже если этих ресурсов хватит на 5 проектов.

Таким образом, все числа укладываются в своеобразный ROM-массив, который можно дописать своими играми. В моем проекте реализовано 32 игры, что занимает чуть меньше 1 блока памяти RAMB16. Следует отметить, что числа задаются в формате integer. Для их перевода в std_logic_vector(2:0) и дальнейшей обработки написана специальная функция. Целочисленный формат упростил запись новых игр и значительно сэкономил время. Многих разработчиков ПЛИС на языке VHDL иногда вводит в ступор ситуация, когда используется целочисленный формат, поскольку конструкции с целочисленным типом не всегда являются синтезируемыми, т.е. их нельзя проверить в реальном железе. Но для ROM-генератора integer является оптимальным выбором.

Для того, чтобы добавить свою расстановку мин — нужно грамотно заполнить поле 8х8 в массив. Вариации игр набивал вручную. Всего в моем проекте 32 различных комбинации расстановки мин.

Блоки отрисовки границ и поля 8х8
Изначально я реализовал их на генераторе символов, но потом решил сэкономить ресурсы кристалла, т.к. подумал, что ради закрашенных квадратиков и рамочки нет смысла использовать целую ячейку RAMB16. (Оптимизация по ресурсам!) Поэтому все сделано на мультиплексорах. Подробно останавливаться на этом не буду.

Блок для отрисовки мин и цифр
Преобразует данные из памяти набора игр в числа и мины на экране, используя память символов. Изначально хотелось вывести квадратное поле 8х8, но потом мне стало лень переписывать ROM-генератор, и я оставил его прямоугольным.
Для этого блока также пришлось создать специальную маску 8х8, с помощью которой по нажатию «Enter» закрашенные ячейки превращались бы в цифру или мину.

Текст и сообщения
Текст написан сплошняком — то есть на экране все пишется сразу, но в зависимости от стадии игры какая-то информация остается невидимой (например, сообщения о поражении или победе). Используется все тот же генератор символов. Размер символа 8х16, поэтому поле дисплея 640х480 можно разбить на секции 80х30, в которых отображаются символы. Как это делается?

Ниже представлен простой пример:
addr_rom <= data_box(6 downto 0) & y_char(3 downto 0) when rising_edge(clk);

x_char_rom: ctrl_8x16_rom -- память коэффициентов 
	port map (
		clk	=> clk,
		addr	=> addr_rom,
		data	=> data_rom);	

pr_sel: process(clk, reset) is -- данные для отображения на дисплей
begin
	if reset = '0' then
		data <= '0';
	elsif rising_edge(clk) then
		data <= data_rom(to_integer(unsigned(not x_char(2 downto 0))));
	end if;
end process; 

g_rgb: for ii in 0 to 2 generate -- окрашивание данных в цвет
begin
	rgb(ii) <= data and color(ii);
end generate;

Для начала нужно придумать, как с помощью адреса памяти можно выбирать тот или иной символ. Видно, что адрес состоит из двух векторов «y_char» и «data_box».

y_char(3 downto 0) — это младшие разряды вектора координат по оси Y. Эти данные обновляются автоматически и приходят с контроллера VGA.
data_box(6 downto 0) — сигнал выбирает, какой символ будет использоваться на поле. Этот вектор необходимо писать самому.

Если записать data_box <= «000001», то в вектор «data_rom» запишется первый символ из генератора. В процессе «pr_sel» происходит преобразование вектора данных в последовательный код. В зависимости от 3 младших битов регистра координаты Х выбирается конкретный бит вектора «data_rom». На первых порах я столкнулся с проблемой зеркального вывода данных на экране. Решение тривиальное — инверсия сигнала x_char.

Выходные данные — сигнал RGB, который поступает на VGA-разъем после логического преобразования с данными из памяти коэффициентов.

Реализация в железе


Все это собирается в один большой проект. Для красоты с помощью простого счетчика прикрутил мигание сообщений победы/поражения, а также добавил генератор для выбора случайной игры.
К исходникам на VHDL обязательно прикручивается файл *.UCF, в котором описано подключение портов ПЛИС и различные атрибуты. Пример:
## Switches
NET "RESET"	LOC = "P148" | IOSTANDARD = LVTTL | PULLUP ; ## SW<0>
NET "ENABLE"	LOC = "P142" | IOSTANDARD = LVTTL | PULLUP ; ## SW<1>

## VGA ports
NET "VGA_R" 	LOC = "P96" | IOSTANDARD = LVTTL | DRIVE = 8 | SLEW = FAST ;
NET "VGA_G" 	LOC = "P97" | IOSTANDARD = LVTTL | DRIVE = 8 | SLEW = FAST ;
NET "VGA_B" 	LOC = "P93" | IOSTANDARD = LVTTL | DRIVE = 8 | SLEW = FAST ;
NET "VGA_HSYNC" LOC = "P90" | IOSTANDARD = LVTTL | DRIVE = 8 | SLEW = FAST ;
NET "VGA_VSYNC" LOC = "P94" | IOSTANDARD = LVTTL | DRIVE = 8 | SLEW = FAST ;

## CLK 50 MHz
NET "CLK" 	LOC = "P183" | IOSTANDARD = LVCMOS33 ;
NET "CLK" TNM = "CLK_TN";
TIMESPEC TS_CLK = PERIOD "CLK_TN" 20 ns HIGH 50%;	

# PS/2 KEYBOARD
NET "PS2_CLK" 	LOC = "P99" | IOSTANDARD = LVTTL | DRIVE = 8 | SLEW = FAST ;
NET "PS2_DATA" 	LOC = "P100" | IOSTANDARD = LVTTL | DRIVE = 8 | SLEW = FAST ;


С помощью САПР Aldec Active-HDL и Xilinx ISE производится синтез и трассировка проекта ПЛИС. Из-за сложности обработки событий, отладку проводил без написания Testbench, напрямую заливая прошивку в ПЛИС и проверяя вывод на дисплей. Как правило, работало всё сразу. Основные ошибки заключались в синхронизации сигналов. Например, одновременные операции защелкивания адреса и попытки чтения данных. Исправляются такие ошибки быстро введением в нужном месте дополнительной задержки на такт. В тяжелых случаях использовался ChipScope Pro (Core Inserter и Analyzer).

Заключение


Мини-игра «Сапёр» успешно заработала на отладочной плате.
Размеры поля 8х8, количество мин на поле — 8.
Количество игр — 32. Перед стартом расстановка мин выбирается случайно из памяти для поля.
Занимаемые ресурсы кристалла (ПЛИС почти пустая):



Фото
Результат выглядит примерно вот так:



Ещё фото...
Трассировка в FPGA-Editor'e в области контроллера игры:



Схематический вид проекта в RTL Schematic:



Отладка проекта в ChipScope Pro Analyzer (подсчет количества открытых пустых полей):



Исходный код на github.

Видео-демонстрация игры

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 21

    +2
    Подскажите, как вы получаете 25,175 МГц из 50 (для VGA)? У меня получается только 50 * 74 / 147 = 25,170
      +2
      Такие коэффициенты умножения и деления для Spartan3E задать нельзя, поэтому я 50МГц просто поделил на 2.
      Дальше достаточно экспериментально подстроить значения «Front Porch» и «Back Porch» для вертикальной и горизонтальной синхронизации. Мне хватило увеличить значение back porch до 36 для вертикальной, и все заработало.
        0
        Ясно, спасибо.
      –6
      Если есть желающие поэкспериментировать на железе самостоятельно, как раз ищу покупателя отличной отладочной плате на Altera Cyclone II FPGA.
        0
        Кстати, если это она, то плата и в самом деле не плохая — 20 тысяч логических элементов в продаже встречаются значительно реже. Обычно 10 тысяч и меньше. Так что если цена устроит, то можно и взять — влезет много.

        image
        +1
        Тёплый ламповый интерфееейс =^_^=
          0
          Я когда-то на первом курсе делал сапера для доса и на Паскале.
          Тогда была проблема, когда игрок открывал пустую ячейку и рядом с ней не было ячеек с минами и их нужно было открыть все Я тогда это решил просто методом растекающейся воды (рекурсия и все дела)
          а вы как решили??
            0
            Я задумывался об этой проблеме на начальной стадии игры, а потом уже стало как-то не до этого — не стал делать (алгоритм конкретно для ПЛИС тоже несложный: проверка смежных ячеек на ноль мин вокруг, но рекурсия тут не пройдет: все строится на мультиплексорах). Сложность прохождения игры при этом не возросла — просто для открытия всех ячеек потребуется больше времени.
              0
              Абсолютно ничего не понимаю в ПЛИС, но давным давно реализовывал это на паскале, позже пригодилось для реализации волнового алгоритма при поиске путей. Делал цикл, условие выхода — достигнуто максимальное число повторений либо переменная нулю. Перед входом в цикл переменной присваиваем единицу. В цикле соответственно первым делом обнуляем переменную. Дальше пробегаемся в этом же цикле по всем точкам хранящимся в массиве и проверяем граничащие с ними точки, если есть хоть одна равная нулю то добавляем ее во второй массив, отмечаем на карте как открытую и переменную для выхода из цикла делаем равную единице. После завершения проверки точек первый массив переписываем вторым и цикл повторяется.
              В итоге когда вокруг не будет ни одной нулевой точки цикл завершится и останется еще раз по такому же принципу пробежаться чтобы открыть точки граничащие с нулевыми.
                0
                Для ПЛИС скорее всего тоже подойдет. Сложность — учесть все задержки сигналов в цикле, чтобы правильно сравнивать. Попробую реализовать это в будущем.
                  0
                  А почему не сделать потактную обработку?
                  Даже если это будет 100-1000 тактов — глаз этого не заметит)
                    +1
                    Как я понимаю — чтобы сравнить соседние ячеки на «0» — нужно пройти полный цикл вывода «кадра» на дисплей (сравнение по pixel_x, pixel_y ±1 от текущего). Пусть все мины лежат на одной линии, например, на последней строке поля — ситуация, когда количество нулей максимально. Открываем ячейку в левом верхнем углу. Тогда циклов проверки на 0 (и заполнения кадра) будет все равно мало для того, чтобы глаз мог это заметить.
                    Пока писал комментарий, понял, что можно учесть факт того, что мы сравниваем не по pixel_x, pixel_y, а поля размером 8х16. Тогда можно вывести нулевые ячейки вообще за один цикл отображения кадра на дисплей.
                      0
                      Не знаю как реализуется в ПЛИС, но хорошей практикой является является использование так называемого видеобуфера. Т.е. Имеется два буфера, назовем А и Б. На экран постоянно, непрерывно и аппаратно производится вывод того что хранится в буфере А. Мы в свою очередь во время хода игрока, каких либо вычислениях выводим данные в буфер Б. После завершения всех вычислений, когда все готово для обновления картинки буферы А и Б переключаются местами и на экран выводится буфер Б.

                      Есть различные реализации, например с тремя буферами или самая простая когда по завершении вычисления буферы не переключаются, а в буфер А копируется буфер Б с обновленными данными. В любом случае суть в том чтобы не выводить на экран какие-то промежуточные результаты а обновлять картинку только после того как она полностью готова.
                        0
                        Звучит интересно.
                        Меня смущает только объем ресурсов, необходимый для этих буферов.
                        Для выбранной ПЛИС внутри имеется всего 20 ячеек памяти по 16Кб.
                        Для реализации одного буфера (чтобы хранить всю картинку сразу) нужно: (640*480)/2^14 ~ 18.75 блоков памяти, что уже впритык, т.к еще нужно место для реализации генератора символов.

                        Можно уменьшить объем памяти, используя много мультиплексоров и выводить то одну картинку, то другую. Я так сделал для закрашенных полей и содержимым в каждом поле. То есть при нажатии «Enter» у меня происходит ряд вычислений (в частности — меняется признак выбранной ячейки для маски 8х8), закрашенный прямоугольник убирается, а на его место встает число или мина.

                        Как вариант можно подключить внешнюю память и делать буферы на ней. На этой плате распаяно 64Мб SDRAM.
                          0
                          Необязательно иметь «классический» фреймбуфер, где всю картинку хранить.
                          Можно хранить только текущее состояние игры/поля, для этого 16Кб должно хватить)
                          [Либо даже на регистрах всё сделать, если совсем мало получается].
                          Дальше уже иметь модуль, который из такой памяти «состояния» игры отрисовывает картинку.

                          Можно даже сначала только одну память (один буфер) — с двумя портами: одна для чтения ( её читает VGA модуль, и отрисовывает что-то на экране ), другая для чтения и записи — её читает/пишет логика, которая обеспечивает игру. Да, в таком подходе, возможно в какой-то момент будет отрисовываться неправда, но, возможно, глаз это не заметит :)
                            0
                            Согласен. Я думаю, что так скорее всего и нужно делать для более динамичных игр типа «танчики», где нужно постоянно отрисовывать анимацию движения нескольких объектов одновременно.
                            К счастью, для сапёра все очень статично и событийно, поэтому придумывать сложных буферов не пришлось!)
                              0
                              Почитал внимательней. Предполагал что вывод графики осуществляется через какой-то встроенный в макетную плату видео контроллер а оказывается видеосигнал генерируется ПЛИСом. Преклоняюсь перед таким хардкором. Тогда да, в таком случае не стоит заморачиваться, в любом случае для какой-то более практической задачи будет проще добавить специализированную микросхему для вывода графики а не мучить ПЛИС.
                                0
                                Да, вроде ПЛИС не особо напрягается от такой задачи :)
                                А какую микросхему предлагаете использовать?
                                  0
                                  На ПЛИС контроллер VGA в проекте занял меньше всего места (обратите внимание на маленький прямоугольник на третьей картинке, где я показал объем занимаемых ресурсов для каждой части проекта). Так что реализация VGA дело пустяковое, я его вообще из своего старого проекта взял и никак не переделывал для новой задачи.
                                  Самый смак — в конечном автомате для логики игры. :)
                                    0
                                    Наверное ошибаюсь, плис для меня черный ящик. Плюс от контроллера будет скорее в удобстве кода, и цены теоретически очень демократичные, я правда сужу по устройстве и ценам хоббийных OSD плат, камер, LCD дисплеев с контроллерами. При использовании МК видеоконтроллер нам дает бонус в виде возможности обновления картинки в любой удобный для нас момент времени не задумываясь о сложных синхронизациях и т.д., Грубо говоря у нас дисплей 50 кадров в секунду чересстрочной развертки. Нам не надо задумываться о выводе одной половины строк, другой половины строк, синхронизации всего этого дела, мы просто в любой удобный момент для нас посылаем в контроллер например для текстового режима матрицу 80х25 или даже ее изменившуюся часть а контроллер уже сам занимается растеризацией этого счастья и вывода на экран, ну и собственно генерацией одной и той же картинки пока не получит новых данных. Тут пожалуй ключевым будет «любой удобный для нас момент» т.е. не важно сколько у нас вычисление занимает времени, пол кадра, кадр, 10 секунд.
                                      0
                                      С таким контроллером было бы неинтересно. =)
                                      Но его присутствие в любом случае обязало бы в прошивке для ПЛИС описать интерфейс обмена между ПЛИС и контроллером. Но это уже другого рода задача.

            Only users with full accounts can post comments. Log in, please.