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
Project Modifications
- Add a print for the Computer's board.
- Add a print for which square that was attacked by each player.
- Modify user-defined objects to be allocated dynamically.
- Implement the Big Three for all required classes.
- Implement the insertion and extraction operators for the Board class.
- Add a Queue class to improve the Computer's intelligence.
Functional Description
Your application must function in the same way as described in Project 2 with
some minor changes, within the game-playing portion, play proceeds as follows:
- Loop as long as there is no winner
- Print the current player's tracking board (yes, you will print the
computer's board on its turn)
- Let the player take a turn, repeat request for a board position until a
valid position is given by the player.
- Report which square was attacked
- Report whether it was a hit or miss
- Record the result
- Report who the winner of the game is
Artificial Intelligence
In order to make the game more exciting, we need to add a little
intelligence to the computer component. One of the basic strategies of
BattleShip is that once you have detected a hit, you should try the squares
around that square. We will use a Queue (FIFO: first in, first out) in order
to select and store a sequence of "guesses" for the computer. Using a Queue
to represent the set of "next guesses" is a Breadth-first searching technique
that is common to basic Artificial Intelligence systems.
Queue's have two basic operations:
enqueue - add an item to the back of the queue and
dequeue - remove an item from the front of the queue.
When the computer gets a hit, it must enqueue the 4 surrounding squares onto
the queue. It must enqueue them in the following order: above, right, below,
left. If one or more of these four squares have already been guessed, they
must be enqueued anyway (we will take care of removing them later). If one
or more of these four squares does not exist (outside the board), it must
NOT be enqueued.
When it is the computer's turn, it must first look to see if there are any
squares currently listed on the Queue, if there are, it must remove them one
at a time until a square is found that has not previously been guessed. If
no such squares are found, and the Queue is exhausted, then the Computer should
default to the "random" strategy that it employed for the previous project.
Design and Implementation Requirements
Classes
You are required to keep the Human, Computer and Board classes from Project 2.
However, you may make any changes you desire or are necessary to support the
additional requirements of this project.
You may also find it useful to introduce small "helper" classes to
represent a square of the board that was selected or other small tasks. These
classes need not implement the Big Three nor be dynamically allocated.
You are also required to add a Queue class that relies upon a linked structure
to help the Computer determine which square to attack next. Queue objects
need not be dynamically allocated, however, their internal structure will be.
Queue Class
The basic design of a Queue class supports the following functionality:
- Enqueue - add an item to the back of the Queue
- Dequeue - remove an item from the front of the Queue
- Is Empty - determines if there are any more items in the Queue
You will most likely need to implement additional functions, operators, etc. in
order to complete the Queue class. Since the Queue will have dynamic memory,
you are also required to include the Big Three.
You are required to implement your Queue as a dynamically linked structure
(much like the Linked List you studied in 201). Your Queue class will need a
smaller "helper" class that represents a single Item (or Node) in the Queue.
Your Queue class will also require a head pointer that points to the first
Item in the Queue and a tail pointer that points to the last Item in the Queue.
Each Item in the Queue will need a pointer to the next Item in the Queue.
The last Item in the Queue should have its 'next' pointer set to NULL. If no
Items are in the Queue, then the head and tail pointers must be NULL. Below
is an illustration of what several Queues might look like.
To assist in the debugging of your Queue class, you are encouraged to implement
the overloaded insertion operator - so that you can print all of the Items in
the Queue.
In designing and implementing your Queue class, attempt to keep it as general
as possible - we may reuse this in a future project (hint, hint).
Overloaded Operators
All overloaded operators must operate on OBJECTS of each class, NOT on pointers
to an object. You should remember to dereference pointers
before attempting to use overloaded operators on them.
Insertion Operator
You are required to overload the insertion operator for your Board
class. You should take advantage of any code you have already
written and reuse it. Do not duplicate code. Replace any calls to existing
"Print" (or similar) functions with calls using the insertion operator. You
may choose to delete any functions that accomplish the same task.
Extraction Operator
You are also required to overload the extraction operator for the Board class.
Again, reuse any existing code. Do not duplicate code. You may
choose to delete any existing methods that accomplish the same task. The
stream passed into the extraction operator should be an open file.
Dynamic Memory
You are required to modify your existing system to use dynamic memory in the
creation and maintanence of user-defined objects. All instances of Humans,
Computers, and Boards must be created dynamically.
Each of these classes must have the Big Three implemented and used
appropriately. All instances of dynamic memory in these classes should be
properly allocated and deallocated in the Big Three. Even if your class does
not allocate dynamic memory, you must overload the Big Three.
You will need this component working for Project 4.
Example Output
Updated!
Here is an example of what your output might look like. You need not adhere to
this format exactly, but it gives you a good idea of what we are looking for.
Feel free to add labels to each board to differentiate the two or use your own
wording for interaction with the user.
Welcome to Battleship!
The goal of this game is to completely destroy your opponent's
ships. By alternating turns, you will be able to attack squares
on your opponent's board. If you hit a ship, the system will
report this. If you miss, the system will report this.
0 1 2 3 4 5 6 7 8 9
A o o o o o o o o o o
B o o o o o o o o o o
C o o o o o o o o o o
D o o o o o o o o o o
E o o o o o o o o o o
F o o o o o o o o o o
G o o o o o o o o o o
H o o o o o o o o o o
I o o o o o o o o o o
J o o o o o o o o o o
The Computer has missed at (G, 4)!
0 1 2 3 4 5 6 7 8 9
A o o o o o o o o o o
B o o o o o o o o o o
C o o o o o o o o o o
D o o o o o o o o o o
E o o o o o o o o o o
F o o o o o o o o o o
G o o o o o o o o o o
H o o o o o o o o o o
I o o o o o o o o o o
J o o o o o o o o o o
Where would you like to attack? (row column) (ex: A 1)
A 1
You have missed at (A, 1)!
0 1 2 3 4 5 6 7 8 9
A o o o o o o o o o o
B o o o o o o o o o o
C o o o o o o o o o o
D o o o o o o o o o o
E o o o o o o o o o o
F o o o o o o o o o o
G o o o o M o o o o o
H o o o o o o o o o o
I o o o o o o o o o o
J o o o o o o o o o o
The Computer has missed at (D, 4)!
0 1 2 3 4 5 6 7 8 9
A o M o o o o o o o o
B o o o o o o o o o o
C o o o o o o o o o o
D o o o o o o o o o o
E o o o o o o o o o o
F o o o o o o o o o o
G o o o o o o o o o o
H o o o o o o o o o o
I o o o o o o o o o o
J o o o o o o o o o o
Where would you like to attack? (row column) (ex: A 1)
A 2
You have hit a ship at (A, 2)!
0 1 2 3 4 5 6 7 8 9
A o o o o o o o o o o
B o o o o o o o o o o
C o o o o o o o o o o
D o o o o M o o o o o
E o o o o o o o o o o
F o o o o o o o o o o
G o o o o M o o o o o
H o o o o o o o o o o
I o o o o o o o o o o
J o o o o o o o o o o
The Computer has missed at (J, 8)!
0 1 2 3 4 5 6 7 8 9
A o M H o o o o o o o
B o o o o o o o o o o
C o o o o o o o o o o
D o o o o o o o o o o
E o o o o o o o o o o
F o o o o o o o o o o
G o o o o o o o o o o
H o o o o o o o o o o
I o o o o o o o o o o
J o o o o o o o o o o
Where would you like to attack? (row column) (ex: A 1)
B 2
You have hit a ship at (B, 2)!
[Cut for length]
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 (this is neither exhaustive nor a
requirement, simply a recommendation):
- Add the overloaded insertion operators to Board class
- Add the overloaded extraction operator to the Board class.
- Change the creation of the Human and Computer to be dynamically allocated.
- Add a constructor and the Big Three to the Human class.
- Add a constructor and the Big Three to the Computer class.
- Add a constructor and the Big Three to the Board class.
- Modify the Computer class to store the "nearest" squares from a hit
- Modify the Computer class to try a single item from the Queue
- Modify the Computer class to go through the Queue, testing squares
until it finds one that has not yet been guessed
- Flesh out any other dynamic memory that needs to be completed.
- Test your application between each change! Take it slow. Get everything
else working before you try to implement the dynamic memory.
- Submit a copy of your application BEFORE you start working on the
dynamic memory.
- Submit a copy of your application BEFORE adding the dynamic links (but
after creating the Big Three for all three classes).
- TEST your program thoroughly - the makefile provided has a 'make test'
target that you can use to ensure that your application will work with our
test suite. HOWEVER, you need to test your application using other boards that
you create yourself. 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.
- This project is approximately 150 - 250 lines of code... don't
procrastinate.
- Ms Wortman's public directory for this project is
/afs/umbc.edu/users/d/a/dana3/pub/CMSC202/p3.
- 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 p3design.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 Proj3
at the Linux prompt.
This will compile all necessary .cpp files and create the
executable named Proj3.
The make utility can also be used for compiling a single file without
linking. For example, to compile Proj3.cpp, type make Proj3.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, Proj3
executable and backup files created by the editor. More information about
these commands can be found at the bottom of the makefile.
If you are building your own 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++.
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.
- All unmet function pre-conditions are handled.
- Classes demonstrate high cohesion.
- Classes demonstrate low coupling.
- Classes demonstrate appropriate distribution of tasks.
- All classes have the Big Three implemented.
- All dynamic memory is allocated and deallocated appropriately.
- The Board class has an overloaded insertion operator.
- The Board class has an overloaded extraction operator.
- All project requirements are met.
15% - Coding Standards
Your code adheres to the