The MineSweeper Program The MineSweeper Program 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: Basic syntax and layout conventions for Java programs. Java arithmetic and logical (Boolean, true/false) expressions. Simple Java text I/O: BufferedReaders, System.out, etc. Iteration statements: for and while loops. Decision statements: if and switch. Some basic concepts of object-oriented programming: objects, classes and inheritance. 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/ Rules of the game 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: The program will indicate how many of the revealed cell's eight neighbours do contain mines. Any neighbouring empty cells will also be revealed in the same way. 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. Program overview 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. The Board class Obviously 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: What data structures should we use to represent the state of the game board? What operations should we provide to manipulate the state of the game board? What representation of the board state should be made available to the rest of the program? How should the board be presented to the user of the program? 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: }
The 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: }
The MineSweeper class The final element of the program is the MineSweeper class, which is responsible for: Creating all of the objects needed for the game. Reading and interpreting user commands. Providing (and following) a consistent set of game rules. 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: If the token type is TT_WORD (a word) we call the doCommand method to carry out the command identified by the word. If the token type is 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. If the token type is 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. If any other token type is seen, we print an error message and try again. 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: If the number of unknown cells is equal to the number of mines, then all the unknown cells must contain mines. This means that the player has found all of the mines, without stepping on any of them, and therefore that they have won the game. We set both the done and win flags to true to indicate this. If, on the other hand, the last cell to be revealed by the player was a mine, the player has unfortunately lost. We set 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: }
Extensions and Exercises 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)! Scott Mitchell 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
