緣起：
去年（大三上學期）比較喜歡寫小游戲，于是想試著寫個迷宮試一下。
程序效果：
按下空格顯示路徑：
思考過程：
迷宮由一個一個格子組成，要求從入口到出口只有一條路徑.
想了一下各種數據結構，似乎樹是比較合適的，從根節點到每一個子節點都只有一條路徑。假設入口是根節點，出口是樹中某個子節點，那么，從根節點到該子節點的路徑肯定是唯一的。
所以如果能構造一棵樹把所有的格子都覆蓋到，也就能夠做出一個迷宮了。
另外還要求樹的父節點和子節點必須是界面上相鄰的格子。
在界面顯示時，父節點和子節點之間共用的邊不畫，其他的邊都畫出來，就能畫出一個迷宮。
之后就是想一下該怎么實現這樣一棵樹。
首要的兩個問題：
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); }} |
