Loading repository data…
Loading repository data…
chili-chips-ba / repository
Demo of how to use https://github.com/openXC7 tools (yosys+nextpnr-xilinx) to implement the HW side of a custom SoC with RISC-V CPU & our special Video Controller in Basys3 Artix7-35T. Complemented with SW in the bare-metal 'C' they, together, make for this classic game. Except that it's now, in the standard BiH tradition, with a twist of our own.
This is the very first, independent and unbiased attempt to use openXC7 tool flow for a real-life FPGA design. All its earlier uses and example projects were created by the insiders, who knew ahead of time about what pitfalls to avoid. And yes, we have uncovered issues along the way, duly reported them, and kept marching along, at times even resorting to hacks to make it work.
Most importantly, we did not even know that we were the Alpha testers, and learned it only when everything was already done 😂.
The compute platform used for this work was Windows Subsystem for Linux (WSL) as opposed to native Linux/Ubuntu. The decision to go with WSL came from our intent to maximize project accessibility, not leaving out even the middle school youngsters, who typically don't have native Linux machines.
While we did not use any of https://www.nand2tetris.org materials, our project can be viewed as a bootstrapped, super-compressed variant of it. We therefore warmly recommend this superb step-by-step guide /put together by Shimon Schocken and Noam Nisan/ on how to build functioning Tetris starting from the mere NAND gates.
If you're starting without prior knowledge of electronics, digital logic circuits, computers or programming, then JMP to the link above, else CONT.
Even though most of us know what Tetris is and how to play it, we'll first briefly explain its logic and rules.
Tetris is a combinatorial game where a player maneuvers differently-shaped pieces (aka 'tetrominoes') as they descend onto the playing field. The objective is to complete the lines by filling them with tetrominoes. When a line is fully filled, it gets automatically cleared, and the player earns points. The player can then utilize the cleared space to continue the game. It's Game Over when the lines with gaps (thus not cleared) reach the top of the playing field. The longer a player can delay this outcome, the higher his/her score. In the multiplayer games, the players compete to outlast their opponent(s).
In our TetriSaraj, the pieces (tetrominoes) are entering the field from the sides, in the random fashion, so leaving less time to think about approach and strategy. While our pieces are "falling" horizontally from both sides, one at the time, the logic is otherwise the same as ordinary Tetris. The objective is to complete vertical lines by filling them with tetrominoes.
There are two main parts of our solution: HW and SW. To save time, and in the spirit of FPGA parallism, we've worked on both in parallel.
The first development track was the construction of Basys3 SOC with soft-core CPU, complemented with our special, simple, yet capable Mega-Character (MC) Video Controller for game visualization. This work was undertaken by the HW (Verilog RTL) group within our team.
At the same time, the SW group was working out the game algorithm in the comfortable WinOS PC Visual Studio setting, where the hi-res graphic output was emulated on a low-res terminal, as illustrated in the image below:
When the logic of our game was fully worked out, we've switched to integration activities.
Integration in this context is the merge of SW and HW track.
Other than this terminal emulation of the Game Logic, we opted out of logic simulation. Even the hardware team found it more productive to validate the Video Controller directly on the board, using test patterns much simpler than the final game, which they wrote in 'C', indepedently from the software team.
The hard-core digital design puritans may declare it as a bad practice, and may even bring Formal into the fray. We would counter them with: Welcome to the world of full field programmability! Joking aside, it was the nature and low complexity of the problem at hand that allowed us to take this shortcut:
Porting from WinOS and to the bare-metal RISC-V was a sizeable part of our integration and merging effort.
To expedite the software iterations without having to rebuild the entire FPGA, we've developed a simple, robust and platform-agnostic own method for CPU program uploads via UART. That's a notable departure from the two typical approaches used in most other projects:
Not possible due to lack of openXC7 support for BSCANE2 Xilinx component
Not possible with Basys3, due to shortsightedness of board designers, coupled with openXC7 lack of support for STARTUPE2 Xilinx component
The beauty of our CPU code download method is that it's fully portable across FPGA vendors and boards -- It's without inherent dependencies on the special, vendor-specific IP.
This section is about the algorithm basics, i.e. the logic of the game. It's worth emphasizing that this the heart of our app, and stays the same for both full-fledged PC and bare-metal RISC-V implementation.
The other SW parts are: Game Controls, Timing and Rendering. They depened on the HW platform, and have to be adapted to it through porting process from PC host to embedded CPU.
Tetrominoes are the essence of the Game Logic element. They're illustrated in the figure below.
There are 7 primary tetromino shapes. Including rotations, we get to 28 different shapes. However, to save memory, we store only the original shapes, using a 7x16 matrix of 1s and 0s, where 1s represent blocks, and 0s represent empty space. For example, let's take the 2nd tetromino, the squared one, and write it row-by-row from left to right:
0, 0, 0, 0; 0, 1, 1, 0; 0, 1, 1, 0; 0, 0, 0, 0;
This is clearly an array of 16 elements. Seven such arrays make the full primary tetromino set. The entire 40x30 playing field is stored in a similar array, for which we use "field" variable.
So, how can this 7x16 primary tetromino matrix account for all 28x16 rotations? The answer is: By using algorithmic smarts in lieu of the brute force. For that, we have rotate function with 3 input arguments: X coordinate, Y coordinate, and Rotation. This function returns the Index of the so-rotated block in the original piece. We should note that the X, Y coordinates take values from 0..3; R is {0, 90, 180, 270}; and returned Index is 0..15. Rotation is executed clockwise.
For example, let's have a look at this shape and its rotations:
The 1st piece is the original, primary tetromino. The remaining 3 are its rotations. We now want to find the Index in the original piece for the corresponding mutant with coordinates X=2, Y=1, R=90 degrees. The relation between shapes rotated by 90 degrees is: "Index = 12 + Y - (X * 4)". Which means that this specific block is on Index=5 of the original piece.
The same applies to other rotations and other figures. Let's now have a look at R=270 degrees. We observe the block on coordinates X=1, Y=2. The relation for this case is "Index = 3 - Y + (X * 4)". That gives us 5 again, meaning that this specific block is the same as the block on Index 5 of the original piece.
So, what is the Game Logic?
Upon receiving a game tick, we first look at the commands. If one of the command buttons is pressed, we try to move the piece in the specified direction, or rotate it. For that, we first check whether the moved-or-rotated piece can fit in the position the command wants it to be in. If it cannot fit, we lock the piece in the field /* write a shape-specific values in the field variable */, i.e. don't honor the command.
If it can fit, we honor the command, check whether any vertical lines were formed, and store the X coordinates of the formed lines so we can delete them. The erasing of the vertical is straightforward -- We just set the current line to empty and move all lines "above" it to one place "below". When all this is done, we generate a new random piece.
So, how do we check if the piece can fit in a specific position?! That's a 4-step process: - find the correct Index in the rotated piece - variable "pi" in the function - find the correct Index in the field - variable "fi" in the function - check the boundaries - check if the piece can fit
This fit test is done by checking if both:
The timing of the game is controlled by our own ticks. As the game progresses, the game ticks become more frequent, making it more challenging for the player.
On the PC side (implemented in C++), we use "this_thread::sleep_for" method, where the sleep is 50ms, and also a counter which we increment after the sleep. When the counter gets to a certain value (let's call it speed) we move our piece. This is one game tick. As the game progresses, and we've stacked a few blocks, the speed value decrements, which is perceived as a faster play.
A similar method was used for Basys3. Except that, in the absence of "this_thread::sleep_for" there, we had to come up with our own embedded sleep methods. Other than that, the rest of the logic is the same.
On the PC side we used "GetAsyncKeyState" method to detect if a keyboard button was pressed. The controls are: Left, Right, Up, Down arrow, and "Z" key for rotation. Upon detecting that a key was pressed, we first check whether the piece can be moved at all. That's covered by "DoesPieceFit" function.
The same logic applies to Basys3, where FPGA provides a GPIO register for the pushbuttons, from which we then read the button values. This is accomplished by "GetButtonsState" function.
For video on the PC side we use Windows.h library to create a console screen and draw on it. This drawing is based on our field variable, which keeps the complete info about the playfield, with all the shapes on it, including the current game state.
The video rendering on the FPGA side is a bit more complicated and involves writting into MC Frame Buffer registers from the same field variable.
This HW/SW setup is more than the mere TetriSaraj game. It'