in c++ programming language
Evil Battleship Assignment written and developed by Varick Erickson, CSU East Bay, November 2019 Introduction Battleship is a two player game dating back to WWI. Originally this was a pencil and paper game, but Milton Bradley released as a board game in 1967. The following are figures from the original game instructions[1]. Each player has two 10×10 grid as shown above. The target grid is used to record previous shots made against the other. The ocean grid is used to secretly position ships and record how many hits each ship has received. Ships are placed on the grid at right angles. Ships cannot be placed diagonally. At each turn, a player chooses a location to hit. If the guessed coordinate contains a ship, then opponent must announce that a ship has been hit. Otherwise, the opponent states the attempt was a miss. Evil Battleship Page 1 Sneaky Ship Strategy In the official rules, once you position your ships, the ship positions are fixed and cannot be moved. However, for this implementation, we are going to be sneaky and move ships around as the oppo- nent makes guesses. The idea behind evil battleship is to continually move the ships out of harms way. Let’s consider a simple 5×5 grid. Suppose the opponent gave the coordinate (A, 1) as the opening move: 1 2 3 4 5 E D C B A Our goal is to figure out if there is a configuration such that the ships can still be placed on the board. In this case, there is plenty of open spots available. Here is one possible configuration: 1 2 3 4 5 E D C B A Evil Battleship Page 2 Suppose the opponent chooses (B,2) next. Note that since (A,1) has been used, our potential ship placement can’t use this coordinate. However, there is still enough space to find a possible configuration: 1 2 3 4 5 E D C B A As you may notice, the more misses there are, the harder it is to find a valid placement for the ships. Suppose the opponent has guessed (A, 1), (B, 2), (C, 3), and (D, 4). Now suppose the opponent now guesses (E, 5). Notice there is no place where the carrier can be placed (there is no row or column that contains at least 5 empty spots). In this case, we have to admit to a hit: Carrier cannot be placed if E5 a miss 1 2 3 4 5 E D C B A Forced to admit E5 a hit 1 2 3 4 5 E D C B A Evil Battleship Page 3 However, admitting to a hit still allows for quite a bit of flexibility. Suppose we have the following configuration: 1 2 3 4 5 E D C B A There are multiple ways we could place the ships that account for this hit. 1 2 3 4 5 E D C B A 1 2 3 4 5 E D C B A In the example above, we show that we don’t necessarily have to commit a particular ship to a hit. The left board shows the Carrier receiving the hit. The right board shows the Battleship receiving the hit. In fact, we can treat any "hit" location as a free space where a ship can be placed. Again, as long as we can find a place for the ships to be placed, we don’t have to actually assign a ship to be hit. Evil Battleship Page 4 The only time we actually have to admit a ship has been sunk is if all the grid positions of a ship position has been marked as hit. Suppose we have the following: 1 2 3 4 5 E D C B A As you can see, the only place the Patrol boat fits is the at the coordinates (A, 3)-(B, 3). In this case, we admit that the Patrol ship has been sunk. From this point onward, we permanently place the Patrol ship at this position and these spots can no longer be used as potential locations for placing ships. 1 2 3 4 5 E D C B A Evil Battleship Page 5 Greedy Ship Placement Algorithm A greedy algorithm tries to make an optimal choice at every opportunity. For ship placement, we will always try to place the ships from largest to smallest. 1. Carrier 2. Battleship 3. Submarine 4. Destroyer 5. Patrol The following are the basics of the greedy ship placement algorithm: Temporarily mark the current guess location as a "Miss" For each ship in descending order (place biggest ship first) { For each row and column { Try to place the ship at the current row and column (Try both orientations... see next sections for details) } If you can’t find a (row,column) for the ship, mark the last opponent guess coordinate as a "Hit" } If you were able to find a spot for all ships, then you officially declare the guess location a "Miss" Evil Battleship Page 6 Board Class The Board class implements most of the functionality of the battleship game. It is in charge of maintaining the target and ocean grids. It is also in charge of the sneaky ship strategy. Listing 1: Board Class const int SIZE = 10; // Grid size for the game class Board { public: Board(); void FireAttempt(int row, int col); // Attempts to fire on (row, col) void AddShip(Ship* ship); // Add Ship to the game// (add to ships vector) void PrintHitMiss(); // Prints the hits and misses void PrintShips(); // Prints the ship locations void PlaceShip(Ship* v); // Places ship v on boardbool ShipSunk(Ship* v); // Returns True if ship was sunkbool ValidPlacement(Ship* s); // Returns True if placement is validint ShipsLeft(); // Returns the ships left void SetEvil(bool e); // Sets the board to be evil or not void SetDebug(bool d); // Prints out debugging information // for ship positions private: char board[SIZE][SIZE]; // Stores the ship placements char missHits[SIZE][SIZE]; // Stores the miss and hits vector
* ships; // Stores all shipsbool debug = true; // Is the debug mode on? bool evil = true; // Is the board using evil strategy int shipsLeft; // How many ships left void PlaceAllShips(int row, int col); // Try to place all ships given the // guess (row, col) void PlaceSunkShips(); // Places sunk ships on board void ResetPlayBoard(); // Resets the board to be missHits void PrintBoard(char grid[SIZE][SIZE]); // Prints a board }; Evil Battleship Page 7 Ship Class It is your responsibility to design and implement a Ship class. There are many different ways to represent the ship. One convenient way to represent the ship and placement is to use: • Coordinate (row, col) • Direction (East, South) • Ship Length For example, if we wanted to place the patrol ship from (A,3)-(B,3), we could represent this with the data {(0,2), South, 2}. This means start at the coordinate (0, 2) and fill 2 spaces south. 1 2 3 4 5 E D C B A Ships cannot overlap any coordinate marked as a "miss". As previously mentioned, "hit" locations are valid placement locations. However, if every position of the ship is on top of a "hit" location, then you must declare the ship sunk and permanently place the ship. Evil Battleship Page 8 Sample Output Debug (y/n): n Evil (y/n): y Place Carrier Coordinate (row col): a 1 Direction (S/E): e ______________________ 1 2 3 4 5 6 7 8 9 10 a C C C C C b c d e f g h i j ______________________ Place Battleship Coordinate (row col): z 1 z is not a valid row Coordinate (row col): b 11 11 is not a valid col Coordinate (row col): b 1 Direction (S/E): s ______________________ 1 2 3 4 5 6 7 8 9 10 a C C C C C b B c B d B e B f g h i j ______________________ . . . etc. . . . ______________________ 1 2 3 4 5 6 7 8 9 10 a C C C C C b B c B d B e B f S S S g D D D h P P i j ______________________ Evil Battleship Page 9 ============= LET’S PLAY!!! ============= ______________________ 1 2 3 4 5 6 7 8 9 10 a C C C C C b B c B d B e B f S S S g D D D h P P i j ______________________ ______________________ 1 2 3 4 5 6 7 8 9 10 a b c d e f g h i j ______________________ Enter Coord: a 1 MISS!!! Computer Guess: b 1 HIT!!! ______________________ 1 2 3 4 5 6 7 8 9 10 a C C C C C b H c B d B e B f S S S g D D D h P P i j ______________________ ______________________ 1 2 3 4 5 6 7 8 9 10 a M b M c d e f g h i j _______________________ Enter Coord: b 2 . . . etc Evil Battleship Page 10 . etc . . ______________________ 1 2 3 4 5 6 7 8 9 10 a M M M M M M M M M M b M H H H H M M c M M M d M M e M M M M M M M M M M f M M g M M M M h M M M M M i M M M M j M M M M ______________________ Enter Coord: b 3 YOU SUNK MY Carrier!!! Computer Guess: b 1 MISS!!! ______________________ 1 2 3 4 5 6 7 8 9 10 a C C H C C b H c B d B e B f S H S g H D D h P P i j ______________________ ______________________ 1 2 3 4 5 6 7 8 9 10 a M M M M M M M M M M b M C C C C C M M c M M M d M M M e M M M M M M M M M M f M M g M M M M h M M M i M M M j M M M ______________________ Enter Coord: . . . Computer Guess: h 2 YOU SUNK MY Patrol Boat! ______________________ 1 2 3 4 5 6 7 8 9 10 a H H H H H b H c H d H e H f H H H g H H H h H H i j ______________________ YOU LOST!!!! Evil Battleship Page 11 DEBUG ON SAMPLE OUTPUT ______________________ 1 2 3 4 5 6 7 8 9 10 a b c d e f g h i j ______________________ Coord: a 1 Placing Carrier... ______________________ 1 2 3 4 5 6 7 8 9 10 a M C C C C C b c d e f g h i j ______________________ Placing Battleship... ______________________ 1 2 3 4 5 6 7 8 9 10