|
|
Before you do anything, please read the entire assignment carefully. It contains many suggestions which can save you a lot of struggle later on.
You should print out hard copy of your code and any example outputs, and either turn them in at lecture or in the TA's mailbox at Sudikoff by class time on Wed. Dec. 2, 2009. Late assignments will be strongly penalized, so please start early.
For this assignment, you may work either alone, or with one (1) other partner. You may not share your code with anyone other than your partner, nor may you look at anyone else's code. See the Course Information for a review of the policies on joint work.
For CS 8 programming assignments, such as this one, you must turn in a hard copy listing of any procedures you wrote yourself, or modified from the example code provided with the assignment. You must also turn in example output for each section of the problem set, as applicable.
You should not turn in printouts of any code we provided you which you did not make any changes to, and please be sure to label everything carefully, so that the graders will know what they are looking at.
You must also e-mail an electronic version of your code to cs8hw@cs.dartmouth.edu with the subject "CS 8 Problem Set 7", by no later than 2:00 am on the date it is due. Please organize your code in one or more plain text files and attach them as enclosures to your message. Do not include your code directly in the body of the e-mail message! If you are sending more than one file, please make sure the files have descriptive names, and that you include comments that will let the graders know what they are looking at.
Code submitted electronically must be sent as plain text, in one or more files with the filename extension ".hs" or ".lhs" (e.g., mycode.hs). Do not send your programs as Word documents, RTF, or other "formatted" types of files.
For each part of any assignment, we require output which demonstrates that your code correctly solves the problem it is supposed to solve. If you turn in code with no output, you may receive only partial credit, or no credit, for that part of the assignment.
Some problems will give specific test cases you need to provide output for. However, even if specific test cases are not provided, and even if it is not listed under "What to Turn In" for a particular problem, you must provide some sample output that shows how your code behaves on typical inputs.
If you are unable to get your code working, please turn in whatever you do have, so that we can determine if you should receive partial credit. Please do not include output which suggests your code works if it doesn't -- however, if your code works for some of the test cases, and not for others, you should turn in whatever output you are able to generate, even if it is incorrect. You will get credit for the "Testing" part of the score, even if the tests indicate that the program is incorrect.
Output is not required to be submitted electronically, although you are welcome to do so if you wish. If you do choose to submit output electronically, put your output samples in a separate file from your code submissions. Output may be submitted in any reasonable file format, though plain text is easiest to read.
Tetris is a video game where pieces fall from the top of the window towards the bottom, until they collide with another piece or the bottom of the window. The user has the options of moving the piece one column left or right or rotating it by typing keys on the keyboard. The user also has the option of "dropping" the piece instantly as far as it will fall before a collision occurs. If an entire row of squares is filled in, that row is removed and the pattern above it is shifted down. The game continues until a falling piece is stopped before it is entirely onto the board. Score is based on the number of pieces dropped and the number of rows removed before the game ends.
There are seven pieces - all connected arrangements of 4 unit squares. They are a rod (4 in a line), a block (2x2), a T (3 in a row with one above the center), two L's (3 in a row with one above an end, with two ends to choose from), and two zig-zags (start with the block and shift the top row left or right one square). They appear below.
I assume that most of you are familiar with Tetris. (A show of hands in class confirmed this). If you are not, come see me and I will demonstrate the game. Alternately, download one of the many implementations available on the internet (but not their source code!).
In this assignment you will implement a version of Tetris in Haskell. I have provided you with TetrisFramework.hs to give you a starting place, and you have modified it in SA 9. Start with this, and download all the files provided in SA 9.
Tetris is not especially hard to implement, given the RegionEX and PictureEx modules. Manipulating the piece as it falls requires translations and rotations of the piece. When a piece stops falling it can be unioned with all the other pieces currently in the Tetris game board. Removing a row can be done by intersecting everything below the row with a rectangle, intersecting everything above the row with a rectangle, translating the upper rectangle down one row, and unioning the two intersections.
One thing that I have not discussed is how to detect collisions between a falling piece and pieces in the game board and the boundary of the window. The RegionEX and PictureEX code does not give us an easy way to do this in general. The intersection operator creates a graphical object representing the intersection, but not a Shape or Region that could be examined. However, for Tetris there is an easy way to do this. If all of the pieces are built up from unit squares represented as polygons, then for the type of intersections that can occur in the game it is sufficient to ask if any of the vertices of the polygons in the piece (suitably rotated and translated) lie within some region representing a piece in the board or lie outside of the rectangle defining the window. This can be done via containsR tests from the RegionEX code.
Note that if the piece is constructed out of bigger rectangles rather than unit squares it may be possible for part of a falling piece to overlap another piece without a vertex of the falling piece lying within the the second piece. Think of a horizontal rod represented by a single 1 x 4 rectangle falling onto a vertical rod. The left vertices of the falling rod could lie to the left of the vertical rod and the right vertices of the falling rod could lie to its right.
The basic idea is to check the piece each time through the event loop. (This is the function in TetrisFramework.hs called loop - it looks for a key press event, and handles it if one is present, moves the piece if one is not, and calls itself recursively.) If the user chose to translate or rotate the object, verify that that translation or rotation will not move part of the piece outside of the window or on top of another piece in the game board. Do not allow the operation if it causes a conflict with another piece or the boundary of the board. If the user took no action compute the new location of the piece (based on time) and decide if a collision took place with a piece in the board or the bottom of the window. If the user chose to drop the piece move it down until a collision is detected.
There is a problem with this approach - two pieces in adjacent columns will overlap on their shared edge, so a falling piece would get stuck with one of its bottom corners touching one of the top corners of the other piece. This is not desirable because we want the piece to slip by the other piece. A way to deal with this is to shrink down each unit square in the piece slightly, at least in the horizontal direction. Then its vertices will not be contained in rectangles in adjacent columns.
Note that scaling each square about its center is subtly different than scaling the whole piece. Scaling the whole piece can cause vertices of a rectangle to move into an adjacent column. There are cases where doing this with the L and zig-zag pieces can cause an apparent intersection where none should exist.
I implemented Tetris following the approach described above. It worked fine for the first few pieces dropped, but after 20 or 30 pieces were dropped the animation became quite jerky and there were relatively long delays between typing a key and seeing the result on the screen. As more pieces dropped some of the keyboard commands were missed entirely. This is a not atypical problem in writing animations or games - the computations took too long to have smooth animation and responsive game play.
Needless to say, it is discouraging to write a game program and then to have the response too slow to play a reasonable game. My first thought was that the containment tests were taking too long. Every vertex in the piece has to be tested against every piece already in the board, and those containsR tests might have to do a number of rotations and translations on the query point. I thought of ways to eliminate some of these tests, but before I implemented them I decided to try some experiments to see if that was indeed the problem.
It turned out that intersection tests were not the main problem. Commenting out the command to test for collisions with pieces in the board (but leaving tests for intersecting with the edge of the window) created a board with a big pile of overlapping pieces at the bottom, but did not eliminate the slowdown. On the other hand, leaving the collision detecting alone but commenting out the command the draws the board each time through the loop lead to reasonably smooth falls and a responsive program.
So the problem was the graphics were too slow to draw the number of regions required when the board became fuller. This was discouraging. My first thought was that I could draw the board once at the start of dropping the piece and redraw only the piece dropping. I could do this by remembering the previous location and drawing it in black before drawing the piece in its new position. (This is not possible if the piece covers other graphics, but the falling piece never passes over another piece.) Unfortunately this did not help. Apparently the screen was being periodically re-drawn from some internal data structure, and this was taking too long.
The book described how intersections, unions, etc. of Regions were handled graphically. The regions are converted to bit maps and than the operations are performed on these. It is the only efficient way to handle intersections and Xors, because intersecting n vertical rectangles with n horizontal rectangles leads to n*n rectangles in the intersection. However, drawing general bitmaps requires a fair amount of computation. Fortunately, Tetris does not require general intersections. The layout of the regions in the board is extremely regular - rows and columns of squares. In the algorithm described above we only use intersections to split the board into the region above a row boundary and the region below a row boundary.
I therefore decided to try to avoid the general PictureEX graphics when drawing the board. I represented the board as a list of unit square polygons. When a piece is added to the board it is broken into unit squares that have been translated and rotated to their final positions. Because they require no further transformations I could use the polygon draw command used on Shapes in the DrawX module instead of the more complex createPolygon command that creates graphical regions in PictureEX. Point containment was tested by calling containsS on each polygon in the board. Given a horizontal line that lies between two rows it is easy to split the list into those squares above the row and those below the row.
This change was enough to get a reasonably responsive game. I improved it a bit more by combining adjacent rectangles in the same row into rectangles that were still only one row high, but could span a number of columns. This reduced the number of things to be drawn and the number of containment tests needed substantially. The resulting code is in TetrisBoard.hs. Use it as an ADT, depending only on what is exported. This consists of:
By restricting the operations on Regions to these operations on a Board I was able to get faster graphics and containment tests. It demonstrates a useful way to write efficient programs. Implement the program cleanly using good abstractions without worrying overly much about efficiency. If the program is slow then run experiments or use tools like code profilers to find out where most of the time is being spent. (For example, there is little purpose in optimizing containsR testing if the problem is slow graphics.) Then figure out a way to speed up the slow operations. One thing that is often useful is what was done here: restrict the generality of the operations to what is actually needed to solve the problem. It is often the case that you can devise a better data structure and algorithm to solve the restricted cases than the data structures used to solve the more general problem.
Create the seven pieces. Use a unit square polygon as your building block. Note that the center (where the origin lies) of the entire piece should be the center of one of the unit squares. It might seem more natural for the center of the block to be the center of the 2 x 2 square, but then translating it would lead to each unit square overlapping two columns.
There are two approaches to the problem of shrinking the unit squares slightly so that a falling piece will not overlap pieces in adjacent columns. One is to create for each piece a full-sized version for drawing and adding to the board (this version can be constructed from unit squares) and a version with all of its squares slightly shrunk. Then both must be passed, rotated, and translated as the piece falls. The other is to write a function to take a piece and return a copy with all unit squares slightly shrunk. Do one of these things.
Turn in your code to create blocks as part of your overall program. You should union each of them (suitably translated and/or rotated) with an empty Board and draw the result on the screen. Hand in the code to do this test and a screen shot of this picture. (Note this does not require you to play the game or even use the TetrisFramework. You can write a driver program that creates an empty board, add the pieces, and draw it.)
Modify the TetrisFramework to detect if a collision occurs as the piece falls or when you try to rotate the piece or move it left or right. (For each of these a collision means that the final position overlaps a piece in the board or the window boundary. You need not worry about the intermediate positions as a piece rotates.) Do not worry about the drop command yet (having the piece instantly fall as far as it can fall before a collision occurs).
The easiest way to detect collisions between a falling Tetris piece and the contents of the board or the window boundary is to get all vertices of the four squares comprising the piece and to test if any of them lie within the occupied part of the board (via a containsB test) or outside of the window. To do this I strongly suggest writing a function which takes a Region representing a Tetris piece (which is built out unit squares via translations, rotations, scalings, and unions) and returns a list of all the vertices of the squares. (Note that this will be 16 vertices.) Each vertex should be in its correct position in user coordinates.
Note that a very similar thing is done in order to figure out if a point is in a region the containsR function in RegionEX. There the query point is transformed using the the inverse operations. You need to do the forward (non-inverse) transforms, and you need to do them on all of the points. An alternative is to do something similar to what the functions regionToGRegion, regToGReg, and shapeToGRegion do in PictureEx, but this is a bit more complicated. You need not deal with ellipses or right triangles, and for that matter only need to deal with one of the Rectangle and Polygon constructors. Similarly, you need not deal with intersection, complement, and xor operations.
Given the function to get the vertices of the falling piece it is easy to write a function to determine if any of them collide with something in the board or lie outside of the window boundary. You need to modify the functions left, right, and rotateL in TetrisFramework.hs to only perform the operation if the piece moved to its new position does not collide with anything. You also need to see if when the piece simply falls it collides with anything.
When you are done with this you should be able to move pieces left or right or rotate them as they fall, unless this action would cause a collision. In this case you should ignore the request and do nothing. The pieces should stop falling when they reach the bottom or rest on a piece in the board. Add pieces to the board when they stop falling. Before doing this, adjust the piece position so that it lines up properly with the row. (The piece location depends on time, so it is likely that the piece will slightly overshoot its correct position before you detect a collision.)
Finally, when a piece stops falling determine if any part of it extends above the top of the window. If so, end the game. Wait for the user to type "q" before you close the graphics window.
At this point you should be able to play a game of Tetris, with the exception that rows of squares are not eliminated when they become full. (I admit that the game is a lot less interesting if you don't eliminate full rows.)
Hint - Some people have handled falling off the bottom of the board by adding a "zeroth row" of squares just off the bottom of the board. Colliding with this row is equivalent to falling off the bottom of the board. A similar trick can be used for the sides, but you have to be careful when you eliminate rows.
Turn in your code. Union some pieces into a Board and do collision testing with another piece in various positions. In particular, show that side-by-side pieces are not considered to be colliding. Also show that there are not collisions between a piece adjacent to the side of the window and the window, but that there are collisions if part of the piece leaves the window.
These tests do not require any graphical output - simply write a driver that creates and empty board and adds overlapping pairs of pieces, non-overlapping pairs of pieces, and pairs of pieces that are in adjacent columns. Then call your collision test functions on the various pairs of pieces and hand in the results. You can do these calls from the interpreter if you prefer.
Implement the command that drops the piece straight down to its final position without waiting for it to drift down slowly. The final position is the first place where a collision occurs. You should be able to do better than moving it by a little step hundreds of times. (Moving it to a dozen or so positions is fine.)
Turn in your code. This should be tested, but a visual test is easier than printing out results, so you need not turn in test data.
After a piece is added to the board check to see if there are any full rows created, and remove them if there are. Basically you need to test whether every square in a row is occupied using the containsB test in some way or another.
Turn in your code. The program should be tested, but a visual test is easier than printing out results, so you need not turn in test runs. We will run your programs to see if they work correctly.
There is one test for which we require output. Add pieces to the board to create a situation where the bottom row is only partially full, the next two rows are full, the the row above is partially full. Draw the contents of the board before and after you call your function to eliminate full rows.
Implement a "pause" feature: If the user types a "p" key freeze the screen, and then resume when he or she types "p" again.
Create a "Game Over" message: Create some sort of display to indicate that the game has ended.
Keep score: Keep count of the number of pieces dropped and the number of rows removed and report this at the end of the game. For more extra credit, display it on the screen as the game progresses
Re-implement TetrisBoard: The current implementation of TetrisBoard was developed from code that represented and manipulated the board using the Region module. If you set out to implement the ADT from scratch you can use more efficient methods. Create such an implementation. You might want to read about Haskell arrays (which cannot be changed, but the board does not need to be updated often).
Invent your own additions: Think of some interesting extension and implement it.
If you choose to do one or more of the extra credit problems, turn in your code and make it clear on the first page of what you turn in which extra credit problems you have done.
The rubric for grading can be found here.
Home Page |
Announcements |
Course Info |
Materials |
Software |
Department of Computer Science, Dartmouth College, Hanover, New Hampshire, USA
Last modified: 12-August-2009