這兩天因為要做一個隨機的地圖生成系統，所以一直在研究隨機迷宮生成算法，好吧，算是有一點小小的成果。
隨機迷宮生成我自己的理解簡而言之分為以下幾步：
1、建立一張地圖，我用的二維數組表示，地圖上全是障礙物。然后再創建一個用來表示每個格子是否被訪問過的二維數組。再創建一個用來表示路徑的棧結構。
2、隨機選擇地圖上的一點，呃為了方便我初始點直接取的是左上角即坐標表示為0,0的格子。終點的話因為不涉及到交互就暫時沒有。
3、查找當前格子的鄰接格（注意，這里的鄰接格子都是還未被訪問的，下面的代碼里有寫）。隨機選擇一個鄰接格子為下一格，當前格移動到下一格，標記當前格為已訪問，將當前格壓入路徑棧中。一直重復第三步操作。
4、在第三步操作中，如果當前格子不存在可訪問的鄰接格，則將棧頂的元素彈出，即退回上一步操作，如果棧為空，則結束程序，打印結果。
附上結果和源碼，這是基于java控制臺來寫的。
|
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
|
package maze;import java.util.arraylist;import java.util.list;import java.util.random;import java.util.stack;public class maze { int len = 11; //迷宮長度 int wid = 11; //迷宮寬度 char wall = '■'; //代表墻 char blank = '○'; //代表空地 char[][] maze; //迷宮 boolean[][] visit; //用來標記某一格是否被訪問過 node start = new node(0,0); //開始節點 node exit = new node(len - 1, wid - 1); //出口，其實現在也沒什么用，因為沒有交互只是生成了一個迷宮而已 node cur; //當前格 node next; //下一格 stack<node> path = new stack<node>(); //表示路徑的棧 int[][] adj = { {0,2},{0,-2},{2,0},{-2,0} }; //用來計算鄰接格 /** * 迷宮的格子類 * @author yan */ class node { int x,y; public node(){} public node(int x, int y) { this.x = x; this.y = y; } public string tostring() { return "node [x=" + x + ", y=" + y + "]"; } } /** * 初始化，初始化迷宮參數 */ void init() { maze = new char[len][wid]; visit = new boolean[len][wid]; for(int i = 0; i < len; i++) { for(int j = 0; j < wid; j++) { maze[i][j] = wall; visit[i][j] = false; } } visit[start.x][start.y] = true; maze[start.x][start.y] = blank; cur = start; //將當前格標記為開始格 } /** * 打印結果 */ void printmaze() { for(int i = 0; i < len; i++) { for(int j = 0; j < wid; j++) { system.out.print(maze[i][j] + " ");// if(maze[i][j] == '○')// {// system.err.print(maze[i][j] + " ");// }// else// {// system.out.print(maze[i][j] + " ");// }// try {// thread.sleep(100);// } catch (interruptedexception e) {// e.printstacktrace();// } } system.out.println(); } system.out.println("=========================================="); } /** * 開始制作迷宮 */ void makemaze() { path.push(cur); //將當前格壓入棧 while(!path.empty()) { node[] adjs = notvisitedadj(cur);//尋找未被訪問的鄰接格 if(adjs.length == 0) { cur = path.pop();//如果該格子沒有可訪問的鄰接格，則跳回上一個格子 continue; } next = adjs[new random().nextint(adjs.length)]; //隨機選取一個鄰接格 int x = next.x; int y = next.y; //如果該節點被訪問過，則回到上一步繼續尋找 if(visit[x][y]) { cur = path.pop(); } else//否則將當前格壓入棧，標記當前格為已訪問，并且在迷宮地圖上移除障礙物 { path.push(next); visit[x][y] = true; maze[x][y] = blank; maze[(cur.x + x) / 2][(cur.y + y) / 2] = blank; //移除當前格與下一個之間的墻壁 cur = next;//當前格等于下一格 } } } /** * 判斷節點是否都被訪問 * @param ns * @return */ boolean allvisited(node[] ns) { for(node n : ns) { if(!visit[n.x][n.y]) return false; } return true; } /** * 尋找可訪問的鄰接格，這里可以優化，不用list * @param node * @return */ node[] notvisitedadj(node node) { list<node> list = new arraylist<node>(); for(int i = 0; i < adj.length; i++) { int x = node.x + adj[i][0]; int y = node.y + adj[i][1]; if( x >= 0 && x < len && y >= 0 && y < wid) { if(!visit[x][y]) list.add(new node(x,y)); } } node[] a = new node[list.size()]; for(int i = 0; i < list.size(); i++) { a[i] = list.get(i); } return a; } /** * 入口方法 * @param args */ public static void main(string[] args) { maze m = new maze(); m.init(); m.makemaze(); m.printmaze(); }} |
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對服務器之家的支持。如果你想了解更多相關內容請查看下面相關鏈接
原文鏈接：https://blog.csdn.net/y378076136/article/details/19832659
