# 分治算法代写 | Divide And Conquer Algorithm

Introduction

2048 is a single-player game where the player tries to construct a 2048 tile on a 4×4 grid (see Figure 1). At any time each grid position is either empty or labelled with a power of two. Two random tiles are placed in random empty positions to initialize the game. Random tiles are usually 2’s but 4’s are occasionally possible.

Each turn, the player moves all tiles up, down, left, or right, by pressing w, s, a, or d respectively.

Tiles move in the chosen direction until they hit a wall or another tile. If a tile hits another tile with the same value the two tiles merge (in the direction of the move) into a single tile with twice the value. After this move, and before the next, a random tile is placed on a random empty board position.

If the player constructs a 2048 tile they win and the game ends. If no more moves can be made that would change the game state, the player loses and the game ends.

To get a better idea of how the game works, try playing it here: https://play2048.co/.

Implement a GUI-based 2048 application using tkinter. You can find the tkinter documentation on effbot1 and New Mexico Tech2 . Your implementation should follow the Apple MVC structure3.

Rules, Tips, and Hints

Functionality marking for this assignment is automated and works by analysing your GUI. Consequently, solutions that do not display, or display incorrectly, may not receive marks. You may obtain partial marks for partial displays; e.g. you can receive partial marks for a correct title label, even if your tiles do not display, and you can receive partial marks for correct initial tiles,even if you do not get player input to modify the game state. It is recommended to work on the model, view, and controller classes simultaneously.

This assignment has two tasks for undergraduate students and an additional task for postgraduate students. You can pass the assignment and achieve a playable game by implementing task one only. Successful completion of task two is challenging and only necessary to obtain a top grade.

The number of marks associated with each task is not an indication of difficulty. Task one may take less effort than task two, yet is worth significantly more marks.

Minor differences in the look (e.g. colours, fonts, etc.) of the GUI are acceptable provided they do not cause the Gradescope tests to fail. Except where specified, you are only required to do enough error handling such that regular game play does not cause your program to crash or error.

If your solution contains code that prevents it from being run, you will receive a mark of 0.

You must only make use of libraries listed in Appendix A. You must not import anything that is not on this list; doing so will result in a deduction of up to 100% of your mark.

You may use any code from the support files or sample solutions for previous assignments from this semester only, as well as any lecture or tutorial code provided to you by course staff. However,it is your responsibility to ensure that this code is styled appropriately, and is an appropriate and correct approach to the problem you are addressing.

Task 1: Basic Gameplay

By the end of Task 1 you should have implemented a functional GUI-based version of 2048, which looks like Figure 2 and Figure 3. A heading label with yellow background and white text ‘2048’ should appear at the top of the window at all times. Below the label, the 4×4 grid of tiles should be displayed on a canvas. These tiles are represented by coloured rectangles annotated with their values. They must use the tile and text colours for each value found in a3_support.py. Certain events should cause behaviours as per Table 1.

When the player wins or loses the game inform them of the outcome via an askyesno messagebox.

The messagebox must display the text of WIN_MESSAGE or LOSS_MESSAGE that are defined in a3_support.py. Both of these messages ask the player if they would like to play again. If ‘yes’,the messagebox should close and a new game should begin. If ‘no’, the entire program should end

Table 1: Events and their corresponding behaviours. A move is only applicable if it would cause a change to the game state. All other keypresses should be ignored (no error should occur on other keypresses).

gracefully (e.g. the window should close and the >>> should reappear in the REPL).

To complete this task implement

1. a model class to maintain and modify the game state,
2. a single view class for the 4×4 grid, and
3. a controller class to maintain instances of and communication between, the model and view.

The following sub-sections outline the required structure for your code. You will benefit from writing these classes in parallel, but you should still test individual methods as you write them.

You are permitted to add additional modelling classes and any additional helper methods if they improve your solution.

1.1 Model class

You must use the generate_tile function from a3_support.py to generate random tiles, when required. If you make your own calls to random your code may not generate the expected tiles and fail Gradescope tests. While you are not required to use the other support functions, they will likely be very useful in achieving the various move methods.

You must define a class called Model that implements the following messages.

• __init__(self) -> None:

Constructs a new 2048 model instance. This includes setting up a new game (see new_game method below).

• new_game(self) -> None:

Sets, or resets, the game state to an initial game state. Any information is set to its initial state, the tiles are all set to empty, and then two new starter tiles are randomly generated (see the add_tile method below).

• get_tiles(self) -> list[list[Optional[int]]]:

Return the current tiles matrix. Each internal list represents a row of the grid, ordered from top to bottom. Each item in each row list is the integer value on the tile occupying that space, or None if no tile is occupying that space.

• add_tile(self) -> None:

Randomly generate a new tile at an empty location (you must use generate_tile for this) and add it to the current tiles matrix.

• move_left(self) -> None:

Moves all tiles to their left extreme, merging where necessary. This involves stacking all tiles to the left, merging to the left, and then restacking to the left to fill in any gaps created. If you are keeping track of a score (see Task 2), this method should also add any points gained from the move to the total score.

• move_right(self) -> None: Moves all tiles to their right extreme, merging where necessary. This can be achieved by reversing the tiles matrix, moving left, and then reversing the matrix again. If you are keeping track of a score (see Task 2), this method should also result in gained points being added to the total score.
• move_up(self) -> None:

Moves all tiles to their top extreme, merging where necessary. This can be achieved by transposing the tiles matrix, moving left, and then transposing the matrix again. If you are keeping track of a score (see Task 2), this method should also result in gained points being added to the total score.

• move_down(self) -> None:

Moves all tiles to their bottom extreme, merging where necessary. This can be achieved by transposing the tiles matrix, moving right, and then transposing the matrix again. If you are keeping track of a score (see Task 2), this method should also result in gained points being added to the total score.

• attempt_move(self, move: str) -> bool:

Makes the appropriate move according to the move string provided. Returns True if the move resulted in a change to the game state, else False. The move provided must be one of wasd (this is a pre-condition, not something that must be handled within this method).

• has_won(self) -> bool:

Returns True if the game has been won, else False. The game has been won if a 2048 tile exists on the grid.

• has_lost(self) -> bool:

Returns True if the game has been lost, else False. The game has been lost if there are no remaining empty places in the grid, but no move would result in a change to the game state.

1.2 GameGrid

The GameGrid is a view class which inherits from tk.Canvas and represents the 4×4 grid. On the GameGrid canvas, tiles should be drawn using a combination of the create_rectangle and create_text method on self. You should not create a new tk.Canvas instance as an attribute within this class; doing so will cause the Gradescope tests to report that your GameGrid canvas contains no items. You should implement the following methods in this class:

• __init__(self, master: tk.Tk, **kwargs) -> None:

Sets up a new GameGrid in the master window. **kwargs is used to allow GameGrid to support any named arguments supported by tk.Canvas. The canvas should be 400 pixels wide and 400 pixels tall.

• _get_bbox(self, position: tuple[int, int]) -> tuple[int, int, int, int]:

Return the bounding box for the (row, column) position, in the form

(x_min, y_min, x_max, y_max).

Here, (x_min, y_min) is the top left corner of the position with 10 pixels of padding added, and (x_max, y_max) is the bottom right corner of the cell with 10 pixels of padding subtracted.

• _get_midpoint(self, position: tuple[int, int]) -> tuple[int, int]:

Return the graphics coordinates for the center of the cell at the given (row, col) position.

• clear(self) -> None:

Clears all items.

• redraw(self, tiles: list[list[Optional[int]]]) -> None:

Clears and redraws the entire grid based on the given tiles.