使用 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 解决了扫雷中空白格连锁打开的问题。