Learning Objectives

By the end of this assignment, you will be able to model hierarchical data using trees.  You will also be comfortable implementing recursive methods which take advantage of the fact that the data structure you are working with is recursively defined.  You will learn how to convert a tree into a flat, two-dimensional structure, and, finally, you will strengthen your knowledge and your comfort with using inheritance in Java.

General Instructions

This assignment contains 3 parts. You need to download the files provided. Your task is to complete and submit the three following files:

Block. java

PerimeterGoal. java

BlobGoal. java

. Do not change any of the starter code that is given to you. Add code only where instructed, namely in the “ADD YOUR CODE HERE” block. You may add private helper methods to the three classes you have to submit, but you are not allowed to modify any other class.

.  Please make sure that all the files you submit are part of a package called assignment3.

. You are NOT allowed to use any class other than those that have already been imported for you. Any failure to comply with these rules will give you an automatic 0.

. Do NOT start testing your code only after you are done writing the entire assignment.  It will be extremely hard to debug your program otherwise. If you need help debugging, feel free to reach out to the teaching staff.  When doing so, make sure to mention what is the bug you are trying to fix, what have you tried to do to fix it, and where have you isolated the error to be.

Submission instructions

.  Submissions will be accepted up to 2 days late.  Remember that you each have 2 free late days to use this semester.  Any additional late day will be penalized by 10 points per day. Note that submitting one minute late is the same as submitting 23 hours late. We will deduct points for any student who has to resubmit after the due date (i.e.  late) irrespective of the reason, be it the wrong file submitted, the wrong file format submitted or any other reason. We will not accept any submission after the 2 days grace period.

. Don’t worry if you realize that you made a mistake after you submitted:  you  can submit multiple times but only the latest submission will be evaluated. We encourage you to submit a first version a few days before the deadline (computer crashes do happen and Ed Lessons may be overloaded during rush hours).

. Do not submit any other files, especially .class files and the tester files. Any failure to comply with these rules will give you an automatic 0.

. Whenever you submit your files toEd, you will see the results of some exposed tests. If you do not see the results, your assignment is not submitted correctly. If your assignment is not submitted correctly, you will get an automatic 0.  If your submission does not compile on ED, you will get an automatic 0.

. The assignment shall be graded automatically on ED.  Requests to evaluate the assign- ment manually shall not be entertained, and it might result in your final marks being lower than the results from the auto-tests. Please make sure that you follow the instruction closely or your code may fail to pass the automatic tests.

.  The exposed tests on ED are a mini version of the tests we will be using to grade your work. If your code fails those tests, it means that there is a mistake somewhere.  Even if your code passes those tests, it may still contain some errors.  Please note that these tests are only a subset of what we will be running on your submissions, we will test your code on a more challenging set of examples. Passing the exposed tests assures you that your submission will not receive a grade lower than 40/100.  We highly encourage you to test your code thoroughly before submitting your final version.

. Next week,a mini-tester will also be posted. The mini-tester contains tests that are equivalent to those exposed on Ed. We encourage you to modify and expand it.  You are welcome to share  your tester code  with  other students  on Ed.  Try to identify tricky cases.  Do not hand in your tester code.

. Failure to comply with any of these rules will be penalized. If anything is unclear, it is up to you to clarify it by asking either directly a TA during office hours, or on the discussion board on Ed.

Of course, the player could have chosen many other possible blocks on the board and they could have decided to perform a different type of move.

Goals and Scoring

At the beginning of the game, each player is assigned a randomly-generated goal.  There are two types of goal:

.  Blob goal.  The player must aim for the largest  “blob” of a given color c.  A blob is a group of orthogonally connected blocks with the same color.   That is, two blocks are considered connected if their sides touch; touching corners does not count.   The player’s score is the number of unit cells in the largest blob of color c.

.  Perimeter goal.  The player must aim to put the most possible units of a given color c on the outer perimeter of the board.  The player’s score is the total number of unit cells of color c that are on the perimeter. There is a premium on corner cells: they count twice towards the score.

Notice that both goals are relative to a particular color. We will call that the target color for the goal.

PART - 0: Familiarize yourself with the starter code

Let’s start by getting comfortable with the code provided and the idea behind the block data structure.

As mentioned in the introduction, we will be using a quad-tree to represent the structure of a block.  Quad-trees are trees in which each internal node has exactly four children.  It would not make sense for us to use a tree in which nodes could have a different number of children, say three. This is because a block is either solid-colored or subdivided; if it is solid-colored, it is represented by a node with no children (i.e.  a leaf), and if it is subdivided, it is subdivided into exactly four sublocks.

Each node should contain the values that would be assigned to their corresponding Block objects. You can assume that the size of the top-level block is 16.  How many nodes have you drawn?

NOTE: If you come to office hours, we will ask to see your drawing before answering questions!

Now that you can draw the block structure on paper, can you translate it into code?  Inside the main method of the Block class, create a Block object that corresponds to the same game board above. You can access constants representing the Colors needed from the class GameColors. Once you have created the board, you can display its text representation using the method printBlock() provided to you. If the structure has been created correctly the following should be displayed:

pos=(0,0),  size=16,  level=0

GREEN, pos=(8,0),  size=8,  level=1

RED, pos=(0,0),  size=8,  level=1

YELLOW, pos=(0,8),  size=8,  level=1

pos=(8,8),  size=8,  level=1

BLUE, pos=(12,8),  size=4,  level=2

RED, pos=(8,8),  size=4,  level=2

YELLOW, pos=(8,12),  size=4,  level=2

BLUE, pos=(12,12),  size=4,  level=2

Invariants.   While thinking about the block structure, you might have noticed that each nodes must satisfy a lot of invariants for the tree to correctly represent a Block.  Here is a list of some of them:

.  Nodes have either 4 children or 0.

. If this Block has children then:

– their maxDepth is the same as the one of this Block

– their size is half that of this Block

– their level is one greater than that of this Block

– the position of their upper left corner can be determined from their size and the position of the upper left corner of this Block (I’ll leave it up to you to figure out how).

– the color of this Block is null

.  level is always smaller than or equal to maxDepth

TEST and DEBUG.   Please note that to test and debug your code you should not rely on the GUI. The GUI can definitely help fine tune your code, but you should test and debug it before using it.  The method printBlock() provided to you displays a text representation of the block and can help you through this process.  Remember that you are allowed and encouraged to add as many private helper methods as you wish.  This will help you to:  keep your code cleaner and better organized, as well as break each task into smaller steps.  All of this will in turn help you when testing and debugging.

PART - I: Set up the board (30 points)

With a good understanding of the data structure, you are now ready to start working on the completion of the class Block.

[10 points]  For the game,  we want to be  able to generate random boards.   This  is  what  the constructor Block(int  lvl,  int  maxDepth) is for.  The method generates a random Block with level lvl, and maximum depth maxDepth using the following the strategy:  if a Block is not yet at its maximum depth, it can be subdivided.  Decide whether or not to do so as follows:

.  Use the Random object stored in the field gen to generate a random number in the interval [0, 1). Please note that you should generate this number if and only if it is possible for this Block to be subdivided.

.  Subdivide the block if the random number is less than Math. exp(-0.25  *  level), where level is the level of the Block within the tree.

. If a Block is not going to be subdivided, use a random integer to pick a color for it from the array of colors in GameColors. BLOCK COLORS . Make sure to generate the integer in the appropriate range, and use gen to do so.

Notice that the randomly-generated Block may not reach its maximum allowed depth. It all depends on the random numbers generated.

This constructor is responsible for assigning the appropriate values to the fields of all Blocks within the Block it generates except the fields size, xCoord, and yCoord which should be instead initialized by default.  Next, you will write a method that can be used to correctly initialize all these fields.

If you use the seed 2 when initializing the Random variable gen on line 17 of Block. java, then when executing the following snippet of code

Block blockDepth2  = new  Block(0,2);

blockDepth2.printBlock();

the text below will be displayed:

pos=(0,0),  size=0,  level=0

GREEN, pos=(0,0),  size=0,  level=1

RED, pos=(0,0),  size=0,  level=1

YELLOW, pos=(0,0),  size=0,  level=1

pos=(0,0),  size=0,  level=1

BLUE, pos=(0,0),  size=0,  level=2

RED, pos=(0,0),  size=0,  level=2

YELLOW, pos=(0,0),  size=0,  level=2

BLUE, pos=(0,0),  size=0,  level=2

[10 points] Implement the method updateSizeAndPosition().  This method takes three integers as input: one representing the size of this block, and the others representing the coordinates of the upper left corner of this block.  The method updates the size and position for this block and all of its sub-blocks, while ensuring consistency between the values of the fields and the relationship of the blocks.  Make sure the invariants are all respected!  The method should throw an IllegalArgumentException is the input for the size is invalid, i.e. if it is negative or it cannot be evenly divided into 2 integers until the max depth is reached.  There’s no need to perform any input validation for the coordinates.

If you use the seed 2 when initializing the Random variable gen on line 17 of Block. java, then when executing the following snippet of code

Block blockDepth2  = new  Block(0,2);

blockDepth2. updateSizeAndPosition(16,  0,  0);

blockDepth2.printBlock();

the text below will be displayed:

pos=(0,0),  size=16,  level=0

GREEN, pos=(8,0),  size=8,  level=1

RED, pos=(0,0),  size=8,  level=1

YELLOW, pos=(0,8),  size=8,  level=1

pos=(8,8),  size=8,  level=1

BLUE, pos=(12,8),  size=4,  level=2

RED, pos=(8,8),  size=4,  level=2

YELLOW, pos=(8,12),  size=4,  level=2

BLUE, pos=(12,12),  size=4,  level=2

[10 points]  In order for the game to be able to draw the blocks you can now generate, you need to provide an implementation for the method getBlocksToDraw().  The method returns an ArrayList of BlockToDraws.  Open the file BlockToDraw. java to familiarize yourself with this data type. The list returned by getBlocksToDraw() should contain, for each undivided Block:

. one BlockToDraw in the color of the block

.  another BlockToDraw in the FRAME COLOR (see GameColors. java) and a stroke thickness equal to 3.

Note that a stroke thickness equal to 0 indicates that the block should be filled with its color. The order in which the objects BlockToDraw appear in the list does not matter.

After having implemented this method, you can try to run BlockGame. If you use the seed 2 when initializing the Random variable gen on line 17 of Block. java and you select 2 as the maximum depth when running the game, you will see the following board displayed:

PART - II: Make the game playable (30 points)

Time to make the game real by allowing players to be able to select a block from the board and apply a move of their choice.

[12 points] The first thing to do is implement the method getSelectedBlock() which allows the game to retrieve the Block selected by the player.  In order for the user to play the game, they must be able to select a block on which they would like to make a move.  They will do so by clicking on the board at a desired location, and using the up and down arrows to choose the level of the block. The method getSelectedBlock() takes those inputs (the (x,y) coordinates of where the user clicked, and an int representing the level selected), and finds the corresponding Block within the tree.  If the level specified is lower than the lowest block at the specified location, then the method returns the block at the location with the closest level value.  Note that if a Block includes the location  (x,y), and that Block is subdivided, then one of its sub-Blocks will contain the location (x,y) too.  This is why the level is needed to identify which Block should be returned.  Please note that you can view the quad-tree representing the block data structure as a search tree.  As such, this method should run in O(h), where h is the height of the tree.

Input validation:  if the level provided is smaller than this Block’s level or larger than its maximum depth,  then the method should throw an  IllegalArgumentException.   If the position, (x,y), is not within this Block, then the method should return null.

For example, using the seed 4 when initializing the Random variable gen online 17 of Block. java, the following snippet of code generates a board with maximum depth 3, top left corner in    position (0, 0), and size equal to 16.

Block blockDepth3  = new  Block(0,3);

blockDepth3. updateSizeAndPosition(16,  0,  0);

We can then select and print the Block at level 1 containing the location (2 , 15) as follows:

Please note, that the same would have been displayed even if the level selected was 2 or 3. On the other hand, we can select and print the Block at level 2, containing the location (3 , 5) as follows: