Block Stacker Report
ECE 2220 – Digital Logic
Brandon Hill1, Jeremy Partaker2, Marc Pelland3, Ryan Kruk4 1
Electrical Engineering Student
[email protected] 2
Electrical Engineering Studen
[email protected] 3 Electrical Engineering Student
[email protected] 4
Electrical Engineering Student
[email protected]
Acknowledgements: The members of BASE 2 wish to recognize the generous contribution in time and mentorship of the following individuals in the production of Block Stacker: Dr. Ahmad Byagowi, Mr. Daniel Card and Mr. Erik Johnson.
Abstract: This paper is our final report accompanying our ECE 2220 final project “Block Stacker”. In this report will be discuss the various elements of the game design and the source code will be included in the appendix. The following report will includes: Introduction, Team Members and Contributions, Summary of Features, Summary of Inputs/Outputs, PS/2 Keyboard Input, Generating Random Blocks, Rotating Block Clockwise, Shifting Blocks Left, Right, and Downwards (Auto and Manual shifts), Checking for Collisions, Auto Deletion of Rows, Displaying Game on LCD Display
Introduction: Block Stacker by BASE 2 is based on the popular Tetris by Alexei Pajitnov made in 1984 in the USSR. Our project was developed from scratch on a Terasic De2-115 using the Verilog HDL in the Quartus II IDE.
Block Stacker Report
1. Team Members and Their Contributions • Brandon Hill • Jeremy Partaker • Marc Pelland • Ryan Kruk
Team Member Team Member Team Leader Team Member
2. Summary of Features This block stacker game has the following features: • PS/2 Keyboard Input • Generating Random Blocks • Rotating Block Clockwise • Shifting Blocks Left, Right, and Downwards (Auto and Manual shifts) • Checking for Collisions • Auto Deletion of Rows • Displaying Game on LCD Display
3. Summary of Inputs and Outputs Our block stacker game has the following inputs: • 50 MHz clock signal – This non-user input will come from a square wave with a 20 ns period (50/50 duty cycle) • The keyboard clock signal – This non-user clock input will come from the PS/2 keyboard that connects to the board • The keyboard data signal – This user-based input will come from the PS/2 keyboard that connects to the board. The possible choices of buttons from the keyboard will be block action buttons (w, a, s, or d) – This user input will be represented by 4 keys on a PS/2 keyboard connected to the DE2-115 design board: - w = rotate the random block clockwise - a = shift the random block horizontally to the left - s = shift the random block vertically downwards - d = shift the random block horizontally to the right Our block stacker game has the following outputs: • A single LED – This output will show the main logic clock speed (for automatic shifting of blocks) • The VGA game display – This will be displayed using a LCD screen connected to the DE2-115 development board.
Block Stacker Report 4. PS/2 Keyboard Input – Jeremy Partaker, Marc Pelland The PS/2 keyboard is our method of input for the block stacker game. The keyboard information interfaces with the DE2-115 board through the built-in keyboard controller on the board that decodes all of the data received form the keyboard. The keyboard initiates a bit on the data line when clock is high, and is read by the keyboard controller on the board when clock is low (process can be seen in Figure 1 below). Information from the keyboard is sent to the board through serial protocol with 11-bit frames:
Figure 1 – Device-to-host communication showing clock and data signals • 1st bit: start bit (always 0); this bit begins communication. • 2nd – 9th bits: data bits (least significant bit first); these 8 data bits represent an 8-bit ASCII scan code that indicates which key was pressed (can be seen in Figure 2 below) • 10th bit: parity bit (odd parity); this bit is set to 1 if there is an even number of 1’s in the data bits and reset to 0 if there is an odd number of 1’s in the data bits. When you add the total number of 1’s in the data bits with the corresponding parity bit you get an odd number, which is used simply for error detection. The keyboard will automatically respond as if the command was invalid if the bit is incorrect. • 11th bit: stop bit (always 1); this bit results in one last clock pulse being sent with communication being inhibited afterwards.
Figure 2– PS/2 keyboard buttons/keys with corresponding scan codes Since we used w, a, s and d in our project, the corresponding hexadecimal scan codes are as follows: » w = 1D » a = 1C » s = 1B » d = 23
Block Stacker Report It should be noted that there are two different codes that are sent when a key is used; the code sent from the keyboard differs when a key is pressed versus when a key is released. When a key is pressed a “make code” is sent, which means a single 11-bit frame is sent. As long as the key is held down, these identical make codes will be continuously sent. On the other hand, when a key is released a “break code” is sent, which means two 11bit frames are sent. The break code is similar to the make code because it contains the same 11-bit frame, but this frame is preceded by another 11-bit frame that contains f0 (hexadecimal) as the data code within it. We implemented our Verilog Code on make code data sent by the keyboard only, by filtering out the break code data sent from the implemented keys. This was done by checking the 11-bit frame that preceded the current 11-bit frame to see if it contained an f0 8-bit data code within it. The resultant output from this keyboard module will be a 4 bit binary number representing the four possible keys (only one bit will be 1 for each option of 4-bit numbers, differing in bit positions: ex. 0001, 0010, 0100, 1000).
5. Generating Random Blocks – Ryan Kruk Blocks are generated from a high frequency counter which constantly shuffles through numbers 0 to 6, each corresponding to one of the seven tetrominoes. When a new block is required, the counter value is sampled and fed directly to a module named sprites which produces a 16 bit vector corresponding to the sampled value. The sprites are kept in a case statement which interpret the random word values. Here are the seven counter values with their attributed sprites:
These tetrominoes are stored internally as 16 bit vectors which are displayed across 4 rows in the game field.
6. Rotating Block Clockwise – Ryan Kruk, Jeremy Partaker & Marc Pelland Block rotation is handled by a dedicated module named rotate which filters input from the keyboard for the value corresponding to the W key (signal for clockwise rotation). Whenever the rotate clockwise signal is detected, an internal counter is incremented and the value at the counter called angle is changed. Upon changing angle a corresponding transformation is applied to the input.
Block Stacker Report
Below is an example of a 90° CW (clockwise) transformation. Similar transformations exist for 180° CW and 270° CW. This is accomplished in a case statement with the concatenation of the bits of the original sprite in the order prescribed by the value of angle.
Therefore, every value of angle has a corresponding transformation which maps the sprite to a final orientation.
7. Shifting Blocks Left, Right and Downwards – Ryan Kruk, Jeremy Partaker & Marc Pelland Since the game field is a matrix of size 19x12 stored as a 228 bit vector (the total area is 228 squares). The sprite which is rotated by the rotate module is then broken into four parts and spread out into a 40 bit vector named sequence. Sequence is then shifted into the game field a given number of times in order for the block to settle at the correct location in the game field.
The number of shifts required to place sequence in the game field is given the name xpos. Xpos is updated every time the player presses the A, S or D keys (shift left, shift down and shift right, respectively).
Block Stacker Report
The shifts to the left and right require that xpos be incremented once or decremented once. This results in the sequence (the 40 bit vector containing the falling block) being shifted once to the left or once to the right from its previous position. Shift down is performed by subtracting 12 from the value of the xpos in order to have the entire block appear a whole 12 positions further to the left and thus one row lower than it previously was. An automatic shifting component also updates xpos creating a forced “down shift” timed by a counter on the clock. This would force the player to position blocks rapidly in order to avoid having the game stack them recklessly, building a pile of blocks up to the top of the game field.
8. Checking for Collisions – Brandon Hill Checking for collisions is performed by comparing the contents of a vector containing the information for the falling block (V1) and the information for the already positioned blocks (V3). The placer module which is responsible for depositing the falling tetromino (V1) in its terminal position at the base of the playing field (V3) is constantly ANDing the vectors for the falling block and the game field. When the AND of these two vectors is not equal to zero then logically the AND of the vectors containing the placed blocks and the falling block must contain a one. This would imply that they have overlapped and that the move is invalid. Thus in order to validate actions requested by the player we create a tentative position vector (V2). This tentative position vector allows the actions to be validated before the game commits to moving the falling block (V1) to a new position in the game field (V3). The tentative position vector (V2) is a copy of the falling block vector (V1) shifted down by a full row (thus its xpos is 12 less than that of V1). When the tentative position vector (V2) collides with the game field vector (V3) then the next position of the falling block will be invalid and the game will add the falling block to the game field vector (V3
