Due: Monday, 18 September 2017
Navigation
- Introduction
- The Game
- Program Design
- Instrumentation and Testing
- Algorithm
- Submission and Version Control
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
, andTile
classes. - A view of the model, which displays the game state to the user.
Our view resides in the
GUI
andBoardWidget
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 methodscol
androw
. If S is aSide
, thenS.col(c, r)
andS.row(c, r)
return the original column and row numbers for the square that would reside at columnc
and rowr
if you turned the board so that side S is the side opposite you. SoNORTH.col(0, 1)
is simply 0 andNORTH.row(0, 1)
is simply 1. HoweverWEST.col(0, 1)
is 2 andWEST.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 methodsvtile
andsetVtile
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 add <filepath> # To add, or stage, any modified files.
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.]