Java Swing基于树实现的迷宫小游戏

需求是这样的，我们需要实现根据量级来自动生成迷宫，并且从出口到入口需要有且只有一条通路。基于各数据结构的考虑，因为树的特性很好地符合了我们对生成迷宫的要求，树的任意两个节点之间是可达的，而且路径唯一。最终选择了树形数据结构。

如下图，选取A、B两个结点，能找到唯一可达路径：

迷宫的方格表示一个树的结点：

为保证迷宫的随机性，随机选取一个格子作为根结点起点：

并且随机向外（四个方向）延伸路径（若两点可达，则将“墙”打通），经过数次回溯迭代则可遍历所有结点，这样就保证了迷宫的所有格子都是可达的，而不会单纯随机生成“死路一条”的尴尬：

最后把标记出入口：

这样迷宫的实现就完成了。

基于这样的迷宫，我们需要找到一个可行路径。那么，我们从根节点开始，使用DFS分别找到到达入口和出口的路径，取并集-交集即可。如下图：

核心代码：

//方块类
class Square{

	static final int INTREE = 1;  //方块进树1
	static final int NOTINTREE = 0; //方块未进树0
	private int x ,flag, y;
	private Square father;       //父亲方块

	public Square() {  //构造	
		x=-1;	
		y=-1;	
		flag=NOTINTREE;	
		father=null;
	}
	public Square(int x, int y) {//设置方块的xy坐标	
		super();
		this.x = x;
		this.y = y;
	}

	public int getX() {  //返回x坐标
		return x;
	}

	public int getY() {  //返回y坐标
		return y;
	}

	public int getFlag() {   //返回标志位
		return flag;
	}

	public Square getFather() {  //获得父亲方块
		return father;
	}

	public void setFather(Square father) { //设置父亲方块
		this.father = father;
	}

	public void setFlag(int flag) {  //设置标志位
		this.flag = flag;
	}

	public String toString() {   //重定义对象输出
		return new String("(" + x + "," + y + ")\n");
	}
}

 private void createMaze() {           //随机生成迷宫
		    Random random = new Random();
		    int rx = Math.abs(random.nextInt())%num;
		    int ry = Math.abs(random.nextInt())%num;
		    Stack<Square> s = new Stack<Square>();
		    Square p = maze[rx][ry];
		    Square neis[] = null;
		    s.push(p);
		    while (!s.isEmpty()) {
		      p = s.pop();
		      p.setFlag(Square.INTREE);
		      neis = getNeis(p);
		      int ran = Math.abs(random.nextInt()) % 4;
		      for (int a = 0; a <= 3; a++) {
		        ran++;
		        ran %= 4;
		        if (neis[ran] == null || neis[ran].getFlag() ==Square.INTREE)
		          continue;
		        s.push(neis[ran]);
		        neis[ran].setFather(p);
		      }
		    }
		    // changeFather(maze[0][0],null);
	  }

为了增强用户交互，设置了使用方向键来控制人物逃出迷宫。每次逃出迷宫则难度升级，当然用户也可以自行调整难度。

其实现最终效果如下：

初始难度以及通关提醒（使用方向键可以控制小人移动）：

    

难度增大（按空格键可以显示正确路径）：

    

终极变态难度：

附上该实现的打包exe：

点击打开链接 https://download.csdn.net/download/qq_36840162/10386350