讲讲我在实现扫雷游戏时用到的算法,包括 Knuth shuffle、Union Find 和 Flood Fill。

可以在GitHub下载体验,Emoji Mines 是一年前就完成的作品。今天把雷生成的算法改了改,游戏体验变好许多,遂又向女胖友推销自己游戏(笑

在阅读之前假设你已可以熟悉扫雷的游戏规则。为了方便描述,将扫雷游戏中的方块分为:空白方块(即周围都没有雷方块的方块)、数字方块和雷方块。

雷的生成

雷的生成要保证随机,游戏体验才会好。游戏刚开始的阶段,也可以快速标记雷的位置。

替换法

替换法也就是把一个方块随机替换为雷,知道所有雷都放置完成。但是实际玩耍起来,体验不是很好,根本看不出哪个是雷,全靠盲猜。这样肯定要怀疑这个算法(特指下面实现方法)的随机性的,也不知道是不是Random的锅。

1
2
3
4
5
6
7
8
9
10
11
12
private void genRandomMines(int mineSize) {
Random random = new Random(System.currentTimeMillis());
while (mines.size() != mineSize) {
// [0, 63]
int nextMine = random.nextInt(size * size);
Point point = oneD2point(nextMine);
if (!mines.contains(point)) {
board[point.x][point.y] = true;
mines.add(point);
}
}
}

洗牌法

然后一年过去,在知乎上偶然看到关于雷生成的算法,里面提到了洗牌法(shuffle)。使用的是 Knuth shuffle ,简单的说就是遍历数组,随机交换两个元素:

1
2
3
for i from 0 to n−2 do
j ← random integer such that i ≤ j < n
exchange a[i] and a[j]

洗牌法分为两步:

  • 首先将雷按序填入游戏地图
  • 再使用 Knuth shuffle 打乱顺序

为了更好的游戏体验,下面算法可以实现第一次点击时,不会碰到雷。不过这也意味着雷的生成要推迟到第一次点击时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  // ensure excludePoint is not mine
private void genRandomMinesEnsured(int mineSize, Point excludePoint) {
// fill mines
int minesCnt = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == excludePoint.x && j == excludePoint.y) continue;
board[i][j] = true;
minesCnt++;
if (minesCnt == mineSize) break;
}
if (minesCnt == mineSize) break;
}
// shuffle array
Random random = new Random(System.currentTimeMillis());
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
int randomPoint = random.nextInt(size * size);
Point point = oneD2point(randomPoint);
if (i == excludePoint.x && j == excludePoint.y || point.equals(excludePoint)) continue;
boolean temp = board[point.x][point.y];
board[point.x][point.y] = board[i][j];
board[i][j] = temp;
}
}
}

空白区域

当点击空白方块,会连带出所有连通的空白方块和周围的数字方块。如下图所示:

mines-blank

这里有两种算法可以选择,也就是文章题目中的:Union Find 和 Flood Fill 。

Union Find

使用 Union Find 来实现连带空白方块是我最初的想法。在学习 Union Find 这个算法的时候,就想到:“诶,这个好像可以用在扫雷里吧”。之后,用了一晚上的时间写出了使用 Union Find 实现的扫雷。也是第一次觉得算法还是有用的(

Union Find API

初始化,每个节点各自成一个连通块:

1
2
3
4
> for (int i = 0; i < n; i++) {
> parent[i] = i;
> }
>
  • union:连接两个连通块。将两个节点设置为同一个root
1
2
3
4
5
6
7
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
  • connected:判断两个连通块是否相连。相同root的两个连通块就是连通的。
1
2
3
4
5
6
7
8
9
public int find(int p) {
validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}

应用到扫雷游戏

我们可以利用union操作将全部空白方块合成一个连通块,到我们点击到一个空白方块时,遍历游戏地图,将与其连通的空白方块都显示出来。因为游戏地图为二维数组,需要将二维坐标转化为一维坐标。

联合所有空白方块:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private void unionAllBlankBlock() {
//as known, [i, j] is already a blank.
for (int row = 0; row < size; row++) {
for (int col = 0; col < size; col++) {
if (isBlank(row, col)) {
int thisPoint = xyTo1D(row, col);
// top
if (isBlank(row - 1, col)) {
unionUF.union(thisPoint, xyTo1D(row, col));
}
// left
if (isBlank(row - 1, col)) {
unionUF.union(thisPoint, xyTo1D(row - 1, col));
}
// bottom
if (isBlank(row, col + 1)) {
unionUF.union(thisPoint, xyTo1D(row, col + 1));
}
// right
if (isBlank(row + 1, col)) {
unionUF.union(thisPoint, xyTo1D(row + 1, col));
}
}
}
}
}

显示和当前空白方块相连的空白方块:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void showUnionBlankBlock(Point point) {
if (isFirstTimeBlankClick) {
unionAllBlankBlock();
isFirstTimeBlankClick = false;
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
// 判断是否相连
if (unionUF.connected(xyTo1D(point.x, point.y), xyTo1D(i, j))) {
Point p = new Point(i, j);
// 显示空白方块
setBlankBox(p);
// 显示周围的数字
showNumberAroundBlank(i, j);
clearFlag(p);
}
}
}
}

Flood Fill

Flood Fill(平铺算法?)其实就是个DFS,递归遍历四连通的方块,并将其标记。同样可以用来连带出所有连通的空白方块。

因为我的游戏已经使用 Union Find 实现,而且自己当时写的代码扩展性较差,如果要换算法,大概要全部重写。所以这里用一个简单的例子介绍 Flood Fill 算法。

假设有游戏地图如下:

flood-fill-example

当我们点击坐标(5, 4)时,可以连带出5个空白方块组成的连通块(下方的T型)。

这个游戏地图用二维数组表示,把雷用“9”表示,因为一个方块周围最多有8个雷;已经展示的空白方块用“10”表示,防止重复遍历。

1
2
3
4
5
6
7
8
9
10
int[][] board = new int[][]{
{0, 0, 1, 1, 2, 9, 1, 0},
{1, 1, 2, 9, 3, 2, 2, 0},
{1, 9, 3, 2, 3, 9, 2, 1},
{1, 1, 2, 9, 2, 2, 9, 1},
{1, 1, 2, 1, 1, 1, 2, 2},
{1, 9, 1, 0, 0, 0, 1, 9},
{1, 2, 2, 1, 0, 1, 2, 2},
{0, 1, 9, 1, 0, 1, 9, 1}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
public void floodFill(int[][] board, int x, int y) {
if (x < 0 || x >= rows || y < 0 || y >= cols) return;
if (board[x][y] != 0) return;
// show blank box
board[x][y] = 10; // showed
System.out.printf("show blank: (%d, %d)\n", x, y);
showNumberAroundBlank(board, x, y);
// DFS right, left, up, down
floodFill(board, x + 1, y);
floodFill(board, x - 1, y);
floodFill(board, x, y + 1);
floodFill(board, x, y - 1);
}

输出如下:

1
2
3
4
5
show blank: (5, 4)
show blank: (6, 4)
show blank: (7, 4)
show blank: (5, 5)
show blank: (5, 3)

使用哪个算法

首先还是推荐使用 Flood Fill 算法,因为它更加适合这个场景,实现简单。

使用 Union Find 我们还要进行坐标转化、额外的存储空间、连带时需要遍历整个地图。所以整个连带操作的时间复杂度为O(row*col*lg(row*col))