Your cart is currently empty!
Introduction…………………………………………………………………………………………………………………………………………….. 1 The Assignment……………………………………………………………………………………………………………………………………… 2 The Direction and Point Types……………………………………………………………………………………………………… 3 The Game Class…………………………………………………………………………………………………………………………………. 3 The Board Class………………………………………………………………………………………………………………………………… 6 The Player Abstract Base Class………………………………………………………………………………………………….. 10 The AwfulPlayer Class………………………………………………………………………………………………………………….. 12 The HumanPlayer Class………………………………………………………………………………………………………………… 12 The MediocrePlayer Class……………………………………………………………………………………………………………. 13 The GoodPlayer Class…………………………………………………………………………………………………………………… 17 Your main() Function…………………………………………………………………………………………………………………….. 17 What We Provide You………………………………………………………………………………………………………………………. 17 Other Requirements……………………………………………………………………………………………………………………………. 18 What…
Introduction…………………………………………………………………………………………………………………………………………….. 1
The Assignment……………………………………………………………………………………………………………………………………… 2
The Direction and Point Types……………………………………………………………………………………………………… 3
The Game Class…………………………………………………………………………………………………………………………………. 3
The Board Class………………………………………………………………………………………………………………………………… 6
The Player Abstract Base Class………………………………………………………………………………………………….. 10
The AwfulPlayer Class………………………………………………………………………………………………………………….. 12
The HumanPlayer Class………………………………………………………………………………………………………………… 12
The MediocrePlayer Class……………………………………………………………………………………………………………. 13
The GoodPlayer Class…………………………………………………………………………………………………………………… 17
Your main() Function…………………………………………………………………………………………………………………….. 17
What We Provide You………………………………………………………………………………………………………………………. 17
Other Requirements……………………………………………………………………………………………………………………………. 18
What You Must Turn In……………………………………………………………………………………………………………………. 18
Introduction
You have been hired to write a computer version of the classic Battleship game. Battleship is a simple game where each player attempts to sink their opponent’s fleet of ships before the opponent sinks theirs.
Here’s how you play it:
1
0123456789
The Assignment
For this assignment, you will have to complete the Battleship game we started building, including the following classes:
2
need to implement most of this class’s member functions. Your Mediocre Player must work exactly as specified later in this specification.
The Direction and Point Types
The file globals.h that we supply defines two types used in many places in the program. A Direction is an orientation for a ship, and a Point is a (row,column) coordinate for a position on the board.
enum Direction {
HORIZONTAL, VERTICAL
};
class Point
{
public:
Point() : r(0), c(0) {}
Point(int rr, int cc) : r(rr), c(cc) {}
int r;
int c;
};
The Game Class
The Game class is used to run a complete game between two players. It also answers queries about game parameters:
class Game
{
public:
Game(int nRows, int nCols);
~Game();
int rows() const;
int cols() const;
bool isValid(Point p) const;
Point randomPoint() const;
bool addShip(int length, char symbol, string name);
3
int nShips() const;
int shipLength(int shipId) const;
char shipSymbol(int shipId) const;
string shipName(int shipId) const;
Player* play(Player* p1, Player* p2, bool shouldPause = true);
};
Game(int nRows, int nCols)
Construct a game with the indicated number of rows and columns, which must not exceed MAXROWS and MAXCOLS, respectively. (Those constants are defined in globals.h.)
int rows() const
Return the number of rows in the game board.
int cols() const
Return the number of columns in the game board.
bool isValid(Point p) const
Return true if and only if the point denotes a position on the game board.
Point randomPoint() const
Return a random point on the game board.
bool addShip(int length, char symbol, string name)
Add a new type of ship to the game. (Later, when play() is called, each player will place one of each type of ship on their board.) The ship has the indicated length, which must be positive and must allow the ship to fit on the board. When the board is displayed, the indicated symbol will be displayed in the positions occupied by that ship; that symbol must be a printable character other than X, o, and . (which are used for other purposes in the display), and must not be the same as for any other ship. The indicated name is what will be used to denote the ship when writing messages. If g is a Game, the function might be called like this:
g.addShip(5, ‘A’, “aircraft carrier”)
If the arguments in a call to addShip satisfies the constraints, the call results in a new ship type being added to the game, and the call returns true. Otherwise, a new ship type is not added, and the call returns false.
4
int nShips() const
Return the number of ship types in the game, which will be the number of times addShip was called returning true. The integers from 0 to nships()−1 will be the ship IDs of the ships in the game, each one corresponding to the ship type added by one of the successful calls to addShip. Although each ship type’s ship ID will be a distinct integer in the range 0 to nShips()-1, it is not required that the first ship added have ship ID 0, the next 1, the next 2, etc. (although that may what naturally happens with your implementation).
int shipLength(int shipId) const
Return the number of positions occupied by the ship whose ID is shipId.
char shipSymbol(int shipID) const
Return the character that, when displaying a board, will be used to represent the ship whose ID is shipId.
string shipName(int shipID) const
Return the string that, when writing messages, will be used to denote the ship whose ID is shipId.
Player* play(Player* p1, Player* p2, bool shouldPause)
This function runs a complete game between the two indicated players, returning a pointer to the player who won the game, or nullptr if some situation occurred that makes it impossible to complete the game (e.g., a player being unable to place the ships on their board). The parameter p1 is a pointer to the player who goes first; p2 is a pointer to the other player.
If the third parameter is true, then after displaying the result of each shot, the function displays a “Press enter to continue: ” prompt and waits for the user to press enter before continuing. This parameter defaults to true if the play function is called with only two arguments. If the parameter is false, no such pause occurs; this is useful when testing the function merely to determine the winner, such as might be done from a script that discards the actual output.
The play function must do the following:
5
the ships because of blocked squares). If a player’s placeShips function returns false, your play function must return nullptr.
You can’t go wrong by having your play function conduct the game the way it does in our sample program.
To ensure that you do not change the interface to the Game class in any way, we will implement that class for you. But don’t get your hopes up that we’re doing any significant work for you here: Our implementation is to simply give Game just one private data member, a pointer to a GameImpl object (which you can define however you want in Game.cpp) The member functions of Game simply delegate their work to functions in GameImpl.1 You still have to do the work of implementing those functions, although we have done some of that work for you. (Examine the last half of Game.cpp to see what we did.)
Other than Game.cpp, no source file that you turn in may contain the name GameImpl. Thus, your other classes must not directly instantiate or even mention GameImpl in their code. They may use the Game class that we provide (which indirectly uses your GameImpl class).
The Board Class
The Board class maintains the board data structure. Here is the required interface that you must implement:
class Board
{
public:
Board(const Game& g);
~Board();
void clear();
void block();
void unblock();
6
bool placeShip(Point topOrLeft, int shipId, Direction dir); bool unplaceShip(Point topOrLeft, int shipId, Direction dir); void display(bool shotsOnly) const;
bool attack(Point p, bool& shotHit, bool& shipDestroyed, int& shipId); bool allShipsDestroyed() const;
};
Board(const Game& g)
Initialize a board. The parameter g refers to the game the board is being used in. Board member functions that need to know the number of rows or columns or the characteristics of ships will presumably find out from the game object the board was constructed with.
void clear()
This function clears the board so it is empty, ready to be populated with ships.
void block()
This function blocks about half the positions on the board. This function will be used only by the MediocrePlayer when placing ships on the board at the start of play. If a position is blocked, then that player may not place a ship that occupies that location.
void unblock()
This function unblocks all the blocked positions on the board. This function will be used only by the MediocrePlayer, after placing ships on the board, but before the start of play.
bool placeShip(Point topOrLeft, int shipId, Direction dir)
This function attempts to place the specified ship at the specified coordinate, in the specified direction. The parameter topOrLeft specifies the topmost segment of the ship if dir is VERTICAL, or the leftmost segment if dir is HORIZONTAL. The parameter shipId is the ship ID number. This function returns false if the ship cannot be placed because:
7
If this function returns false, then the board must remain unchanged (i.e. no part of the ship may remain on the board upon failure). If this function successfully places the ship, the board is updated to reflect that, and the function returns true.
bool unplaceShip(Point topOrLeft, int shipId, Direction dir)
This function attempts to remove the specified ship from the board, so the positions it occupied may be used to place other ships. The parameters are the same as for placeShip. This function returns false if the ship cannot be removed because:
If this function returns false, then the board must remain unchanged (i.e. no part of the ship may be removed upon failure). If this function successfully removes the ship, the board is updated to reflect that, and the function returns true.
void display(bool shotsOnly) const
This function displays the board, using the following format:
8
Here’s an example with shotsOnly being false:
0123456789
2 | .o….. | P.. |
3 | ………. |
8 | ..X… | BBBB |
9 | ..o……. |
Here’s that same board with shotsOnly being true:
0123456789
6 | ..X… | o… |
7 | ..X……. | |
8 | ..X……. | |
9 | ..o……. |
bool attack(Point p, bool& shotHit, bool& shipDestroyed, int& shipId)
This function is used to submit an attack against the board. The function must return false if the attack is invalid (the attack point is outside of the board area, or an attack is made on a previously attacked location). The function returns true if the attack is valid, regardless of whether or not any ship is damaged.
If any undamaged segment of a ship is at position p on the board, then the shotHit parameter must be set to true, and the segment must henceforth be considered a damaged segment. Otherwise the shotHit parameter must be set to false.
If this specific attack destroyed the last undamaged segment of a ship, then the shipDestroyed parameter must be set to true and the shipId parameter must be set to the ship ID of the ship that was destroyed; otherwise the shipDestroyed parameter must be set to false and shipId must be left unchanged.
It’s up to you whether to set to some value or leave unchanged:
9
bool allShipsDestroyed() const
This function returns true if all ships have been completely destroyed on the current board and false otherwise. (If this is true, it means that the player who was attacking that board has won the game.)
As with the Game class, the real work will be implementing the auxiliary class BoardImpl in Board.cpp. Other than Board.cpp, no source file that you turn in may contain the name BoardImpl. Thus, your other classes must not directly instantiate or even mention BoardImpl in their code. They may use the Board class that we provide (which indirectly uses your BoardImpl class).
The Player Abstract Base Class
The Player abstract base class specifies the interface for all players. We have implemented this class for you.
class Player
{
public:
Player(string nm, const Game& g);
virtual ~Player();
string name() const;
const Game& game() const;
virtual bool isHuman() const;
virtual bool placeShips(Board& b) = 0;
virtual Point recommendAttack() = 0;
virtual void recordAttackResult(Point p, bool validShot, bool shotHit,
bool shipDestroyed, int shipId) = 0;
virtual void recordAttackByOpponent(Point p) = 0;
};
Player* createPlayer(string type, string nm, const Game& g);
Player(string nm, const Game& g)
Initialize a player whose name is nm. The parameter g refers to the game the player is being used in.
string name() const
Return the name of the player.
10
const Game& game() const
Return a constant reference to the game the player is being used in. (Derived classes can use this to find out the number of ships in the game, for example.)
bool isHuman() const
Return true if the player is a human. (This affects how an opponent’s board will be displayed.)
bool placeShips(Board& b)
This function must be implemented in concrete derived player classes. It must implement the logic required to place the ships on the board before game play begins. It returns true if all ships could be placed, and false otherwise (e.g., because the game parameters are such that there is no configuration of ships that will fit, or because a MediocrePlayer is unable to place all of the ships after 50 tries).
Point recommendAttack()
This function must be implemented in concrete derived player classes. It must return a point that indicates the position on the opponent’s board that the player would like to attack next.
void recordAttackResult(Point p, bool validShot, bool shotHit,
bool shipDestroyed, int shipId)
This function must be implemented in concrete derived player classes. Game::play() must call this function after an attack is made on an opponent’s board to report the result of the attack to the attacking player. The position p is where the attack was made. The parameter validShot will be true if the attack was valid, or false if it was invalid (i.e., p is outside of the board area, or is a position that had already been attacked previously). If validShot is true, then shotHit is true if the attack hit a ship segment, and false otherwise. If shotHit is true, then shipDestroyed is true if that was the last undamaged segment of the ship that was hit, and false otherwise. If shipDestroyed is true, then shipId is the ship ID of the ship that was destroyed. You can not assume anything about the value of
This function is intended to let an intelligent non-human player update its data members in a way that will let the next call of recommendAttack make a good choice.
11
void recordAttackByOpponent(Point p)
This function must be implemented in concrete derived player classes. Game::play() must call this function when an attack is made on this player’s board. The position p is where the attack was made. The player may very well have this function do nothing. However, an intelligent non-human player might want to keep track of an opponent’s attacks and adjust its own attack strategy accordingly. For example, the player might notice the opponent is attacking in a certain pattern, use that to predict how far from winning the opponent is, and play differently depending on whether or not an opponent is far from or close to winning.
Player* createPlayer(string type, string nm, const Game& g)
This is not a member function of any class. It is a so-called factory function that lets you create a player without the compiler’s needing to have seen a class declaration for that player at the point where you create that player. The parameter nm is the name of the player and g is the game the player is being used in. The first parameter determines the kind of concrete player to be created:
“awful” for an AwfulPlayer
“human” for a HumanPlayer
“mediocre” for a MediocrePlayer
“good” for a GoodPlayer
The function returns nullptr if the type string is not one of those four. Otherwise, it returns a pointer to a dynamically allocated object of the indicated type. It is the caller’s responsibility to ultimately delete the object.
All concrete classes derived from Player must have a constructor that takes a string for the player’s name and a constant reference to a Game, since that what createPlayer assumes.
Other than Player.cpp, no source file that you turn in may contain the names AwfulPlayer, HumanPlayer, MediocrePlayer, or GoodPlayer.
The AwfulPlayer Class
This is a concrete class derived from Player, for which we have provided the code. It places ships in the same dumb way every time, and recommends attacks in a systematic pattern, paying no attention to the effect of previous shots.
The HumanPlayer Class
This is a concrete class derived from Player. It places ships and recommends attacks based on user input. The isHuman function must return true, so that Game’s play function can ensure that a human player doesn’t get to see where the opponent’s ships are during play. The placeShips and recommendAttack functions must prompt the user for
12
where to place the ships and where to attack, respectively, in the manner of the posted sample program. The recordAttackResult and recordAttackByOpponent probably need not do anything.
The MediocrePlayer Class
This is a concrete class derived from Player class that implements an artificially intelligent mediocre Battleship player. You are required to use particular algorithms for placeShips and recommendAttack/recordAttackResult/recordAttackByOpponent.
bool placeShips(Board& b)
For a MediocrePlayer, this function must place the ships on the board using the following algorithm:
(Hint: placeShips itself will probably not be recursive. For step 2 above, though, it may well call an auxiliary function that will be recursive.)
Here’s an example of the backtracking algorithm. Suppose we wish to place three ships into the board below, a 4-segment battleship, a 3-segment submarine, and a 2-segment patrol boat. (Note that # represents a blocked position; the actual block() function will not block this high a percentage of the squares):
13
0123456789
If our algorithm attempted to place the battleship first vertically at (1,3), our board will look like this:
0123456789
Next our algorithm would have to place the submarine on the board. It fits vertically at (2,5):
0123456789
However, as you can see, there is no room left to place the patrol boat, so the placement algorithm must backtrack, removing the submarine and then attempting to place it elsewhere. But it won’t fit elsewhere, so the algorithm backtracks to the battleship placement; it must remove the battleship and place it somewhere else. It will fit horizontally at (4,2):
14
0123456789
Trying the submarine again, we find it fits vertically at (1,3). Finally, the algorithm would place the patrol boat vertically at (2,5):
0123456789
void recordAttackByOpponent(Point p)
For a MediocrePlayer, this function does nothing. What attacks an opponent has made do not affect a MediocrePlayer’s attack decisions.
Point recommendAttack()
void recordAttackResult(Point p, bool validShot, bool shotHit,
bool shipDestroyed, int shipId)
For a MediocrePlayer, these functions work together to implement the following algorithm:
15
0123456789
Subsequent shots in state 2 must be to the positions denoted with a + below:
0123456789
By attacking this set of coordinates, the mediocre player is guaranteed to eventually sink the ship that was hit in state 1 if that ship’s length is 5 or less. As it turns out, it is possible that the mediocre player may also sink other ships inadvertently with this algorithm, but that’s OK.
16
If the game has ships of length 6 or more, it’s possible that every position no more than 4 steps from (r,c) has been previously chosen. In that case, switch to state 1 and use its selection algorithm.
There are three possible outcomes from the recommended attack:
The GoodPlayer Class
Here’s your chance to shine. This is a concrete class derived from Player class that implements an artificially intelligent Battleship player. You may use any algorithms you like to place your ships and to attack the other player, but a call to recommendAttack, then Board::attack, then recordAttackResult must not take more than 5 seconds. (The FAQ addresses the issue of how to limit the time.) See if a GoodPlayer object can beat a MediocrePlayer object most of the time.
Your main() Function
Your main routine must be in a file that you will not turn in. It can do whatever you like.
What We Provide You
We provide you with the following files:
main.cpp a sample main routine
globals.h pervasive constants and types and a function for generating random
integers
Board.h the declaration of the Board class
Player.h the declaration of the Player abstract base class and the
implementations of some of its member functions
Game.h the declaration of the Game class.
Board.cpp a skeleton of the implementation of the board functionality
Player.cpp the declaration and implementation of AwfulPlayer, and placeholders for the declarations and implementations of HumanPlayer, MediocrePlayer, and GoodPlayer. Also, the implementation of createPlayer
Game.cpp a skeleton of the implementation of the game functionality
17
Other Requirements
You must not make any changes whatsoever to the .h files that we provide you. You will not be turning in those files; we will test your code using our versions of those files, to ensure you didn’t sneak in any changes to the required interfaces.
If you write any helper functions, put then in one of the files you will be turning in:
Board.cpp, Player.cpp, or Game.cpp.
Functions that you write must not write to cout except for the following member functions and helper functions you write that they might call: GameImpl::play, BoardImpl::display, and any member functions of HumanPlayer. Functions you write may freely write to cerr. Functions that you write must not read from cin except for the following member functions and helper functions you write that they might call: GameImpl::play and any member functions of HumanPlayer.
Subject to the constraints we imposed (e.g., no changes to the public interface of Game, no mention of GameImpl in any file other than Game.cpp), you’re otherwise pretty much free to do whatever you want in Game.cpp as long as it’s related to the support of only the Game implementation; for example, you may add members (even public ones) to the GameImpl class (but not the Game class, of course) and you may add non-member support functions. Similar freedom applies to Board, BoardImpl, and Board.cpp, and also to Player, HumanPlayer, MediocrePlayer, GoodPlayer, and Player.cpp.
A program consisting of the main.cpp and the .h files that we provided you, along with the Board.cpp, Player.cpp, and Game.cpp files that you turn in, must build successfully under both g32 and either Visual C++ or clang++.
What You Must Turn In
You can still get a good amount of partial credit if you implement most of the project. We will test your Board.cpp in a framework containing our correctly implemented Game.cpp, so that even if your Game.cpp is incorrect, you can earn points for a correctly implemented Board.cpp. Similarly, we will test your Player.cpp in a framework containing our correctly implemented Board.cpp and Game.cpp, and we will test your Game.cpp in a framework containing our correctly implemented Board.cpp and Player.cpp.
You will turn in a zip file consisting of four files:
18
19