`
zpsailor
  • 浏览: 43715 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

基于Java的"迷宫问题"求解(带算法描述)

算法JavaSwingJ#QQ 
阅读更多

       这学期的算法课，老师要求期中做一个算法设计出来，我选择了迷宫。自己当时没有想出好的算法来，后来参考了网上一篇关于迷宫算法的论文，于是写出了这个迷宫求解程序。现在将程序分享出来，如有不妥之处，敬请大家指正。

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

 

分享到：
| JS版俄罗斯方块（带程序说明文档）
评论
10 楼 taolei0628 2010-12-05  
zpsailor 写道
taolei0628 写道
既然是算法设计，就应该把算法思路用文字方式清晰地表达出来，光贴代码不好。

附件里有简单的设计思路。

抱歉，没有下载附件。不过包括我在内可能有许多人是更愿意看算法描述，而不是分析代码的，最好一并贴出来。

递归算法是天然受堆栈深度限制的，迷宫如果足够复杂的话，用递归算法可能会存在堆栈溢出的问题。
用回溯算法或模拟堆栈的递归才可以。
9 楼 zpsailor 2010-12-04  
taolei0628 写道
既然是算法设计，就应该把算法思路用文字方式清晰地表达出来，光贴代码不好。

附件里有简单的设计思路。
8 楼 taolei0628 2010-12-04  
既然是算法设计，就应该把算法思路用文字方式清晰地表达出来，光贴代码不好。
7 楼 zpsailor 2010-12-02  
sam_kee 写道
用回溯法可以哦

正解~
6 楼 sam_kee 2010-12-02  
用回溯法可以哦
5 楼 zpsailor 2010-12-01  
guispor7 写道
LZ,有个问题请教您。就是怎么能保证生成的迷宫一定能走出去呢？

在生成迷宫的时候使用到了树的深度优先算法，遍历了树中的所有节点，所以生成的迷宫一定是可以走得通的哈。
4 楼 guispor7 2010-12-01  
LZ,有个问题请教您。就是怎么能保证生成的迷宫一定能走出去呢？
3 楼 zpsailor 2010-04-26  
lzyzizi 写道
稍微粗略看了下你的代码，没怎么看懂你的实现~~

这个走迷宫的算法，一般会用到栈，栈就记录走过的迷宫的位置和已经访问过的方向，没有前进方向的时候，就出栈。

为什么会有comed和willvisit两个list，也没见你存走过的方向。还有你有考虑是思路的情况么？

是这个样子的，willvisit用来记录生成迷宫和走迷宫的时候，从当前位置可以移动到的下一个位置，comed就是在走迷宫的时候用于记录已经走过的位置的，也就是栈，不知道这样说清楚不。
2 楼 lzyzizi 2010-04-26  
稍微粗略看了下你的代码，没怎么看懂你的实现~~

这个走迷宫的算法，一般会用到栈，栈就记录走过的迷宫的位置和已经访问过的方向，没有前进方向的时候，就出栈。

为什么会有comed和willvisit两个list，也没见你存走过的方向。还有你有考虑是思路的情况么？
1 楼 zpsailor 2010-04-24  
随机生成迷宫的算法怎么这么快就沉下去了
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    遗传算法求解迷宫问题代码（java）

    本文将深入探讨如何使用遗传算法来求解迷宫问题，并结合Java编程语言进行实现。 首先，我们要理解迷宫问题的本质。迷宫通常表示为一个二维网格，其中每个节点代表一个位置，而边则表示可以移动的方向。目标是从起点...

    Java编写的求解迷宫问题的小程序.zip_Java 迷宫_java小程序_java迷宫_迷宫java_迷宫问题

    这个迷宫问题的Java小程序结合了图形界面、用户交互和算法实现，对于学习和理解Java编程以及如何用算法解决实际问题具有很好的实践价值。它可能涵盖了数据结构（栈、队列）、图形界面设计、事件处理、类的设计和实现...

    java实现的求迷宫最短路径算法

    本主题聚焦于使用Java实现求解迷宫最短路径的算法。在给定的压缩包中，包含两个文件：ShortPath.java和Position.java，它们分别代表了核心算法和坐标位置的数据结构。 首先，`Position.java`文件可能定义了一个类，...

    labyrinth-java.rar_Java 数据结构_Java 迷宫_数据结构 java_迷宫 java_迷宫算法

    常见的迷宫求解算法有深度优先搜索（DFS）和广度优先搜索（BFS）。DFS通常使用栈来实现，它会尽可能深地探索迷宫的一条分支，直到无法继续，然后回溯；BFS则使用队列，按照距离起点的远近顺序依次探索。这两种算法都...

    java迷宫课程设计

    Java迷宫课程设计是一项常见的编程练习，旨在帮助初学者掌握Java编程语言...通过完成这个Java迷宫课程设计，学生不仅可以巩固Java编程技能，还能提升对图形界面设计和算法实现的理解，为今后的学习和开发奠定坚实基础。

    基于java解决迷宫程序

    通过以上步骤，我们可以编写出一个完整的Java迷宫求解程序。对于初学者来说，这是一个很好的练习项目，能够加深对数据结构、算法和面向对象编程的理解。而对于有经验的开发者，这个话题也可以提供一个有趣的挑战，...

    迷宫求解 java语言实现.docx

    在计算机科学中，迷宫求解是指使用算法和数据结构来解决迷宫问题的过程。迷宫问题是指在一个迷宫中，从起点到终点的最短路径问题。今天，我们将讨论使用Java语言来实现迷宫求解的方法。 问题描述 迷宫问题是指在一...

    链式栈实现递归和非递归迷宫路径求解

    "pers.hr.homework.maze"可能是包含迷宫求解算法实现的Java源代码文件。在这个文件中，我们可能会看到类的设计，包括节点类（Node）用于表示迷宫中的位置，栈类（Stack）用于存储和管理路径，以及主类（如MazeSolver...

    迷宫求解的代码

    在IT领域，迷宫求解是一个经典的问题，它涉及到图论、算法和数据结构等多个方面的知识。本主题的核心是设计一个程序，能够找到从迷宫的起点（入口）到终点（出口）的一条可行路径。这里我们将深入探讨迷宫求解的原理...

    迷宫求解——栈的简单应用

    它会帮助我们验证迷宫求解算法的正确性。 栈在迷宫求解中的应用体现了其在路径搜索中的优势，因为栈的特性使得我们可以轻松地回溯到前一步，直到找到正确的路径。这种方法称为深度优先搜索（DFS），是一种常用且...

    java 迷宫算法.rar

    总结来说，"java 迷宫算法.rar"提供的资源可能是一个使用Java实现的迷宫生成与求解程序，涵盖了深度优先搜索和广度优先搜索等基本算法，以及迷宫数据结构和回溯路径的恢复等核心概念。通过学习和理解这个程序，...

    基于Java的迷宫程序.rar.rar

    【描述】: "基于Java的迷宫程序" 提示这是一个用Java编写的迷宫生成和求解程序。可能包含了迷宫的生成算法（如深度优先搜索、Prim算法或Kruskal算法）、路径寻找算法（如广度优先搜索或A*算法）以及用户界面交互设计...

    迷宫自动求解程序

    2. 迷宫求解算法： - 广度优先搜索（BFS）：这是一种基础的图遍历算法，适合用于无权图的最短路径问题。BFS从起点开始，逐层探索所有可能的路径，直到找到目标为止。它的特点是找到的路径是最短的。 - 深度优先...

    迷宫问题 java swing

    在本项目中，我们将使用Java Swing作为图形用户界面（GUI）工具包，来实现一个可视化的迷宫求解器。Java Swing是Java Foundation Classes（JFC）的一部分，提供了一套丰富的组件和API，用于构建桌面应用程序。 首先...

    栈的应用 - 迷宫求解

    在IT领域，数据结构是计算机科学的基础，而栈是一种常用且重要的数据结构，它遵循“后进先出”（LIFO）的原则...通过对压缩包中的“maze”文件进行分析和实现，可以加深对栈和迷宫求解算法的理解，进一步提升技术实力。

    基于SWING的可视化迷宫算法

    本项目利用Java的SWING库来实现一个可视化的迷宫求解器，帮助用户直观地理解回溯法这一经典算法。 **一、SWING库简介** SWING是Java的一个图形用户界面（GUI）工具包，它是Java Foundation Classes (JFC)的一部分...

    迷宫游戏的Java实现及基于蚁群算法在寻找迷宫路径上的探究.pptx

    3. 蚁群算法在迷宫求解上的应用： * 蚂蚁碰到障碍物时，查看周围可到达点上信息素的浓度。 * 蚂蚁走进死角，必须要返回原路，删除该蚂蚁。 * 当蚂蚁到达终点时，停止行进。 4. 蚁群算法的特性： * 使用蚁群算法...

    算法实验报告：罗密欧与朱丽叶迷宫求解

    描述罗密欧与朱丽叶迷宫求解步骤，方便开发。

    迷宫问题用队列解决

    在IT领域，迷宫问题是一种经典的图论问题，它涉及到如何在一个二维网格中找到从起点到终点的最短路径...这种算法不仅适用于迷宫问题，也常用于其他寻找最短路径或最近节点的问题，如网络路由、社交网络中的朋友推荐等。

    JAVA迷宫 JAVA程序设计

    **迷宫求解算法** 解决迷宫问题最常用的方法是Dijkstra算法或A*算法。Dijkstra算法是一种寻找从起点到终点最短路径的无权图算法，而A*算法是Dijkstra算法的一种优化，引入了启发式函数来预测到达目标的估计成本，...

Magicbox
Global site tag (gtag.js) - Google Analytics