这两天因为要做一个随机的地图生成系统，所以一直在研究随机迷宫生成算法，好吧，算是有一点小小的成果。
随机迷宫生成我自己的理解简而言之分为以下几步：
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