CS 202 - Computer Science II - Spring 2007
Lab 5 - Recursion
Loyola College >
Department of Computer Science >
Dr. James Glenn >
CS 202 >
Labs >
Lab 5
Due
Wednesday, March 14th at 11:59pm.
Labs submitted one day late will be assessed a
20% penalty. Labs will not be accepted more than one day late.
Objectives
- to write a recursive method
Reading
Morelli and Walde, Chapter 12
Introduction
In
Tetris, quadrominoes fall down the screen and the player has to move
then so as to complete lines across the screen. Tetris begat
Columns, in
which stacks of three colored blocks fall down the screen and the player
has to maneuver them to get three or more blocks of the same color in a
straight line. Columns begat Collapse, in which the player strives to
arrange the colored blocks in connected regions of the same color. The
falling blocks have been replaced by rows of blocks pushing up from the
bottom. The game is over when a block is pushed all the way to the top
of the screen.
Assignment
Complete the void makeMove(int r, int c) method in the
CollapseBoardModel
class. This is the method that is invoked when the player clicks on a block.
The missing piece is the code that determines if the block the player
clicked on was part of a monochromatic connected region of size 3 or more.
The code must mark the blocks that are in the same monochromatic connected
region as the block the player clicked on by storing true in the
corresponding location in the marked array. The code must also
store how many blocks were marked in the numMarked variable.
For example, if the puzzle looks like
R G B
R R G G
R R B B B
G B B R B
G G B B R
(using R for red, G for green, and B for blue) and the user clicks on any
blue block except the one in the top row, then the marked array
should be
f f f f f
f f f f f
f f T T T
f T T f T
f f T T f
If this is done correctly then the existing code at the end of
makeMove
will take care of removing the blocks and collapsing the puzzle.
The blocks are stored as CollapseBlock objects in the
pieces array that is inherited from GameBoardModel.
These objects have a getColor method you can use to check
their color.
You may find it helpful to write a recursive method
int markBlocks(boolean[][] marked, int r, int c, Color color)
that takes as its arguments the marked array, the row and column
to check, and the color that marked blocks must match. The marked
array serves two purposes: during the recursion it will keep track of
which blocks have already been counted so they are not counted again,
and at the end it will record which blocks need to be removed (i.e., which
blocks have been counted).
The initial invocation
would pass in the row and column of the block the player clicked on as
well as the color of that block. The method would then check that the
position was in bounds (using the getWidth and getHeight
methods), that there is a block at that position (empty positions will
have null in the pieces array), that the block hasn't
been marked yet, and that the block has the right color. If all those
conditions are met then the code should mark the position
and recursively invoke markBlocks for the four adjacent positions.
The method can also return how many blocks were marked by it
and any recursive invocations. Note that the correct value to return
can be computed trivially in the base case, and from the values returned
by the recursive invocations in the recursive case.
Files
The nearly complete code for CollapseBoardModel is in
a Java archive along with all of
the other files needed to run the game. CollapseWindow is the
main class.
The archive contains the following files.
To test your code you should run CollapseWindow.
Advice
- You can start by finding the blocks to mark and not counting them
as well. You will still need to return a value from all cases
of markBlocks, but you can ignore that value in
makeMove and instead initialize numMarked to
3. By doing so, any blocks the player clicks on will be
removed. Once that is working, you can add the code to
return the correct count from markBlocks.
- You may find it easier to debug your code without the GUI.
There is a main method in CollapseBoardModel
that will create a board and click on the middle of the bottom
row. The board is printed before and after the click. You can
initialize the board to fixed values instead of random values
in the CollapseBoardModel constructor. You could,
for example, initialize the board to only red blocks on the bottom
row and make sure markBlocks finds all of those blocks.
Exercises
- How would you change your code if the monochromatic regions were allowed
to be connected diagonally in addition to horizontally and vertically?
- Switch the order of the statements in the recursive method so that
the statement that marks the position in the marked array is
last. What happens? Try to explain the program's behavior (hint:
a StackOverflowException usually means that a recursion has gone
too deep).
- Consider the following non-recursive way to find the blocks to remove:
first mark the block the player clicked on, then find the blocks
of the same color that are adjacent to that one, then find the blocks
that are adjacent to those, and so on until no new blocks are found.
How do you think the speed of this new
version compares to the recursive version?
Submissions
Submit the source code (.java file) for your CollapseBoardModel
class.
Submit your answers to the exercises either in the body of your
e-mail or on paper.