HW3 Tetris Solution

For HW2 you will build up a set of classes for Tetris. This assignment emphasizes the basic Divide and Conquer strength of OOP design -- using encapsulation to divide a big scary problem into several slightly less scary and independently testable problems. Tetris is a large project, so the modular OOP design matters.

 

This assignment is due at 11:59pm Sunday February 4th.   To submit the assignment, zip your entire Android project directory  and then add in your Piece and Board unit test classes to the zip file as we will grade those as well.  Rename the zip file FirstNameLastName_hw3Tetris.zip.  Do not underestimate the difficulty of this assignment – it is much, much longer than HW1 or HW2 were.

 

For reasons that will become clear later, there is a theme of efficiency in this design. We are not just writing classes that implement Tetris. We are writing classes that implement Tetris quickly.

 

I’ve provided two separate project folders for this assignment (all zipped together into one big bundle). There’s an Eclipse version of the project.   This will allow you to implement and test data structures representing the Tetris Pieces and the Tetris Board.  You should build and test these thoroughly in Eclipse by using the Junit Test Framework.  There’s also a Text Version of Tetris which you can optionally use to further test your structures.  Once your Piece.java and Board.java code is thoroughly tested, you can move it to the second project, which is an Android Studio project, which will allow you to play Tetris on your phone (or via the emulator):

 

In contrast with the previous assignment, you will not be developing Tetris from scratch. As I’ve discussed in class, most software is built as part of a team. In this case I’m one of your team members, as is Professor Parlante (whose work this assignment is based on).  I’ve completely implemented the high level code for Android and text versions of Tetris, but I’m leaving it to you to implement the Piece and Board structures. Note that you must follow the specification of the Piece and Board structures, if you start changing any public method or modify in anyway how your Piece.java and Board.java files interact with the code you’re given, the project will not work.

 

On a real project, your team would agree on how the different parts of the project will interact.   Any deviations from that publically agreed upon interface will cause the project to fail when the parts are integrated. The same thing is true here.

 

In  addition to  implementing Piece.java and  Board.java, we  will also  be  grading your  test  cases  for Piece.java,  so please make sure to turn in your Piece and Board test classes along with the completed Android project.  You’ll also get a bit of a chance to practice your Android UI skills by expanding a bit on the Android version of Tetris I provide you with.

 

Part A -- Piece

There are seven pieces in standard Tetris.

 

The Stick   (also known as "the long skinny one") The L    and its mirror L2  

 

The S    and its mirror S2  

 

 

The Square  

 

 

The Pyramid  

 

 

Each standard piece is composed of four blocks. The two "L" and "S" pieces are mirror images of each other, but we'll just think of them as similar but distinct pieces. A chemist might say that they were "isomers" or more accurately "enantiomers" (note: I only looked that word up in an effort to make the handout more impressive.).

 

 

A piece can be rotated 90 degrees counter-clockwise to yield another piece. Enough rotations get you back to the original piece — for example rotating an S twice brings you back to the original state. Essentially, each tetris piece belongs to a family of between one and four distinct rotations. The square has one, the S's have two, and the L's have four. For example, here are the four rotations (going counter -clockwise) of the L:

Our abstraction will be that a piece object represents a single Tetris piece in a single rotation, so the above diagram shows four different piece objects.

 

Body

A piece is defined by the coordinates of the blocks that make up the "body" of the piece. Each Piece has its own little coordinate system with its (0,0) origin in the lower left hand corner and with the piece positioned as low and as left as possible within the coordinate system. So, the square tetris piece has the body coordinates:

 

(0,0)  <= the lower left-hand block (0,1)  <= the upper left-hand block (1,0)  <= the lower right-hand block (1,1)  <= the upper right-hand block

 

In rare cases, a piece will not even have a block at (0, 0). For example, this rotation of the S…

 

has the body:

 

{(0,1),(0,2),(1,0),(1,1)}

 

A piece is completely defined by its body -- all its other qualities, such as its height and width, can be computed from the body.

 

We will measure the "width" and "height" of a piece by the rightmost and topmost blocks in its body. The above S has a width of 2 and height of 3. Another quality that turns out to be useful for playing Tetris quickly is the "skirt" of a piece....

 

Skirt

The skirt is an int[] array with as many elements as the piece is wide. The skirt stores the lowest y value that appears in the body for each x value in the piece. The x values are the index into the array. So for example, for this S...

 

the skirt is {1, 0}. That is, at x=0, the lowest y value in the body is y=1, and for x=1, the lowest y value is y=0. We assume that pieces do not have holes in them -- for every x in the piece coordinate system, there is at least one block in the body for that x.

 

Rotation, Version 1

The Piece class needs to provide a way for clients to access the various piece rotations. The piece class supports rotations in two ways. The first and most straightforward way is the computeNextRotation()

method, which computes and returns a new piece which represents a 90 degrees counter-clockwise rotation of the receiver piece. Note that the piece class uses the "immutable" style -- there is no method that changes the receiver piece. Instead, computeNextRotation() creates and returns a new piece.

 

Rotation Code

For computeNextRotation(), work out an algorithm that, given a piece, computes the counterclockwise rotation of that piece. Draw a piece and its rotation and list out the x,y values of their body points. Get a

nice, sharp pencil, and think about a sequence of operations on the body points of the first body that will

yield the second body. Hint: write out the coordinates of each of the body points before and after the rotation and determine what the formula for calculating the new x and new y is.

 

Rotation, Version 2

The problem with computeNextRotation() is that it's a little costly if we want very quickly to look at all of the rotations of a piece. It's costly because it re-computes the rotated body every time, and it allocates a new piece with "new" every time. Since the piece objects are immutable, we can just compute all the rotations once, and then just store them all somewhere.

 

To do this, we will use a ".next" pointer in each piece that points to its pre-computed next counter- clockwise rotation. The list is circular, so the .next pointer in the last rotation points back to the first rotation. The method fastRotation() just returns the .next pointer. So starting with any piece in the list, with fastRotation() we can quickly cycle through all its rotations.

 

For a newly created piece, the .next pointers are null. The method makeFastRotations() should start with a single piece, and create and wire together the whole list of its rotations around the given piece.

 

The Piece class contains a single, static "pieces" array that contains the "first" rotation for each of the 7 pieces. The array is set up (see the starter code) with a call to makeFastRotations(), so all the rotations are linked off the first for each piece.

 

The array is allocated the first time the client calls getPieces(). This trick is called "lazy evaluation" -- build the thing only when it's actually used. The array is an example of a static variable, one copy shared by all the piece instances. In OOP, this is sometimes called the "singleton" pattern, since there is only one instance of the object and clients are always given a pointer to that once instance.

Piece.java Code

The Piece.java starter files has a few simple things filled in and it includes the prototypes for the public methods you need to implement. Do not change the public prototypes or constants, so your Piece will fit in with the later components and with our testing code. You will want to add your own private helper methods

that can have whatever prototypes you like. The end of this section also describes setting up unit -tests for

the Piece class.

 

Piece.java

Here are a few notes on the features you will see in the Piece.java starter file.

 

The provided TPoint class is a simple struct class that contains an x,y and supports equals() and toString().

 

Constructors

The main constructor takes an array of TPoint, and uses that as the basis for the body of the new piece. The constructor may assume that there are no duplicate points in the passed in TPoint array. There is a provided

alternate constructor that takes a String like "0 0  0 1  0 2  1 0" and parses it to get the points and then calls the main constructor. A parsePoints() method is provided in the starter file for that case.

 

Piece.equals()

It's standard for the .equals() code to start with an "==this" test and an "(object instanceof Piece)" test for the passed in object. The starter code has this standard code already included.

 

Note: Piece does not include an implementation of hashCode.  This means that it will inherit hashCode from object.   We do not recommend using Piece in a manner in which using a hashCode would be necessary.   However, if you decide to use a Piece as a hashmap key or in other situations in which a hashCode would be necessary, you’ll need to write your own hashCode implementation.

 

Private Helpers

As usual, use decomposition to divide the computation into reasonable sized pieces and avoid code duplication. You may declare any helper methods "private".

 

Generality

Our strategy uses a single Piece class to represent all the different pieces distinguished only by the different state in their body arrays. The code should be general enough to deal with body arrays of different sizes -- the constant "4" should not be used in any special way in your code.

 

Unit Testing

Create a PieceTest JUnit class (use Eclipse command: New JUnit Test Case). Look at all public methods supported by Piece: getWidth(), getHeight(), getSkirt(), fastRotation(), equals() -- the output from each of these should be checked a few times. Rather than check the raw output of getBody(), it's easier to check the computed width, height, skirt, etc. are derived from the body. Likewise, checking that fastRotation() is correct works as a check of computeNextRotation().

 

Basic testing plan: Get a few difference start pieces -- create some with the constructor and get some from the getPieces() array. Test some of the attributes of the start pieces. Then get some other pieces that are rotated a few times away from the start pieces, and check the attributes of the rotated pieces. Also check that the getPieces() structure looks correct and has the right number of rotations for a couple pieces. You can use the constants, such as PYRAMID, to access specific pieces in the array. The pictures on page 2 show the first "root" rotation of each piece.

 

Work on your unit-tests before getting in too deep writing your Piece code. Writing the tests first helps you get started thinking about Piece methods and what the various rotations, skirt, etc. cases look like before you write the code. Then, having the tests in place makes it easy to see if your code is working as you build out the code for the various cases.

 

Your unit-tests are part of the homework deliverable, and we will look at them in two ways...

 

• First there's just a baseline of having a decent looking unit-test: The Piece unit test should look at 5 or more different piece objects, and should call and check the output of each method -- getWidth(), getHeight(), getSkirt(), fastRotation(), equals() -- at least 5 times for each method.

 

Then, we try running your unit-test against various Piece classes we have to see how it sifts the good from the ugly.

 

•     When run against a correct Piece class, the unit test should not report any problems. This is very important.

 

•     We have many Piece implementations that have one or more bugs in them. When run against a buggy piece, it's good if your unit-test can notice that the piece has a problem. Your unit test does not need to articulate what the bug is -- just discern correct from buggy piece implementations.

 

Of course the other advantage to doing a good job with the piece unit-tests is that your own piece class has a great chance of being correct, since you will have worked it over so well with your unit tests.