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

• 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

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 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

• 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 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.

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

Insertion Operator

Extraction Operator

Dynamic Memory

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

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.

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

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

• 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