In the notes and exercises so far, you have been introduced to most of the main concepts common to all imperative programming languages, as well as some features specific to object-oriented languages and the Java language in particular. Before embarking on this set of notes you should review the previous material and make sure that you have at least some understanding of the following:
BufferedReaders,
System.out, etc.
for and while
loops.
if and switch.
The aim of these notes is to draw together all of the material you have
covered already, in the context of a larger, more ambitious program than
you have tackled before -- a simple version of the `MineSweeper' game
that many of you will have encoutered before. The program presented
here totals almost 600 lines of Java code, which may seem a little
overwhelming at first. However, very few completely new ideas will be
introduced by this program so you should be able to understand most of
it without too much difficulty. The complete source code for the
program will be available in the directory /import/teaching/BSc/1st/ItP/MineSweeper/
In case you are not already familiar with the MineSweeper game we will briefly review the rules here. The games is played on a M by N grid of `cells', each of which is either empty or contains an explosive mine. Your task (should you choose to accept it) is to locate all of the mines without causing any of them to explode.
Sounds easy? Well, unfortunately for you the location of the mines is a well-kept secret. In fact, at the beginning of the game you have no information as to whether any given cell contains a mine or not. Your only course of action is to `reveal' the contents of a chosen cell. Should you reveal a mine, the game is over and you have lost. If, however, you reveal an empty cell, two useful things will happen:
Together these should provide you with enough information to determine where the mines are hidden. The game is over (and you have won) when the number of unrevealed cells is equal to the number of mines on the board (since every unrevealed cell must then contain a mine).
This description of the game will make a lot more sense if you actually
play a few games. Copy the files from
/import/teaching/BSc/1st/ItP/MineSweeper/ into your own
file space. You can then run the program with a command such as:
java MineSweeper X Y Z
where X, Y and Z represent the
width and height of the game board, and the number of mines on the
board, respectively. For example:
java MineSweeper 15 10 15
will produce a display something like the following:
11111
012345678901234
0 ############### 0
1 ############### 1
2 ############### 2
3 ############### 3
4 ############### 4
5 ############### 5
6 ############### 6
7 ############### 7
8 ############### 8
9 ############### 9
11111
012345678901234
Mines remaining: 15
Command:
The #'s represent cells that are yet to be revealed. There
are mines hiding under 15 of these cells. Typing help at
the Command: prompt will produce a list of the available
commands. We will rejoin the game a few dozen moves later:
11111
012345678901234
0 .......1X212X21 0
1 .11211.112X22X1 1
2 .1###1...122211 2
3 .1###21...1X1.. 3
4 11####1...111.. 4
5 ###1111........ 5
6 ###1........... 6
7 ###2..11211.... 7
8 ###1..1X2X1.111 8
9 ###1..11211.1X1 9
11111
012345678901234
Mines remaining: 7
Command:
By this point, the player has located all of the mines on the board
except for those in the cluster of cells on the left hand side. Cells
marked with a `.' are empty and have no neighbouring mines,
while those marked with a digit are also empty but have the indicated
number of mines as neighbours (exactly which neighbours is up to
you to find out!). The X's indicate cells that have been
marked by the player as probably containing mines. The markers
serve no function other than as a reminder to the player -- the
prescence of a marker does not necessarily mean that there is a
mine in that cell, so be careful where you place them. However,
markng a cell does reduce the count of mines remaining displayed beneath
the board, so you can see at a glance how many more mines there are to
be found. After a few dozen more moves the game is finally over:
11111
012345678901234
0 .......1*212*21 0
1 .11211.112*22*1 1
2 .1*2*1...122211 2
3 .112221...1*1.. 3
4 111.1*1...111.. 4
5 1*21111........ 5
6 12*1........... 6
7 1322..11211.... 7
8 *2*1..1*2*1.111 8
9 1211..11211.1*1 9
11111
012345678901234
Mines remaining: 15
Congratulations -- you found all the mines!
Total game time: 806 seconds
At the end of the game the program will reveal all of the mines (whether marked by the player or not) and indicate the time taken to play this game. You should probably play a few games with different board sizes and numbers of mines to familiarise yourself with the operation and behaviour of the program before continuing to delve into the details of the code.
The MineSweeper program consists of three classes, Board,
TextBoard and MineSweeper. Together these
classes illustrate a typical use of inheritance as well as a
number of good software engineering practices that will be introduced as
necessary.
Before we start to investigate the code for these classes, it is probably worth reiterating the point made earler, that you will probably find this program a little overwhelming at first, if only because the sheer size of the code is ten times that of any programs you have written already! However, the division of the program into three distinct classes also serves to divide it more easily digested and understood chunks. You should probably not attempt to work through this whole set of notes in one sitting; it might be best instead to just read the material for one class and make sure you have fully understood this before moving on to the next.
Board classObviously the game board is a fairly significant aspect of the MineSweeper game -- the decisions we make about its design and implementation will have consequences for the entire program. There are several major points to consider:
These questions, and their answers, are all somewhat interrelated. We will address the last question, "How should the board be presented to the user of the program?", first. As written, the user interface to the program consists of a simple text-based representation of the board in a terminal window, controlled by commands typed at the keyboard. We might, however, want to modify the program to use a true graphical interface in the style of most other MineSweeper programs, or even have it support multi-player games over the Internet. Of course, neither of these extensions change the basic idea of the game board as a grid of cells, some of which contain mines. Bearing this in mind, it seems like a good idea to separate out this fundamental idea of what the game board is and how it behaves, from the particular way in which we choose to present it to the user, or even the particular set of rules we want our game to follow.
Therefore, we will implement the game board as a separate class
Board that maintains the state of the board and provides a
set of operations that other classes can use to manipulate that state.
What the Board class will not do is provide any user
interface, nor impose any fixed set of rules on the game. By
implementing the board in this way, we leave the way open to provide any
user interface and set of rules that we care to, while ensuring that the
Board class itself is reusable and does not have to
be changed for each new variation of the game that we create. For the
class to be truly reusable, it must be carefully designed to make sure
that all of the necessary functionality is made available to both
current and potential future users of the class.
Now that we know basically what the Board class is supposed
to do, it is time to start looking at the code and to address the other
three questions posed above. The complete source code for class
Board is presented below, interspersed with explanatory
notes and commentary. You can also find the code (including the line
numbers, so don't try to compile it!) in the file /import/teaching/BSc/1st/ItP/MineSweeper/Board.html.
If you are reading this online, you might want to open this file in
another window (try clicking on the link with the middle mouse button)
so you can easily refer to it while reading the notes.
1: import java.util.Random;
2:
3: /**
4: * This class implements the basic behaviour of a MineSweeper game board;
5: * i.e. a grid of cells, each of which may contain a mine. The cells are
6: * initially covered (unknown) and can be selectively 'revealed'. A revealed
7: * cell either contains a mine or an integer indicating the number of mines in
8: * the (up to) eight adjacent cells. Cells may also be 'marked', to indicate
9: * cells that might contain a mine. No more cells can be marked than there
10: * are mines on the board.
11: *
12: * The board does not enforce any particular game rules (e.g. no special
13: * action is taken if a mine is revealed). Even the behaviour of the reveal()
14: * and mark() methods can be overridden if desired. In particular, the draw()
15: * method is abtract and must be implemented in a subclass to give the board
16: * any kind of visual representation.
17: */
18: public abstract class Board {
Line 1 informs the compiler that we will be using the
Random class from the java.util package and
that we would like to refer to it simply as Random rather
than by its full name java.util.Random.
Import statements such as this are never necessary;
they are merely a convenience feature that allows you to save a few
keystrokes by referring to a class by a shorter name. You can always
use the fully qualified name, whether or not an import
statement is present. The Random class will be used later
to assist in randomly dispersing mines across the game board.
Lines 3--17 make up a large comment block. It is difficult to stress how important it is for your programs to be well documented, with liberal use of comments within the code. The comments are ignored by the compiler, but they are essential for anyone attempting to read and understand your code. That said, don't go overboard with your commenting -- it is not necessary to annotate every line with comments such as
// Add one to the value of i
i++;
where the comment provides no useful information at all. In this case
it might have been appropriate to explain what the variable
i is used for, and what the implications of adding one to
it might be.
Line 18 begins the definition of the Board class. The
class is declared to be both public (meaning that it is
visible and accessible to all other classes) and abstract
(meaning that instances of Board cannot be created
directly; the purpose of this will be made clear shortly).
The next group of lines declares the instance variables for the
class. Each Board object that we create will have its own
independent copy of these variables, distinct from those in any other
Board object.
19:
20: // Subclasses have access to protected variables
21:
22: // Board size
23: protected int width, height;
24:
25: // Number of mines on the board
26: protected int numMines;
27:
28: // Number of cells currently marked
29: protected int numMarked;
30:
31: // Number of cells yet to be revealed
32: protected int numUnknown;
33:
34: // Indicates where the mines are hidden
35: protected boolean[][] mines;
36:
37: // The current state of the board
38: protected int[][] board;
39:
40: // Constants for cell contents. The MINE value might be returned by
41: // reveal(), the others are only used internally but will probably be
42: // required in subclasses.
43: public static final int UNKNOWN = -1;
44: public static final int MARKED = -2;
45: public static final int MINE = -3;
46:
Note firstly that all of the instance variables are declared to be
protected. Essentially this means that these variables
will be accessible to subclasses of the Board class
(ie, class that inherit from Board), but not to any
other class. This protection is important, because we do not want other
classes -- perhaps written by other people -- manipulating the internal
state of the board in undefined or illegal ways. This notwithstanding,
we want subclasses -- which presumably know what they are doing -- to
have full access to the board state. The protected
declaration is ideal for this purpose.
The second point to note is that each of the variable declaration is
accompanied by a descriptive comment stating the purpose of the
variable. Furthermore, the names themselves -- such as
width and height -- also help to describe the
data that will be stored in each variable.
We have chosen to represent the state of the board with two
two-dimensional arrays of the same size as the board. The first array
is a grid of boolean values, each indicating the presence
or absence of a mine in the corresponding cell of the board. The second
array stores the state of the board as seen by the player, that
is, a grid of cells whose contents are either unknown (and
perhaps marked as potentially containing a mine), empty,
or a mine. For cells that are known to be empty we also wish to
know how many of the up to eight neighbouring cells contain a mine. The
second array is an array of ints, which is in the range
0..8 for empty cells with that number of neighbouring mines, or one of
the special values defined as constants in lines 43-45 to indicate cells
that are unknown, marked or known to contain a mine.
We could have represented the entire state of the board using a single array and a more complicated encoding of cell states. Under such a scheme we could even have done away with the auxiliary variables storing the board size, number of marked cells, etc. While the single-array approach would use less storage, it would clearly be far more difficult to use and understand. A good rule of thumb in programming is to get the program working first, then worry about optimising it to run faster or use less memory. It is far better to have a slightly slower program that runs correctly and is easy to maintain, than one which is blindingly fast but doesn't quite work right!
Following the variable declarations we have a constructor method.
Recall that a constructor is a special method that will be called
whenever a Board object is created using the
new operator. In general, the purpose of a constructor is
to initialise the instance variables of the new object and to ensure
that the object is in a known state before it is used. The constructor
for the Board class takes three integer parameters: the
width and height of the game board, and the number of mines to place on
it.
47:
48: /**
49: * Create a new game board with the given size and number of mines. The
50: * mines are randomly distributed across the board. Currently no error
51: * checking is done, so if numMines > width*height the program will hang.
52: * C'est la vie.
53: */
54: public Board(int width, int height, int numMines) {
55:
56: // Initialise instance variables. Note the use of 'this' when parameters
57: // have the same name.
58: this.width = width;
59: this.height = height;
60: this.numMines = numMines;
61: this.numMarked = 0;
62: this.numUnknown = width * height;
63:
64: // Allocate storage for game board and mines
65: mines = new boolean[width][height];
66: board = new int[width][height];
67:
68: // Clear the board
69: for (int i = 0; i < width; i++) {
70: for (int j = 0; j < height; j++) {
71: mines[i][j] = false;
72: board[i][j] = UNKNOWN;
73: }
74: }
75:
76: // Randomly allocate mines. The loop runs until numMines mines have been
77: // placed on the board. The the purposes of this operation we treat the
78: // board as a width*height linear array of cells, and simply try again if
79: // the chosen cell already contains a mine.
80: int cells = width * height;
81: int temp = 0;
82: Random rand = new Random();
83:
84: while (temp < numMines) {
85: int cell = rand.nextInt();
86: cell = (cell < 0 ? -cell : cell)%cells;
87: if (!mines[cell%width][cell/width]) {
88: mines[cell%width][cell/width] = true;
89: temp++;
90: }
91: }
92: }
93:
Lines 58-66 initialise the variables of the new object. Note that the
three parameters have the same names as three of the instance variables
-- this is another example of the aliasing problem covered in an
earlier set of notes. To refer to the instance variable
width instead of the parameter width, the
notation this.width is used. The word this is
a Java keyword that always refers to 'the current instance of the
class', in this case the new object that we are constructing. The
arrays holding the board state are created with the appropriate sizes in
lines 65 and 66. The two nested loops in lines 69-74 simply set the
entire board to a known state: all cells are unknown and no cells (at
this point) contain mines.
Lines 80-91 actually place mines in the requisite number of randon
locations on the board (by setting the appropriate cells in the
mines array to true. The algorithm used here
is neither particularly efficient nor wonderful, so it will not be
described in detail. Suffice it to say that it will eventually get the
job done, provided that the number of mines does not exceed the number
of cells on the board!
Line 100 declares a method called draw, which you will
notice has no associated method body. This is an example of an
abstract method, one which is declared as being part of a class
but not actually implemented by it. The presence of the abstract
draw method explains why the entire Board
class must be declared abstract -- if we were to be
able to create a Board object and call its
draw method, there would in effect be no method to execute!
Therefore, Board must be declared abstract and
Board objects can only be created indirectly by creating an
instance of a subclass of Board. Any such subclass must of
course implement the draw method, otherwise it too would
have to be declared abstract.
94:
95: /**
96: * Print/draw/(speak?) some representation of the board that can be
97: * understood by a human player. This method must be implemented by
98: * subclasses.
99: */
100: public abstract void draw();
101:
Lines 109-128 implement the reveal method which, as is
explained in the comment before the method, reveals the contents of a
particular cell identified by its x and y co-ordinates on
the board, where (0,0) is taken to be the top left corner of the board.
As well as modifying the internal data structures to reflect the new
state of the board, the method returns the contents of the cell that was
revealed (as an integer value, using the same coding scheme as the
board array).
102:
103: /**
104: * Reveal the contents of the cell at position (x, y) on the board. Returns
105: * the contents thus revealed, which may be an integer in the range 0..8
106: * indicating the number of neighbouring cells that contain a mine, or the
107: * special constant MINE indicating that the cell contains a mine.
108: */
109: public int reveal(int x, int y) {
110: switch (board[x][y]) {
111: case MARKED:
112: // If the cell was marked, unmark it
113: numMarked--;
114: case UNKNOWN:
115: // One less unknown cell now
116: numUnknown--;
117: if (mines[x][y]) {
118: board[x][y] = MINE;
119: }
120: else {
121: // How many mines in the vicinity?
122: board[x][y] = closeMines(x, y);
123: }
124: break;
125: }
126: // Return the revealed value
127: return board[x][y];
128: }
129:
The reveal method only has to worry about cells whose
contents are still unknown -- if the cell identified by the
x and y parameters has already been revealed
then all we have to do is return its known contents. This is achieved
by the switch statement beginning on line 110. The
switch only has cases for the
MARKED and UNKNOWN states -- the cell contains
any other value it must have already been revealed, and the program will
simply 'fall through' to the return statement in line 127.
If the cell is currently in the MARKED state, we decrement
the counter that keeps track of the number of marked cells (since the
cell will not be marked once it has been revealed). The lack of a
break statement after line 113 means that the program will
continue executing the code the UNKNOWN case -- this is
entirely appropriate since all marked cells are also unknown cells, by
definition.
For a cell in the UNKNOWN state, we first decrement the
counter tracking the number of unknown cells. Then we check the
corresponding element of the mines array to see if the
cells contains a mine. If it does, we set the element of the
board array to the appropriate value. Otherwise, the cell
must be empty, so we call the closeMines method to count
the number of neighbouring cells that contain mines. This method
returns a number in the range 0..8 that is stored in the
board array. In any case, once the appropriate part of the
array has been updated, we will drop down to the end of the
switch statement in line 125 and then to the
return statement in line 127.
The next method is revealMore, implemented in lines
140-162. As its name implies, this method is used to reveal the
contents of additional cells around the selected cell. If you have
played the game at all, you will have seen this method in action, as it
is called every time you use the reveal command. The
method will reveal as many cells as it can without uncovering any mines,
so on a board with very few mines it is possible to find all of them
after a single move! The revealMore method is an example
of a recursive method, which can be simply defined as a method
that calls itself.
130:
131: /**
132: * Reveal the contents of more cells around cell (x, y). For each of the
133: * (up to) eight cells surrounding (x, y):
134: * - if the cell contents are currently unknown and the cell does *not*
135: * contain a mine, the contents of the cell are revealed.
136: * - if the revealed cell is empty and has no neigbouring mines,
137: * revealMore() is called recursively on it.
138: * The behaviour of this method is best understood by using it!
139: */
140: public void revealMore(int x, int y) {
141: int minx, miny, maxx, maxy;
142: int result = 0;
143:
144: // Don't try to check beyond the edges of the board...
145: minx = (x <= 0 ? 0 : x - 1);
146: miny = (y <= 0 ? 0 : y - 1);
147: maxx = (x >= width - 1 ? width : x + 2);
148: maxy = (y >= height - 1 ? height : y + 2);
149:
150: // Loop over all surrounding cells
151: for (int i = minx; i < maxx; i++) {
152: for (int j = miny; j < maxy; j++) {
153: if (!mines[i][j] && board[i][j] == UNKNOWN) {
154: reveal(i, j);
155: if (board[i][j] == 0) {
156: // Call ourself recursively
157: revealMore(i, j);
158: }
159: }
160: }
161: }
162: }
163:
Each time it is called, revealMore checks (and possibly
reveals) all of the (up to eight) cells surrounding the location given
by its x and y parameters. The local
variables minx, miny, maxx and
maxy define the boundaries of the area to be checked.
Lines 145-148 adjust the values of these variables to ensure that we
don't attempt to check beyond the boundaries of the board, which would
result in a runtime error. These lines make use of the conditional
operator denoted by '?' which is a useful shorthand for
a very common class of if statements. For example, line
145 could have been written as:
if (x <= 0) {
minx = 0;
}
else {
minx = x - 1;
}
Obviously the version using the conditional operator is much more
compact, but it could be argued that the if statement is
easier to read. In this case the conditional operator was used because
four almost-identical if statements would have made the
method about five times as long, perhaps obscuring the half-dozen lines
at the end of the method that do the actual work! Note also that the
conditional operator is just that -- an operator -- and as such
can be used in arithmetic and conditional expressions. Remember however
that you must assign or test the result of the operation in order to do
anything useful with it.
The rest of the method is a doubly nested loop over the (up to) eight
neighbours of the cell, and the cell itself. For each cell in this
range that has not already been revealed (and does not contain a mine),
we reveal it. If the cell thus revealed has no neighbouring mines
(ie. reveal returns zero), we recursively call
revealMore on the cell. This simple explanation hides some
potentially quite complex behaviour from this method. Probably the best
way to fully understand its operation is to walk through (by hand) some
invocations of revealMore on some sample board
configurations.
The following two methods allow cells on the board to be 'marked' and
'unmarked'. Their operation should be fairly self explanatory.
Together the methods maintain the value of the numMarked
instance variable, incrementing when a cell is marked and decrementing
it again when the cell is unmarked. The mark method will
only allow as many cells to be marked as there are mines on the board.
Both methods return a boolean value to indicate whether or
not the operation succeeded. For instance, a mark
operation succeeds only if the cell at location
(x,y) is both unknown and not already marked.
164:
165: /**
166: * 'Mark' the cell (x, y), probably to indicate that a player thinks there
167: * may be a mine there. Up to numMines cells may be marked simultaneously.
168: * Returns true is the mark succeeded, false otherwise.
169: */
170: public boolean mark(int x, int y) {
171: if ((numMines - numMarked) > 0 && board[x][y] == UNKNOWN) {
172: board[x][y] = MARKED;
173: numMarked++;
174: return true;
175: }
176: else {
177: return false;
178: }
179: }
180:
181:
182: /**
183: * Unmark the previously marked cell at (x, y). Returns true if the unmark
184: * succeeded (meaning that the cell was marked, false otherwise.
185: */
186: public boolean unmark(int x, int y) {
187: if (board[x][y] == MARKED) {
188: board[x][y] = UNKNOWN;
189: numMarked--;
190: return true;
191: }
192: else {
193: return false;
194: }
195: }
196:
The next five methods simply return various items of information about
the board, such as its width and height, or the number of cells still
unknown. We have to write methods to get at this information, because
the variables that store, for example, the board size internally are
declared protected and can thereofre only be accessed
directly by subclasses of Board. By providing these
accessor methods, we allow other classes access to certain parts
of the board state while preventing them from changing the state in
undefined ways. Also, if we (for some reason) decided to implement the
numUnknown method by counting the number of unknown cells
rather than just reading a variable, we could do this without changing
the interface to Board seen by other classes. This is an
example of encapsulation: the state and behaviour of the
MineSweeper board are encapsulated inside a well-defined interface.
Within this we can implement the board in any way we choose, as long as
it conforms to the documented behaviour of the interface. An
object-oriented language such as Java lends itself readily to this style
of programming; it is however equally possible, although sometimes
harder to enforce, to use this technique in other languages.
197:
198: /**
199: * Return the width of the game board.
200: */
201: public int getWidth() {
202: return width;
203: }
204:
205: /**
206: * Return the height of the game board.
207: */
208: public int getHeight() {
209: return height;
210: }
211:
212: /**
213: * Return the number of mines on the board.
214: */
215: public int getMines() {
216: return numMines;
217: }
218:
219: /**
220: * Return the number of currently 'marked' cells on the game board.
221: */
222: public int getMarked() {
223: return numMarked;
224: }
225:
226: /**
227: * Return the number of 'unknown' (as in not yet revealed) cells on the game
228: * board.
229: */
230: public int getUnknown() {
231: return numUnknown;
232: }
233:
The final method in the Board class is
closeMines, which counts the number of mines neighbouring a
particular cell. The structure of the method is very simliar to
revealMore, consisting of bounds-checking code in lines
244-247 and a doubly-nested loop over the cell and its (up to eight)
neighbours. For each cell in this area that contains a mine, we
increment a counter variable. The value of this variable is returned at
the end of the method, in line 257.
234:
235: /**
236: * Work out how many neighbours of cell (x, y) contain mines. Return the
237: * number of explosive neighbours.
238: */
239: private int closeMines(int x, int y) {
240: int minx, miny, maxx, maxy;
241: int result = 0;
242:
243: // Don't check outside the edges of the board
244: minx = (x <= 0 ? 0 : x - 1);
245: miny = (y <= 0 ? 0 : y - 1);
246: maxx = (x >= width - 1 ? width : x + 2);
247: maxy = (y >= height - 1 ? height : y + 2);
248:
249: // Check all immediate neighbours for mines
250: for (int i = minx; i < maxx; i++) {
251: for (int j = miny; j < maxy; j++) {
252: if (mines[i][j]) {
253: result++;
254: }
255: }
256: }
257: return result;
258: }
259: }
TextBoard class
So, we now have a nice abstract implementation of the MineSweeper games
board, that contains most of the functionality we expect to need in the
basic game and any minor variations on it. As we discussed above, we
will be using separate classes to implement the user interface and game
rules. The first of these is the TextBoard class which
provides a very simple text-based representation of the board state in a
terminal window. You can also find the code in the file /import/teaching/BSc/1st/ItP/MineSweeper/TextBoard.html.
TextBoard is implemented as a subclass of
Board, so that it will have access to the
protected instance variables of Board. Note
that any private variables or methods of Board
(if it had any) would not be accessible to TextBoard.
The most complicated part of the TextBoard code is the
printing of row and column numbers around the edges of the board. The
instance variables of a TextBoard object are used to
support this task. colLength and rowLength
hold the maximum length of the column and row number, respectively. For
example, if we had a 120 by 50 sized board, colLength would
have the value 3 and rowLength would have the value 2. The
two arrays colNums and rowNums hold all of the
necessary row and column numbers, converted into character strings. The
final instance variable, spacer, will be used to provide
some additional spacing between the numbers and the board itself.
1: /**
2: * Simple extension of class Board that provides a textual representation of
3: * the MineSweeper game board on System.out.
4: */
5: public class TextBoard extends Board {
6:
7: // Maximum length of string to hold column/row numbers
8: private int colLength, rowLength;
9:
10: // Printable versions of column and row numbers
11: private String[] colNums, rowNums;
12:
13: // Spacing for column-header lines
14: private String spacer;
15:
All of these variables will be initialised in the TextBoard
constructor in lines 21-64. Constructors are not inherited by
subclasses, so TextClass will have only the (fairly
useless) default constructor TextClass() unless we define
another. We define the constructor to take the same set of parameters
as the Board constructor: three integers giving the size of
the board and the number of mines to be placed on it. Remember that a
subclass constructor must make sure to call a constructor in its
superclass. By default, if the code does not specify anything else,
Java will automatically call the default constructor in the superclass.
That is, Board() will be invoked as the first action of the
TextClass constructor. However, in this case this is no
Board() constructor, because we have provided our own
constructor in the Board class. This, to avoid a
compile-time error we must explicitly call the Board
constructor with appropriate parameters, as in line 23. The superclass
constructor call must be the first thing done by a constructor.
The rest of the constructor code is concerned with setting up the tables
of row and column numbers in the rowNums and
colNums arrays. Each number is converted to its string
representation, and the string is then 'padded out' with spaces so that
all of the strings are the same length. The length is of course given
by the rowLength and colLength variables.
Note that the padding spaces are inserted at the start of the
string rather than the end, to ensure the correct alignment of the
numbers when they are printed. This code makes use of the
StringBuffer class, a more powerful variation on the
familiar String class that allows the characters of the
string to be edited 'in place', without the need to construct a new
string object. You should refer to the StringBuffer API
documentation, available via a link on the course web page, for more
information about this class.
16:
17: /**
18: * Create a new TextBoard of size width*height and containing numMines
19: * mines.
20: */
21: public TextBoard(int width, int height, int numMines) {
22: // Don't forget to initialise the superclass!
23: super(width, height, numMines);
24:
25: // Allocate storage for column and row number, and work out how long the
26: // respective strings need to be. Note that the largest column/row number
27: // is actually one less than width/height, respectivaly.
28: colLength = Integer.toString(width-1).length();
29: rowLength = Integer.toString(height-1).length();
30: colNums = new String[width];
31: rowNums = new String[height];
32:
33: // Generate column numbers. These are all padded out to colLength for
34: // ease of printing later on. The numbers are right-justified within the
35: // string.
36: for (int i = 0; i < width; i++) {
37: StringBuffer col = new StringBuffer(Integer.toString(i));
38: while (col.length() < colLength) {
39: col.insert(0, ' ');
40: }
41: colNums[i] = col.toString();
42: }
43:
44: // Generate a spacer for column numbers. Just a string of spaces that
45: // takes up the same space as a row number, for aligning the column
46: // headers correctly.
47: StringBuffer spaces = new StringBuffer();
48: for (int i = 0; i < rowLength + 2; i++) {
49: spaces.append(' ');
50: }
51: spacer = spaces.toString();
52:
53: // Generate row numbers. Exactly the same procedure as the column
54: // numbers, except that we are extra spaces around the number to make the
55: // display more readable.
56: for (int i = 0; i < height; i++) {
57: StringBuffer row = new StringBuffer(Integer.toString(i));
58: while (row.length() <= rowLength) {
59: row.insert(0, ' ');
60: }
61: row.append(' ');
62: rowNums[i] = row.toString();
63: }
64: }
65:
The only other method in the TextBoard class is the
draw method. This implements the abstract method of the
same name from Board and ensures that
TextBoard does not also have to be declared abstract. The
method is quite long-winded, but not really all that complicated. The
state of each cell on the game board itself is represented by a single
character, as described by the comments in lines 67-75.
The only major complication is that, due to the line-based nature or character terminals, we must draw the board in a line-at-a-time fashion. This presents a small problem in the case of the column numbers, which we want to write vertically down the screen, so that each is only one column wide but as tall as it needs to be. The problem is solved by the string-based representation of the column numbers that was generated by the constructor. Recall that each string was padded out to a constant length. If we know that all of the column number strings are (say) three characters long, we know that they will occupy three rows of the terminal when printed in vertical orientation. The first line will contain the first (i.e. the 'leftmost') character of each of the strings, and so on. By making sure that all the strings were the same length, we ensured that we do not run out of characters to print, and that all of the numbers will be aligned correctly.
The rest of the draw method should be fairly
sefl-explanatory. The board cells are handled by the
switch statement in lines 102-126. Below the board, we
print an indication of the number of mines remaining to be found. This
is calculated using the number of mines marked by the player, any
of which might be wrong, so it is unwise to reply too completely on this
number when playing the game.
66:
67: /**
68: * Draw the current state of the board on System.out, as follows:
69: * - An unknown cell is indicated by '#'
70: * - A marked cell is indicated by 'X'
71: * - A revealed mine is indicated by '*'
72: * - A revealed empty cell contains a digit indicating the number of
73: * immediate neighbours containing mines, or '.' if there are no such
74: * neighbours.
75: */
76: public void draw() {
77:
78: // Some space
79: System.out.println();
80:
81: // Do column numbers. We print these out vertically, 'bottom-justified'.
82: // Note the use of the spacer defined in the constructor.
83: for (int i = 0; i < colLength; i++) {
84: System.out.print(spacer);
85: for (int j = 0; j < width; j++) {
86: System.out.print(colNums[j].charAt(i));
87: }
88: System.out.println();
89: }
90:
91: // Some more space
92: System.out.println();
93:
94: // Do rows, complete with numbers
95: for (int i = 0; i < height; i++) {
96: // Print row number. We do this again at the end of the row in case the
97: // board is huge and hard to read.
98: System.out.print(rowNums[i]);
99:
100: // Print something appropriate for the cell
101: for (int j = 0; j < width; j++) {
102: switch (board[j][i]) {
103: case UNKNOWN:
104: System.out.print("#");
105: break;
106: case MARKED:
107: System.out.print("X");
108: break;
109: case MINE:
110: System.out.print("*");
111: break;
112: case 1:
113: case 2:
114: case 3:
115: case 4:
116: case 5:
117: case 6:
118: case 7:
119: case 8:
120: case 9:
121: System.out.print(board[j][i]);
122: break;
123: case 0:
124: System.out.print(".");
125: break;
126: }
127: }
128: System.out.println(rowNums[i]);
129: }
130:
131: // Some more space
132: System.out.println();
133:
134: // Do column numbers, again in case the board is humongous and hard to
135: // read.
136: for (int i = 0; i < colLength; i++) {
137: System.out.print(spacer);
138: for (int j = 0; j < width; j++) {
139: System.out.print(colNums[j].charAt(i));
140: }
141: System.out.println();
142: }
143:
144: // Some more space (surprise)
145: System.out.println();
146:
147: // Display the number of mines left to find. This number reflects the
148: // number of marked mines, any of which might of course be wrong!
149: System.out.println("Mines remaining: " + (getMines() - getMarked()));
150:
151: // Yet more spacing
152: System.out.println();
153: }
154: }
MineSweeper class
The final element of the program is the MineSweeper class,
which is responsible for:
The class makes use of the java.io.StreamTokenizer class
for reading user input and breaking it up into recognisable commands.
If you have not encountered this class before it may be worthwhile
reading through the relevant web-based API documentation and tutorials
before continuing. You can also find the code in the file /import/teaching/BSc/1st/ItP/MineSweeper/MineSweeper.html.
The instance variables of a MineSweeper object are quite
simple. The board variable is a reference to a
Board object, which may of course refer to a
Board, a TextBoard or any other subclass of
Board. As a subclass of Board, every
TextBoard instance is also an instance of
Board. Thus we can safely assign a TextBoard
object to a Board variable. The tok variable
is a reference to the StreamTokenizer object that will be
used to read and parse user commands. The remaining variables are used
to keep track of the state of the game, and in particular whether the
game is over or not.
1: import java.io.*;
2:
3: /**
4: * A basic implementation of the MineSweeper game, using a TextBoard for
5: * display purposes and a StringTokenizer to parse commands entered at the
6: * keyboard. No support yet for anything fancy like high score tables (or
7: * graphics :) We do, however, time how long it takes you to finish the
8: * game.
9: */
10: public class MineSweeper {
11:
12: // The game board
13: private Board board;
14:
15: // Tokenizer for commands
16: private StreamTokenizer tok;
17:
18: // Various flags used by play() and doCommand()
19: private boolean done, quit, win;
20:
21: // Contents of last cell revealed
22: private int lastCell;
23:
The constructor for the MineSweeper class takes the same
parameters as the Board and TextBoard
constructors, and uses these to create a new TextBoard of
the appropriate size. Line 33 creates a new
StreamTokenizer object that will read commands from
System.in (usually the keyboard). Line 35 initialises the
remaining instance variables to suitable starting values.
24:
25: /**
26: * Create and initialise a new game of the given dimensions.
27: */
28: public MineSweeper(int width, int height, int mines) {
29: // Create the game board
30: board = new TextBoard(width, height, mines);
31:
32: // Set up the command tokenizer
33: tok = new StreamTokenizer(new InputStreamReader(System.in));
34:
35: done = win = quit = false;
36: }
37:
The play method is the most important part of the class.
This method is called to start a new game and does not return until the
game is over, for better or worse. The method begins by recording the
start time of the game in line 44, then enters a while loop
that will repeat until the boolean done variable becomes
true (remember that the constructor set this variable to
false). The loop body itself begins by asking the board to
display its current state, using the draw method. Note
that we don't particularly care how it does this -- our current
implementation displays the board as text in the terminal window, but it
could just as easily have drawn a pretty graphical display or sent the
board state to a remote player across the Internet. All of these could
be achieved easily by writing new subclasses of Board. Of
course, our program currently only knows how to deal with a
TextBoard, but it could easily be adapted for other styles
of output.
After displayed the board, the method prompts for a command from the
user. The flush method of System.out is
called to make absolutely sure that all of the text sent to
System.out has actually been displayed (some Java
implementations may not output text requested using
System.out.print until a newline character has been
printed). Line 55 asks the tokeniser to read the next 'token' from the
input stream. For the purposes of this program (and the
StreamTokenizer class), we can define a token as a 'word'
from the input stream, separated from other words by spaces. Thus the
input line:
reveal 11 16
Consists of three tokens: 'reveal', '11' and '16'. The first of these
is clearly a string, while the other two can be treated as strings or
integer values depending upon the language recognised by the program.
The nextToken methods reads the next token from the stream
and stores its value in instance variables of the tokeniser object. One
of these is the ttype variable, which indicates what 'type'
of token was read. The switch statement on lines 58-69
checks this variable and takes appropriate actions:
TT_WORD (a word) we call the
doCommand method to carry out the command identified by
the word.
TT_EOL (end-of-line), indicating
that the user pressed 'Enter' without typing a command, we jump
immediately back to the top of the loop.
TT_EOF (end-of-file), we will assume
that the user has had enough of the game and immediately quit, by
setting the boolean done flag to true.
Once the command, if any, has been acted on, we must check to see if the game has been won or lost. The program checks two conditions:
done and win flags to true to
indicate this.
done
to true but leave the win flag
false in this case. The lastCell variable
is set by doCommand whenever the player reveals a new
cell.
As soon as the game is over, the while loop terminates and
the program falls through to line 87. Here we calculate the total time
elapsed in playing the game and, in lines 90-94, reveal the entire board
so that the player can see where the mines were really hiding.
Line 97 redraws the board in its fully revealed state. Lines 98-103
print out an appropriate message depending upon whether or not the
player won the game, and line 104 displays the total game time
calculated back in line 87. After this, the method returns to its
caller and the game is over.
38:
39: /**
40: * Main game loop.
41: */
42: public void play() throws IOException {
43: // Start the clock
44: long startTime = System.currentTimeMillis();
45:
46: // Loop until game over, for whatever reason
47: while (!done) {
48:
49: // Redraw board
50: board.draw();
51:
52: // Get next command
53: System.out.print("Command: ");
54: System.out.flush();
55: tok.nextToken();
56:
57: // Dispatch on command
58: switch (tok.ttype) {
59: case StreamTokenizer.TT_WORD:
60: doCommand();
61: break;
62: case StreamTokenizer.TT_EOL:
63: continue;
64: case StreamTokenizer.TT_EOF:
65: done = quit = true;
66: break;
67: default:
68: System.out.println("Unknown command -- try 'help'");
69: }
70:
71: // Check whether the game is up. If the number of unknown cells = the
72: // number of mines, you must have won (by finding all the mines). If,
73: // on the other hand, you revealed a mine, time to die :(
74: if (board.getUnknown() == board.getMines()) {
75: done = win = true;
76: }
77: else if (lastCell == Board.MINE) {
78: done = true;
79: }
80:
81: // Suck any remaining crap out of the input stream. I'm not sure that
82: // this works properly (not on my machine, at least).
83: System.in.skip(System.in.available());
84: }
85:
86: // Game over, one way or another. Figure out how long it took
87: long elapsedTime = System.currentTimeMillis() - startTime;
88:
89: // Reveal everything, just so the stats are correct
90: for (int i = 0; i < board.getWidth(); i++) {
91: for (int j = 0; j < board.getHeight(); j++) {
92: board.reveal(i, j);
93: }
94: }
95:
96: // Redraw the board and print out some messages
97: board.draw();
98: if (win) {
99: System.out.println("Congratulations -- you found all the mines!");
100: }
101: else if (!quit) {
102: System.out.println("Bad luck -- you stepped on a mine!");
103: }
104: System.out.println("Total game time: "+(elapsedTime/1000)+" seconds");
105: }
106:
The doCommand method is responsible for processing commands
entered by the player. The play method assumes that
whenever a token of type TT_WORD is read, this is the start
of a command; it then calls doCommand to read the rest of
the command and carry out the appropriate action(s).
doCommand is structured as a large if..else
if..else statement, with one if clause for each of
the available commands, and a final else to cover the
situation where the command is not recognised. The presence of a
particular command is tested for by looking at the sval
variable of the StringTokenizer object. This holds the
string value of the last token to be read. We will examine the code for
the 'reveal' command: the other commands are quite similar.
The 'reveal' command requires two further pieces of information: the co-ordinates of the cell to be revealed. thus, we expect to be able to read two integer values immediately following the 'reveal' keyword, e.g:
reveal 11 6
would reveal the contents of the cell at position (11,6). As before,
the nextToken method is used to read the tokens. The
StringTokenizer will automatically convert the strings it
reads into numeric values, where this is possible. A numeric token is
stored in the nval variable of the tokeniser rather than
the sval used for strings. Two token are read, and their
numberic values cast to type int and stored in the two
local variables x and y. We then call the
reveal method of the game board with the given
co-ordinates, and store the contents of the cell thus revealed into the
instance variable lastToken -- remember that this is needed
by the play method to determine if the game is over of
not. Finally, if the cell revealed was not a mine, and had no explosive
neighbours, we call the revealMore method of the board to
uncover more cells in the surrounding area.
Between them, play and doCommand implement a
simple parser, a program that reads a stream of token and assigns
some higher-level meaning to them, in accordance with a 'language'
recognised by the parser. The language recognised by our parser is
lines of the form:
command [ arg ... ]
where the command is one of a small set of recognised
keywords, and the args are extra parameters to that
command. The number and format of the arguments is particular to each
command. The parser can recognise and respond accordingly to any string
that is in its language; any input that is unrecognised will be rejected.
None of the commands implemented by doCommand perform any
error checking. For example, it is unclear how the program will behave
if the 'reveal' keyword is not followed by two integer values
(you may want to try this!). Likewise, we do not ensure that the
co-ordinates given are within the size of the board. Of course, the
Board object may perform that particular check, but we
cannot know that for certain unless it is stated in the
Board documentation or code.
107:
108: /**
109: * Process commands. 'Help' gives a summary of the huge range of available
110: * commands.
111: */
112: private void doCommand() throws IOException {
113: int x, y;
114:
115: if (tok.sval.equals("reveal")) {
116: // Reveal a cell (and perhaps some around it)
117: tok.nextToken();
118: x = (int)tok.nval;
119: tok.nextToken();
120: y = (int)tok.nval;
121: lastCell = board.reveal(x, y);
122: if (lastCell == 0) {
123: board.revealMore(x, y);
124: }
125: }
126: else if (tok.sval.equals("mark")) {
127: // Mark a cell
128: tok.nextToken();
129: x = (int)tok.nval;
130: tok.nextToken();
131: y = (int)tok.nval;
132: board.mark(x, y);
133: }
134: else if (tok.sval.equals("unmark")) {
135: // Unmark a cell
136: tok.nextToken();
137: x = (int)tok.nval;
138: tok.nextToken();
139: y = (int)tok.nval;
140: board.unmark(x, y);
141: }
142: else if (tok.sval.equals("help")) {
143: // Print some help
144: System.out.println("reveal x y");
145: System.out.println("mark x y");
146: System.out.println("unmark x y");
147: System.out.println("help");
148: System.out.println("quit");
149: }
150: else if (tok.sval.equals("quit")) {
151: // Quit and die
152: quit = done = true;
153: }
154: else {
155: System.out.println("Unknown command -- try 'help'");
156: }
157: }
158:
Finally we come to the main program! This is almost trivial in comparison with the rest of the code. The program makes use of command line parameters to obtain the size of the board, and the number of mines to place on it, from the user. Command line parameters are extra information given on the UNIX or DOS command line following the class name in a 'java' command. For example, the command
java MineSweeper 20 20 15
instructs the operating system to run a command called 'java', and to
pass it four extra parameters: 'MineSweeper', '20', '20' and '15'.
Java, in turn, takes its first parameter as the name of a class to run,
and will pass the remaining command line parameters as arguments to the
main method of that class. In this case, Java will load
the MineSweeper class and call its main method
with three parameters: '20', '20' and '15'. The parameters can be
accessed as the elements of the array of strings passed to the
main method (you have been wondering what that was for,
right?). In our example the contents of the array will be:
args[0] = "20", args[1] = "20" and
args[2] = "15". Note that the parameters values are all
treated as strings unless you convert them to something else.
The program begins by checking that the argument array contains enough
parameters: there must be at least three. If insufficient parameters
were given, the program prints a brief message telling the user how to
run the program correctly, then exits. Otherwise, the convert the three
parameters to their integer equivalents, create a new
MineSweeper object and call its play method to
start the game.
And that's all there is to it!
159:
160: /**
161: * Main program to start and run a new game. Expects three command line
162: * parameters: width, height and mine count.
163: */
164: public static void main(String[] args) throws IOException {
165:
166: MineSweeper game;
167:
168: if (args.length < 3) {
169: System.out.println("Usage: java MineSweeper width height mines");
170: System.exit(0);
171: }
172: else {
173: int width = Integer.parseInt(args[0]);
174: int height = Integer.parseInt(args[1]);
175: int mines = Integer.parseInt(args[2]);
176: game = new MineSweeper(width, height, mines);
177: game.play();
178: }
179: }
180: }
The following exercises describe some extensions to the program that you might like to try implementing. They are arranged in (approximate) order of difficulty.
Keep track of the number of moves the player has made, and display this value before each new move is entered.
Implement a continuous timer facility, so that the player can see how long they have been playing the game before each move.
Add a 'high score table', listing the players who complete the game in the shortest time or smallest number of moves, for a given board size. The table should be stored in a file so that it is remembered between runs of the program.
Add appropriate error-checking code to all of the classes. This would include checking that all (x, y) co-ordinates are within the size of the game board, that the number of mines is less than (or equal to) the number of cells on the board, and that the commands are entered correctly.
Implement a multi-player version of the game, where two or more players are attempting to solve the same board simultaneously. It is probably easiest to have the players take turns on the same terminal window; it is up to you whether to rank players based on the number of moves or total time taken to complete the game (this is is quite difficult).
Add a graphical user interface to the game. You will need to read up on Java's graphics and interface toolkit classes, and restructure the program somewhat (this one is very difficult)!
These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.
Last modified: Mon Nov 23 13:32:29 GMT 1998