• 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)

  lc3sim-tk pentrix.obj pentris.obj background.obj

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

Part 1: Draw Shape

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

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

Part 3: Remove Filled Rows

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

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

• 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.