General Project Description
You have just recently started an internship with GamesCo - a local interactive
game company and your supervisor wants you to create an electronic version of
the old BattleShip game. You will be responsible for creating the interface
that users will see, all of the game logic, a networking component that will
allow users to play each other head-to-head, and an artificial-intelligence
component that will allow users to play the computer.
Each phase of this project will add on a different component so that by the
end of the five phases, you will have a completely operational BattleShips
game.
Project Description
In this final iteration of the BattleShip system, you will be required to use
templates and exceptions to enhance your code to work within a variety of
applications and to more elegantly handle errors.
In addition to the BattleShip game, your boss has requested you to generate a
"Tournament Application" that will schedule a collection of players to compete
against one another in a fair way. The goal for the application is to
schedule games approximately equally across all of the players, obviously this
is impossible, but your boss believes that you can get close by using a Queue
to schedule the matches.
Since you already developed a Queue class for another part of the project, you
would like to reuse this code by modifying the Queue class to support
templates so that the same class can be used in the BattleShip and
Tournament applications.
BattleShip!
BattleShip Functional Description
The BattleShip game must function exactly as specified in Project 4.
BattleShip Design Requirements
Your BattleShip application must support Exceptions and Templates.
Templates
You will need to modify your Queue and Node classes to support templates. Your
Queue objects will be defined similarly to the corresponding STL class, in
example:
<![CDATA[
Queue<int> q1;
Queue<Square> q2;
Queue<string> q3;
Queue<double> q4;
Queue<Stuff> q5;
]]>
Your Queue class will work with both the BattleShip application and the
Tournament application. Your Queue class must throw exceptions when error
conditions are detected.
Exceptions
You will need to modify your application to use Exceptions to handle all
errors. Your exceptions should be named for the error that they represent
and not the location of the error. You must throw and catch each exception at
the most appropriate locations (sometimes this will be main, sometimes it will
be a class or other function). Don't forget to account for miscellaneous STL
exceptions like bad_alloc and out_of_bounds (you need not specify the type when
catching these, but you must catch them). Your current strategies for error
handling (returning false to indicate an error, alerting the user, exiting
the program, etc.) should all be modified to throw an exception. Exceptions
should be handled in the smallest scope that is reasonable - not all of them
will be passed to the main() function.
You may put all of your Exception classes into a single pair of
Exception.h and Exception.cpp files.
Tournament!
Tournament Functional Description
The Tournament Scheduler must function according to the following algorithm:
- Enqueue player userIDs from a file
- While there is more than 1 player in the queue
- Dequeue the first two players in the Queue
- Select a winner for the match
- Print the winner's userID
- Print the loser's userID
- Enqueue the winner
- Print out the userID of the "Tournament Champion" (this will be the last
user in the Queue)
- Print out the number of games played per player (in the same order the
names were listed in the file)
- Print the average number of games played (2 decimals of precision)
- Print the median number of games played
- Print the total number of games played
Your output must be "reasonably" formatted including appropriate spacing and
tabular alignment (hint: remember setw(), left and right?)
Selecting a Winner
As your boss is not requiring you to actually run the tournament, you should
simply compare the two player's userID and whichever is "less than" (using the
standard ASCII encoding) should be declared as the winner of the match.
Tournament Example Input File
Your tournament application requires a single file with a series of userIDs
listed. These will be single "words" with no spaces within a userID and any
alphabetic character or number is acceptable. Each userID will be on a line
all by itself. Here is an example of a tournament player list:
<![CDATA[
fred6
john7
mary56
hgo6
oemje10
oweng9
yu90
]]>
Tournament Example Output
Below is an example of what the output might be for the above input file.
<![CDATA[
fred6 won against john7
hgo6 won against mary56
oemje10 won against oweng9
fred6 won against yu90
hgo6 won against oemje10
fred6 won against hgo6
fred6 is the Tournament Champion!
fred6 played 3 games
john7 played 1 game
mary56 played 1 game
hgo6 played 3 games
oemje10 played 2 games
oweng9 played 1 game
yu90 played 1 game
Average games played: 1.71
Median games played: 1
Total games played: 6
]]>
Tournament Guarantees
You may assume that the command line will have a single argument that is
an existing filename.
You may assume that the file is correctly formatted and
the userIDs are perfectly valid.
You need not do ANY input-error checking for this application.
Running your Tournament
Modify your makefile to build both the Proj5 and a 'Tourney' application
(you must name it exactly 'Tourney'). A single make command (make Proj5) must
make both applications.
To run your Tourney application, simply provide it with a single command line
parameter that is the name of the userID file:
<![CDATA[
Tourney users.txt
]]>
Tournament Design Requirements
Your Tournament application must use a templated Queue (that you have written!)
to Enqueue and Dequeue players during the Tournament. This must be the
same class that is used by the BattleShip Application. Your application must
handle exceptions from the Queue class, but need not throw its own exceptions.
Extra Credit
You can implement neither, one or both of the extra credit components.
Stack vs. Queue (10 pts)
Even though your boss requires you to use a Queue for the Tournament
application, you are interested on how the results might change if a Stack
was used instead. Implement a templated Stack class (LIFO - last in, first
out) to support the Tournament application. As before, simply add a second
command-line parameter to the Tournament application to determine which
class to use (STACK or QUEUE). Hint: to simplify your coding, think about
how you can create a templated function to handle the Tournament play without
knowing whether a Stack or Queue is being used. You may consider using the
same method names for both the Stack and Queue classes (even though the actions
are different - another form of polymorphism!).
You must develop a test-suite comparing and contrasting the performance of the
Stack-based and Queue-based Tournaments. What differenced did you see? How
do these differences help you understand a Queue or a Stack better? Is there
a significant difference with different numbers of players? What about when
there are only a few players? What about when there are a large number of
players?
In a README file for the grader,
develop an argument for which strategy you believe is best (Stack vs. Queue).
Support your argument with a detailed analysis of the performance of each
strategy. Discuss your analysis, pointing out how it supports your argument.
Discuss any possible rebuttals to your argument. Discuss your testing strategy
and clearly describe how to run your tests (using an automated test-suite).
Submit your README file and any files needed to run your test-suite.
To run your Stack or Queue application:
<![CDATA[
Tourney names.txt STACK
Tourney names.txt QUEUE
]]>
Queue Iterators (10 pts)
Using what you know about iterators (basically, they are "fancy" pointers),
implement an Iterator class that works with your templated Queue. At minimum,
your iterators and Queue class must support the following:
Queue
- begin() - returns an iterator to the first element in the Queue
- end() - returns an iterator past the last element in the Queue
Iterator
- ++iterator [prefix] - moves the iterator one item toward the tail of the
Queue
- --iterator [prefix] - moves the iterator one item toward the head of the
Queue
[hint: this one is tricky...you may need to modify the Node class to support
it more efficiently]
- *iterator - dereferences the iterator, returning the data pointed to by
the iterator (not the Node pointed to by the iterator) [hint: this one
is pretty tricky, check the following link for information on overloading the
pointer dereferencing operator: Dereference vs Conversion [PDF]
- != operator - returns true if two iterators point to
different items (you may optionally want to implement the ==operator as well)
The following is an example of code that uses the above operations to print
all of the items in the Queue:
<![CDATA[
Queue<int> numbers;
// code cut: store some integers in the Queue...
for (Iterator iter = numbers.begin(); iter != numbers.end(); ++iter)
{
cout << *iter << endl;
}
]]>
Create a third application named 'Iters' (again, the single Proj5 target must
make this executable as well) that uses and thoroughly tests each of these
operators to accept strings from a user, store them in the Queue, print
the Queue in order and then print the Queue in reverse order.
You may safely assume that anything the
user enters is able to be stored in a c++ string and the extraction operator
is sufficient. You need not do any input-error checking in this application.
You need not support exceptions in any way in this application. You must use
the templated Queue class for this application. Submit this
application file and any other files required to run the application.
Your application must accept a single command-line parameter that represents
the file with some strings in it. An example input file might be:
<![CDATA[
adosifnoiwenfw
oweifnwe
fw
wre
2
3t
]]>
The output your application should produce for the above list:
<![CDATA[
IN ORDER:
adosifnoiwenfw
oweifnwe
fw
wre
2
3t
REVERSED:
3t
2
wre
fw
oweifnwe
adosifnoiwenfw
]]>
To run your application:
<![CDATA[
Iters words.txt
]]>
General Tips
- There are several BIG changes that you will need to make, I would recommend
starting small and then implementing the changes one by one. I would also
recommend doing them in the following order (although, depending on your
design you may want to reorder parts of this):
- Modify the makefile to work for your Proj5 files.
- Every time you add a class - modify the makefile to include a rule to
build and compile that class appropriately.
- Determine which exception classes you will need.
- Introduce a single exception class, converting every error of that type
into a thrown exception.
- Compile and Test.
- Add an additional exception class. [repeat as needed]
- Compile and Test. [repeat as needed]
- Catch exceptions in appropriate places
- Compile and Test.
- Convert the Node class to have templates based on whatever object you
are storing in your Queue, so within your Queue class you will have things
like Node<Square>* m_head.
- Compile and Test.
- Convert the Queue class to use templates. This will require changing
other functions/methods/classes as necessary to use Queue<Square>
m_queue (or whatever your data-type is). Your Queue class will now
pass the templated type to the node, so you should have things like
Node<T>* m_head in your Queue class.
- Compile and Test.
- Implement the Tournament application using your newly templated Queue
class.
- Compile and Test.
- Once everything else is done, then try the extra credit. The first one
is probably easiest (especially if you implemented the Stack from the last
project).
- TEST your program thoroughly!!!
- Be sure to examine the guarantees closely and be sure
that your project handles all of the "bad" cases.
- Because your program will be tested using Unix redirection, DO NOT prompt
for any input not specified in the project description.
- Use incremental development, develop one function at a time, write code
that will thoroughly test it, run and test it, then move on to another function.
Don't be afraid to write testing code that you will eventually get rid of.
- I often find it useful to put "DEBUG" at the beginning of all of my
"testing" print statements - this helps me find them later using 'grep DEBUG'
[under linux].
- This project is approximately 200 - 300 lines of code... don't
procrastinate.
- Ms Wortman's public directory for this project is
/afs/umbc.edu/users/d/a/dana3/pub/CMSC202/p5.
- Do not cheat, you will be caught. Do not look at another student's code -
it is very tempting to "borrow" an algorithm. Do not show your code to
another student. Use the Tutors, TA's, and Instructors.
- Check the discussion board before emailing a TA or Instructor - your
question has probably already been answered.
Project Design Assignment
Your project design document for this project must be named p5design.txt.
Be sure to read the
Project Makefile
The "make" utility is used to help control projects with large numbers of files.
It consists of targets, rules, and dependencies. You will be learning about
make files in lab. For this project, the makefile will be provided for
you. You will be responsible for providing makefiles for all future projects.
Copy the file makefile from Ms. Wortman's public directory to your
directory.
When you want to compile and link your program, simply type
the command make or make Proj5
at the Linux prompt.
This will compile all necessary .cpp files and create the
executable named Proj5.
The make utility can also be used for compiling a single file without
linking. For example, to compile Proj5.cpp, type make Proj5.o.
In addition to compiling and linking your files, make can be used
for maintaining your directory. Typing make clean will remove any
extraneous files in your directory, such as .o files and core files.
Typing make cleanest will remove all .o files, core files, Proj5
executable and backup files created by the editor. More information about
these commands can be found at the bottom of the makefile.
You MUST use the /usr/local/bin/g++
compiler to compile and build each file. Do not depend on setting your default
compiler to be this compiler, the grader may use a different compiler. There
are two compilers on the GL systems, and you are required to use the one
located at /usr/local/bin/g++. Also, you MUST be sure to use the same compiler
for compiling ALL of your files - different compilers make different .o files
and they will NOT play well together.
Grading
The grade for this project will be broken down as follows. A more detailed
breakdown will be provided in the grade form you receive
with your project grade.
85% - Correctness
This list may not be comprehensive, but everything on this list will be
verified by the graders.
- Your project produces all required output.
- The output produced is correct.
- The output is in an acceptable format.
- Your program follows good top-down design principles.
- All function parameters are passed using the appropriate method.
- const is used wherever appropriate.
- All unmet function pre-conditions are handled.
- Classes demonstrate high cohesion.
- Classes demonstrate low coupling.
- Classes demonstrate appropriate distribution of tasks.
- You have used templates to support the new functionality.
- You have notified calling code of all errors by using Exceptions.
- All project requirements are met.
15% - Coding Standards
Your code adheres to the
