Java基于深度优先遍历的随机迷宫生成算法

这两天因为要做一个随机的地图生成系统，所以一直在研究随机迷宫生成算法，好吧，算是有一点小小的成果。

随机迷宫生成我自己的理解简而言之分为以下几步：

1、建立一张地图，我用的二维数组表示，地图上全是障碍物。然后再创建一个用来表示每个格子是否被访问过的二维数组。再创建一个用来表示路径的栈结构。

2、随机选择地图上的一点，呃为了方便我初始点直接取的是左上角即坐标表示为0,0的格子。终点的话因为不涉及到交互就暂时没有。

3、查找当前格子的邻接格（注意，这里的邻接格子都是还未被访问的，下面的代码里有写）。随机选择一个邻接格子为下一格，当前格移动到下一格，标记当前格为已访问，将当前格压入路径栈中。一直重复第三步操作。

4、在第三步操作中，如果当前格子不存在可访问的邻接格，则将栈顶的元素弹出，即退回上一步操作，如果栈为空，则结束程序，打印结果。

附上结果和源码，这是基于java控制台来写的。

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();
 }
}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接