Java基于深度优先遍历的随机迷宫生成算法
作者:严洋羽 发布时间:2022-06-01 22:18:50
标签: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();
}
}
来源:https://blog.csdn.net/y378076136/article/details/19832659
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- session对象用于在会话范围内,记录每个客户端的访问状态,以便于跟踪每个客户端的操作状态,在会话存储的信息,在浏览器发出后续请求时可以获
- Java synchronized 关键字 可以将一个代码块或一个方法标记为同步代码块。同步代码块是指同一时间只能有一个线程执行的代码,并且
- 简介mutable(可变)和immutable(不可变)对象是我们在java程序编写的过程中经常会使用到的。可变类型对象就是说,对象在创建之
- 本文实例讲述了Java Web项目部署在Tomcat运行出错与解决方法。分享给大家供大家参考,具体如下:1、在部署Java Web项目的过程
- 前言《摩尔庄园》前段时间上线, 持续超出市场预期,相信也有不错的收益。游戏好玩,所有玩家看到了前端,但是做一款游戏,离不开后台游戏服务器的支
- spring in action第三版读书笔记spring3.0引入了spring expression language(spel)语言,
- 目录前言实践部分测试部分总结前言今天跟小伙伴们分享一个实战内容,使用Spring Boot+Shiro实现一个简单的Http认证。场景是这样
- 简介Android给我们提供了一种轻量级的异步任务类AsyncTask。该类中实现异步操作,并提供接口反馈当前异步执行结果及进度,这些接口中
- 前2天有读者问到是否有带分页功能的表格控件,今天分页功能的表格控件详细解析。PaginatedDataTablePaginatedDataT
- 前言关于mybatis-plus的简介以及基本使用,我在《SpringBoot整合mybatis-plus–入门超详细》一文中已做介绍,此处
- InputStreamReader 类1、概述转换流 java.io.InputStreamReader ,是Reader的子类,是从字节流
- Android手势解锁本文讲述的是一个手势解锁的库,可以定制显示隐藏宫格点、路径、并且带有小九宫格显示图,和震动!让你学会使用这个简单,高效
- 很多App都有这种效果,特别一些电商类的App,顶部每隔几秒钟会向右翻页显示下张图片,用来作推广或者内容展示用的。今天来简单地模仿一下,还自
- 缘起工作时使用java开发服务器后台,用Jersey写Restful接口,发现有一个Post方法始终获取不到参数,查了半天,发现时获取参数的
- 合并有序数组的实现java版本:实例代码public class Merge {//合并有序数组 public static v
- 1.概览该教程中,我将向你展示:如何在测试时设置spring boot 日志级别。虽然我们可以在测试通过时忽略日志,但是如果需要诊断失败的测
- 本文实例为大家分享了java实现简单单链表的具体代码,供大家参考,具体内容如下一、定义:单链表是一种链式存取的数据结构,用一组地址任意的存储
- 一、问题定义:问下有一个数组,这些数组中的值都有自己的权重,怎样设计才能高效的优先取出权重高的数??例如:权重: 8 2&nbs
- Spring * 监测每个Controller或方法的执行时长首先写一个类(TestInterceptor)让他继承HandlerInter
- 很多时候我们开发的软件需要向用户提供软件参数设置功能,例如我们常用的QQ,用户可以设置是否允许陌生人添加自己为好友。对于软件配置参数的保存,