Project 0: 2048

Introduction

This initial programming assignment is intended as an extended finger exercise, a mini-project rather than a full-scale programming project. The intent is to give you a chance to get familiar with Java and the various tools used in the course.

We will be grading solely on whether you manage to get your program to work (according to our tests) and to hand in the assigned pieces. There is a slight stylistic component: the submission and grading machinery require that your program pass a mechanized style check (style61b), which mainly checks for formatting and the presence of comments in the proper places. See the style61b guide for a description of the style it enforces and how to run it yourself.

First, make sure that everything in your repository is properly updated and checked in. Before you start, the command

cd  ~/repo
git status

should report that the directory is clean and that there are no untracked files that should be added and committed. Never start a new project without doing this.

To obtain the skeleton files (and set up an initial entry for your project in the repository), you can use the command sequence

git fetch shared
git merge shared/proj0 -m "Get proj0 skeleton"
git push

from your Git working directory. Should we update the skeleton, you can use the same sequence (with an appropriate change in the -m parameter) to update your project with the same changes.

The Game

You've probably seen and perhaps played the game "2048," a single-player computer game written by Gabriele Cirulli, and based on an earlier game "1024" by Veewo Studio (see his on-line version of 2048). In this mini-project, you are to reproduce this game as a Java application. We have provided code for the actual mechanics of displaying the game board.

The game itself is quite simple. It's played on a $4\times4$ grid of squares, each of which can either be empty or contain a tile bearing an integer--a power of 2 greater than or equal to 2. Before the first move, the machine adds a tile containing either 2 or 4 to a random square on the initially empty board. The choice of 2 or 4 is random, with a 3:1 bias in favor of 2 (that is, there is a 75% chance of choosing 2 and a 25% chance of choosing 4).

On each move, the machine first adds a new tile containing either 2 or 4 to an empty square as for the initial configuration. The player then chooses a direction: north, south, east, or west. All tiles slide in that direction until there is no empty space left in the direction of motion (there needn't be any to start with.) If at this point there are two tiles bearing the same number that are now adjacent in the direction of motion, they merge into a single tile containing the sum of their values (that is, double the value of either one of them, and therefore still a power of two). The tiles then continue to slide in the direction of motion to eliminate any resulting empty space. Even if the merging and subsequent slide bring more tiles together with the same number, there is no further merging. When three adjacent tiles in the direction of motion have the same number, then the leading two tiles in the direction of motion merge, and the trailing tile does not. When there are adjacent four tiles with the same number in the direction of motion, they form two merged tiles.

For example, the board shown in Figure 1a, if tilted to the east, results in the board in Figure 1b. The tile marked with an asterisk in Figure 1b indicates a new, randomly chosen piece that the program then generates for the next turn.

Tilting does not cause a move, and a new piece is not generated, unless the tilt would change the board. For example, an attempt to tilt board (e) north again would not result in a change, the game would not generate a new piece, and the player's turn would not end.

Each time two tiles merge to form a larger tile, the player earns the number of points on the new tile. The game ends when the current player has no available moves (no tilt can change the board), or a move forms a square containing 2048.

Program Design

The skeleton exhibits two design patterns in common use: the Model-View-Controller Pattern (MVC), and the Observer Pattern.

The MVC pattern divides our problem into three parts:

• The model represents the subject matter being represented and acted upon -- in this case incorporating the state of a board game and the rules by which it may be modified. Our model resides in the Model, Side, and Tile classes.
• A view of the model, which displays the game state to the user. Our view resides in the GUI and BoardWidget classes.
• A controller for the game, which translates user actions into operations on the model. Our controller resides mainly in the Game class, although it also uses the GUI class to read keystrokes.

In our particular design, the view is notified of changes to the game state by registering itself as an observer of the Model object. The model itself need not know that it is being observed. Instead, the controller logic from time to time asks the model to notify all observers who have registered on it about changes to the model. The observers then query the model for its current state. The standard Java classes java.util.Observer and java.util.Observable handle this registration and notification: classes that wish to observe implement Observer and those that allow themselves to be observed extend Observable.

Your job for this project is to modify and complete the Model class and the Game class. Don't let that stop you from looking at all the other code in the project (especially parts you will need to use, like Tile and Side). You can learn a great deal about programming by reading other people's programs.

Instrumentation and Testing

To facilitate automated testing of your work, there are a few features that you can use to record sessions and to play back moves for testing or debugging purposes. The skeleton is set up so that when you start your program with

java game2048.Main --log

you'll get a record on the standard output of all of the keys returned by getKey and all the results returned by getNewTile in the order that your program called them. You can capture this log using redirection, like this:

java game2048.Main --log > script1

The --seed option will allow you to prime the random number generation so that you can get the same set of random numbers each time:

java game2048.Main --seed=42

The same seed produces the same random sequence.

Finally, the --testing option reads in a script produced by --log and uses it (in place of user clicks and random numbers) to supply the results of readKey and randomTile. It also prints out data about what calls on the API your program makes (which we use to test the program). For example, to read back the file script1, use

java game2048.Main --testing < script1

Algorithm

The obvious way to keep track of the board is to use a 2D array to keep track of the values of the tiles in each location. That is, _board[c][r] contains the Tile at column c and row r (numbering from 0 left (west) to right (east) and bottom (south) to top (north). It would be easy if the only key the user pressed during play was "Up" (or north). All pieces on row 3 (the top row) stay put, and you can proceed row-by-row down from 3, computing how far each tile can go (and which merge), since if you process in that order, tiles will not have to move again when you go to later rows.

The only problem is that you then have to do the same thing for the other three directions. If you do so naively, you'll get a lot of repeated, slightly modified code, with ample opportunity to introduce obscure errors. Therefore, we've included in the skeleton some methods that will allow you to re-use code that works for "Up" on all the other directions:

• In the class Side, which defines the symbolic names NORTH, EAST, SOUTH, and WEST, we've provided methods col and row. If S is a Side, then S.col(c, r) and S.row(c, r) return the original column and row numbers for the square that would reside at column c and row r if you turned the board so that side S is the side opposite you. So NORTH.col(0, 1) is simply 0 and NORTH.row(0, 1) is simply 1. However WEST.col(0, 1) is 2 and WEST.row(0, 1) is 0, because when you are sitting on the east side of the board with the west side opposite you, the square in your column 0 and row 1 is at column 2 and row 0 to someone sitting on the south side of the board.
• In the class Model, we have provided methods vtile and setVtile that allow you to fetch and set from the board using the row and column numbers for any desired side.

Submission and Version Control

It is important that you commit work to your repository at frequent intervals. Version control is a powerful tool for saving yourself when you mess something up or your dog eats your project, but you must use it regularly if it is to be of any use. Feel free to commit every 15 minutes; Git only saves what has changed, even though it acts as if it takes a snapshot of your entire project.

The command git status will tell you what you have modified, removed, or possibly added since the last commit. It will also tell you how much you have not yet sent to your central repository. You needn't just assume that things are as you expect; git status will tell you whether you've committed and pushed everything.

If you are switching between using a clone of your central repository on the instructional computers and another at home (or on your laptop), be careful to synchronize your work. When you are done working on one system, be sure to push your work to the central repository:

git status                          # To see what needs to be added or committed.
git commit -a -m "Commit message"   # To commit changes.
git push

If you start working on the other system, you then do

git status          # To make sure you didn't accidentally leave
# stuff uncommitted or untracked.
git pull --rebase   # Get changes from your central repo.

Submit your project by committing and tagging it:

git tag proj0-0     # Or proj0-1, etc.
git push
git push --tags

Be sure to respond to all prompts and to make sure the messages you get indicate that the submission was successful. Don't just "say the magic words" and assume that everything's OK.

Aside. Some of you may have noticed that the Git guide in lab1 did not include a --rebase flag with the git pull command. However, in cases where you work on two different local repositories (say your laptop and a lab computer), you just might commit a few changes in one local repository before remembering to pull changes that you sent from the other local repository. There's no problem with that (at least if the changes are not in conflict), but it causes git to create a "merge commit" that has two parents: the last commits from your two repositories. That causes the output from git log to get a touch confusing, since the log is not longer a simple sequence of commits. The effect of git pull --rebase is effectively to create copies of the commits in one repository and splice them after the last commit in the other, leading to a nice, sequential chain of commits in the log. For more information about the difference between these commands, see out the git documentation for git pull, git merge, and git rebase.

To briefly summarize all this: git pull and git pull --rebase both work. The --rebase potentially avoids an extra merge commit and leads to cleaner commit histories.]