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.
This assignment contains 3 parts. You need to download the files provided. Your task is to complete and submit the three following files:
- 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.
- Late assignments will be accepted up to 2 days late and will be penalized by 10 points per late 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 to Ed, 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 assignment 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.
This assignment consists of implementing a visual game in which players apply operations such as rotations to a recursive structure in order to work towards a goal. The main data structure can be represented with a quad-tree (i.e. a tree in which each internal node has exactly four children). The rules are simple, but the game is still challenging to play. The game board resembles a Mondrian painting, and you can easily pick the color scheme that is most appealing to you. This assignment is adapted from an assignment created by Diane Horton and David Liu from University of Toronto.
The game is played on a randomly-generated game board made of squares of four different colors,such as the following:
Each player is randomly assigned their own goal to work towards: either to create the largest connected ”blob” of a given color or to put as much of a given color on the outer perimeter as possible.
There are three kinds of moves a player can do:
- rotating a block (clockwise or counterclockwise),
- reflecting the block horizontally or vertically (i.e. along the x-axis or the y-axis if you imagine the origin of the axes being place in the center of the block), and
- “smashing” a block (giving it four brand-new, randomly generated, sub-blocks).
After each move, the player sees their score, determined by how well they have achieved their goal.
The game continues for a certain number of turns, and the player with the highest score at the end is the winner.
The Game Board
We will call the game board a “block”. Blocks can be recursively defined; a block is either:
- a square of one color, or
- a square that is subdivided into 4 equal-sized blocks.
The largest block of all, containing the whole structure, is called the top-level block. We say that the top-level block is at level 0 (i.e. it would be at the root of the quad-tree used to represent it).
If the top-level block is subdivided, we say that its four sub-blocks are at level 1 (i.e. these would correspond to the children of the root in the aforementioned quad-tree). More generally, if a block at level k is subdivided, its four sub-blocks are at level k + 1.
A board will have a maximum allowed depth, which is the number of levels down it can go. A board with maximum allowed depth 0 would not be fun to play on since it couldn’t be subdivided beyond the top level, meaning that it would be of one solid color. The following board was generated with maximum depth 5:
For scoring, the units of measure are squares the size of the blocks at the maximum allowed depth.
We will call these blocks unit cells.
To achieve their goal, the players are allowed the three type of moves described above. Note that,smashing the top-level block is not allowed, since that would be creating a whole new game. And smashing a unit cell is also not allowed, since it’s already at the maximum allowed depth. What makes moves interesting is that they can be applied to any block at any level. For example, if the player selects the entire top-level block (highlighted) for this board