battleship

Battleship
source: Katrin Becker, 2001

{HELP}

Concepts:

use of arrays
use of sub-programs
interactive, menu-driven programs
use of sub-program stubs
random numbers
introduction to games design
cheat codes and game testing


Contents: Introduction/Background, The Program, Example, Attacking the Solution, Requirements, Marking, Problems, Bonus

Introduction/Background:
While at first glance, this problem may seem too complex for your level of expertise, if you take the time to plan carefully and implement the program in pieces you can do this. Please read the assignment carefully (I know it's long) - it contains many suggestions and hints for how to do this assignment.

Battleship is traditionally a 2-player game played using two square grids (boards). Each player has 5 ships that can be placed anywhere on the board and range in size from 2 to 5 'squares' long. All ships are 1 square wide. Each player chooses where to place her own ships without telling her opponent.

The object of the game is to guess the locations of your opponent's ships before your opponent guesses yours. The first player to sink all of her opponent's ships wins. All squares containing a ship must be hit before that ship is deemed 'sunk'.

Players take turns firing torpedoes at specific locations (squares) in an effort to sink the opponent's ships. Firing a torpedo into a location where one of your own ships lies does not harm your own ships (there are 2 separate boards). Torpedoes may not be fired into the same location twice.

On your turn, the opponent's board is displayed with the ships hidden and only the locations of previous torpedo shots marked.

Ships and Ship Placement:
- Each player has 5 ships:

A Submarine: 3 squares
A Destroyer: 2 squares
A Cruiser: 3 squares
A Battleship: 4 squares
An Aircraft Carrier: 5 squares

- ships may not extend past the edges of the board
- ships may not overlap
- there may be at most one ship (or part there-of) in each square
- ships may not be placed diagonally (vertical or horizontal only)

Your Program:
In our version, we will have only one player - the computer (your program) will be the other player. When a new game starts, your program will initialize it's own board, choosing 5 random locations and orientations for the ships. Then the player chooses (*see specs) locations for her ships. It is sufficient to specify 2 locations to describe a ship - just the end-points. Both boards may be displayed simultaneously.

The player starts: the program's board is displayed (with ships hidden) and the player chooses a location for her torpedo. If it hits nothing, the square is marked and the player is told she has missed. If the player has hit a ship, the square is also marked and she is told which ship. Once all of the parts of that ship have been hit, it is deemed 'sunk' and the player is informed.

After the player's turn, the program chooses a random location and the same thing happens to the player's board (ships need not be hidden on this board).

Example:

OPTIONS:
   H.....: Display Help Screen
   S r c : SHOOT ROW #r COLUMN #c
   P.....: Play a new Game
   Q.....: Quit
   any other key: Continue Game

ENTER REQUEST:

Outline the main program and your data structures (the main program should do very little besides defining the types and initialization). You will need at least 2 arrays (one for each board) - both of the same type. They could simply contain the characters that will be displayed on the screen - one character in each element of the array.

Outline the "Game AI". This is the main driver of your game and it gets called by the main program. At this point in the development this outline is VERY rough and undetailed. The AI's "responsibilities" include (with suggested sub-routines): displaying the game's menu (showMenu) initializing each board (initProgramBoard; initPlayerBoard - start with only the first one) getting and checking user requests (getRequest) starting a new game (newGame) displaying a board keeping track of which squares have been hit keeping track of which ships have been hit displaying the appropriate board at each turn

Now write a 'rough' program shell that calls the AI and the basic AI to initialize ONE board and display it. Once this is working, add the second board. It should not allow user input yet although it may display the menu.

Write the procedure to place ships. Start with a procedure that places ships in specific locations. TEST IT. Then modify it to choose random locations - all with the same orientation (all vertical or all horizontal). TEST IT. Finally modify it to also choose a random orientation. TEST IT AGAIN. If you are going to allow the player to choose the locations of her ships, implement that part near the end after the rest of the program is working.

Write the function to get a user request and the procedure to process it. The function should only return a valid request (invalid requests are handled inside the function). It should return the request and a row and column number for a shot. TEST IT. Then write the procedure to process the request. This procedure will probably contain a case statement that simply calls other routines to actually handle the request. This is one place where "stubs" are handy: each of the procedures called by the processRequest routine can start off empty and do nothing (exception: make the quit routine stop the program. Suggestion: have the processRequest routine return an argument that is the game's "state" and have the gameAI check that value after the call. If the value is < 0 the gameAI should say "Bye" and return to the main program which simply ends).


Add the ability to 'hide' ships. This can be easily done by creating an additional array - this time containing boolean values - for the program's board. The player's board needn't be covered. Suppose this 'board' is called covered and is initialized to all true. As each square in the program's board is being displayed, the corresponding element of the covered array is checked: if it's value is true that square is displayed as a '.' but if it's value is false, then the character currently stored in the program's actual board is displayed instead. When a torpedo is fired, the character in the actual board must be changed and the value in the corresponding covered array is changed to false. [ When implementing a cheat code it simply changes the first initialization of the covered array from all true to all false. Everything else in the program remains the same.]


A Word About Cheat Codes: Cheat Codes are used in the development of virtually all computer games. It involves a special option given to the game at start-up or a special user request that will force game play to proceed in predictable ways so the developers can test various aspects of the game. In a FPS (first-person-shooter) game this may mean that one or more characters become invulnerable and can't be killed: this keeps the game from ending too quickly. It may also involve making the bad guys easier to kill. In an RPG (role playing game) it can give a character special powers or invulnerabilities that allow the tester to try various scenarios that would take too much time to set up otherwise. These codes and program options are often left in the game once it goes into production to make updates and further development easier. Cheat codes may also allow the tester to begin the game from a certain level, to test just that part. This technique for testing is used extensively in many other kinds of programs too - they're just not called cheat codes then.

Our game is a relatively simple one but a cheat code will help us too. It's purpose in our game will be to allow us to play a game with the ships on the program's board visible so we can verify that ships have been properly placed and that hits and misses are being properly implemented. In our game, a simple way to incorporate a cheat code is to allow an "undocumented" menu option (maybe 't' for TEST) that serves the same function as PLAY but will leave the program's board uncovered. This option should not be shown in the menu (it's secret).

Requirements
Your program should be friendly without being too verbose, and it should be reasonably robust (provided the user typed in input types the program should NOT blow up).

The program must be fully documented and follow appropriate style constraints. You must provide sufficient evidence that the program compiles and executes correctly.

Notes on Marking:
In order to pass it must work. (Some marks will be given to all *reasonable* attempts, working or not)
For a Maximum Grade of C+:
The 'C' solution implements a simplified game with no frills.

The program must use functions and procedures in its design.
This version has a single player and one board. The player is the user and the board 'belongs' to the computer.
Ships can be placed at random by the program and the board can be left 'uncovered'.
The game must allow the player to specify the locations of torpedoes; it must not allow the user to try and place a torpedo off the board (the game may not blow up on bad input), but it needn't keep track of ships that are sunk.
A torpedo fired to a location already used is treated as a regular turn.
It need not detect a win or keep score and it is left up to the player to keep track of which ships are left.
This solution must show the locations of the ships and must mark the locations of the torpedoes.

For a Maximum Grade of B+:
The 'B' solution implements the basic, 2-board game with no frills.
All of the Above, PLUS:
good, clean design; good documentation

TWO boards: one for the computer (ships placed at random) and one for the player (ships placed by player). Game play involves taking turns: first the user chooses a location for a torpedo, then the computer chooses one at random.
The player may place her own ships, probably by specifying the row and column number for just one point or for both the bow and stern of each ship. Remember to check that the ship is completely on the board, not being placed diagonally and that it won't end up in a square already used by another ship.
The program must not allow a torpedo to be fired into the same location twice (at least, it shouldn't count as a turn). No points are removed and it doesn't count as a turn. The player should be informed.
The program's board should be covered during game play. Implement the cheat code (which will at least show the board uncovered during play).

For a Maximum Grade of A:
All of the Above, PLUS:

excellent design;

excellent documentation

Detect a win, i.e. when all ships on one side have been sunk.
Display game status:
- each ship as separate entity (both sides) and how much of the ship remains to be hit.
Keep score:
Suggested: 100 points to start; -1 for each hit; -2 for each miss
If you run out of points before sinking all the ships, you loose.

Important Note ALL VERSIONS: if your program does not function properly it is possible to verify that some parts work if you have produced a reasonable trace (see sample solution)

Problems:
Re-printing the board each time something happens may interfere with the 'flow' of the game from the user's perspective. The simplest solution to this problem is to use the easycurses library. Make sure you read and understand how to use it and what to do when your program terminates unexpectedly BEFORE you incorporate it into your program. Keep a previous working copy of your program and use a second copy for this change.
If you want to make a missile hit look like an explosion, one way to accomplish this is to display the board a number of times with an expanding 'circle' of marks around the hit. This will work best when using easycurses, rather than scrolling the output each time. However, you may find that the 'series' of displays happens too fast to actually see the effect. In order to fix this you will have to incorporate some kind of timing mechanism into your program. There are a number of ways to do this. The simplest is to make the player set the pace by forcing them to enter some input (the infamous "press any key to continue") to cause the display of the next 'screen'. A somewhat more elegant solution is to introduce a time delay into your program. There are system routines we can call to make the program 'sleep' for a specified period of time but a simpler way is to write a "busy loop" that gets called whenever you want to slow things down. This busy loop does not affect the rest of the program but it must do something that will take time: calculations are a favorite choice. The busyLoop routine can do a bunch of multiplications or calculate a bunch or square-roots. Be careful: make sure it won't cause the program to terminate with an overflow, or an attempt to get the square root of a negative number. To set the pace you simply need to play around with the number of times the loop is run or the size of the values worked on. This approach works quite well but the actual length of the delay will depend on things outside your program such as how heavily the system is loaded.
Question: What is a good pattern to fire torpedoes?

BONUS:
____1. Use "Easycurses" for screen addressing.
____2. Implement 2-Player Feature [i.e. the other player is a human, not the computer].
____3. Allow player to "move" (re-place) ships (only until play starts).
____4.Allow a variable sized board (either choose from pre-set options or allow user to specify).
____5. Allow more than one shot per turn: Suggested: Allow up to 5 shots or until the first miss, OR: allow as many shots as player has ships left [i.e. if I have 3 ships not yet sunk but the computer has only 1 then I get 3 shots per turn but the computer gets only one]
____6. Give the computer a bit of "intelligence". Once the computer hits something, have it remember and shoot subsequent torpedoes in the same area until it can discover which way the ship is lying. Then it should try to eliminate that ship before going back to choosing shots at random.