使用 Vue 写的扫雷小游戏：MineSweeper
前言
最近在写扫雷小游戏，涉及到了对方格进行连锁点开的操作，具体逻辑就是，点击一个格子，如果这个格子不是地雷且周围 3×3 范围内的另外八个方格中也没有地雷，即minesNearBy 值为 0，则将其周围的同样为 0 的格子也连锁点开，实现如下图所示的效果
图中未显示数字的白色方格的minesNearBy都为 0，并且相互连通
这立刻就让我想到了最近新学的着色法，也就是大名鼎鼎的FloodFill“漫水填充法”。
漫水填充法
漫水填充算法，顾名思义就像洪水漫过一样，把一块连通的区域填满。在图像处理中就是给定一个起始点，向附近相邻的像素点扩散，把颜色相同或者相近的所有点都找出来，并填充上新的颜色，这些点形成一个连通的区域。
漫水填充算法可以用来标记或者分离图像的一部分，Windows画图中的油漆桶工具以及PhotoShop中的魔棒工具的核心思想也是基于漫水填充法的思想来实现的。
漫水填充法本质上也是基于深度优先搜索算法(DFS)实现的，DFS 是一种递归算法，它的运行机制就在于规定好当前应该做什么，而下一步应该做的和当前所做的实际上是一样的事情，只是作用范围有所改变。DFS 的基本模型如下：
1
2
3
4
5
6
7
8
9
10
|
function DFS(args) {
判断条件是否越界 {
是 => 结束遍历(return)
否 => 尝试每一种可能 {
DFS(args + 1)
// 递归调用函数
}
}
结束遍历(return)
}
|
基于这种思维，我们重新看一看开头提到的问题，为了解决连锁点开，首先要定义好当前应该做什么
对于任何一个阶段，当前应该做的是：
- 打开格子，并遍历判断周围格子，如果周围格子中也有符合要求的，则对其进行相同操作
当前应该做的已经做完了，而下一步应该做的，实际上和当前应该做的是同样的事情，即
- 以下一个格子为中心，对下一个格子周围的格子进行判断，有满足要求的就对其进行同样操作
这就是递归的精髓，即反复自己调用自己，不断推进，直到最后被执行的函数有了返回值，再从后往前不断回归，直到第一个执行的函数也完成返回，最终获取值。这一过程类似于一下代码，只有最内层的fn(1)被执行了，我们才能得到倒数第二层fn()的值，从内往外回归，最终得到最外层的函数值
1
2
3
4
|
function fn(n) {
return n + 1;
}
fn(fn(fn(fn(fn(fn(1)))))); // 7
|
如何运用
正如之前分析过的，我们需要判断一个格子周围是否有地雷，就要对符合要求的格子的四周进行遍历。这里会出现一个问题，一个格子可能被周围的其他格子遍历好几次，这显然是极其影响效率的，所以我们给每个格子加上一个tempFlag属性，用于标记该格子是否已经被遍历过。
对于遍历的方法，考虑连通性我们只需要对一个格子的上 下 左 右四个方位进行判定，如下图结构：
我们用一个二维数组来储存其周围四个格子的相对位置：
1
2
3
4
5
6
|
let directions = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
|
这样我们就可以用directions[i][0]表示 x 方向的偏移,用directions[i][1]来表示 y 方向的偏移，如下：
1
2
3
4
|
for (let i = 0; i < 4; i++) {
let tx = x + directions[i][0];
let ty = y + directions[i][1];
}
|
这样就可以实现只对四个方向的遍历了，接下来补全一下完整代码
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
27
28
|
dfs(x, y) {
// 预先写好的打开单个格子的方法，这里不必在意具体内容
// 调用这个方法的格子一定是为0的格子，所以直接执行打开就行
this.openBlankBlock(x, y);
let directions = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
for (let i = 0; i < 4; i++) {
// 对四个方向进行遍历
let tx = x + directions[i][0];
let ty = y + directions[i][1];
// 判断坐标，如果越界了则直接跳过该轮，n为矩阵阶数
if (tx < 0 || tx >= this.n || ty < 0 || ty >= this.n) continue;
// 判断当前格子是否为0以及是否被标记为已遍历
if (
this.blocks[tx][ty].minesNearBy == 0 &&
this.blocks[tx][ty].tempFlag == 0
) {
// 把当前标记为已遍历（1），并以这个格子为中心开始新一轮遍历
this.blocks[tx][ty].tempFlag = 1;
this.dfs(tx, ty);
}
}
return;
}
|
这样我们就实现了对格子的连锁打开功能了，或许开始时有点难以理解，但这的确完完整整地实现了这一功能。
递归算法的核心就在于，每一次执行的操作实际上是相同的，只不过操作的对象发生了改变，在上述代码中就是dfs(x,y)变成了dfs(tx,ty)，而已，而对不同格子执行的是相同的方法。
而这个边缘显示数字的效果，实际上就是在最内层的 dfs 方法中实现的，因为返回了的 dfs 一定是周围存在有数字的格子，并且身边所有的格子都被标记过了的。换句话说就是“无路可走”的格子，那么这样来看，这些“无路可走”的格子一定是紧挨着数字的。那么我们就只需要把边缘显示的代码放在return前面就行了，而内部的格子周围的格子一定不存在不等于 0 的情况，所以不需要考虑（这里也可以先行判断，可以进一步提升效率）
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
dfs(x, y) {
// 预先写好的打开单个格子的方法，这里不必在意具体内容
// 调用这个方法的格子一定是为0的格子，所以直接执行打开就行
this.openBlankBlock(x, y);
let directions = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
for (let i = 0; i < 4; i++) {
// 对四个方向进行遍历
let tx = x + directions[i][0];
let ty = y + directions[i][1];
// 判断坐标，如果越界了则直接跳过该轮，n为矩阵阶数
if (tx < 0 || tx >= this.n || ty < 0 || ty >= this.n) continue;
// 判断当前格子是否为0以及是否被标记为已遍历
if (
this.blocks[tx][ty].minesNearBy == 0 &&
this.blocks[tx][ty].tempFlag == 0
) {
// 把当前标记为已遍历（1），并以这个格子为中心开始新一轮遍历
this.blocks[tx][ty].tempFlag = 1;
this.dfs(tx, ty);
}
}
// 在这里对八个方向进行遍历，因为我希望让数字是连通的
directions = [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 1],
[1, -1],
[1, 0],
[1, 1],
];
for (let i = 0; i < 8; i++) {
let tx = x + directions[i][0];
let ty = y + directions[i][1];
// 越界了直接跳过该轮
if (tx < 0 || tx >= this.n || ty < 0 || ty >= this.n) continue;
// 如果当前格子不为0，则把它显示出来
if (this.blocks[tx][ty].minesNearBy != 0) {
this.showEdge(tx, ty);
}
}
return;
}
|
如此，我们就用 DFS 解决了扫雷中空白格连锁打开的问题。
