Java实现可视化迷宫

Myth丶恋晨 2022-03-10 08:44 230阅读 0赞

> 代码地址如下：  
> [http://www.demodashi.com/demo/14547.html][http_www.demodashi.com_demo_14547.html]

## 需求 ##

使用深度优先算法求解迷宫路径，使用Java实现求解过程的可视化，可单步运行，形象直观。

## 演示效果 ##

红色格子为迷宫终点，迷宫可放大缩小，为了录屏选择了较小的尺寸，有多种不同难度的迷宫可以加载。

1.  简单迷宫  
    ![cWoqNjDmy6cp4tBpVCQ.gif][]
2.  复杂迷宫  
    ![1q6KqDBpNtFEaETARuk.gif][]

## 项目运行 ##

文件中有两个运行脚本，Windows下直接双击`win运行.bat`即可，linux和Mac运行sh文件中的命令即可，喜欢用IDE的也可自行创建项目。  
运行项目后，点击菜单栏左上角的`Map`加载迷宫地图, 点击右下角的`Run`开始解迷宫,`Step`可单步运行,可通过速度进度条调节速度。

## 项目结构 ##

Maze
    ├── classes      # 存放编译生成的class文件
    ├── lib.jar      # 打包好的gui库
    ├── map          # 迷宫地图文件
    │   ├── EasyMaze.txt
    │   ├── FinalMaze01.txt
    │   ├── FinalMaze02.txt
    │   ├── FinalMaze03.txt
    │   ├── FinalMaze04.txt
    │   └── FinalMaze05.txt
    ├── src
    │   ├── MazeBug.java
    │   └── MazeBugRunner.java
    ├── linux运行.sh     # 运行脚本 
    └── win运行.bat     # 运行脚本

## 原理方法 ##

使用`深度优先算法`，每个格子下一步都有上下左右4种走法，但是这4种走法并不是都是合法的，比如有些格子有障碍物，有些格式在边界之外，去掉这些剩下的才是合法的走法。

深度优先算法的思想就是：

1.  找出当前位置A下一步合法的的格子，选择其中一个，往前走一步到达B。
2.  如果B相邻的有合法格子，重复第1步；如果没有合法的，后退一步回到A，选择A的其他合法格子走；
3.  重复以上方法，直到找到迷宫终点；

`算法优化`：上面的方法选择下一步走的方向是随机的，或者按照上下左右的顺序选择。但是很多迷宫都有偏向性，比如如果有右偏向性，那么每次都优先往右走可以更快走出迷宫。所以在实现的时候，记录每个方向走的次数，每往一个方向走一步就加1，如果回退就该方向减1，每次走都优先走次数最多的方向，当迷宫有偏向性时，该方法效率更高。

以项目中的迷宫为例，大部分情况下偏向性所需步数更少。

普通方法:   534 1175 350 973 1052
     偏向性:       552 761 330 175 420

## 代码实现 ##

/* * 节点：存储方向和该方向所走的次数 * 往一个方向前进则加1，后退则减1 */
    class Node { 
    	private int dir;   // 方向，角度值
    	private int ct;    // 该方向所走次数
    
    	public Node(int initdir, int initct) { 
    		dir = initdir;
    		ct = initct;
    	}
    
    	public int getDir() { 
    		return dir;
    	}
    
    	public int getCt() { 
    		return ct;
    	}
    
    	public void setCt(int deta) { 
    		ct += deta;
    	}
    }
    
    // 深度优先算法解迷宫，并且以小甲虫的形式呈现
    public class MazeBug extends Bug { 
    	private Location next;             // 下一步要走的格子
    	private Integer stepCount = 0;     // 所走的步数
    	private boolean isEnd = false;     // 是否到达迷宫出口
    	private boolean hasShown = false;  // 是否显示了结束信息
    	private Stack<Location> path = new Stack<>(); // 存储走过的路径
    	private ArrayList<Node> arr = new ArrayList<>();
    
    	public MazeBug() { 
    		setColor(Color.GREEN);
    		arr.add(new Node(0, 0));
    		arr.add(new Node(90, 0));
    		arr.add(new Node(270, 0));
    		arr.add(new Node(180, 0));
    	}
    
    	// 周期性执行
    	public void act() { 
    		boolean willMove = canMove();   // 是否还能继续移动
    
    		if (isEnd) {   // 是否结束
    			if (!hasShown) {  // 是否显示结束消息
    				String msg = stepCount.toString() + " steps";
    				JOptionPane.showMessageDialog(null, msg);
    				hasShown = true;
    			}
    			return;
    		} else if (willMove) {  // 向前移动一个，步数加1
    			move();
    			++stepCount;
    		} else {  // 不能移动，后退一步，将该方向的计数器减1
    			Grid<Actor> grid = getGrid();
    			Location loc = this.getLocation();
    			Location top = path.pop();
    			++stepCount;
    			grid.remove(top);
    			this.setDirection(loc.getDirectionToward(top));
    			this.moveTo(top);
          // 在走过的死路留下一朵白花
    			Flower flower = new Flower(Color.WHITE);
    			flower.putSelfInGrid(getGrid(), loc);
    
    			// 方向计数器减1
    			int dir = 180 + ((getDirection() / 90) % 2) * 180 - getDirection();
    			for (Node node : arr)
    				if (node.getDir() == dir) { 
    					node.setCt(-1);
    					return;
    				}
    		}
    	}
    
    	// 找出和当前位置相邻的、合法的并且从未走过的格子
    	public Location getValid(Location loc) { 
    		Grid<Actor> gr = getGrid();
    		if (gr == null)
    			return null;
    
    		// 将每个方向走过的次数从大到小排序，下一步优先选次数多的方向走
    		Location adjLocation;
    		arr.sort(new Comparator<Node>() { 
    			@Override
    			public int compare(Node a, Node b) { 
    				return (a.getCt() < b.getCt()) ? 1 : -1;
    			}
    		});
    
    		for (Node node : arr) { 
    			adjLocation = this.getLocation().getAdjacentLocation(node.getDir());
    			if (gr.isValid(adjLocation)
    					&& (gr.get(adjLocation) == null || gr.get(adjLocation).getColor().equals(Color.RED))) { 
    				node.setCt(1);
    				return adjLocation;
    			}
    		}
    		return null;
    	}
    
    	// 判断当前位置是否可以继续移动
    	public boolean canMove() { 
    		Grid<Actor> gr = getGrid();
    		Actor adj;
    		Location loc = this.getValid(this.getLocation());
    		if (loc != null) { 
    			adj = gr.get(loc);
    			next = loc;
    			isEnd = adj != null && adj.getColor().equals(Color.RED);
    			return true;
    		}
    		return false;
    	}
    
    	// 将甲虫的方向转向下一格，往前移动一步，将原来的位置压栈，并放置一朵绿花，表示走过的路径
    	public void move() { 
    		Grid<Actor> gr = getGrid();
    		if (gr == null)
    			return;
    		Location loc = this.getLocation();
    		path.push(loc);
    		this.setDirection(loc.getDirectionToward(next));
    		this.moveTo(next);
    		Flower flower = new Flower(this.getColor());
    		flower.putSelfInGrid(gr, loc);
    	}
    }

## 其他： ##

跟算法无关的代码，比如GUI方面的都打包成`lib.jar`了，如果想要自己更改可以自行解压。Java实现可视化迷宫

> 代码地址如下：  
> [http://www.demodashi.com/demo/14547.html][http_www.demodashi.com_demo_14547.html]

> 注：本文著作权归作者，由demo大师发表，拒绝转载，转载需要作者授权

[http_www.demodashi.com_demo_14547.html]: http://www.demodashi.com/demo/14547.html
[cWoqNjDmy6cp4tBpVCQ.gif]: /images/20220310/89ad2a2cf09b4106971bbd2a4af5fa6f.png
[1q6KqDBpNtFEaETARuk.gif]: /images/20220310/d8c981ee97bc4905a0e9fdd8f557adc6.png