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

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

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

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

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

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

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 path = new Stack(); //表示路径的栈

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;

//如果该节点被访问过，则回到上一步继续寻找http://

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;

}

rethttp://urn true;

}

/**

* 寻找可访问的邻接格，这里可以优化，不用list

* @param node

* @return

*/

Node[] notVisitedAdj(Node node)

{

List list = new ArrayList();

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

}

}

总结

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。