minsweeper

"Minesweeper"
source: Katrin Becker, 1999

see also:
http://scv.bu.edu/~aarondf/java/cafesweep.html
http://www.javascripter.net/games/mines/game.htm
http://flowserv.teco.uni-karlsruhe.de/crew/krebs/InetMines/InetMines.html

Contents:

Introduction, Demo Program, Approach:

- Representing the Board

- Dealing with the Edges of the Board

- Covered vs Uncovered

Cheat Codes, function:
ClickEmptySquare, General Remarks, Minimal Requirements, Testing, Bonus

Introduction

The object of this assignment is to write a program that allows a user to play the game "MINESWEEPER".

Minesweeper is one of the games that comes with the Windows Operating System. It consists of a grid of squares that represents a mine field. The object of the game is to locate all the mines without tripping any. If you manage to mark all mines or uncover all the squares that don't contain mines, you win. If you click on a square that contains a mine, you loose.

The links provided above will allow you to familiarize yourself with the game.

The Windows game keeps track of your score by keeping track of your time as well as the number of mines left to mark. We have not dealt with timing of computer or user actions yet so in our game we will keep score by assigning points to each guess that the user makes. In the Demo, uncovering a square that is not a mine 'costs' 1 point, marking a mine costs 0 points and incorrectly marking a mine costs 10 points.

We also do not yet have the experience to create a fully graphical display, so our game will be displayed using simple ASCII graphics. The demo game in the course directory will give you some idea of how this can work. In the demo, a covered square is represented with the character '~'. Each square contains a number which indicates how many mines are in the 8 squares adjacent to it. '0' means there are none, 8 is the maximum.

The squares themselves can easily be identified using (x,y) coordinates (x=row, y=column). Looking at a portion of the mine field:

j-1 j j+1

i-1 2 X 1

i X 4 1

i+1 X 3 X

On the screen, mines will appear as an 'X'. The numbers indicate how many mines are in the adjacent squares.

Demo Program

- found in /home/231/Asst6/mines
- run with: ./mines
- can be played from course directory without copying to your own directory

1 2 3 4 5 6 7 8

1 ~ ~ ~ ~ ~ ~ ~ 1

2 ~ ~ 1 X X 1 1

3 ~ ~ ~ 2 2

4 ~ ~ 1

5 ~ ~ 1

6 ~ ~ ~ 1

7 ~ ~ ~ 1

8 ~ ~ 1 1

The demo:

- allows you to choose the play level:

b = beginner; grid is 10 X 10; 10 mines
i = intermediate; grid 16 X 16; 40 mines
e = expert; grid 16 X 30; 100 mines

- once the play level is entered, the game will randomly place mines and display a completely covered field.
- it will then request the coordinates of the square you wish to uncover:

[i,j]:

You are to enter 2 numbers, separated by a blank. If you enter a '0', the game will exit.
This version allows you to mark squares that contain mines: simply enter the compliment of the coordinates. For example, to mark a mine in row 7, column 3, enter one of:

-7 -3
-7 3
7 -3

If either of the coordinates are negative, the game assumes you want to mark a mine. If you incorrectly identify a square as a mine you will be penalized 10 points.

This version of the game also contains a "cheat code". (see later for a discussion of cheat codes). If you invoke the game with:

./mines -d

the mine field will be displayed "uncovered" along side the covered field for the duration of the game.

In the traditional game, if the user clicks on a square that has no neighbouring mines, the game will open up the entire area that is clear of mines. The demo does this too and you have been provided with a linkable version of the function that does this. It is called: ClickEmptySquare. It will be explained later.

Approach:

There are, as always, a number of ways to solve this problem. The issue of how to clear an area when the user chooses an empty square is somewhat challenging and so this part of the program will be provided for you. You are, of course free to write your own.

It is suggested that you get the rest of the program working without the clear function before incorporating the one already written or writing your own.

Representing the Board

It is not necessary for the internal representation of the mine field to be exactly the same as the one the user displayed [this is an extremely common and useful approach]. In fact, it is easier to manage the game if the internal representation is NOT the same as that displayed.

Since keeping track of neighbouring mines is of prime importance, representing the field internally as an array of integers makes the most sense. Then we can simply store the count of neighbouring mines at each location. 0 = clear (none); 1->8 = number of mines. 8 is the maximum number of mines that can be adjacent to one square. This leaves the problem of how to represent a mine itself. Since the value '9' is not being used for a count so it can be used to represent a mine.

When the board is displayed, the values 1-8 can be displayed as themselves, '0' is displayed as a blank, and a mine (9) is displayed as an 'X'.

A square that is still covered can be displayed using '~' instead of its count.

Dealing with the Edges of the Board

When marking squares, one would normally check the neighbouring squares:

j-1 j j+1

i-1 ? ? ?

i ? X ?

i+1 ? ? ?

This is fairly straight-forward when the square being examined is in the middle of the field but presents a problem on the edges since we need to treat them as special cases to avoid indexing problems (and the subsequent segmentation errors). A simple solution to this problem is to declare a board (array) with a built-in "cushion". A 10X10 board would then be declared: int field[12][12]; This way, rows 0 & 11 and columns 0 & 11 can be used when checking neighbours but are ignored otherwise (DO NOT place mines in the border!) The borders are not displayed. They are for internal use only.

Covered vs Uncovered

There are 2 main approaches to keeping track of which squares have been uncovered. The first (assumed by ClickEmptySquare) is to keep a second array the same size as the first which is of type boolean. It starts off with all the elements set to "covered" (if the array is called "covered" then this would mean setting them all to true) and then resets each square as the user uncovers it.

The second approach lets us keep all the information in one array. If we assume the array contains counts of neighbouring mines, then our values will range from 0-9 (0=none; 9=this square has a mine). What we need is a way to distinguish between covered and uncovered squares without destroying the value we need for the count. Using the compliment (-3 vs 3) would work EXCEPT we have no way of representing a covered '0' (since there is no '-0'). What we can do though is use a different order of magnitude: 30 vs 3. This way 90 represents a covered mine, 10 represents a covered blank, 30 represents a covered square with 3 neighbouring mines. A covered square can easily be uncovered by dividing it's value by 10. Make sure you check to see if it's covered or not (val >= 10) BEFORE dividing by 10.

Cheat Codes

Anyone who has played computer games to any extent will be aware of the existence of "Cheat Codes": special keys or codes you can enter at various points in the game that will either reveal parts of the solution or make your character invulnerable somehow. These cheat codes were built in to the game by the developers for their own purposes. With them they can more thoroughly test their game before release. It allows them to get to specific parts (like different levels) quickly and try certain actions they would not otherwise be able to try easily. It allows them to do things like face "certain death" in the game and survive, thereby making sure the next step will work even if the character is not killed. Setting the cheat codes make the game predictable which is an absolute necessity when testing - especially if the game relies on the use of pseudo-random numbers. These cheat codes were NOT intended for the users (notice they're called 'CHEAT').

You may find it useful to build a cheat code into your program that will allow you to peek under the covered squares - thus enabling you to test each branch in your program without actually having to play an entire game.

The demo program includes a cheat code.

function: ClickEmptySquare

prototype: void ClickEmptySquare( int i, int j);

This function operates directly on the board and assumes the presence of a number of global variables:

const int MAX_SIZE = 100;
int MAXI = 12; // actual size of board (rows) including the cushion - not a constant
int MAXJ = 12; // actual number of columns - not a constant
int MINE = 9; // value of a square representing a mine
int field[MAX_SIZE][MAX_SIZE]; // the mine field itself
bool covered[MAX_SIZE][MAX_SIZE]; // true if square currently covered

The "field" is assumed to contain integers which indicate the number of neighbouring mines. 0= clear; 9= mine

The function also assumes the presence of another function called Uncover which does AT LEAST the following: (you must provide this yourself)

void Uncover( int i, int j )
{

covered[i][j] = false;

}

To use the ClickEmptySquare function in your program: copy the following files into your directory:

ClickEmptySquare.h
ClickEmptySquare.o
makefile

Modify the makefile to use your version if it is called something other than "mines.cc"

General Remarks

The use of functions is required for this assignment.

The 'board' may be displayed after each turn or you may use easycurses to allow screen addressing.

'Clicking' on a square can be accomplished by simply entering the coordinates of the square you wish to uncover.

Clearing a portion of the board: when you 'click' on an empty square (one with no mines nearby), the game usually opens up as much of the board as it can until it comes up against squares with mine-neighbours. A function called 'ClickEmptySquare' has been provided for you that accomplishes this task. The approriate makefile has also been provided.

Minimal Requirements

There are several 'stages' at which this assignment can be considered complete. Note the maximum grade possible at each stage. This means that if you have a working program that meets the requirements of the first stage the maximum grade attainable will be a C+. NO exceptions. The maximum grade will only be given to programs that are well designed and properly documented. Poor design or inadequate documentation will lower your grade by at least half a letter grade.

STAGE 1: For a maximum grade of C+:

- use of arrays and functions
- implement beginner's game (10X10 field; 10 mines)
- correctly places mines in random locations (different each game)
- correctly labels all squares with the count of the neighbouring mines
- correctly uncovers squares
- detects GAME OVER when user uncovers a mine
- allows user to quit when desired
- terminates gracefully
- detects illegal requests (chosen square not on board)

STAGE 2: For a maximum grade of B+:

All of the above, PLUS:
- keep score [1 point/trun]
- keeps track of how many mines remain uncovered
- detect a win: either all mines have been uncovered or all squares that are not mines have been uncovered
- uncovers the entire board when the player wins or looses (but not when he quits)

STAGE 3: For a maximum grade of A:

All of the above PLUS:

- allow 3 levels of play:

beginner: 10X10; 10 mines
intermediate: 16X16; 40 mines
expert: 16X30; 100 mines

- keeps score similar to the demo game
- allows user to mark mines
- provides a cheat code that displays the board or allows the player to peek. [ highly recommended for all ]

Testing

Stage 1:

- Run through an entire beginner game to the 'win' state.
- test illegal request(s)
- demonstrate that the program allows you to quit
- 'click' on a mine: 'loose' state

Stage 2:

- mark all mines in beginner game to win

Stage 3:

- show other play levels - play partial expert game
- demonstrate use of cheat code

Bonus

Allow different sized boards and a custom number of bombs (to a max of perhaps 100; remember to set a reasonable maximum)

Use screen addressing (with easycurses)

Allow the user to mark uncovered squares with 'M' or '?'

Write your own ClickEmptySquare function - function must be reasonably small and clean

Implement a Clear function to uncover squares around a marked mine. You are not allowed to clear around a square if you have not marked enough mines in the surrounding eight squares, or if the square is covered. For example, if you try to clear around a square labeled 3, and you have marked only two squares with mines, nothing will happen. Or, if you try to clear around an uncovered square, nothing will happen.
If you clear around a square, and there is an unmarked mine in the surrounding eight squares, it is uncovered and the game is over.
If you clear around a square whose mines are incorrectly marked and a mine is uncovered, the game is over.

	j-1	j	j+1
i-1	2	X	1
i	X	4	1
i+1	X	3	X

	j-1	j	j+1
i-1	?	?	?
i	?	X	?
i+1	?	?	?