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

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

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

 

随机生成迷宫的算法怎么这么快就沉下去了

稍微粗略看了下你的代码，没怎么看懂你的实现~~

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

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

是这个样子的，willvisit用来记录生成迷宫和走迷宫的时候，从当前位置可以移动到的下一个位置，comed就是在走迷宫的时候用于记录已经走过的位置的，也就是栈，不知道这样说清楚不。

LZ,有个问题请教您。就是怎么能保证生成的迷宫一定能走出去呢？

在生成迷宫的时候使用到了树的深度优先算法，遍历了树中的所有节点，所以生成的迷宫一定是可以走得通的哈。

用回溯法可以哦

正解~

既然是算法设计，就应该把算法思路用文字方式清晰地表达出来，光贴代码不好。

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