-
Notifications
You must be signed in to change notification settings - Fork 1
/
maze_dfs_back.js
154 lines (141 loc) · 4.61 KB
/
maze_dfs_back.js
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
// 采用DFS + Back的方法构建
// 迷宫的一个小方格作为一个cell,cell四边称作墙
// Step1: 选择开始的cell,设置访问过标记
// Step2: 如果还有未访问过的cell
// Step2.1: 如果当前cell有一些邻居没有访问过,随机选择一个未访问过的邻居,将当前cell加入栈,拆掉当前cell和选择的邻居之间的墙,将选择的邻居设置为当前cell,设置为已访问
// Step2.2: 如果当前cell所有邻居都访问过了,且如果栈非空,那么从栈里面pop出一个cell,设置为当前cell
var mp; // mazePanel 保存迷宫的方格cell相关数据结构
var maze; // constructMaze 构建迷宫
function setup(){
createCanvas(500, 500);
var s = 20; // 小方格大小
var m = floor(height / s);
var n = floor(width / s);
mp = new mazePanel(s, m, n); // mp mp.grids是个二维数组
for(var i = 0; i < m; i++){
var rowGrids = [];
for(var j = 0; j < n; j++){
rowGrids.push(new cell(i, j, s));
}
mp.grids.push(rowGrids);
}
maze = new constructMaze(mp, 0, 0);
}
function draw() {
background(255);
maze.constructOneStep(); // 逐步构建
displayMaze(); // 显示
}
// 每个小方格cell
function cell(i, j, s){
this.i = i; // 行坐标
this.j = j; // 列坐标
this.size = s; // 大小
this.visited = false; // 是否访问过
this.visible = [true, true, true, true]; // 上 右 下 左
this.display = function(){
stroke(0);
strokeWeight(2);
if(this.visible[0]){
line(this.j * this.size, this.i * this.size, (this.j + 1) * this.size, this.i * this.size);
}
if(this.visible[1]){
line((this.j + 1) * this.size, this.i * this.size, (this.j + 1) * this.size, (this.i + 1) * this.size);
}
if(this.visible[2]){
line(this.j * this.size, (this.i + 1) * this.size, (this.j + 1) * this.size, (this.i + 1) * this.size);
}
if(this.visible[3]){
line(this.j * this.size, this.i * this.size, this.j * this.size, (this.i + 1) * this.size);
}
}
this.paint = function(){
fill(255, 0, 0);
rect(this.j * this.size, this.i * this.size, this.size, this.size);
}
this.setInvisible = function(d){
this.visible[d] = false;
}
this.setVisited = function(){
this.visited = true;
}
}
// 迷宫数据结构
function mazePanel(s, m, n){
this.size = s;
this.rows = m;
this.cols = n;
this.grids = [];
}
// 展示
function displayMaze(){
for(var i = 0; i < mp.rows; i++){
for(var j = 0; j < mp.cols; j++){
mp.grids[i][j].display();
}
}
maze.mp.grids[maze.starti][maze.startj].paint();
}
// 构建迷宫的数据结构
function constructMaze(mazePanel, i, j){
this.mp = mazePanel;
this.starti = i;
this.startj = j;
this.stack = [new cell(i, j, mazePanel.size)]; // 栈,DFS的关键,用于回溯
this.xstep = [0, 0, 1, -1];
this.ystep = [-1, 1, 0, 0];
this.finished = false;
// 下一步
this.constructOneStep = function(){
if(this.finished){
return;
}
var candiNeis = []; // 未访问过的邻居
var hasNeis = false;
for(var k = 0; k < 4; k++){
var nei = this.starti + this.xstep[k];
var nej = this.startj + this.ystep[k];
if(nei >= 0 && nei < this.mp.rows && nej >= 0 && nej < this.mp.cols && this.mp.grids[nei][nej].visited == false){
hasNeis = true;
candiNeis.push(this.mp.grids[nei][nej]);
}
}
if(hasNeis == false){
var len = this.stack.length;
if(len > 1){
this.starti = this.stack[len - 1].i;
this.startj = this.stack[len - 1].j;
this.stack.splice(len - 1, 1); // 出栈
}else{
this.finished = true;
}
}else{
var ri = floor(random(candiNeis.length));
var neiCell = candiNeis[ri];
this.stack.push(neiCell);
this.breakWall(this.starti, this.startj, neiCell.i, neiCell.j); // 拆墙
this.starti = neiCell.i;
this.startj = neiCell.j;
this.mp.grids[neiCell.i][neiCell.j].setVisited(); // 设置为已访问
}
}
// 拆掉两个方格之间的墙
this.breakWall = function(i1, j1, i2, j2){
if(i2 == i1 - 1 && j1 == j2){
this.mp.grids[i1][j1].setInvisible(0);
this.mp.grids[i2][j2].setInvisible(2);
}
if(i2 == i1 + 1 && j1 == j2){
this.mp.grids[i1][j1].setInvisible(2);
this.mp.grids[i2][j2].setInvisible(0);
}
if(i2 == i1 && j2 == j1 - 1){
this.mp.grids[i1][j1].setInvisible(3);
this.mp.grids[i2][j2].setInvisible(1);
}
if(i2 == i1 && j2 == j1 + 1){
this.mp.grids[i1][j1].setInvisible(1);
this.mp.grids[i2][j2].setInvisible(3);
}
}
}