Geekly Articles each Day
📜 ⬆️ ⬇️

Minesweeper on FPGA

Hello to all!

After reading the article “Making Tetris for FPGA” , I remembered that I had a similar project that I once used to give my girlfriend a kind of “hand and heart” offer.

Why not do something like that yourself?
')
Having dug up the sources, I resumed the lost knowledge and decided, on the basis of the old project, hastily to write a simple version of the game “Sapper” on the old Spartan3E FPGA. Actually, the implementation of the game "Minesweeper" at the level of logic gates and the main features of the development of the FPGA company Xilinx and will be discussed in this article.

Debug board


A few years ago, I was looking for a budget version of a debug board with FPGAs and the simplest piping with different interfaces such as VGA, PS / 2, LEDs and an LED display, as well as trigger switches. Then I stopped at the simplest Chinese whale, which was the easiest to order with ebay for $ 135.00, including shipping. By the way, the kit came incomplete, so I left an angry review, for which the seller returned ~ $ 20. So the fee cost me about 4000r at the old prices.


The official website of the manufacturer of the whale.

The main features devikita:

Spartan3E XC3S500E crystal resources are listed in the table:



Of all the variety, VGA and PS / 2 connectors are necessary for the implementation of the game “Minesweeper”. In addition to them, I used a switch for global reset ( reset ) of the logic inside the FPGA.

The basic concept of the game


What happened?
In the old project implemented the following pieces:
- input commands from the keyboard (control PWM modulator and display);
- VGA handwritten interface with a resolution of 640x480;
- blinking heart on the matrix of LEDs 8x8 on the basis of PWM.

The first two points significantly accelerated the development of the game, so I did not reinvent the wheel.

Rules for the game:

FPGA programming language: VHDL .

This is what the finished project in the PlanAhead program looks like after the synthesis and trace stages. The blocks in the purple frame are the crystal resources occupied.



Big block: the main logic of the game;
Middle block: PS / 2 keyboard controller;
Small block: VGA display controller.

Project Hierarchy:
At one of the first design stages, it is necessary to estimate what the project will look like and how many components it is more convenient to describe. I came up with the following structure:

-> Top Level
----> PS / 2 controller
----> VGA 640x480 Controller
----> Game Controller
-------> Block of drawing the borders of a rectangle,
-------> Block for drawing shaded fields 8x8
-------> Block for drawing mines and numbers on the field
-----------> Memory for laying mines
-----------> Memory for characters
-------> Block for drawing text and conversational messages
-----------> Memory for characters

So it looks in the environment "PlanAhead" from Xilinx.



Upper level
It describes the main I / O ports, contains a DCM frequency synthesis block for converting an input frequency from 50 MHz to 25 MHz. The top level code looks like this:

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 controller
Based on this project . Earned immediately. The serial transmission interface is quite primitive: two lines: PS2_CLK and PS2_DATA , which are followed by commands from the keyboard.
Reef - initially, using the “Make” code, I generated a single impulse (on the front), which would signal the “pressing” of the key. This led to a simulated re-press when another key was pressed. Since the bytes of “Make” and “Break” of codes coincide, we had to make the condition more explicit, taking into account the “Break” code.
The code table for the PS / 2 controller is provided by the link above.

VGA controller
I wrote it myself sometime for learning purposes, but the algorithm of its operation is exactly the same as that of all VGA controllers . On Habré, too, there is such .



Key Features:
- The frequency of the controller: 25.175 MHz
- Screen resolution: 640x480
- Refresh rate: 60Hz
- Available palette: RGB

Unfortunately, the debug board does not have built-in chips for decoding the color palette, so only 3 primary colors (red, green, blue) and 5 combinations (yellow, purple, cyan, white, and black) are available. But this does not prevent to come up with a color scheme and even display flashing images! (see video at the end)

Game controller
The easiest way to describe the game controller "Minesweeper" is based on the state machine ( FSM ). It is necessary to invent the conditions of the automaton in which certain events will be processed.

My project uses 5 basic combinations of the machine:
  1. WAIT_START (resetting all control signals, min counter, starting a random game generator;
  2. PLAY (game process: control of buttons from the keyboard, search for min);
  3. CHECK (check if mine is found - go to the end of the game);
  4. GAME_OVER (determines the event of victory or defeat, displays additional messages on the display);
  5. RST (optional stage - clears the screen, resets all control signals, without the possibility of starting a new game).

Character memory
Found on the Internet . The size of one character is 8x16. Example for symbol "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

All characters fit into a single block RAMB16 memory block of the crystal. The memory is arranged in such a way that the symbol consists of 16 vectors of digit capacity 8. To output characters to the display, 4 lower order address digits must be connected to the Y coordinate vector. Logic '1' - colors the symbol in color, '0' - background color (black).

Memory for placing mines on the field
I modified this part of the project for the longest time, inventing various sophisticated solutions. In the end, I decided to make the next component in the form of a ROM-memory, which selects the game.

A piece of code:

 constant N8x8 : integer:=8; --   88 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);

The constants N8x8 and Ngames define the size of the field and the number of games. The number on the field corresponds to the mine or the number of mines around it. The rules are very simple:

Why is that?
I didn’t think of a situation when around a point there can be 7 or 8 minutes at a time. For 8 min and 8x8 field these are too uninteresting decisions. In addition, the numbers from 0 to 7 occupy only 3 bits, whereas combinations from 0 to 8, and 9 for mines occupy 4 bits. In this regard, I am a big fan of saving the internal logic and trace resources of the crystal, even if these resources are enough for 5 projects.

Thus, all the numbers fit into a kind of ROM-array, which can be added to their games. In my project 32 games are implemented, which takes a little less than 1 memory block RAMB16. It should be noted that the numbers are given in integer format. A special function was written to translate them into std_logic_vector (2: 0) and further processing. The integer format has simplified the recording of new games and significantly saved time. Many developers of FPGA in the VHDL language are sometimes introduced into a stupor by the situation when an integer format is used, since constructions with an integer type are not always synthesized, i.e. They can not be checked in real hardware. But for the ROM generator integer is the optimal choice.

In order to add your mine set-up, you need to correctly fill the 8x8 field in the array. Variations of games typed by hand. There are a total of 32 different combinations of mines in my project.

Border rendering blocks and 8x8 margins
Initially, I implemented them on a symbol generator, but then I decided to save crystal resources, since I thought that for the sake of painted squares and frames it makes no sense to use the whole RAMB16 cell. (Resource optimization!) So everything is done on multiplexers. I will not dwell on this in detail.

Block for drawing mines and numbers
Converts data from a memory set of games to numbers and mines on the screen using character memory. Initially, I wanted to bring out a 8x8 square field, but then I was too lazy to rewrite the ROM generator, and I left it rectangular.
For this block, we also had to create a special 8x8 mask, with which, by pressing “Enter”, the filled cells would turn into a number or a mine.

Text and messages
The text is written entirely - that is, everything is written on the screen immediately, but depending on the stage of the game, some information remains invisible (for example, messages about defeat or victory). The same character generator is used. The character size is 8x16, so the display field 640x480 can be divided into sections 80x30, in which the characters are displayed. How it's done?

Below is a simple example:
 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;

First you need to figure out how to choose a particular character using a memory address. It can be seen that the address consists of two vectors "y_char" and "data_box".

y_char (3 downto 0) is the low-order bits of the coordinate vector along the Y axis. This data is updated automatically and comes from the VGA controller.
data_box (6 downto 0) - the signal selects which character will be used on the field. This vector must be written by yourself.

If we write data_box <= “000001”, then the first symbol from the generator will be written to the “data_rom” vector. In the "pr_sel" process, the data vector is converted into a sequential code. Depending on the 3 least significant bits of the register of the X coordinate, a particular bit of the “data_rom” vector is selected. At first, I was faced with the problem of mirroring data on the screen. The solution is trivial - inversion of the x_char signal.

The output data is an RGB signal that goes to the VGA connector after a logical conversion with data from the coefficient memory.

Implementation in the gland


All this is going into one big project. For beauty, using a simple counter, screwed up the blinking of the messages of victory / defeat, and also added a generator for selecting a random game.
The source code on the VHDL necessarily screwed the * .UCF file, which describes the connection of FPGA ports and various attributes. Example:
 ## 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 ;


With the help of CAD Aldec Active-HDL and Xilinx ISE , the FPGA project is synthesized and traced. Due to the complexity of event handling, debugging was done without writing Testbench, directly uploading the firmware in the FPGA and checking the display output. As a rule, everything worked at once. The main mistakes consisted in synchronization of signals. For example, simultaneous address snapping operations and data read attempts. Such errors are fixed quickly by introducing in the right place an additional delay per clock. In severe cases, ChipScope Pro ( Core Inserter and Analyzer ) was used.

Conclusion


The mini-game "Saper" successfully earned on the debug board.
The field size is 8x8, the number of mines on the field is 8.
The number of games is 32. Before starting, the placement of mines is chosen randomly from the memory for the field.
Crystal resources occupied (FPGA almost empty):



A photo
The result looks like this:



One more photo...
Tracing in FPGA-Editor in the game controller area:



Schematic view of the project in RTL Schematic:



Debugging a project in ChipScope Pro Analyzer (counting the number of open empty fields):



Source code on github .

Video demonstration of the game

Source: https://habr.com/ru/post/274841/

More articles:


All Articles