Homework07

[zender991]

Representing Grids

Mathematically, a grid is a partition of a 2D region into a disjoint collection of cells. Typically, these cells are all a single simple shape such as a square, triangle or hexagon. Several mini-projects, including 2048, Zombie Apocalypse, and the Fifteen puzzle, involve rectangular grids of squares. Grids are useful in many computational applications because they provide a convenient way to partition a geometric region in a way that can be easily modeled as a 2D data structure.

Indexing rectangular grids

For now, we focus on rectangular grids that are composed entirely of squares. Mathematically, such a grid has a height grid_height and a width grid_width, measured in terms of individual squares. The standard terminology when referring to the size of such a grid is to specify height first, followed by width. For example, a three-by-four grid is three squares high and four squares wide.

When working with such grids, we will index individual squares in the grid in the same manner that entries in a matrix are indexed, top to bottom then left to right. In particular, a square is indexed by its row i and its column j in the grid where the row index ii lies in the range 0, 1, ..., height - 1 and the column index j lies in the range 0, 1, ..., width - 1. This program produces a diagram in CodeSkulptor that illustrates this indexing scheme http://www.codeskulptor.org/#poc_indexed_grid.py

When compared to canvas coordinates, this matrix-based indexing scheme transposes the horizontal and vertical dimensions. For example, note that the coordinates given to draw_polygon in the diagram-plotting program linked above order the column index first and the row index second when generating vertices of each square drawn in the grid. For now, you don't need to worry about this issue since the GUIs that we provide for each mini-project handle this transposition without any effort on your part.

Modeling rectangular grids in Python

Given a square, we can store the index associated with a square as the tuple (row, col) in Python. Then, we can represent some relevant property of that square as the entry cells[row][col] in the 2D list cells. Note the expression cells[row] returns a 1D list corresponding to a row of the grid. We can initialize this 2D list via the code fragment:
cells = [ [... for col in range(grid_width)] for row in range(grid_height)]

Note that if row or col are not used in the expression ..., Pylint will warn that these variables are unused. To avoid this warning, you can rename these variables to dummy_row and dummy_col to alert Pylint that these variables are intentionally unused. This renaming will suppress the warning.

2048 game

2048 is a simple grid-based numbers game. The object of the game is to combine tiles with the same number to make larger numbered tiles. You "win" when you create a 2048 tile. You can play it here https://play2048.co/

Moving: Sliding and Merging
On each turn, you may slide all of the tiles on the board in one direction (left, right, up, or down). When you do so, all of the tiles on the board slide as far as they can go in the given direction leaving no empty squares between the tiles. Further, if two tiles of the same number end up next to each other, they merge to form a new tile with twice the value. If no tiles would slide or combine in a given direction, then that is not a legal move, and you cannot make that move on the current turn.
To understand how the tiles slide and merge, consider the following game board:

https://www.screencast.com/t/bO2bys2w4

If you move right, then the tiles would slide and merge to yield the following final position:

https://www.screencast.com/t/sbl4QrErQf

Note the following about how the tiles slide and merge:

• In the top row, the first two "2" tiles merged to become a "4" tile. The second two "2" files also merged to become another "4" tile. However, the two resulting "4" tiles did not merge. A tile can only merge once on any given move.
• In the second row, the single "4" tile just slides all the way to the right.
• In the bottom two rows, a pair of matching tiles merge. Note that it does not matter if there were empty squares between the tiles before they slid. The merge happens to adjacent tiles after they have slid over as far as possible.
• In the bottom row, only one pair of "4" tiles merge. In particular, the two tiles furthest to the right are the two that merged. This is because you moved right. Had you moved left, for instance, the two tiles furthest to the left would have merged instead.

If instead, you had moved up starting from the original board, then the tiles would have slid and merged to yield the following final position:

https://www.screencast.com/t/SJQo4iQLH2O

Note the following about how the tiles slide and merge here:

• In the left column, the first two "2" tiles merged to become a "4" tile. This "4" tile, however, did not merge with the existing "4" tile, as tiles can only merge once on a turn.
• In all of the other columns, the tiles just slid up as far as they could go with no further merging.

Adding New Tiles
Finally, after all of the tiles have slid and merged, a new tile is added to the board randomly. Note that a new tile is added only if the move actually changed the board in any way (meaning that either at least one tile slid and/or one pair of tiles merged). Otherwise, that direction was not a legal move and nothing should happen.

The new tile is added to a randomly selected empty grid square after the tiles have moved and slid. The new tile is either a "2" or a "4". In our version of the game, the value of the new tile should be randomly selected such that it has a value of "2" roughly 90% of the time and a value of "4" roughly 10% of the time.

The Initial Board
The game starts with a board that has two initial tiles on it. You can think of this board as an empty board with two tiles added, using the procedure described above for adding new tiles. Each tile will either have a value of "2" or "4". And, as described above, the value of a tile will be "2" roughly 90% of the time.

Ending the Game
You lose the game when the board is full and it is not possible to make a legal move in any direction (meaning that there are no possible merges). In our version of the game, we will not worry about detecting whether the game has been won or lost, so you can ignore this.

Coding

SECTION 1

We have provided the following template that contains the basic code that you will need to implement the merge function. The signature (name and parameters) of the functions in this file must remain unchanged, but you may add any additional functions or other code that you need to.

For this assignment, you will implement a merge(line) that models the process of merging all of the tile values in a single row or column. This function takes the list line as a parameter and returns a new list with the tile values from line slid towards the front of the list and merged. Note that you should return a new list and you should not modify the input list. This is one of the more challenging parts of implementing the game.

In this function, you are always sliding the values in the list towards the front of the list (the list position with index 00). You will make sure you order the entries in line appropriately when you call this function later in the next assignment. Empty grid squares with no displayed value will be assigned a value of zero in our representation.

For example, if a row of the board started as follows:

https://www.screencast.com/t/ZOtv2iHDVPR

And you slide the tiles left, the row would become:

https://www.screencast.com/t/MqgsU2TLl

Note that the two leftmost tiles merged to become a 4 and the third 2 just slides over next to the 4.

A given tile can only merge once on any given turn, although many pairs of tiles could merge on a single turn.

For the above example, the input to the merge function would be the list [2,0,2,2]. The function should then produce the output [4,2,0,0]. We suggest you begin to implement this function as follows:

1. Start with a result list that contains the same number of 0's as the length of the line argument.
2. Iterate over the line input looking for non-zero entries. For each non-zero entry, put the value into the next available entry of the result list (starting at position 0).

Notice if you only follow this process, you would end up with the result [2,2,2,0].

Now you should think through what you should add to your function in order to merge tiles. Keep in mind, however, that any tile should only be merged once and that these merges should happen in order from lowest index to highest index. For instance, on the input [2,0,2,4], the result should be [4,4,0,0], not [8,0,0,0].

Note that there are many ways to implement the merge function. The objective of this project is for you to use what you've learned in our previous classes to implement a complex function. You have already learned all of the Python required to implement merge, so the challenge is to think carefully about what the function does and how to best accomplish that.

Here is one basic strategy to implement the merge function:

1. Iterate over the input and create an output list that has all of the non-zero tiles slid over to the beginning of the list with the appropriate number of zeroes at the end of the list.
2. Iterate over the list created in the previous step and create another new list in which pairs of tiles in the first list are replaced with a tile of twice the value and a zero tile.
3. Repeat step one using the list created in step two to slide the tiles to the beginning of the list again.

This is not the most efficient way of implementing merge. While it is fine to implement it in this way, we challenge you to think of other ways of doing it that do not require creating so many lists. Ultimately, how you approach the problem is up to you.

As you work on your merge function, here are some simple tests you should try:

• [2,0,2,4] should return [4,4,0,0]
• [0,0,2,2] should return [4,0,0,0]
• [2,2,0,0] should return [4,0,0,0]
• [2,2,2,2,2] should return [4,4,2,0,0]
• [8,16,16,8] should return [8,32,8,0]

These tests are by no means exhaustive and are just meant to get you started.
You can check your merge function here http://codeskulptor.appspot.com/owltest/?urlTests=poc.poc_2048_merge_tests.py&urlPylintConfig=poc.pylint_config.py

SECTION 2

In the template http://www.codeskulptor.org/#poc_2048_template.py , we have provided the skeleton of a TwentyFortyEight class. You should first implement the game initialization, which consist of the following methods:

• init(self,grid_height,grid_width): This method takes the height and width of the grid and creates the initial 2048 board. You should store the height and width of the grid for use in other methods and then call the reset method to create an initial grid of the proper size.
• reset(self): This method should create a grid of height×width zeros and then use the new_tile method to add two initial tiles. This method will be called by init to create the initial grid. It will also be called by the GUI to start a new game, so the point of this method is to reset any state of the game, such as the grid, so that you are ready to play again.
• new_tile(self): This method should randomly select an empty grid square (one that currently has a value of 0) if one exists and place a new tile in that square. The new tile should have the value 2 90% of the time and the value 4 10% of the time. You should implement this by selecting a tile randomly with that proportion, not by guaranteeing that every 10th tile is a 4.

You will also need to implement the following helper methods, which will help you develop and test the above methods.

• get_grid_height(self): This method should return the height of the grid. It will be used by the GUI to determine the size of the board.
• get_grid_width(self): This method should return the width of the grid. It will be used by the GUI to determine the size of the board.
• str(self): This method should return a human readable string representing your 2048 board. You may format this string however you would like.
• set_tile(self,row,col,value): This method should set the tile at position (row,col) in the grid to value.
• get_tile(self,row,col): This method should return the value of the tile at position (row,col) in the grid. This method will be used by the GUI to draw the game board and by OwlTest to check your code.

You should test all of these methods as you develop them. Note, however, that your reset method will not be completely correct until after you implement the new_tile method. You can still call new_tile from reset before you implement it, it will just not add any tiles. During testing, you will want to use the set_tile method so that you can start with different board states.

You are now ready to implement the final method: move. The move method is where the real logic of the game goes. This method should slide all of the tiles in the given direction. The direction argument will be one of the constants, UP, DOWN, LEFT, or RIGHT. There are many ways of implementing the move method. Here is one approach that will help you avoid writing separate pieces of code for each direction.

For each direction, we recommend pre-computing a list of the indices for the initial tiles in that direction. Initial tiles are those whose values appear first in the list passed to the merge function. For example, the initial tiles for the UP direction lie along the top row of the grid and in a 4 \times 44×4 grid have indices [(0,0),(0,1),(0,2),(0,3)]. Since these lists of indices will be used throughout the game, we recommend computing them once in the__init__ method and then storing them in a dictionary where the keys are the direction constants (UP, DOWN, LEFT, and RIGHT).

With this dictionary computed, the move method can be implemented as follows. Given a direction, iterate over the list of initial tiles for that direction and perform the following three steps for each initial tile:

1. As described in the "Grids" video, use the direction in the provided OFFSETS dictionary to iterate over the entries of the associated row or column starting at the specified initial tile. Retrieve the tile values from those entries, and store them in a temporary list.
2. Use your merge function to merge the tile values in this temporary list.
3. Iterate over the entries in the row or column again and store the merged tile values back into the grid

Following our outline above, we retrieve the list of initial tiles [(0,0),(0,1),(0,2),(0,3)] for the top row of the grid and use the direction (1,0) associated with \color{red}{\verb|UP|}UP to iterate over the grid indices for each column. For the second column, these indices are [(0,1),(1,1),(2,1),(3,1)]. Using these indices, we can create a temporary list [2,0,2,2] that holds the tile values in this column, apply merge to compute the merged list[4,2,0,0], and finally copy the new merged tile values back into the grid. This sequence of operations yields the grid shown below.

If you have done this correctly, a single call to the move method should slide all of the tiles in the given direction. All that remains is that you must determine if any tiles have moved. You can easily do this when you put the line back into the grid. For each element, check if it has changed and keep track of whether any tiles have changed. If so, you should add a new tile to the grid, by calling your new_tile method. Now, you are ready to run the GUI and play 2048!

You can check your code here http://codeskulptor.appspot.com/owltest/?urlTests=poc.poc_2048_tests.py&urlPylintConfig=poc.pylint_config.py&imports=%7Bpoc:(poc_2048_gui)%7D