Java代写：COMS227 Minesweeper

发表于   |   分类于

Introduction

作业要求实现一个Minesweeper，即扫雷游戏。这个作业侧重点在clearRegion算法，也就是当点击到board中cell为0的时候的展开逻辑。
代码自带了部分的用Java写的GUI，不过board的逻辑部分可以通过测试集来验证。

Background

This part of the documentation provides a detailed description and examples for the clearRegion algorithm, which is part of Assignment 2.
When selecting a cell with count zero, we need to find all its neighboring cells that have count zero, and all their neighboring cells that have count zero, and so on. For the purposes of this algorithm, we only consider the four non-diagonal neighbors. Also, for the moment we will concentrate only on the cells that actually have count zero and ignore the “boundary” cells
around the region (shown in a lighter cyan color in previous illustrations). Dealing with the boundary cells turns out to be easy.
Here is the basic idea. Suppose we start at a cell c that has count zero. Before we reveal c, we need to explore its four neighbors to see whether any of them also has count zero. Say we start by looking at the cell d that is directly above c. If d also has count zero, we have a conundrum: we now need to explore all the neighbors of cell d. Again suppose we start looking at the cell e above d. Somehow, we have to remember to eventually go back and continue exploring the other neighbors of d, as well as the other neighbors of c.
The general solution is that each time we encounter a cell with count zero, if we haven’t already seen it we save it in a “things to do list”, and then start exploring its non-diagonal neighbors. Eventually we must reach a cell whose non-diagonal neighbors have counts greater than zero, or have already been seen. At that point, we mark it as REVEALED, remove it from the to-do list, and resume where we left off with the previous cell in the list.
There are two basic strategies for implementation: using an explicit to-do list, or using recursion. The code using recursion is shorter, but may be more difficult to understand at first. Understanding the the to-do list version will help you understand recursion. (Recursion will be covered in class during the week after break.)
To support this there are 5 additional Status values that a cell can take on:

  • SEEN - the cell has been added to the list, but we have not looked at its neighbors
  • EXPLORING_UP - we are exploring the cell above
  • EXPLORING_LEFT - we are exploring the cell to the left
  • EXPLORING_DOWN - we are exploring the cell below
  • EXPLORING_RIGHT - we are exploring the cell to the right

We require that each of these values be assigned in exactly in the order given above.
The last few pages of this document contain a detailed example with screenshots from the GUI animation and a picture of the contents of the to-do list.

About the GUI animation

A secondary purpose of the five Status values above is to enable the GUI to animate the progress of the algorithm. Animation is enabled by constructing the GUI with a sleepTime parameter that is greater than zero, and then checking the “Animate” check box on the GUI window. Each time a cell’s status changes, the GUI is notified, and the execution is delayed for sleepTime milliseconds.

Recursive implementation

The recursive version of the algorithm performs exactly the same sequence of cell updates as the version above using a to-do list. The difference is that we don’t have to explicitly add cells to a list. Instead, we just call clearRegion for the neighboring cell. The call stack automatically keeps track of where we need to resume exploration of a previously seen cell.
You might notice in the algorithm below that the changes in the cell status, other than the final change to REVEALED, seem to be unnecessary for the algorithm to work. That is true; however, we still require the status changes in order to support the animation.

The boundary cells

The algorithm described above an illustrated at the end of this document will just reveal a connected region of cells that have value zero.
This turns out to be easy. Just call GridUtil.revealNeighbors whenever setting a zero cell to REVEALED (the line marked (*) in the pseudocode above).

Diagonal connections

The clearRegion algorithm is defined to reveal a connected region of zeros, plus the boundary of nonzero cells. What about a grid like this one? Is the zero cell at (1, 1) part of the same region as the zero cell at (2, 2)?
According to our specification, only the zero cells that are reachable via up, left, bottom, or right neighbors are explored. We also specify that the only boundary cells revealed are those with count greater than zero.
Please note, this is not the same as many other available implementations of Minesweeper. We are specifying it this way to simplify the description and implementation of the algorithm.

Detailed example of clearRegion

Here is a detailed example. Suppose we start with the grid shown below, with all cells initially HIDDEN, and we call clearRegion at row 4, column 0, denoted (4, 0). To initialize, cell (4, 0) is set to status SEEN and put on the list (the list is shown below the grid).
Now the while-loop begins. We look at the end of the list, find a cell with status SEEN, so change it to EXPLORING_UP. Since the cell above has count zero and is still HIDDEN, we change it to SEEN and add it to the end of the list. (In the picture, the EXPLORING_UP status is shown with a vertical line.)
Back to the top of the loop. Look at the end of the list. The cell there has status SEEN, so change it to EXPLORING_UP. The cell above has count zero, change it to SEEN and add to the end of the list.

  • Cell at the end of the list is SEEN, so change it to EXPLORING_UP. The cell above has count 2, so it is not added to the list.
  • Cell at the end of the list is EXPLORING_UP, so change it to EXPLORING_LEFT. Cell to left is nonexistent, so nothing to add to list.
  • Cell at the end of the list is EXPLORING_LEFT, so change it to EXPLORING_DOWN. Cell below is already seen (i.e. not HIDDEN), so not added to list.
  • Cell at the end of the list is EXPLORING_DOWN, so change it to EXPLORING_RIGHT. Cell at right does not have count zero, so not added to list.
  • Cell at end of list is EXPLORING_RIGHT, so change it to REVEALED and remove from list.
  • Cell at the end of the list is EXPLORING_UP, so change it to EXPLORING_LEFT. Cell to left is nonexistent, so nothing to add to list.
  • Cell at the end of the list is EXPLORING_LEFT, so change it to EXPLORING_DOWN. Cell below is already seen (i.e. not HIDDEN), so not added to list.
  • Cell at the end of the list is EXPLORING_DOWN, so change it to EXPLORING_RIGHT. Cell at right is HIDDEN and has count zero, so change it to SEEN and add it to list.
  • Fast-forward through a few steps: Cell (3, 1) transitions through EXPLORING_UP, EXPLORING_LEFT, EXPLORING_DOWN, EXPLORING_RIGHT, and finally REVEALED, and is removed from the end of the list.
  • Cell at end of list is EXPLORING_RIGHT, so change it to REVEALED and remove from list.
  • Cell at the end of the list is EXPLORING_UP, so change it to EXPLORING_LEFT. Cell to left is nonexistent, so nothing to add to list.
  • Cell at the end of the list is EXPLORING_LEFT, so change it to EXPLORING_DOWN. Cell below is HIDDEN and has count zero, so change to SEEN and add to list.
  • Fast-forward through a few steps: Cell (5, 0) transitions through EXPLORING_UP, EXPLORING_LEFT, EXPLORING_DOWN, EXPLORING_RIGHT, and finally REVEALED, and is removed from the end of the list.
  • Cell at the end of the list is EXPLORING_DOWN, so change it to EXPLORING_RIGHT. Cell at right does not have count zero, so not added to list.
  • Cell at the end of the list is EXPLORING_RIGHT, so change it to REVEALED and remove from list.

Now the list is empty, and the loop ends.