Minesweeper на FPGA

Привет всем!

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

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

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

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

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

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

Основные особенности девкита:

• ПЛИС 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
За основу взят этот проект ^[3]. Заработало сразу. Интерфейс последовательной передачи достаточно примитивный: две линии: PS2_CLK и PS2_DATA, по которым идут команды от клавиатуры.
Подводный камень — изначально с помощью «Make» кода я генерировал единичный импульс (по фронту), который бы сигнализировал «нажатие» клавиши. Это приводило к имитации повторного нажатия, когда происходило нажатие другой клавиши. Так как байт «Make» и «Break» кодов совпадают, то пришлось сделать условие более явным, учитывая «Break» код.
Таблица кодов для PS/2 контроллера приведена по ссылке ^[3] выше.

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

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

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

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

В моем проекте используется 5 основных комбинаций автомата:

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

Память символов
Найдена на просторах Интернета ^[7]. Размеры одного символа 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. Перед стартом расстановка мин выбирается случайно из памяти для поля.
Занимаемые ресурсы кристалла (ПЛИС почти пустая):

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

Исходный код на github ^[8].

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

Автор: capitanov

Источник ^[9]