January 11, 2015 at 17:55Making tetris under FPGA
Hello!
This long New Year's weekend, I wondered: how easy it is to write some kind of simple toy on FPGA with display output and keyboard control. So another FPGA implementation of tetris was born : yafpgatetris .
Of course, games on FPGAs are made more for fun and training than for some real “production” tasks, and I’m very far from the “development” of games , you can say this is a new experience for me.
If you are interested in how you can start a game without an operating system, implementing it at the lowest level, using triggers and combinational logic, welcome to cat.
We need "something" where our game starts. One of the easiest ways is to get the devkit, where there is an FPGA and some kind of peripherals for input / output. At my disposal was a shawl from Terasic called DE1-SoC .
What can I say?
Devkit, like a devkit. A lot of peripherals: from it PS / 2 and VGA connectors will be interesting to us . For training (in schools or universities) the very thing. For our purposes, we bought it just to play around (and to educate students) than to implement some of our “production” ideas.
If suddenly you use DE1-SoC (or similar boards) in your real devices (and not just blink the LED) - share in the comments, it will be interesting.
SoCin the name of the chip means that the chip has both regular FPGA logic and an ARM processor. Looking ahead, I’ll say that I didn’t use either ARM or any software processor for my task, so you can run my project on your boards with other FPGA chips. If you are interested in reading about raising a bunch of FPGA + ARM, and what bonuses you can get from this, I advise you to refer to the article of my colleague Des333 .
Various things can be invested in the concept of tetris, so I sketched an approximate TK, which I wanted to get:
Three main parts can be distinguished:
To be honest, at first I thought to do without a keyboard and use the keys on the whale itself, but surprisingly no problems with the keyboard arose: everything worked out of the box.
To receive commands from the keyboard, you need a PS / 2 controller. I used this one .
If we turn a little to theory, then for each key a set of codes is defined that the keyboard sends when it is pressed or released.
Take the “Enter” key:
Let's see how it looks inside the FPGA:
Normal keystroke: As you can see, really:
If we hold down the key, we get this: It just comes to command 5A with some frequency. We need a small set of keys:
To determine the type of event, you can do with a shift register and a little primitive logic, and just skip all the other keys. As part of this game, I decided that it was enough for me to detect events about a key press and ignore the release. When you hold down the key, commands will still come that the key is pressed, and therefore the player still wants the figure to move or turn over. I admit, I was afraid that the figures would move too unusual, but nothing happened.
After detecting the “event” of interest to us, we put it in the FIFO, from where the “applied logic” of the game will pick it up. If you didn’t have PS / 2 on your board, but there are some keys, toggle switches, then it will be enough to write logic that will push these buttons into “events” and the game will not notice anything.
This controller allows you to connect a mouse, but I have not tried it.
On the one hand, the logic is trivial, and is described by the following FSM:
(To be honest, I don’t know if anyone in the “State Machine Viewer” production uses it, if so, share in the comments why. During the whole time of development under FPGA I opened it a couple times, and even then as part of the training).
FSM "communicates" with the following blocks / modules:
Everything is very similar to the “usual” Tetris implementation, which are written in C ++ / Java / etc: various modules act as functions in those languages. Yes, and the same problems arise: the longest I sat over the coup of the figure, the answer was spied in the quadrapassel code . One option is that you can store a table of all possible spreads (for each figure there are four options).
All code is written in Verilog, and to be more precise, in SystemVerilog. On the one hand, SystemVerilog is much more flexible than Verilog, and on the other hand, it leads to the fact that you are not limited, and you want to implement more and more different things :).
I simplified my life: the current state of the field is stored on registers (instead of internal memory), and because of this (as well as the fact that some things are not optimally done) a lot of logic is formed, and the project takes up a lot of resources (about 3.2k ALM of 32k ) If you move to memory, you will have to do some things sequentially (for example, a shift down the entire field, when you need to remove the line that is filled). Most likely I will not redo the use of memory.
For test purposes, I put together a project for DE0 / DE1 boards (brothers of the board that I have, but with low-cost chips: they have fewer resources, and they are more of a "younger generation"): the resource project breaks in. However…
Information on how to use the FPGA to display an image on the display via VGA can be found a lot, for example on the hub , so I will not dwell on this in detail.
In this whale, the VGA output is made as follows:
Each VGA_CLK clock must be set to a new color value in the RGB model, and then the DAC converts these values to the required signal level.
As a controller of VGA signals, I took the module from demo examples that are on the CD for this kit. It's funny that there is the concept of a CD, but there is no CD included with the board: you need to download the archive from the Internet.
This "controller" Terasic uses in other whales: it is easily googled by the name "vga_time_generator". It is convenient in that you can configure it for any operation mode (640x480, 800x600, etc), and in that it gives the coordinates ( pixel_x , pixel_y ) of the current pixel for display. Our task is to substitute the necessary color values depending on these coordinates. I decided that 640x480 on the big monitor doesn’t look very good and moved to 1280x1024, just passing the necessary values from the standard to the module . In addition, I had to change the VGA_CLK value : instead of 25.175 MHz, it became 108 MHz. True, I later regretted it a little, but beauty requires sacrifice. Let's consider how to display some primitive objects.
For instance:
An orange square 200x300 pixels in size is displayed, with the upper left corner located at (100, 100).
Or:
Displayed HELLO HABR font with a height of 5 pixels in orange on a black background. (Take a look at the units in the msg array ).
I think it’s clear how you can draw some kind of static message or game field.
To display statistics (lines “Score”, “Lines”, “Level” and their values) I decided to go along the “classic” path. You can see it, for example, here .
Suppose some logic has already determined which character (read, letter or number) we want to output # right now (depending on pixel_x , pixel_y ). To display it, we use a ready-made font table, where the units will indicate which pixel should be painted with the font color, and with zero - the background color, such as:
In many projects (which can be found on the network) with VGA such a table ( Font ROM ) is used, but they are designed for a 640x480 display: for 1280x1024 this is too small, so you need to prepare a similar table, but with a "large" font.
The nafe utility helped me with this . At the input, it receives a psf file, at the output, a text file with X, in those pixels that need to be drawn. Using your favorite language (or slightly redo the output of the original program), change X to “1”, and spaces to “0”, and add a header to make an mif file (which is then used to initialize ROM).
The largest font that I found in my psf format was 32x16, and, in principle, it was enough for this task, but I would like to do a little more. As far as I understand, there are no restrictions, and using this utility you can prepare a ROM with any characters (for example, Russian letters).
However, for the yafpgatetris header and the GAMEOVER message , this size seemed small to me, and I decided to output these messages in the same way as the HELLO HABR line in the example above. The only question is how to prepare msg , because I really didn’t want to do this with pens.
Immediately came up with a relatively simple bicycle (?) Solution:
The resulting set of zeros and ones can also be put in ROM (in a different font than, of course).
A couple of photos from the “development in progress” series:
Sources:
https://github.com/johan92/yafpgatetris
Video:
I tried to make the project as parameterized as possible, and logically divided it into parts, so if you want to make “races” based on my project, where you need to dodge other cars, or a snake, just write your main_game_logic and correct the output a little bit (if necessary) .
It took about 5 days to develop, if we consider “clean time”: I had to tinker with the flip of the figure (in fact, rewrite the algorithm twice), it took a lot of time to select the colors, sizes, alignment and location of the messages. The internal perfectionist always demanded that the internal designer move something, increase / decrease something, etc. For myself, I learned that GUI development is not mine) As a result, I took the colors for the figures from the Tetris application on Vkontakte.
If you bought a kit and want to learn how to develop for FPGA, I do not recommend doing tetris directly as the first project. Start with LEDs, segment indicators, watches, and other classic things. When this passes, you can try Tetris, or some other simple game. I hope my project will help in this endeavor.
Thanks for attention! If you have questions, ask without a doubt.
This long New Year's weekend, I wondered: how easy it is to write some kind of simple toy on FPGA with display output and keyboard control. So another FPGA implementation of tetris was born : yafpgatetris . Of course, games on FPGAs are made more for fun and training than for some real “production” tasks, and I’m very far from the “development” of games , you can say this is a new experience for me.
If you are interested in how you can start a game without an operating system, implementing it at the lowest level, using triggers and combinational logic, welcome to cat.
About Devkit
We need "something" where our game starts. One of the easiest ways is to get the devkit, where there is an FPGA and some kind of peripherals for input / output. At my disposal was a shawl from Terasic called DE1-SoC .
What can I say?
Devkit, like a devkit. A lot of peripherals: from it PS / 2 and VGA connectors will be interesting to us . For training (in schools or universities) the very thing. For our purposes, we bought it just to play around (and to educate students) than to implement some of our “production” ideas.
If suddenly you use DE1-SoC (or similar boards) in your real devices (and not just blink the LED) - share in the comments, it will be interesting.
SoCin the name of the chip means that the chip has both regular FPGA logic and an ARM processor. Looking ahead, I’ll say that I didn’t use either ARM or any software processor for my task, so you can run my project on your boards with other FPGA chips. If you are interested in reading about raising a bunch of FPGA + ARM, and what bonuses you can get from this, I advise you to refer to the article of my colleague Des333 .
What do we want to get
Various things can be invested in the concept of tetris, so I sketched an approximate TK, which I wanted to get:
- Standard set of figures. Their behavior should be as similar as usual.
- The game is colorful. Each figure has its own color.
- The figures are randomly generated with a uniform distribution.
- There should be a window in which the following figure is displayed.
- There should be information about the state of the game: the number of points, the number of lines removed, the current level.
- Points are awarded on a "progressive" scale: the more lines removed at a time, the more points.
- The higher the level, the greater the falling speed of the figures.
- The “end of the game” is correctly detected, it is possible to start a new game.
- User actions are input from the keyboard (PS / 2).
- The display of the status of the field and other things takes place on a regular display via the VGA interface.
Project outline
Three main parts can be distinguished:
- User input. We accept data from the keyboard and “act” on the system.
- Everything related to the game itself. In fact, FSM (finite-state machine), which receives “requests” from the player, and “does everything”: generates new figures, moves them, removes lines, and so on.
- Displays the status of the game. We draw on the display via the VGA interface.
PS / 2
To be honest, at first I thought to do without a keyboard and use the keys on the whale itself, but surprisingly no problems with the keyboard arose: everything worked out of the box.
To receive commands from the keyboard, you need a PS / 2 controller. I used this one .
If we turn a little to theory, then for each key a set of codes is defined that the keyboard sends when it is pressed or released.
Take the “Enter” key:
- Make: 5A
- Break: F0.5A.
Let's see how it looks inside the FPGA:
Normal keystroke: As you can see, really:
- Press the key, 5A comes.
- We release: F0 comes, after it 5A.
- Press again: comes 5A and so on.
If we hold down the key, we get this: It just comes to command 5A with some frequency. We need a small set of keys:
- conventional arrows - to control the figure.
- n - to start a new game.
To determine the type of event, you can do with a shift register and a little primitive logic, and just skip all the other keys. As part of this game, I decided that it was enough for me to detect events about a key press and ignore the release. When you hold down the key, commands will still come that the key is pressed, and therefore the player still wants the figure to move or turn over. I admit, I was afraid that the figures would move too unusual, but nothing happened.
After detecting the “event” of interest to us, we put it in the FIFO, from where the “applied logic” of the game will pick it up. If you didn’t have PS / 2 on your board, but there are some keys, toggle switches, then it will be enough to write logic that will push these buttons into “events” and the game will not notice anything.
This controller allows you to connect a mouse, but I have not tried it.
The basic logic of the game
On the one hand, the logic is trivial, and is described by the following FSM:
(To be honest, I don’t know if anyone in the “State Machine Viewer” production uses it, if so, share in the comments why. During the whole time of development under FPGA I opened it a couple times, and even then as part of the training).
FSM "communicates" with the following blocks / modules:
- gen_sys_event - a timer that counts the time after which it is necessary to automatically move the figure down.
- gen_next_block - generator of a new figure.
- check_move - check if the current "move" is possible.
- tetris_stat - accumulation of "statistics".
- user_input - reads the event that the user "generated".
Everything is very similar to the “usual” Tetris implementation, which are written in C ++ / Java / etc: various modules act as functions in those languages. Yes, and the same problems arise: the longest I sat over the coup of the figure, the answer was spied in the quadrapassel code . One option is that you can store a table of all possible spreads (for each figure there are four options).
All code is written in Verilog, and to be more precise, in SystemVerilog. On the one hand, SystemVerilog is much more flexible than Verilog, and on the other hand, it leads to the fact that you are not limited, and you want to implement more and more different things :).
I simplified my life: the current state of the field is stored on registers (instead of internal memory), and because of this (as well as the fact that some things are not optimally done) a lot of logic is formed, and the project takes up a lot of resources (about 3.2k ALM of 32k ) If you move to memory, you will have to do some things sequentially (for example, a shift down the entire field, when you need to remove the line that is filled). Most likely I will not redo the use of memory.
For test purposes, I put together a project for DE0 / DE1 boards (brothers of the board that I have, but with low-cost chips: they have fewer resources, and they are more of a "younger generation"): the resource project breaks in. However…
Hidden text
... straight out of the box will not work:
- Quartus will swear at some things in the qsf file, as I collected for the 14th quarter, where there is no Cyclone II / III. The early versions of the quartus do not know these things: you have to use the pens to delete these lines in the qsf file, and then, in the sense, put the same daws in the quartus GUI.
- It does not fit in frequency: the “main” frequency in this project is 108 MHz (main_game_logic itself and VGA rendering work on it). Looking a little ahead, the frequency is 108 MHz - because the resolution is 1280x1024, if you use 640x480, then there will be a frequency of 25 MHz, and it will fit.
- You may need to regenerate megafunctions for PLL and FIFO, as They were created for Cyclone V.
- The display output may need to be slightly edited (select other colors), as there, for each color, only four bits are allocated (as I understand it), against eight, as in this board.
Display
Information on how to use the FPGA to display an image on the display via VGA can be found a lot, for example on the hub , so I will not dwell on this in detail.
In this whale, the VGA output is made as follows:
Each VGA_CLK clock must be set to a new color value in the RGB model, and then the DAC converts these values to the required signal level.
As a controller of VGA signals, I took the module from demo examples that are on the CD for this kit. It's funny that there is the concept of a CD, but there is no CD included with the board: you need to download the archive from the Internet.
This "controller" Terasic uses in other whales: it is easily googled by the name "vga_time_generator". It is convenient in that you can configure it for any operation mode (640x480, 800x600, etc), and in that it gives the coordinates ( pixel_x , pixel_y ) of the current pixel for display. Our task is to substitute the necessary color values depending on these coordinates. I decided that 640x480 on the big monitor doesn’t look very good and moved to 1280x1024, just passing the necessary values from the standard to the module . In addition, I had to change the VGA_CLK value : instead of 25.175 MHz, it became 108 MHz. True, I later regretted it a little, but beauty requires sacrifice. Let's consider how to display some primitive objects.
For instance:
`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;
An orange square 200x300 pixels in size is displayed, with the upper left corner located at (100, 100).
Or:
`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;
Displayed HELLO HABR font with a height of 5 pixels in orange on a black background. (Take a look at the units in the msg array ).
I think it’s clear how you can draw some kind of static message or game field.
Print lines
To display statistics (lines “Score”, “Lines”, “Level” and their values) I decided to go along the “classic” path. You can see it, for example, here .
Suppose some logic has already determined which character (read, letter or number) we want to output # right now (depending on pixel_x , pixel_y ). To display it, we use a ready-made font table, where the units will indicate which pixel should be painted with the font color, and with zero - the background color, such as:
"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
In many projects (which can be found on the network) with VGA such a table ( Font ROM ) is used, but they are designed for a 640x480 display: for 1280x1024 this is too small, so you need to prepare a similar table, but with a "large" font.
The nafe utility helped me with this . At the input, it receives a psf file, at the output, a text file with X, in those pixels that need to be drawn. Using your favorite language (or slightly redo the output of the original program), change X to “1”, and spaces to “0”, and add a header to make an mif file (which is then used to initialize ROM).
The largest font that I found in my psf format was 32x16, and, in principle, it was enough for this task, but I would like to do a little more. As far as I understand, there are no restrictions, and using this utility you can prepare a ROM with any characters (for example, Russian letters).
However, for the yafpgatetris header and the GAMEOVER message , this size seemed small to me, and I decided to output these messages in the same way as the HELLO HABR line in the example above. The only question is how to prepare msg , because I really didn’t want to do this with pens.
Immediately came up with a relatively simple bicycle (?) Solution:
- We type the text of the desired font and size in Paint / GIMP.
- We save in PNG without compression and smoothing.
- We use some ready-made library to read the PNG file and for each pixel print 0 if “color is white”, 1 if “color is black”.
The resulting set of zeros and ones can also be put in ROM (in a different font than, of course).
A few pictures
A couple of photos from the “development in progress” series:
Hidden text
We learned how to display the field: the figures simply fall down and all are of the same color.
Added statistics and different colors. The colors are vyrviglaznye :)
Well, the final version is at the beginning of the article :)
PS
To be honest, I don’t know why when photographing such “stains” on the display, maybe I didn’t turn on some settings in the VGA-crust, or I’m just out of luck ...
Added statistics and different colors. The colors are vyrviglaznye :)
Well, the final version is at the beginning of the article :)
PS
To be honest, I don’t know why when photographing such “stains” on the display, maybe I didn’t turn on some settings in the VGA-crust, or I’m just out of luck ...
Summary
Sources:
https://github.com/johan92/yafpgatetris
Video:
I tried to make the project as parameterized as possible, and logically divided it into parts, so if you want to make “races” based on my project, where you need to dodge other cars, or a snake, just write your main_game_logic and correct the output a little bit (if necessary) .
It took about 5 days to develop, if we consider “clean time”: I had to tinker with the flip of the figure (in fact, rewrite the algorithm twice), it took a lot of time to select the colors, sizes, alignment and location of the messages. The internal perfectionist always demanded that the internal designer move something, increase / decrease something, etc. For myself, I learned that GUI development is not mine) As a result, I took the colors for the figures from the Tetris application on Vkontakte.
If you bought a kit and want to learn how to develop for FPGA, I do not recommend doing tetris directly as the first project. Start with LEDs, segment indicators, watches, and other classic things. When this passes, you can try Tetris, or some other simple game. I hope my project will help in this endeavor.
Thanks for attention! If you have questions, ask without a doubt.