这学期的算法课，老师要求期中做一个算法设计出来，我选择了迷宫。自己当时没有想出好的算法来，后来参考了网上一篇关于迷宫算法的论文，于是写出了这个迷宫求解程序。现在将程序分享出来，如有不妥之处，敬请大家指正。
package com.sailor.maze;
/****************************************************************************/
/**Author: Sailor */
/**Vision: Maze1.00 */
/**Date: 2010-04-15 */
/**E-Mail:zpsailor@yahoo.com.cn */
/**QQ:251396377 */
/**********************************************************************/
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.TimerTask;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
// 迷宫
@SuppressWarnings("serial")
public class Maze extends JFrame implements ActionListener {
private JPanel panel;
private JPanel northPanel;
private JPanel centerPanel;
private MazeGrid grid[][];
private JButton restart;
private JButton dostart;
private int rows;// rows 和cols目前暂定只能是奇数
private int cols;
private List<String> willVisit;
private List<String> visited;
private LinkedList<String> comed;
private long startTime;
private long endTime;
public Maze() {
rows = 25;
cols = 25;
willVisit = new ArrayList<String>();
visited = new ArrayList<String>();
comed = new LinkedList<String>();
init();
this.setTitle("回溯法--走迷宫");
this.add(panel);
this.pack();
this.setVisible(true);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
public void init() {
panel = new JPanel();
northPanel = new JPanel();
centerPanel = new JPanel();
panel.setLayout(new BorderLayout());
restart = new JButton("重新生成迷宫");
dostart = new JButton("开始走迷宫");
grid = new MazeGrid[rows][cols];
centerPanel.setLayout(new GridLayout(rows, cols, 1, 1));
centerPanel.setBackground(new Color(0, 0, 0));
northPanel.add(restart);
northPanel.add(dostart);
dostart.addActionListener(this);
restart.addActionListener(this);
for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[i].length; j++) {
if (j % 2 == 0 && i % 2 == 0)
grid[i][j] = new MazeGrid(true, 20, 20);
else
grid[i][j] = new MazeGrid(false, 20, 20);
}
grid[0][0].setVisited(true);
grid[0][0].setPersonCome(true);
grid[0][0].setStart(true);
visited.add("0#0");
grid[rows - 1][cols - 1].setEnd(true);
grid = createMap(grid, 0, 0);
for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[i].length; j++) {
grid[i][j].repaint();
centerPanel.add(grid[i][j]);
}
panel.add(northPanel, BorderLayout.NORTH);
panel.add(centerPanel, BorderLayout.CENTER);
}
/**
* 生成迷宫
*
* @param mazeGrid
* @param x
* @param y
* @return
*/
public MazeGrid[][] createMap(MazeGrid mazeGrid[][], int x, int y) {
int visitX = 0;
int visitY = 0;
if (x - 2 >= 0) {
if (!mazeGrid[x - 2][y].isVisited()) {
willVisit.add((x - 2) + "#" + y);
}
}
if (x + 2 < cols) {
if (!mazeGrid[x + 2][y].isVisited()) {
willVisit.add((x + 2) + "#" + y);
}
}
if (y - 2 >= 0) {
if (!mazeGrid[x][y - 2].isVisited()) {
willVisit.add(x + "#" + (y - 2));
}
}
if (y + 2 < rows) {
if (!mazeGrid[x][y + 2].isVisited()) {
willVisit.add(x + "#" + (y + 2));
}
}
if (!willVisit.isEmpty()) {
int visit = (int) (Math.random() * willVisit.size());
String id = willVisit.get(visit);
visitX = Integer.parseInt(id.split("#")[0]);
visitY = Integer.parseInt(id.split("#")[1]);
mazeGrid[(visitX + x) / 2][(visitY + y) / 2].setMark(true);
mazeGrid[visitX][visitY].setVisited(true);
if (!visited.contains(id)) {// 将这个点加到已访问中去
visited.add(id);
}
willVisit.clear();
createMap(mazeGrid, visitX, visitY);
} else {
if (!visited.isEmpty()) {
String id = visited.remove(visited.size() - 1);// 取出最后一个元素
visitX = Integer.parseInt(id.split("#")[0]);
visitY = Integer.parseInt(id.split("#")[1]);
mazeGrid[visitX][visitY].setVisited(true);
createMap(mazeGrid, visitX, visitY);
}
}
return mazeGrid;
}
/**
* 走迷宫
*
* @param mazeGrid
* @param x
* @param y
*/
public String goMaze(MazeGrid mazeGrid[][], int x, int y) {
int comeX = 0;
int comeY = 0;
// left
if (x - 1 >= 0) {
if (mazeGrid[x - 1][y].isMark()) {
if (!comed.contains((x - 1) + "#" + y))
willVisit.add((x - 1) + "#" + y);
}
}
// right
if (x + 1 < cols) {
if (mazeGrid[x + 1][y].isMark()) {
if (!comed.contains((x + 1) + "#" + y))
willVisit.add((x + 1) + "#" + y);
}
}
// up
if (y - 1 >= 0) {
if (mazeGrid[x][y - 1].isMark()) {
if (!comed.contains(x + "#" + (y - 1)))
willVisit.add(x + "#" + (y - 1));
}
}
// down
if (y + 1 < rows) {
if (mazeGrid[x][y + 1].isMark()) {
if (!comed.contains(x + "#" + (y + 1)))
willVisit.add(x + "#" + (y + 1));
}
}
if (!willVisit.isEmpty()) {
int visit = (int) (Math.random() * willVisit.size());
String id = willVisit.get(visit);
comeX = Integer.parseInt(id.split("#")[0]);
comeY = Integer.parseInt(id.split("#")[1]);
mazeGrid[x][y].setPersonCome(false);
mazeGrid[comeX][comeY].setPersonCome(true);
mazeGrid[x][y].repaint();
mazeGrid[comeX][comeY].repaint();
willVisit.clear();
comed.add(x + "#" + y);
} else {
if (!comed.isEmpty()) {
String id = comed.removeLast();
comeX = Integer.parseInt(id.split("#")[0]);
comeY = Integer.parseInt(id.split("#")[1]);
mazeGrid[x][y].setPersonCome(false);
mazeGrid[comeX][comeY].setPersonCome(true);
mazeGrid[x][y].repaint();
mazeGrid[comeX][comeY].repaint();
comed.addFirst(x + "#" + y);
}
}
return comeX + "#" + comeY;
}
int comeX = 0;
int comeY = 0;
@Override
public void actionPerformed(ActionEvent e) {
if (e.getActionCommand().equals("重新生成迷宫")) {
refreshMap(grid);
} else if (e.getActionCommand().equals("开始走迷宫")) {
startTime = System.currentTimeMillis();
dostart.setVisible(false);
restart.setText("禁止刷新");
int delay = 1000;
int period = 500;// 循环间隔
java.util.Timer timer = new java.util.Timer();
timer.scheduleAtFixedRate(new TimerTask() {
public void run() {
if (grid[rows - 1][cols - 1].isPersonCome()) {
endTime = System.currentTimeMillis();
JOptionPane.showMessageDialog(null, "已经走出迷宫，耗时"
+ (endTime - startTime) / 1000 + "秒", "消息提示",
JOptionPane.ERROR_MESSAGE);
this.cancel();
restart.setText("重新生成迷宫");
} else {
String id = goMaze(grid, comeX, comeY);
comeX = Integer.parseInt(id.split("#")[0]);
comeY = Integer.parseInt(id.split("#")[1]);
}
}
}, delay, period);
}
}
/**
* 刷新地图
*/
public void refreshMap(MazeGrid mazeGrid[][]) {
comeX = 0;
comeY = 0;
willVisit.clear();
visited.clear();
comed.clear();
this.remove(panel);
init();
this.add(panel);
this.pack();
this.setVisible(true);
}
public static void main(String args[]) {
long start = System.currentTimeMillis();
new Maze();
long end = System.currentTimeMillis();
System.out.println("使用ArrayList生成迷宫耗时：" + (end - start) + "毫秒");
}
}
package com.sailor.maze;
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Graphics;
@SuppressWarnings("serial")
public class MazeGrid extends Canvas {
private boolean mark;// 标记是否是通路，TRUE为通路，FALSE为不通
private boolean isVisited;// 标记是否是访问过的,这是在生成迷宫的时候判断的。
private boolean isPersonCome;// 标记是否已经走过
private boolean isStart;// 判断是否为入口
private boolean isEnd;// 判断是否为出口
public MazeGrid() {
this.setBackground(new Color(120, 0, 0));
this.setSize(25, 25);
}
public MazeGrid(boolean mark, int width, int height) {
this.mark = mark;
this.setSize(width, height);
if (mark == true) {
this.setBackground(new Color(255, 255, 255));
} else {
this.setBackground(new Color(120, 0, 0));
}
}
public boolean isMark() {
return mark;
}
public void setMark(boolean mark) {
this.mark = mark;
}
public void paint(Graphics g) {
if (this.mark) {
if (this.isStart || this.isEnd) {
this.setBackground(new Color(255,0,0));
} else
this.setBackground(new Color(255, 255, 255));
} else {
this.setBackground(new Color(120, 0, 0));
}
if (this.isPersonCome) {
g.setColor(Color.BLACK);
g.fillOval(2, 2, 15, 15);
}
}
public boolean isVisited() {
return isVisited;
}
public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}
public boolean isPersonCome() {
return isPersonCome;
}
public void setPersonCome(boolean isPersonCome) {
this.isPersonCome = isPersonCome;
}
public boolean isStart() {
return isStart;
}
public void setStart(boolean isStart) {
this.isStart = isStart;
}
public boolean isEnd() {
return isEnd;
}
public void setEnd(boolean isEnd) {
this.isEnd = isEnd;
}
}
分享到：
相关推荐
用遗传算法求解迷宫问题的Java代码，代码有注释。
数据结构课程设计java求解迷宫，回溯法，A算法.docx
描述罗密欧与朱丽叶迷宫求解步骤，方便开发。
Java迷宫算法该项目的主要目标是为迷宫生成动画和求解算法。 并非所有算法都包括在内，由于所涉及的动画，实现方式可能不是最有效的。 Main方法位于main / Maze.java中，可以使用IDE或 如果以较小的分辨率运行，则...
数据结构课程设计，使用了回溯法和A*算法，求解迷宫。有代码和文档，另附A*算法教程
用java完成的，关于启发式搜索算法在迷宫问题中的求解。
问题描述： 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 实现要求： ⑴ 实现一个以链表作存储结构的栈...
代码有详细注释！ 1.语言：使用java编程 2.数据结构：使用单链表头插法仿实现栈 3.非递归使用DFS搜索一条路径 4.递归求解所有路径
迷宫求解——栈的简单应用 要熟练得掌握一种数据结构，要经过大量的练习，而将数据结构应用于实际用用中则是一种非常好的锻炼方式。 此次便是应用java来实现 迷宫求解 这个经典的程序设计问题。
用可视化的SWING 组件实现迷宫算法,回朔法的迷宫求解是数据结构和算法课的必备知识
彩信用Java编写Micromouse迷宫求解算法。 与模拟器一起使用。设置克隆此存储库运行模拟器，然后单击“ +”按钮以配置新算法输入算法的配置（名称，目录，构建命令和运行命令） 点击“运行”按钮例子视窗： Linux...
A星算法(寻路问题,八数码问题 java版)
（1）算法功能描述 利用递归回溯/深度优先随机生成迷宫 （2）算法描述 a.将起点作为当前迷宫单元并标记为已访问 b.当还存在未标记的迷宫单元，进行循环 ①.如果当前迷宫单元有未被访问过的的相邻的迷宫单元 ㈠...
利用BFS算法对迷宫问题进行求解并给出最短路径，利用java可视化工具对迷宫进行可视化，并标注出路径可探索过程中丢弃的非最短路径上的节点，更直观易懂。
电子老鼠闯迷宫 算法分析 java源码 利用贪心算法求解布线和迷宫一类的问题。
用java写了一个回溯法求解迷宫的程序，还有一个八皇后的问题，因为水平一般，不敢说一定正确，但是希望对你有一些提示。
包含了递归算法和非递归算法的实现、程序有注释、阅读很方便
java写的一个用堆栈进行迷宫求解的算法演示，可以动态显示迷宫的状态和堆栈的状态。
将走迷宫中的搜索出口路径的问题转化为遗传算法中的问题通过构造针对此特定问题的适值函数，基因移动方向的定位，巧的进行问题的求解。详细介绍链接 CABDDCC 基于连通图的分裂聚类算法。也是属于层次聚类算法主要...
java实现迷宫的自动求解，bfs算法，实现了可视化，有兴趣可以完善监听事件