” 写作CIT594编程、 辅导java程序HW4: BlockyLearning goalsTopics: Spatial Data Structures/QuadTree, Recursive data structures, Tree Search,Algorithm analysis, TestingBy the end of this assignment, you should be able to: Model hierarchical and spatial data using trees Implement recursive operations on trees (both non-mutating and mutating) Convert a tree into a flat, two-dimensional structure Explain and perform runtime analysis of the code you wroteIntroduction: The Blocky gameBlocky is a game with Simple moves on a simple structure, but like a Rubiks Cube, it is quitechallenging to play. The game is played on a randomly-generated game board made of squares ofdifferent colors, such as this:The goal of the game called Perimeter goal is to put the most possible units of a given color c onthe outer perimeter of the board. The players score is the total number of unit cells of color cthat are on the perimeter. There is a premium on corner cells: they count twice towards the score.After each move, the player sees their score, determined by how well they have achieved theirgoal. The game continues for a certain number of turns or until the user runs out of moves (inthis assignment, we will allow an unlimited number of moves).Now lets look in more detail at the rules of the game and the different ways it can be configuredfor play.The Blocky boardWe call the game board a block. It is best defined recursively. 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 thatthe top-level block is at level 0. If the top-level block is subdivided, we say that its four subblocksare at level 1. More generally, if a block at level k is subdivided, its four sub-blocks are atlevel k+1.A Blocky board has 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 it couldnt be subdividedbeyond the top level, meaning that it would be of one solid color.This board was generated with a maximum depth of 2:This board was generated with a maximum depth of 3:This board was generated with a maximum depth of 4:As you can see the deeper the board the more blocks you might have.For simplicity, we recommend limiting the maximum depth to 3 or 4.For scoring, the units of measure are squares the size of the blocks at the maximum alloweddepth. We will call these blocks unit cells.Choosing a block and levelsThe moves that can be Made are things like rotating clockwise a block. What makes movesinteresting is that they can be applied to any block at any level. For example, if the user selectsthe entire top-level block for this board:and chooses to rotate it, the resulting board is this:But if instead, on the original board, they rotated the block with id 3 (at level 1) (one level downfrom the top-level block) in the bottom right-hand corner, the resulting board is this:Of course, there are many other blocks within the board at various levels that the player couldhave chosen.MovesThese are the moves that are Allowed on a Blocky board: Rotate the selected block (90 degrees) clockwise. Implemented in Block.java Swap two blocks (and their sub-blocks if any). Implemented in Game.java Smash the selected block, giving it four new, randomly generated sub-blocks. Smashingthe top-level block is not allowed that would be creating a whole new game. Andsmashing a unit cell is also not allowed since its already at the maximum allowed depth.Implemented in Block.javaGoals and scoringAt the beginning of the game, the player is assigned a target color for the perimeter goal.Perimeter goal:The player must aim to put the most possible blocks of a given target color c on the outerperimeter of the board. The players score is the total number of cells of color c that are on theperimeter. There is a premium on corner cells: they count twice towards the score.PlayersThis version of Blocky is single player.Configurations of the gameA Blocky game can be configured in several ways: Maximum allowed depth.While the specific color pattern for the board is randomly generated, we control howfinely subdivided the squares can be. Target color.Setup and starter codePlease download the starter Code files. Do not forget to test your code as you implement yoursolution.Task 1: Understand the Block data structure and the Game classSurprise, surprise: we will use a tree (QuadTree) to represent the nested structure of a block. Ourtrees will have some very strong restrictions on their structure and contents, however. Forexample, a node cannot have 3 children. This is because a block is either solid-colored orsubdivided; if it is solid-colored, it is represented by a node with no children, and if it issubdivided, it is subdivided into exactly four subblocks.How are the blocks numbered?The blocks are numbered using a breadth-first traversal. The image below shows the mappingof quadtree nodes to blocks ids. The maximum depth of this blocky game is 3:Open the IBlock interface. Read through the class documentation carefully.Create a Block class that will implement IBlock. The Block class has quite a few attributesto understand. The attributes are listed in the IBlock documentation. You must name your datafields exactly as they are named in IBlocks documentation (bullet listed).Open the IGame interface. Read through the class documentation carefully. The Game classrepresents an instance of the Blocky game. It creates and maintains the Quadtree. The Gameclass performs the swap operation and computes the score of the player.1. Open Block.java and implement the constructor and the attributes accessors andmutators.2. Manually draw (construct) the Block data structure corresponding to the game boardbelow, assuming the maximum depth was 2 (and notice that it was indeed reached). Inthis assignment, we will assume that the top-level blocks top-left point is at (0,0)and its bottom-right point is at (8, 8).Use the TestBlocky class to check your code. Comment out the lines raising errors aswe have not yet implemented Game. To display the Block data structure, add it to theGameFrame instance (using the addQuad method) and call display().Task 2: Initialize the gameWith a good understanding of the data structure, you are ready to implement the Game and theBlock classes.1. Open Block.java and implement the smash() method. Verify that smash randomlyassign colors to subblocks.2. Now that we have the smash method ready, we can generate random boards. This is whatfunction random_init is for.3. Create a Game.java class that implements IGame.java. Implement the constructor andrandom_init. The method is Outside the Block class because it doesnt need to refer to aspecific Block.Here is the strategy to use in random_init: If a Block is not yet at its maximum depth, itcan be subdivided; this function must decide whether or not to do so. To decide:o Use the function Math.random to generate a random number to randomly select aBlock in the tree.o Subdivide if the Block at the random index is not already at max_depth.o If a Block is not going to be subdivided (smashed), use a random integer to pick acolor for it from the list of colors in IBlocks.COLORS.Notice that the randomly generated Block may not reach its maximum allowed depth. Itall depends on what random numbers are generated.Check your work: Use TestBlocky.java to confirm that your smash() and random_init()methods work correctly.Task 3: Complete the Block classImplement the rest of the methods in the Block classCheck your work: Thoroughly test your Block class and use TestBlocky.java to verify that yourimplementation is correct. Name your test class BlockTest.javaTask 4: Complete Game classNow we have enough pieces to assemble a rudimentary game!Implement all the methods in Game.java except for flatten() and perimeter_score.Check your work: Thoroughly test your Game class and use TestBlocky.java to verify thatyour implementation is correct. Name your test class GameTest.javaAt the end of Task 4, you should have a functioning game without the scores.Task 5: Implement scoring for perimeter goalNow lets get scoring working.The unit we use when scoring against a goal is a unit cell. The size of a unit cell depends on themaximum depth in the Block. For example, with a maximum depth of 4, we might get thisboard:If you count down through the levels, youll see that the smallest blocks are at level 4. Thoseblocks are unit cells. It would be Possible to generate that same board even if the maximumdepth was 5. In that case, the unit cells would be one size smaller, even though no Block hasbeen divided to that level.Notice that the perimeter may include unit cells of the target color as well as larger blocks of thatcolor. For a larger block, only the unit-cell-sized portions on the perimeter count. For example,suppose maximum depth was 3, the target color was red, and the board was in this state:Only the red blocks on the edge would contribute, and the score would be 4: one for each of thetwo unit cells on the right edge, and two for the unit cells inside the larger red block that areactually on the edge. (Notice that the larger red block isnt divided into four unit cells, but westill score as if it were.)Remember that corner cells count twice towards the score. So, if the player rotated the lowerright block to put the big red block on the corner:the score would rise to 6.Now that we understand these details of scoring for a perimeter goal, we can implement it.1. It is very difficult to compute a score for a perimeter goal through the tree structure.(Think about that!) The goal is much more easily assessed by walking through a twodimensionalrepresentation of the game board. Your next task is to provide thatpossibility: In the Game class, define the method flatten.2. Now implement the perimeter_score method in class Game to truly calculate the score.Begin by flattening the board to make your job easier!Check your work: Now when you play the game, you should see the score changing. Check toconfirm that it is changing correctly.Polish!Take some time to polish up. This step will improve your mark, but it also feels so good. Hereare some things you can do: Pay attention to style and documentation warnings raised by the IDE. Fix them! Read through and polish your internal comments. Remove any code you added just for debugging, such as print statements. Remove the word TODO Wherever you have completed the task. Take pride in your gorgeous code!Grading: The assignment is worth 212 pointsDescription PointsAutograder Tests 130Algorithm Analysis Document 12Testing: Point.java, Block.java, Game.java 50 (90% code coverage for full credit)Documentation/Style 15Readme file 5请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
