In this project, you will build clients for a simple online game. The game of anti-battleship is similar to the game of battleship, but the victory condition is flipped: the player who first gets all of his own ships sank wins the game.
The purpose of this project is three-fold. First, you will have an opportunity to practice the countless design and implementation techniques you've learned in the course -- most notably, designing mutable data-types, along with ideas from the earlier paradigms (state machines, functions over immutable types, data abstraction, decoupling, etc).
Second, the project will give you practice in using a variety of technologies -- networking, sockets I/O and GUI toolkits -- and will help you deepen your understanding of common design patterns, such as view hierarchy, model-view-controller for user interfaces, and publish/subscribe patterns (such as Observer).
Third, you'll have another chance to work in a team, but this time for a more ambitious project, and with some more (self-determined) structure than before.
Game Rules
The game of anti-battleship is played by two players. Each player uses two rectangular grids, both of the same size; individual squares on the grids are identified by their coordinates. On one grid the player arranges ships and records the shots made by the opponent; on the other grid the player records his/her own shots.
Before play begins, players agree on the size of the grid, and the number and type of ships. Each ship occupies 1 x n consecutive squares on a grid, arranged vertically or horizontally; the value of n is determined by the type of ship. Ships cannot overlap or be adjacent; that is, each square is occupied by at most one ship, and any two squares occupied by distinct ships must have at least one empty square between them.
Example: for the grid depicted above, players agreed to use a 10x10 grid, with ships of sizes 5, 4, 4, 3 and 2.
After the ships have been positioned, the game proceeds in a series of turns. In each turn, the current player announces a target square in the opponents' grid that he has not announced yet. There are three possible outcomes:
When either player has no ships remaining (i.e., all of that player's ships have been sunk), that player declares victory, and the game is over.
There is a variant of the game known as the Salvo variant; in that version, instead of announcing one square each turn, the firing player announces as many squares as the number of his own unsunk ships, and the opponent gives the reply for each of the squares. Players do not take extra turns no matter the results.
ApplicationYou should implement a program that can play both variants of the game of anti-battleship over network, between two human players. Grid size and number / type of ships should be user configurable parameters.
Your application should apply some form of security to ensure that players are not cheating by moving their ships after the match has started. We recommend exchanging SHA hashes of the board position before the match, and comparing them with the revealed grids after the match is done. You may use a SHA hash as a 'signature' of the board position, since the signature is non-invertible. Thus, when you send a hash of your board, it doesn't provide your opponent information about what your actual board looks like (i.e. which squares are occupied by your ships etc). Furthermore, a SHA hash signature is collision-resistant: that is, it is not possible for someone to easily forge two board positions that have the same SHA hash signature. Both these properties ensure that it is safe for players to communicate hashes, and that when the opponent reveals his/her final board position, you can compute its SHA hash and ensure that it is the same as the one he/she reported in the beginning of the game. This is sufficient to prevent cheating. To be more careful, you can (and should) also check the game history against the provided board, and can use any other sound strategy to catch potential cheating. Learning how mutually suspicious parties can communicate over a network is a cool part of this project.
Your application should have a graphical user interface that displays the current status of game, with a 2D representation of the player's grid with ship positions and hit squares, and another grid representing which squares the player have shot at. Your interface should allow a player to initiate, or receive, a request for a new game (and specify the game parameters if he/she wishes to). You should try to make your user interface as practical as possible for real-world usage. For instance, you may wish to provide functionality from: allowing users to store/specify user-names, storing user's win/lose record (this will obviously need user names), allowing users who are playing a game to also chat in the same window, allowing users to have buddy-lists, supporting tournaments between buddies, supporting timed games (e.g. users have, say, a total of 5 minutes to make all their moves), and so on. You have to implement at least two of the features listed above, and are welcome to do more (be creative!). Impressive submissions may receive bonus points or awards from the staff.
Your user-interface will be graded on the metrics we discussed in lecture, including learnability, memorability, visibility, efficiency, accessibility, error handling, and of course, aesthetics.
No staff code is provided for this project.
Individual preparation. Complete the lab on networking.
Team preparation. Meet with your team and complete the team building exercise.
Familiarize yourself with Swing and 2D Graphics. The Java tutorials on Swing and 2D Graphics provide a good introduction. You are welcome to use any other libraries in your project.
Abstract design. Using models such as state machines and datatypes, explore the behavioural design of your program. Make sure to record not only the decisions you made, but the decisions you rejected, along with their rationale.
Architecture and protocol. Design an architecture (server and clients, host and client, or something else) and a protocol for the system's components. Express your protocol as a state machine or grammar, and give the structure of the protocol messages using a grammar or datatype productions.
Usability design. Sketch your user interface and its various screens and dialogs. Use these sketches to explore alternatives and to plan the structure and flow of your interface. Sketching on paper is recommended.
Code design. Design the code structure of your program using module dependency diagrams. Record important design decisions -- in particular all the patterns you chose (see the lecture notes for reminders of all the patterns covered in class) -- and their rationale. Pay particular attention to extensibility, and to making it easy to run automated tests.
Testing strategy. Devise a strategy for testing your system (determining what order you will test components in, how you will derive test cases, what level of coverage you plan to achieve, how you will test the user interface, etc). Justify your strategy with an argument that the level of effort is appropriate for the likely prevalence and location of bugs, and the degree of reliability required.
Implementation. Write code based on your design. Make sure to update the design documents if the design changes; at the very least, you are likely to find additional dependences that you had not anticipated. Make sure to make extensive use of specification annotations, data abstraction and representation invariants.
Testing. Execute your testing strategy, and document the results.
Reflection. Write a brief commentary (e.g. half a page to one page in length) describing what you learned from this experience:
There are three deadlines for this project listed at the top of this document, each with its own deliverables.
For the first deadline:
A design amendment will be out the day after the first deliverable is due.
For the second deadline:
The purpose of the demo is to demonstrate progress, and to help you focus on understanding a critical or high-risk area of the design. It might include, for example, a basic server that sends and receives messages but without a GUI client (see the the hints about telnet). Or you might have a working basic GUI with no server backend but a simple API for connecting to one. Talk to your TA beforehand if you are unsure about what is sufficient.
For the third and final deadline:
The grading breakdown is as follows:
Your grade for implementation depends on correctness, but also on good coding practices and program usability. Impressive submissions may receive bonus points or staff awards.
Each deliverable should be submitted as one PDF in the deliverables folder of your project repository. After each of the first two deliverables, you will meet with your TA during the next lecture period or lab period to review them and plan your next steps. Be prepared to do your demo for your TA at your second meeting. You should bring a printout of your deliverable to these meetings. For your user interface sketches, either scan the files and place them in your PDF document (see resources for a list of scanners on campus), or use a drawing tool.
Communicate with your Team. This is a large project; it is important for you to start early, work together, and resolve issues up-front. Meet regularly. If you split the work into three parts and meet on the last day before the due date(s), you're setting yourself up for disappointment and stress. Make sure you split work in an even fashion, so that you all know what is going on in the project.
Spend your time wisely. This is a large project, and there is a large amount of material to be absorbed just from Swing and Java 2D Graphics, not all of which you will use. Smaller goals of this project are to get you to 1) divide up many tasks among people in ways that make sense, and 2) learn how to skim through a new API and understand it well enough to be able to choose and look for just what you need.
Design models. In the grading of the design documents, we will be looking to see whether you really addressed fundamental issues. A small and focused design model is always better than a large, diffuse one; your aim is to shed light on real problems, not to do mindless documenting of obvious things. A reader can tell when a design model was developed incrementally as the focal point of the design (because it's clear, easy to follow, and addresses interesting questions) and a design model that was hurriedly generated after the fact (because it's usually obscure, misses important issues, and includes boring details). Brief comments on your design models will help the reader understand the role they play and the key decisions you made. Also, the relationship between your design models and code should be very clear, and should be documented using the language of design patterns you have learned.
Designing architecture and protocol. You must also devise a network architecture and a protocol for this project. A client/server architecture is potentially the easiest choice here, but it isn't required.
You should strongly consider using a text-based protocol, which may be easier for testing and debugging.
Services that use plain text protocols — e.g. HTTP or SMTP — can talk to a human just as well as another machine by using a client program that sends and receives characters. Such a client program already exists on almost all operating systems, called telnet. You can run telnet by opening a command prompt and typing telnet hostname port. The lab gives you some experience with using telnet.
Handling multiple users. Your system must be able to handle multiple users connected at the same time. The Friendly server you'll develop in the lab gives you some starting code, but note that Friendly doesn't need its clients to interact or share any state. Your system will certainly need to do that. One reasonable design approach follows the Friendly model (using one thread for reading input from each client) but adds a central state machine representing the state of the server (using one more thread, to which each of the client threads pass messages through a shared queue).
Read the socket documentation referenced in the lab to understand how network sockets operate in Java.
Swing and thread safety. Note that, even though user interfaces are concurrent by nature, Swing is not thread-safe. Recommended reading: Threads and Swing.
Design for testability. To make it possible to write unit tests without having to open socket connections and parse streams of responses, you should design your components so that they can be driven directly by a test driver -- eg, by calling methods, or by putting messages into a queue.
Testing GUIs is particularly challenging. Follow good design practice and separate as much functionality as possible into modules you can test using automated mechanisms. You should maximize the amount of your system you can test with complete independence from any GUI.