For more information about Tetris and its history, please see:
For those of you that have never played Tetris, you can play a web-based variant of the game at:
Playing field: Recall that the playing field is 20 rows of 10 blocks each. The top-most row of the playing field is row 0 and the left-most column of the playing field is column 0.
Tetris shapes: The shape of a Pentris piece is encoded by interpreting a 16-bit value as a 4 by 4 grid. The high-order 4 bits, [15..12], represent the first row of the square from left to right, the next 4 bits, [11..8], represent the second row, and so on. The following table depicts which bits represent which block in the shape.
15 | 14 | 13 | 12 |
11 | 10 | 9 | 8 |
7 | 6 | 5 | 4 |
3 | 2 | 1 | 0 |
A 1 bit means the corresponding block is filled, while a 0 means that the block is empty. Thus, a 16-bit word can encode any 4 by 4 shape. For example, the following hex numbers represent the following shapes:
|
  |
|
  |
|
  |
|
Selecting and Rotating shapes: As each shape is exactly 16 bits, there is a corresponding memory location for every shape. Don't worry, we're giving you the definitions of the shapes (see below). In addition, each shape has 4 possible orientations, so there are actually 4 consecutive memory locations that hold the shapes in various orientations. There are 7 different shape types (0 to 6), and for the sake of regularity, 4 rotations for all shapes (0 to 3) even if some of the 4 rotations are the same (for example, for the square, all 4 rotations are exactly the same). Thus, there are 28 shapes in total. However, we will only use 1 label, SHAPES, to address all 28 of these shapes, and just use offsets to reach any shape. In general, for a given type and rotation, the 16 bit encoding will be stored at Memory[SHAPES + (4*type) + rotation].
SHAPES .FILL xCC00 .FILL xCC00 .FILL xCC00 .FILL xCC00 .FILL xF000 .FILL x4444 .FILL xF000 .FILL x4444 .FILL x8E00 .FILL x6440 .FILL x0E20 .FILL x44C0 .FILL x2E00 .FILL x4460 .FILL x0E80 .FILL xC440 .FILL xC600 .FILL x4C80 .FILL xC600 .FILL x4C80 .FILL x6C00 .FILL x8C40 .FILL x6C00 .FILL x8C40 .FILL x4E00 .FILL x4640 .FILL x0E40 .FILL x4C40Changing colors: To add some color to the game, each shape has a different color. Because there are 7 different shapes, there will be 7 colors that can be loaded. Use the label COLORS plus a 0 to 6 offset to access all 7 colors. The color of a type of shape is stored at Memory[COLORS + type].
COLORS .FILL xFFFF ; White .FILL x43FF ; Light Cyan .FILL x7E1F ; Light Magenta .FILL x7FF0 ; Light Yellow .FILL x421F ; Light Blue .FILL x43F0 ; Light Green .FILL x7E10 ; Light Red
Image for background: We're also giving you an image for the game background. This images serves two purposes: (1) it gives a "border" which prevents pieces from moving off the playing field, and (2) it makes the game look better. The background images is loaded directly into the video memory using the command line or via loading an object file through the graphical interface.
Code template: We're giving you a template for the pentris.asm user-level code that contains the many of the declarations you'll need and place holders for the code. You'll also need your pentrix.asm file from homework 6. You can get the pentris.asm template, the background image code, and your pentrix.asm from homework 6 by executing the following commands:
cd ~ mkdir cse240hw7 cd cse240hw7 cp ~cse240/project/hw/hw7/* . cp ../cse240hw6/pentrix.asm . lc3as background.asm lc3as pentrix.asmRunning the simulator: The
lc3sim-tk pentrix.obj pentris.obj background.objAfter starting the simulator, you can reload the background.obj file to clear the screen, or you can reload the pentris.obj file to update the user-level code. Note that the PC of the processor is unaffected by loading object files, so you may need to reset the PC to x0200 to reboot the operating system (which then will proceed to call your user-level code at x3000). You will also need to set the privileged bit in the PSR (the high-order bit) to start executing the OS code at x0200.
Testing and Turnin: Much like the previous two assignments, we've included testing code in the same directory as the pentris.asm and background.asm file. The only file you need to turn in is your version of the pentris.asm file. Similar as before, do the following:
ssh eniac-s.seas.upenn.eduIf prompted, enter your eniac password. Continue by typing:
cd cse240hw7 turnin -c cse240 -p HW7 pentris.asm exit
;;; DRAW_SHAPE ;;; Register Input ;;; r0: "row" - row in game field ;;; r1: "col" - column in game field ;;; r2: "shape" - 16-bit encoding of the piece ;;; r3: "color" - color to be drawn ;;; Register Output ;;; None for(r=0; r<4; r++) for(c=0; c<4; c++) if high-order bit of shape is 1 ; do this by checking if "shape" is negative DRAW_BLOCK(row+r, col+c, color) ; called using a TRAP instruction shift the bits of shape to the left ; do this by adding shape to itself
Pseudocode explanation: The doubly-nested loop in the above code walks through the 16-bit shape vector. Each iteration examine the high-order bit of shape before shifting all of shapes bits left one position. By checking the high-order bit and shifting shape each iteration, each bit position in shape is checked from high-order bit to low-order bit. If a bit is found to be set, the subroutine calls DRAW_BLOCK for the proper row and column to tell the operating system to fill in the corresponding 4-pixel by 4-pixel block.
;;; DETECT_COLLISION ;;; Register Input ;;; r0: "row" - row in game field ;;; r1: "col" - column in game field ;;; r2: "shape" - 16-bit encoding of the piece ;;; Register Output ;;; r5: 1 if a collision would occur, otherwise return 0 for(r=0; r<4; r++) for(c=0; c<4; c++) if high-order bit of shape is 1 ; do this by checking if "shape" is negative curr_color = GET_BLOCK_COLOR(row+r, col+c) ; called using a TRAP instruction if curr_color != 0 ; zero is black return 1 ; return true shift the bits of shape to the left ; do this by adding shape to itself return 0 ; return falsePseudocode explanation: The algorithm is similar to the one for drawing a block. The only difference is that instead of putting something into the block, its checking through every block marked by the shape definition to make sure that it's blank, i.e. that its color is black. When the subroutine detects a collision, it exits out of the loop and reports a collision by returning the value 1. If the loop terminates without having detected a collision, it reports no collision by returning the value 0.
Another important part of the game of Tetris is removing completely-filled rows. Although there are many reasonable algorithms for scanning the game board and removing filled rows, we're using one that is simple, yet reasonably efficient: copy the rows of the board from bottom to top, omitting any rows that are completely full. The pseudocode is provided below:
;;; REMOVE_FILLED_ROWS ;;; Register Input ;;; None ;;; Register Output ;;; None scan_row = 19 fill_row = 19 while fill_row >= 0 counter = 0 for(col = 0; col < 10; col++) scan_color = 0 ; zero is black if scan_row >= 0 scan_color = GET_BLOCK_COLOR(scan_row, col) ; get current color ; keep track of how many blocks are filled if scan_color != 0 ; zero is black counter++ if scan_color != GET_BLOCK_COLOR(fill_row, col) DRAW_BLOCK(fill_row, col, scan_color) ; copy downward if necessary scan_row-- if counter != 10 ; row was not full fill_row--
Pseudocode explanation: The algorithm begins by initializing the scan counter (scan_row) and fill counter (fill_row) to the coordinates of the bottom row. The scan_row names the row we are currently scanning (to determine if it is full of blocks). The fill_row is where we are placing the blocks read out of the scan_row. If no rows are full, fill_row and scan_row will always be the same. If a row is full, scan_row is decremented, but fill_row is not changed. This will have the effect of copying the next row (above) over the full row (in fill_row).
If the scan_row is less than 0 (i.e., off the board), we set the scan_color (i.e., the color of the block copied into the fill_row) to black. Note that (as an optimization) we only actually copy the block (i.e., call DRAW_BLOCK) if the current block is of a different color.
As it's scanning the scan_row, it also counts the number of non-black blocks. Once the whole row has been scanned, if the row is full, then that row should not have been copied and should actually have been skipped... oops. (Oh well, not that much work has been wasted). The algorithm handles this situation by keeping the fill row counter the same (not incrementing it) for the next iteration. Doing so results in the row being overwritten during the next iterations.
Moving a piece requires three steps: (1) erasing the piece at its current location (by using DRAW_BLOCK with the color black), (2) using DETECT_COLLISION to check for a collision at the piece's new location, and (3) drawing the piece at either the new location (if no collision was detected) or redrawing it at the old location (if a collision was detected). We erase the shape so that when detecting collision, we do not mistake the current shape as occupied space. (Consider moving a 2x2 square piece: if it wasn't erased first, a single-unit movement in any direction would cause a false conflict. By erasing the piece first, these false conflicts are avoided.)
The pseudocode is provided below:
;;; MAIN ;;; Register Input ;;; None ;;; Register Output ;;; None ; initialize row, col, type, rotation, shape next_type = 0 row = 0 col = 3 type = 0 rotation = 0 shape = Memory[SHAPES + (4*type)] color = Memory[COLORS + type] DRAW_SHAPE(row, col, shape, color) loop: ; main loop ; get next event curr_event = GET_EVENT() ; erase current shape DRAW_SHAPE(row, col, shape, 0) ; zero is black ; handle event new_row = row new_col = col new_rotation = rotation if curr_event == Down new_row++ if curr_event == Left new_col-- if curr_event == Right new_col++ if curr_event == RotateLeft new_rotation-- if curr_event == RotateRight new_rotation++ if curr_event == Quit jump out of loop ; keep rotation in range 0..3 by ANDing with two low bits new_rotation = new_rotation AND 0x3 ; calculate new shape new_shape = Memory[SHAPES + (4*type) + new_rotation] ; detect collision collision = DETECT_COLLISION(new_row, new_col, new_shape) if collision == 0 ; no collision row = new_row col = new_col rotation = new_rotation shape = new_shape ; redraw shape (in either the same or new position) DRAW_SHAPE(row, col, shape, color) ; check to see if piece was placed if (curr_event == Down) and (collision != 0) REMOVE_FILLED_ROWS() ; set up the new piece row = 0 col = 3 type = next_type rotation = 0 shape = Memory[SHAPES + (4*type)] color = Memory[COLORS + type] ; detect game over condition (newly-placed piece collision) collision = DETECT_COLLISION(row, col, shape) DRAW_SHAPE(row, col, shape, color) if collision != 0 ; collision occurred halt the machine ; game over ; "randomize" which type of shape is next by incrementing it each event next_type++ if next_type >= 7 ; handle wrap around next_type = 0 goto loopRecall that the return values of the GET_EVENT trap are:
Pseudocode explanation: Although we explained the general approach in the prose above, there are some aspects of the pseudocode that deserve explanation.