这两天因为要做一个随机的地图生成系统，所以一直在研究随机迷宫生成算法，好吧，算是有一点小小的成果。
随机迷宫生成我自己的理解简而言之分为以下几步：
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
查看更多关于Java基于深度优先遍历的随机迷宫生成算法的详细内容...