缘起：
去年（大三上学期）比较喜欢写小游戏，于是想试着写个迷宫试一下。
程序效果：
按下空格显示路径：
思考过程：
迷宫由一个一个格子组成，要求从入口到出口只有一条路径.
想了一下各种数据结构，似乎树是比较合适的，从根节点到每一个子节点都只有一条路径。假设入口是根节点，出口是树中某个子节点，那么，从根节点到该子节点的路径肯定是唯一的。
所以如果能构造一棵树把所有的格子都覆盖到，也就能够做出一个迷宫了。
另外还要求树的父节点和子节点必须是界面上相邻的格子。
在界面显示时，父节点和子节点之间共用的边不画，其他的边都画出来，就能画出一个迷宫。
之后就是想一下该怎么实现这样一棵树。
首要的两个问题：
1、树怎么表示？
2、怎么构造这棵树？
1.树怎么表示？
假设像写二叉树一样实现这棵树，那么每个树节点里就要存储一个坐标（X,Y）表示一个格子，另外还要存储四个指针。指针中有的为空，有的不为空，不为空的指针指向子节点，子节点保存邻居格子的坐标。这样做最大的问题是无法判定是否所有的格子都在树中。也许还要用一个二维数组作标志数组。
假如用二维数组表示迷宫的格子。每个数组元素存储一个指向父节点的引用，这样也可以形成一个虚拟的树。于是就用一个N*N的二维数组，表示N*N个格子，每个数组元素(Lattice)中有一个指向父节点的引用(father)。另外，为了能方便的获取格子的坐标，还要保存坐标信息。
2.怎么构造这棵树？
首先选定一个格子作为根节点。为了让迷宫的形状够随机，我选择随机生成一个坐标作为根节点。其实，选择确定的一个坐标也可以。
然后，怎样往这棵树上增加节点呢？
在这里我走了不少弯路，一开始想的是一种现在看来类似回溯的算法（当时还不知道回溯算法。。），但是时间复杂度很高，大概当迷宫为64*64的时候，算法就不出结果了。
然后，又使用了一种扫深度搜索也是回溯描的方法，每次扫描在当前树中找一个节点，看它的邻居格子是否在树中，如果还没在树中，就将该邻居格子加入树中，如果已在树中，就看下一个邻居格子，如果该节点所有邻居格子都在树中了，就找下一个节点，继续同样的操作。另外为了让迷宫生成的随机，扫描的起始位置是随机的就可以了。但是，该方法生成的迷宫中的路径总是不够深，没有我想要的曲折深入的效果。毕竟是类似广度搜索的方法。而且，这样做总还像是靠蛮力，算法不够聪明简洁。
最后，我终于想到使用深度搜索。。大概是因为数据结构已经学过了一年，又没太练，忘了不少，所以一直没想到这个应该第一想到的方法。。
随机选择一个格子作为根节点，从它开始随机地深度搜索前进，开出一条路来，直到无路可走了，退回一步，换另一条路，再走到无路可走，回退一步，换另一条……如此循环往复，直到完全无路可走。。。其实也还是回溯。
在程序里就是以下过程（详见代码中的createMaze()函数）：
随机选择一个格子作为根节点，将它压进栈里。
然后在栈不为空的时候执行以下循环：
取出一个格子，将它的INTREE标志设置为1，然后将它的所有不在树中的邻居格子压进栈里（顺序随机），并且让这些邻居格子的father指向该格子。
解决了这两个问题，其余的画迷宫、显示路径、小球移动也就比较简单了。
代码
|
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
|
package maze;import java.awt.Color;import java.awt.Graphics;import java.awt.event.KeyAdapter;import java.awt.event.KeyEvent;import java.util.Random;import java.util.Stack;import javax.swing.JFrame;import javax.swing.JOptionPane;import javax.swing.JPanel;class Lattice { static final int INTREE = 1; static final int NOTINTREE = 0; private int x = -1; private int y = -1; private int flag = NOTINTREE; private Lattice father = null; public Lattice(int xx, int yy) { x = xx; y = yy; } public int getX() { return x; } public int getY() { return y; } public int getFlag() { return flag; } public Lattice getFather() { return father; } public void setFather(Lattice f) { father = f; } public void setFlag(int f) { flag = f; } public String toString() { return new String("(" + x + "," + y + ")\n"); }}public class Maze extends JPanel { private static final long serialVersionUID = -8300339045454852626L; private int NUM, width, padding;// width 每个格子的宽度和高度 private Lattice[][] maze; private int ballX, ballY; private boolean drawPath = false; Maze(int m, int wi, int p) { NUM = m; width = wi; padding = p; maze = new Lattice[NUM][NUM]; for (int i = 0; i <= NUM - 1; i++) for (int j = 0; j <= NUM - 1; j++) maze[i][j] = new Lattice(i, j); createMaze(); setKeyListener(); this.setFocusable(true); } private void init() { for (int i = 0; i <= NUM - 1; i++) for (int j = 0; j <= NUM - 1; j++) { maze[i][j].setFather(null); maze[i][j].setFlag(Lattice.NOTINTREE); } ballX = 0; ballY = 0; drawPath = false; createMaze(); // setKeyListener(); this.setFocusable(true); repaint(); } public int getCenterX(int x) { return padding + x * width + width / 2; } public int getCenterY(int y) { return padding + y * width + width / 2; } public int getCenterX(Lattice p) { return padding + p.getY() * width + width / 2; } public int getCenterY(Lattice p) { return padding + p.getX() * width + width / 2; } private void checkIsWin() { if (ballX == NUM - 1 && ballY == NUM - 1) { JOptionPane.showMessageDialog(null, "YOU WIN !", "你走出了迷宫。", JOptionPane.PLAIN_MESSAGE); init(); } } synchronized private void move(int c) { int tx = ballX, ty = ballY; // System.out.println(c); switch (c) { case KeyEvent.VK_LEFT : ty--; break; case KeyEvent.VK_RIGHT : ty++; break; case KeyEvent.VK_UP : tx--; break; case KeyEvent.VK_DOWN : tx++; break; case KeyEvent.VK_SPACE : if (drawPath == true) { drawPath = false; } else { drawPath = true; } break; default : } if (!isOutOfBorder(tx, ty) && (maze[tx][ty].getFather() == maze[ballX][ballY] || maze[ballX][ballY].getFather() == maze[tx][ty])) { ballX = tx; ballY = ty; } } private void setKeyListener() { this.addKeyListener(new KeyAdapter() { public void keyPressed(KeyEvent e) { int c = e.getKeyCode(); move(c); repaint(); checkIsWin(); } }); } private boolean isOutOfBorder(Lattice p) { return isOutOfBorder(p.getX(), p.getY()); } private boolean isOutOfBorder(int x, int y) { return (x > NUM - 1 || y > NUM - 1 || x < 0 || y < 0) ? true : false; } private Lattice[] getNeis(Lattice p) { final int[] adds = {-1, 0, 1, 0, -1};// 顺序为上右下左 if (isOutOfBorder(p)) { return null; } Lattice[] ps = new Lattice[4];// 顺序为上右下左 int xt; int yt; for (int i = 0; i <= 3; i++) { xt = p.getX() + adds[i]; yt = p.getY() + adds[i + 1]; if (isOutOfBorder(xt, yt)) continue; ps[i] = maze[xt][yt]; } return ps; } private void createMaze() { Random random = new Random(); int rx = Math.abs(random.nextInt()) % NUM; int ry = Math.abs(random.nextInt()) % NUM; Stack<Lattice> s = new Stack<Lattice>(); Lattice p = maze[rx][ry]; Lattice neis[] = null; s.push(p); while (!s.isEmpty()) { p = s.pop(); p.setFlag(Lattice.INTREE); neis = getNeis(p); int ran = Math.abs(random.nextInt()) % 4; for (int a = 0; a <= 3; a++) { ran++; ran %= 4; if (neis[ran] == null || neis[ran].getFlag() == Lattice.INTREE) continue; s.push(neis[ran]); neis[ran].setFather(p); } } // changeFather(maze[0][0],null); } private void changeFather(Lattice p, Lattice f) { if (p.getFather() == null) { p.setFather(f); return; } else { changeFather(p.getFather(), p); } } private void clearFence(int i, int j, int fx, int fy, Graphics g) { int sx = padding + ((j > fy ? j : fy) * width), sy = padding + ((i > fx ? i : fx) * width), dx = (i == fx ? sx : sx + width), dy = (i == fx ? sy + width : sy); if (sx != dx) { sx++; dx--; } else { sy++; dy--; } g.drawLine(sx, sy, dx, dy); } protected void paintComponent(Graphics g) { super.paintComponent(g); for (int i = 0; i <= NUM; i++) { g.drawLine(padding + i * width, padding, padding + i * width, padding + NUM * width); } for (int j = 0; j <= NUM; j++) { g.drawLine(padding, padding + j * width, padding + NUM * width, padding + j * width); } g.setColor(this.getBackground()); for (int i = NUM - 1; i >= 0; i--) { for (int j = NUM - 1; j >= 0; j--) { Lattice f = maze[i][j].getFather(); if (f != null) { int fx = f.getX(), fy = f.getY(); clearFence(i, j, fx, fy, g); } } } g.drawLine(padding, padding + 1, padding, padding + width - 1); int last = padding + NUM * width; g.drawLine(last, last - 1, last, last - width + 1); g.setColor(Color.RED); g.fillOval(getCenterX(ballY) - width / 3, getCenterY(ballX) - width / 3, width / 2, width / 2); if (drawPath == true) drawPath(g); } private void drawPath(Graphics g) { Color PATH_COLOR = Color.ORANGE, BOTH_PATH_COLOR = Color.PINK; if (drawPath == true) g.setColor(PATH_COLOR); else g.setColor(this.getBackground()); Lattice p = maze[NUM - 1][NUM - 1]; while (p.getFather() != null) { p.setFlag(2); p = p.getFather(); } g.fillOval(getCenterX(p) - width / 3, getCenterY(p) - width / 3, width / 2, width / 2); p = maze[0][0]; while (p.getFather() != null) { if (p.getFlag() == 2) { p.setFlag(3); g.setColor(BOTH_PATH_COLOR); } g.drawLine(getCenterX(p), getCenterY(p), getCenterX(p.getFather()), getCenterY(p.getFather())); p = p.getFather(); } g.setColor(PATH_COLOR); p = maze[NUM - 1][NUM - 1]; while (p.getFather() != null) { if (p.getFlag() == 3) break; g.drawLine(getCenterX(p), getCenterY(p), getCenterX(p.getFather()), getCenterY(p.getFather())); p = p.getFather(); } } public static void main(String[] args) { final int n = 30, width = 600, padding = 20, LX = 200, LY = 100; JPanel p = new Maze(n, (width - padding - padding) / n, padding); JFrame frame = new JFrame("MAZE(按空格键显示或隐藏路径)"); frame.getContentPane().add(p); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.setSize(width + padding, width + padding + padding); frame.setLocation(LX, LY); frame.setVisible(true); }} |
