Project 0: Signpost
Due: Tuesday, 18 February 2020
Please see @331 for updates and changes to the assignment.
- The Puzzle
- Program Design
- Instrumentation and Testing
- Submission and Version Control
This initial programming assignment is intended to give you a chance to get familiar with Java and the various tools used in the course. This project is smaller in scale compared to the other three projects you will complete this semester. However, you may still find it challenging and we encourage you to start as early as possible.
We will be grading solely on whether you manage to get your program to work (according to our tests, which are provided to you in the skeleton) 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 assignment 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 repo 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 puzzle game Signpost is one of Simon Tatham’s collection of GUI games (available on a variety of operating-system configurations, including Ubuntu.) He attributes the puzzle to Angela and Otto Janko, who call it Pfeilpfad (arrow path). In this project, you are given an incomplete Java program that creates these puzzles and allows its user to solve them, and you must supply the missing parts to complete the implementation.
The puzzle itself is quite simple. It is played on a W×HW×H rectangular grid of square cells. Every square on the board is annotated with an arrow pointing horizontally, vertically, or diagonally. One special square, the goal, is not annotated with an arrow, but instead is annotated with a star. The goal square also contains the number W⋅HW⋅H. Another special square, the start, always contains the number 1. By default, the start and the goal will appear in the top-left and bottom-right corners of the board, respectively. Alternatively, the puzzle may be set to have free ends, in which case the start and the goal squares may appear anywhere on the board. The bottom-left corner of the board has the coordinates (0,0)(0,0), with the positive x-axis running horizontally to the right, and the positive y-axis running vertically upwards.
The player’s goal is to assign each unnumbered square a sequence number so that the squares form a chain following the arrows from 1 to W⋅HW⋅H, using up all numbers in between. We say that square A is connectable to square B if B is one queen move away from A in the direction specified by A’s arrow (here, “queen move” refers to the queen move in chess.) For example, in the following board, the start, at coordinates (0,3)(0,3), is connectable to the squares at
The first step in tackling the project is to play the game. That is, you should familiarize yourself with what the final product should look like. You can do so by playing the game on an instructional machine using the staff solution program.
On the instructional machines (only), you can run the staff version of this program with the following command:
It takes the same options as your project (see Instrumentation and Testing).
If you are working on your local computer you will have to SSH into your instructional machine to run the staff solution. To allow the GUI of the program to appear via SSH you will have to follow the instructions here: Staff GUIs over SSH. Section C of the linked guide will show you how to SSH to your instructional machine with X11 forwarding enabled (which allows to view the staff solution’s GUI on your local computer over an SSH connection).
Once you are on an instructional machine, run the following command:
This command starts the signpost program (specifically, the one implemented by the course staff). The
--log option will output information about the program’s execution. Every time the program is invoked, it creates a signpost puzzle board with some randomly generated solution. In your terminal you will see an output very similar to the following:
PUZZLE 4 4 1 14 12 15 8 5 13 4 7 6 2 3 9 10 11 16 1 10 16 ENDPUZZLE
This is a log of the program, describing its operations. In the first line, PUZZLE, indicates that a puzzle is being created. The second line indicates that it is a 4×44×4 signpost puzzle. The next 4 lines define the solution of this puzzle. The 7th line says that the fixed numbers on the board are 1, 10, and 16. Finally, ENDPUZZLE indicates that this board is done initializing.
If you want to always get the same board, you can use the seed option as in the following example:
staff-signpost --seed=42 --log
The same seed number produces the same random sequence, which will make the puzzle deterministic. This way bugs and other behavior can be reproduced.
Now that the puzzle has been generated by the program, it’s time to play the game. If we tried to connect the start to the square that contains 2 in the solution, the program would output the following log:
CONN 0 3 2 1
There was an attempt to connect the square whose coordinates on the board are (0,3), and the square whose coordinates are (2,1). Try to play the game and see what are the logs the program produces. You should also try the options in the program’s menu bar.
The skeleton exhibits a design pattern in common use: the Model-View-Controller Pattern (MVC).
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 and the rules by which it may be modified. Our model resides in the
- A view of the model, which displays the puzzle state to the user. Our view resides in the
- A controller for the puzzle, which translates user actions into operations on the model. In our case, it also notifies the view when the model has been modified. Our controller resides mainly in the
Controllerclass, although it also uses the GUI class to read mouse clicks.
Your job for this project is to modify and complete the
BoardWidget classes. We’ve marked places that need attention with comments containing “
FIXME” (the style checker will point these out to you should you forget to fix one). Don’t let that stop you from looking at all the other code in these classes. That’s actually part of the point of giving you the skeleton. You can learn a great deal about programming by reading other people’s programs. It is unlikely that you will be able to complete the “
FIXME“s successfully without understanding the majority of the provided code in the aforementioned classes.
FIXME“s appear in the classes
PuzzleGenerator. There is also one trivial
BoardWidget, which is only there as a stopgap to make the initial skeleton display something. Generally the
FIXME‘s will have instructions to implement something specific, remove certain lines, etc.
Initially, the skeleton contains some dummy code so that when run, you’ll see a board, although you won’t be able to do anything with it to speak of.