## Homework 7 CSE240 - Introduction to Computer ArchitectureAutumn 2004

### Due: Monday 15 November (at midnight)

Now that you've built the Pentrix Operating System as a foundation, your next task is to implement the actual Pentris game code. Similar to last time, we've broken the task into parts and given you the pseudocode for each part. In total, you'll need to write up to 300 lines of code, so make sure you start early!

## Background Information

The Game of Tetris: Our Pentris game is inspired by the game of Tetris, one of the most famous computer games of all time. In the game of Tetris, the player must maneuver game pieces of various shapes as they fall from the top of the playing board toward the bottom. The goal of the player is to pack the pieces to form contiguous rows. When an entire row is filled, it disappears and all the rows above it shift down. The game ends when there is no room at the top for a new piece to enter the game board.

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:

 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0

 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0

 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0

 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0

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 x4C40
```
Changing 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.asm
```
Running the simulator: The Pentris game consists of three object files (remember that you need to build these from the corresponding .asm files):
• pentrix.obj: operating system code loaded at location x0000 (this your code from HW6)
• pentris.obj: user-level code loaded at location x3000 (this is what you are completing for HW7)
• background.obj: background image loaded at location xC000 (the video memory; the .asm file is provided)
The following command line will load all three object files when starting the simulator:
```  lc3sim-tk pentrix.obj pentris.obj background.obj
```
After 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.edu
```
```    cd cse240hw7
turnin -c cse240 -p HW7 pentris.asm
exit
```

## Subroutine Descriptions

The user-level code of Pentris consists of four subroutines.

### Part 1: Draw Shape

The first subroutine draws a tetris piece of a specified shape at a specified location on the game board. The color of the shape is specified by the 16-bit encoding described previously described. By specifying the color as black, this subroutine can be used to effectively erases a piece. The pseudocode is provided below:

```;;; 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.

### Part 2: Detect Collision

In this part of the assignment, you will write a subroutine that takes the game row and column as well as the shape of the current block as input, and detect whether any block of the shape, if drawn, would overwrite another block that is already there. This code will be used later to detect when moving a piece a certain direction will or won't be legal. A block can be moved only after this subroutine makes sure that the new position that the block wants to move to is actually unoccupied. Your task is to write a subroutine that will detect if placing a specified shape and a specified row and column location would cause a collision. A collision is defined as: any block that would be filled in by DRAW_SHAPE is already filled in with a non-black color. This routine is similar to DRAW_SHAPE, except is uses the GET_BLOCK_COLOR trap rather than the DRAW_BLOCK trap. The pseudocode is provided below:
```;;; 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 false
```
Pseudocode 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.

### Part 3: Remove Filled Rows

Note: Part 3 and Part 4 can be done in either order, so if you get stuck on Part 3, move on to Part 4.

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.

### Part 4: Main Function

Now we actually have enough pieces to put everything together. The MAIN subroutine should start at 0x3000, and it (1) initializes the first piece, (2) gets the next event (key press or timer event), (3) attempts to move the piece in the direction determined by the event, and (4) checks to see if the piece has been placed by hitting any previously-occupied blocks during an attempted downward move. When a piece has been placed, the algorithm removes the completely-filled rows, initializes a new piece to appear at the top of the playing field, places the new piece, and checks for game over (which occurs when a newly-placed piece collides with existing blocks).

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 loop
```
Recall that the return values of the GET_EVENT trap are:
• Down - 0
• Left - 1
• Right - 2
• RotateLeft - 3
• RotateRight - 4
• Quit - 5

Pseudocode explanation: Although we explained the general approach in the prose above, there are some aspects of the pseudocode that deserve explanation.

• In the main loop, the event that triggers the rest of the loop is a user input, so the game waits for user input as the first step.
• The algorithm uses a second set of "new" coordinates for row, column, and rotation, updating them to the location or rotation as determined by the event. It uses these new_ variables to avoid forgetting the previous location and rotation of the piece. The previous location is needed in the case of a collision that causes the move to be aborting and thus the piece must be redrawn in the original location.
• What does the code: new_rotation = new_rotation AND 0x3 do? By ANDing new_rotation with x0003, it zeros out all the bits except for the last two bits. In essence, this just truncates the number to keep it in the legal range of rotations, 0 to 3.
• The penultimate part of the loop detects if the piece was just "placed". If the last command issued, whether by the timer or by the user, is a down command that couldn't move down, then that means the piece has reached the bottom of the game field. To place the shape, simply leave it there and initialize a new set of shape coordinates.
• If the new piece can't be drawn without a collision, the player has stacked up way too many blocks and it's game over. The code ends the game by calling HALT.
• The final part of the loop increments the next_type variable. This variable is incremented each time through the event loop to pseudo-randomly determine which type of shape of next piece. The pseudocode includes a check if next_type is greater than or equal to seven to keep it in the legal range, 0 to 6.

### Hints and Suggestions

• Local variables: Especially for part 4, you may find you don't have enough registers. In this case, you'll need to allocate local variables to hold values (in addition to just using registers).
• Register allocation: If you're clever about which registers you use to hold which values, you can simplify your code by reducing the amount of shifting of values between registers (and perhaps reducing the number of local variables).
• If you get stuck: If you get stuck on Part 3, work on Part 4. You can complete almost the entire game without part 3. The only functionality you'll be missing without Part 3 is removing the filled rows. Granted, this won't make the game much fun, but it will allow you to make coding progress if you get stuck.

### Optional Extensions

• Keep score - one point per line erased, print out the score to the terminal at the end. Note that you will need to update your pentrix.asm to provide a new trap for doing console I/O.
• Make the game speed up - we've added an I/O register (xFE0A) to the LC-3 for controlling the timer's frequency. To change the timer interval, write a value to this memory-mapped register. The value is the number of milliseconds between timer ticks. The default timer interval is 1000ms (1 second). Note that you will need to update your pentrix.asm to provide a new trap for updating the timer interval register.