代做CIT594编程代写、代写java程序、java编程代写

日期：2021-05-11 09:41

HW4: Blocky

Learning goals

Topics: Spatial Data Structures/QuadTree, Recursive data structures, Tree Search,

Algorithm analysis, Testing

By 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 wrote

Introduction: The Blocky game

Blocky is a game with simple moves on a simple structure, but like a Rubik’s Cube, it is quite

challenging to play. The game is played on a randomly-generated game board made of squares of

different colors, such as this:

The goal of the game called Perimeter goal is 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.

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 or until the user runs out of moves (in

this assignment, we will allow an unlimited number of moves).

Now let’s look in more detail at the rules of the game and the different ways it can be configured

for play.

The Blocky board

We 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 that

the top-level block is at level 0. If the top-level block is subdivided, we say that its four subblocks

are at level 1. More generally, if a block at level k is subdivided, its four sub-blocks are at

level 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 couldn’t be subdivided

beyond 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 allowed

depth. We will call these blocks unit cells.

Choosing a block and levels

The moves that can be made are things like rotating clockwise a block. What makes moves

interesting is that they can be applied to any block at any level. For example, if the user selects

the 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 down

from 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 could

have chosen.

Moves

These 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. Smashing

the top-level block is not allowed – 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.

Implemented in Block.java

Goals and scoring

At 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 outer

perimeter of the board. The player’s score is the total number of cells of color c that are on the

perimeter. There is a premium on corner cells: they count twice towards the score.

Players

This version of Blocky is single player.

Configurations of the game

A Blocky game can be configured in several ways:

? Maximum allowed depth.

While the specific color pattern for the board is randomly generated, we control how

finely subdivided the squares can be.

? Target color.

Setup and starter code

Please download the starter code files. Do not forget to test your code as you implement your

solution.

Task 1: Understand the Block data structure and the Game class

Surprise, surprise: we will use a tree (QuadTree) to represent the nested structure of a block. Our

trees will have some very strong restrictions on their structure and contents, however. For

example, a node cannot have 3 children. 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, and if it is

subdivided, 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 mapping

of 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 attributes

to understand. The attributes are listed in the IBlock documentation. You must name your data

fields exactly as they are named in IBlock’s documentation (bullet listed).

Open the IGame interface. Read through the class documentation carefully. The Game class

represents an instance of the Blocky game. It creates and maintains the Quadtree. The Game

class performs the swap operation and computes the score of the player.

1. Open Block.java and implement the constructor and the attributes’ accessors and

mutators.

2. Manually draw (construct) the Block data structure corresponding to the game board

below, assuming the maximum depth was 2 (and notice that it was indeed reached). In

this assignment, we will assume that the top-level block’s 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 as

we have not yet implemented Game. To display the Block data structure, add it to the

GameFrame instance (using the addQuad method) and call display().

Task 2: Initialize the game

With a good understanding of the data structure, you are ready to implement the Game and the

Block classes.

1. Open Block.java and implement the smash() method. Verify that smash randomly

assign colors to subblocks.

2. Now that we have the smash method ready, we can generate random boards. This is what

function random_init is for.

3. Create a Game.java class that implements IGame.java. Implement the constructor and

random_init. The method is outside the Block class because it doesn’t need to refer to a

specific Block.

Here is the strategy to use in random_init: If a Block is not yet at its maximum depth, it

can 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 a

Block 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 a

color for it from the list of colors in IBlocks.COLORS.

Notice that the randomly generated Block may not reach its maximum allowed depth. It

all 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 class

Implement the rest of the methods in the Block class

Check your work: Thoroughly test your Block class and use TestBlocky.java to verify that your

implementation is correct. Name your test class BlockTest.java

Task 4: Complete Game class

Now 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 that

your implementation is correct. Name your test class GameTest.java

At the end of Task 4, you should have a functioning game without the scores.

Task 5: Implement scoring for perimeter goal

Now let’s get scoring working.

The unit we use when scoring against a goal is a unit cell. The size of a unit cell depends on the

maximum depth in the Block. For example, with a maximum depth of 4, we might get this

board:

If you count down through the levels, you'll see that the smallest blocks are at level 4. Those

blocks are unit cells. It would be possible to generate that same board even if the maximum

depth was 5. In that case, the unit cells would be one size smaller, even though no Block has

been divided to that level.

Notice that the perimeter may include unit cells of the target color as well as larger blocks of that

color. 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 the

two unit cells on the right edge, and two for the unit cells inside the larger red block that are

actually on the edge. (Notice that the larger red block isn’t divided into four unit cells, but we

still score as if it were.)

Remember that corner cells count twice towards the score. So, if the player rotated the lower

right 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 twodimensional

representation of the game board. Your next task is to provide that

possibility: 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 to

confirm that it is changing correctly.

Polish!

Take some time to polish up. This step will improve your mark, but it also feels so good. Here

are 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 points

Description Points

Autograder Tests 130

Algorithm Analysis Document 12

Testing: Point.java, Block.java, Game.java 50 (90% code coverage for full credit)

Documentation/Style 15

Readme file 5

This Assignment was adapted by Eric Fouh, it was originally developed by Diane Horton and

David Liu.