Embedded Files
FPGA Minesweeper
FPGA Minesweeper
An implementation of the classic Minesweeper video game, but on an FPGA!
What?
What?
The FPGA Minesweeper is written in VHDL and flashed onto the Basys3 FPGA Dev Board, but was designed for general use for most FPGAs. This project was a final project for a VHDL/Digital Design course from university. The Basys3 features 16 switches, 16 green LEDs above those switches, 5 push buttons in a "+" shape, and a multiplexed 7-segment display.
Unlike the famous Minesweeper video game, this version is one-dimensional. The "minefield" is the 16 LEDs on the Basys3, where a lit position indicates an "uncleared" position (potential bomb here), and an unlit position indicates a "cleared" position (no bomb here). Three bombs will randomly be placed inside of the minefield. The bombs can be length 1 or 2, and there must be atleast a one "LED" gap between bombs. This is neat! But, how can you clear positions in the minefield? When a switch is activated, all of the positions between two bombs will be cleared. Unless you hit a bomb, of course! What about the 7-segment display? The game lasts 60 seconds, and your remaining time left is your score. The two left digits are the record score, and the two right digits are the current score/timer (counts down from 60 to 0).
Minesweeper Flashed on the Basys3 Dev Board!
Win/Lose Conditions
The conditions for winning the game are, of course, being able to clear the minefield! "Clearing the minefield" is essentially clearing all of the positions around the bombs, leaving just the bombs lit.
The conditions for losing the game are either hitting a bomb or running out of time.
At the end of the game, the bombs will flash within the LED array, showing you where they were located.
How?
How?
In this section, some of the more complicated technical implementations are going to be detailed pertaining to the design of the Minesweeper game.
Game Flow State Machine
A finite state machine is used to control the flow of the game with 4 states, NOGAME, INITIALIZATION, GAMERUNNING, and ENDGAME.
NOGAME: No game is running. When all of the switches are deactivated and the start button is presesed, then the game will begin to initialize. Additionally, a 15-bit timer begins when NOGAME is entered. This timer is used to randomly place the bombs within the minefield. (More about bomb placement talked about later).
INITIALIZATION: Main job is to place the randomly generated bombs within the minefield, and resolve instances where bombs may collide with each other. Other things, such as the LEDs and the game timer, are also initialized.
GAMERUNNING: The game begins! When a switch is activated, positions will be cleared in the minefield. Checks for win and lose conditions, and migrates the game to the ENDGAME state.
ENDGAME: The bomb locations are blinked at 4Hz, and the high score is updated.
Reset: On reset, the high score is cleared and the game is returned to the NOGAME state.
State Machine Diagram for the Game Control Flow
Random Bomb Generation
Randomly generating the bombs is an interesting task that can be approached multiple different ways, especially on an FPGA. The solution chosen was to use a 15-bit counter to generate a random number that would increment on each rising clock edge. With a 100MHz clock signal, it would take approximately 327 microseconds to fully cycle through the count, giving us a truly random number (unless you have insanely quick reflexes and can do this!). This 15 bit number is then separated into three 5-bit numbers, representing the three bombs. The lower four bits correlate to the placement of the bomb (bit 0-15 in the 16-bit minefield), and the fifth bit determines the length of the bomb (0 = length of 1, 1 = length of 2).
Now, there is another interesting problem, what happens if two bombs are randomly generated ontop of eachother? Before the bomb is placed inside the bombPositions array, collisions are checked through a bitwise AND of the new bomb and the bombs that have been placed (0 = no bomb, 1 = bomb). If there is no collisions between the bombs, the entire bitwise AND will result in 0's, but if there is a 1 at all, then there is a collision. To resolve this problem, the new bomb's position is shifted to the left (looping back to 0 if the position is 15) until there is no collision.
This can seem like a rather complicated method just to randomly place the bombs for the Minesweeper game. However, it is necessary so that the bomb generation truly is random.
RTL Design Block Diagram for the Minesweeper Game
Clearing Positions in the Minefield
During the GAMERUNNING state, when a switch is activated then all positions between two bombs must be cleared. To accomplish this, the concept of "shift left" was modified to fit this problem as well to deactivate LEDs that were between two bombs. When a switch is activated, a pointer of a single "1" is shifted left and bitwise AND with bombPositions (0 = no bomb, 1 = bomb). When the resulting vector is all 0's, it signifies that the bomb has not been found, the LED should be deactivated, and to continue shifting (unless the end of the minefield is reached). However, when there is a "1" within this resulting vector, then a bomb has been found and the shifting should stop. After the shift left is completed, then the pointer is shifted right in a similar manner until the right bomb is located or the end of the minefield is reached.
This solution, although a fairly complex implementation for a simple task, allows for consistency throughout the design of how the minefield is represented and that modifications are only made on the 16-bit array. It is also important to consider how loops are synthesized with the FPGA board or manufacturer, as improper considerations could lead to glitches in the game (I learned this the hard way here).
Result
Result
The end result was a fully functional Minesweeper game that could be repeatedly played until your heart is content. My personal high score was a 59 out of 60, it will be hard to beat that! This was certainly one of the more challenging projects that I have completed, as there is a rather complicated digital design underneath the hood of this FPGA Minesweeper. Despite the challenges faced in this project, it was a great way to build confidence in digital design and FPGA development. Here are some takeaways I have from this project:
It is important to articulate a general system design before tackling any complex software problems (not just for digital/FPGA, but across all engineering)
Design block diagrams and RTL schematics can be very useful for organizing the development, testing, and integration of your system
Focus on writing code that can be easily synthesized -- the best solutions are often the most simplest!
This will always be one of my favorite projects that I completed. It certainly felt the most rewarding when my solution was fully functional! I hope to begin some more FPGA-related projects in the future soon.
Google Sites
Report abuse