java图的深度优先遍历实现随机生成迷宫
作者:woshizoe 发布时间:2023-06-26 06:06:05
最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢。
1、从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中的随机一个访问(每访问到一个可访问的点,就去掉该点的那个方向的墙),被访问点继续以这种方识向下进行访问。
2、对每个被访问的点都被标识为已访问,当一个点对某个方向进行访问时我们首先会判断被访问点是否已被访问,或者触到边界.如果该点四个方向皆已访问或已无法访问,就退回上一个点。上一个点继续这个过程。
这样一次遍历下来,可以确定每个点都被访问过,而且由于每次访问的方向都是随机,这就会形成许多不同遍历情况,同时每两个点之间的路径是唯一,也就形成不同的迷宫,且是起点到终点只有唯一路径,这是由于图的深度遍历算法的特点所决定的。算法的实现上,主要是利用栈,第一次,先把第一个点压进栈里,每访问到一个点,就把该点压进栈里,我们再对栈顶的点进行四个方向的随机访问,访问到新点,又把新点压进去,一旦这个点四个方向都无法访问了,就让该点退栈,再对栈顶的点的四个方向进行访问,以此类推,直到栈里的点都全部退出了,我们的遍历就成功了,这是一个递归的过程,这个算法自然可以用递归的方法来实现,不过这里我这样做,而是手工用一个数组作为栈来实现,呵呵~~说了这么多,也不知道自己要表达的有没表达出来。不过我感觉我的具体代码设计还是写的不好,还有很多地方缺乏完善和优化,权当是算法练习,以下是两个关键类的核心代码,至于表示层的代码就不贴出来了,因为那些都很琐碎。
下面是效果图:
迷宫的类:
//作者:zhongZw
//邮箱:zhong317@126.com
package cn.zhongZw.model;
import java.util.ArrayList;
import java.util.Random;
public class MazeModel {
private int width = 0;
private int height = 0;
private Random rnd = new Random();
public MazeModel() {
this.width = 50; //迷宫宽度
this.height = 50; //迷宫高度
}
public int getWidth() {
return width;
}
public void setWidth(int width) {
this.width = width;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public MazeModel(int width, int height) {
super();
this.width = width;
this.height = height;
}
public ArrayList < MazePoint > getMaze() {
ArrayList < MazePoint > maze = new ArrayList < MazePoint > ();
for (int h = 0; h < height; h++) {
for (int w = 0; w < width; w++) {
MazePoint point = new MazePoint(w, h);
maze.add(point);
}
}
return CreateMaze(maze);
}
private ArrayList < MazePoint > CreateMaze(ArrayList < MazePoint > maze) {
int top = 0;
int x = 0;
int y = 0;
ArrayList < MazePoint > team = new ArrayList < MazePoint > ();
team.add(maze.get(x + y * width));
while (top >= 0) {
int[] val = new int[] {
-1, -1, -1, -1
};
int times = 0;
boolean flag = false;
MazePoint pt = (MazePoint) team.get(top);
x = pt.getX();
y = pt.getY();
pt.visted = true;
ro1: while (times < 4) {
int dir = rnd.nextInt(4);
if (val[dir] == dir)
continue;
else
val[dir] = dir;
switch (dir) {
case 0: // 左边
if ((x - 1) >= 0 && maze.get(x - 1 + y * width).visted == false) {
maze.get(x + y * width).setLeft();
maze.get(x - 1 + y * width).setRight();
team.add(maze.get(x - 1 + y * width));
top++;
flag = true;
break ro1;
}
break;
case 1: // 右边
if ((x + 1) < width && maze.get(x + 1 + y * width).visted == false) {
maze.get(x + y * width).setRight();
maze.get(x + 1 + y * width).setLeft();
team.add(maze.get(x + 1 + y * width));
top++;
flag = true;
break ro1;
}
break;
case 2: // 上边
if ((y - 1) >= 0 && maze.get(x + (y - 1) * width).visted == false) {
maze.get(x + y * width).setUp();
maze.get(x + (y - 1) * width).setDown();
team.add(maze.get(x + (y - 1) * width));
top++;
flag = true;
break ro1;
}
break;
case 3: // 下边
if ((y + 1) < height && maze.get(x + (y + 1) * width).visted == false) {
maze.get(x + y * width).setDown();
maze.get(x + (y + 1) * width).setUp();
team.add(maze.get(x + (y + 1) * width));
top++;
flag = true;
break ro1;
}
break;
}
times += 1;
}
if (!flag) {
team.remove(top);
top -= 1;
}
}
return maze;
}
}
迷宫
//作者:zhongZw
//邮箱:zhong317@126.com
package cn.zhongZw.model;
import java.util.*;
import java.lang.*;
public class MazePoint {
private int left = 0;
private int right = 0;
private int up = 0;
private int down = 0;
private int x;
private int y;
public boolean visted;
public MazePoint(int x, int y) {
this.x = x;
this.y = y;
}
public int getLeft() {
return left;
}
public void setLeft() {
this.left = 1;
}
public int getRight() {
return right;
}
public void setRight() {
this.right = 1;
}
public int getUp() {
return up;
}
public void setUp() {
this.up = 1;
}
public int getDown() {
return down;
}
public void setDown() {
this.down = 1;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
来源:http://blog.csdn.net/woshizoe/article/details/27345201
猜你喜欢
- 一、概要1.Java虚拟机(Jvm)是什么?2.Java虚拟机是用来干什么的?3.Java虚拟机它的体系结构是什么样子的?4.Java虚拟机
- 通过本篇文章主要给大家讲解了在JAVA开发中Servlet3.0异步处理遇到的问题以及处理办法,以下是具体内容:Servlet 3.0 开始
- 最近由于工作原因,没时间更新,开始吧~~关于json的返回需要用到一个工具包来将书转换为json格式,在此用到的jar包为: im
- 1.引入AOP依赖<dependency>
- SQLite是Android自带的关系型数据库,是一个基于文件的轻量级数据库。Android提供了3种操作数据的方式,SharedPrefe
- 前言LocalDateTime、LocalDate、LocalTime 是 Java8 全新的日期框架,加强了对时间的管理,有很多特别好用的
- 使用 DateFormat 格式化日期、时间DateFormat 也是一个抽象类,它也提供了如下几个类方法用于获取 DateFormat 对
- 使用maven引入jar<dependency> <groupId>com.itextpdf</g
- 释放公平锁(基于JDK1.7.0_40)1. unlock()unlock()在ReentrantLock.java中实现的,源码如下:pu
- 本节我们来探讨如何使用Feign构造多参数的请求。笔者以GET以及POST方法的请求为例进行讲解,其他方法(例如DELETE、PUT等)的请
- 1.登录腾讯云点击登录选择浏览器登录。输入用户名 按回车键 然后输入 密码。2.安装java环境直接命令:yum -y install ja
- 1.问题描述汉诺塔问题是一个经典的问题。汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说。大梵天创造世界的时候做了三根金刚
- 1 问题手写一个程序,完成List集合对象的逆序遍历2 方法创建List接口的多态对象向创建好list集合添加元素使用hasPrevious
- 质数又称素数。一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除的数;否则称为合数。根据算术基本定理,每一个比1大的整数,要么本
- 需求: 使用IO流将指定目录下的若干个音频文件的高潮部分,进行剪切,并重新拼接成一首新的音频文件 思路(以两首歌为例):第一首歌有
- 一、内部类1.内部类的概念内部类是定义在类中的类。内部类把逻辑上相关的类放在一起。而有的内部类不会在其他地方用到,它没有类名,在定义的时候就
- 今天给大家介绍一下SpringBoot中JPA的一些常用操作,例如:增删改查、分页、排序、事务操作等功能。下面先来介绍一下JPA中一些常用的
- 目录第一种方式第二种方式第三种方式第四种方式(缺点:将所有的数字类型都会转为字符串)web项目中,Java后端传过来的Long/long类型
- 首先我们看看为什么需要对象复制?为什么需要对象复制如上,是我们平时开发中最常见的三层MVC架构模型,编辑操作时Controller层接收到前
- MyBatis简介MyBatis是一个支持普通SQL查询,存储过程和高级映射的优秀持久层框架。MyBatis消除了几乎所有的JDBC代码和参