基于递归分割的迷宫生成算法与自动寻路

import java.util.LinkedList; import java.util.Queue; import java.util.Random; import java.util.Stack; /** * 迷宫生成算法和迷宫寻路算法 * @author ygch */ public class Maze { private int height; private int width; private Random r; //随机位置生成器 private boolean blocked[][]; boolean[][] visited;//寻路过程中判断某个位置是否已经被访问过 private Stack<Coordinate> path;//寻路过程中保存的路径 private final int[][] direction={{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; /** * 重构equals函数，方便后面的比较操作 */ @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Maze other = (Maze) obj; return height == other.height && width == other.width; } public Maze(int height, int width) { super(); this.height = height; this.width = width; //让整个迷宫的大小为奇数，这样可以构造一行路一行墙的迷宫 if(this.height%2==0) this.height+=1; if(this.width%2==0) this.width+=1; r = new Random(); path= new Stack<>(); //给迷宫四周加上墙 blocked = new boolean[this.height + 2][this.width + 2]; visited=new boolean[this.height+2][this.width+2]; // 最左和最右两列置1 for (int i = 0; i < this.height + 2; i++) { blocked[i][0] = true; blocked[i][this.width + 1] = true; } // 最上和最下两行置1 for (int i = 0; i < this.width + 2; i++) { blocked[0][i] = true; blocked[this.height + 1][i] = true; } } public int getHeight() { return height; } public int getWidth() { return width; } public boolean[][] getBlocked() { return blocked; } public Stack<Coordinate> getFoundPath() { return path; } /** * 重置迷宫，使其四周为墙，内部为空 */ public void resetMaze() { // 最左和最右两列置1 for (int i = 0; i < height + 2; i++) { blocked[i][0] = true; blocked[i][width + 1] = true; } // 最上和最下两行置1 for (int i = 0; i < width + 2; i++) { blocked[0][i] = true; blocked[height + 1][i] = true; } //内部全部为空 for(int i=1;i<height+1;i++) { for(int j=1;j<width+1;j++) { blocked[i][j]=false; } } } /** * 重置位置是否访问数组 */ public void resetVisited() { for(int i=1;i<height+1;i++) { for(int j=1;j<width+1;j++) { visited[i][j]=false; } } } /** * 在给定的线上打开一扇位置随机的门 */ private void openAdoor(int x1, int y1, int x2, int y2) { int pos; if (x1 == x2) { pos = y1 + r.nextInt((y2 - y1 )/2+ 1)*2;//在偶数位置开门 blocked[x1][pos] = false; } else if (y1 == y2) { pos = x1 + r.nextInt((x2 - x1 )/2+ 1)*2; blocked[pos][y1] = false; } else { System.out.println("wrong"); } } /** * 迷宫生成算法，采用递归方式实现，随机画横竖两条线，然后在线上随机开三扇门 * @param x：迷宫起点的x坐标 * @param y：迷宫起点的y坐标 * @param height：迷宫的高度 * @param width：迷宫的宽度 * *********** * * * * * * * *********** * 针对上述迷宫，四个参数为：1,1,2,9 */ private void genMaze(int x, int y, int height, int width) { int xPos, yPos, isClosed; System.out.println("input is " + x + " " + y + " " + height + " " + width); if (height <= 2 || width <= 2) return; //横着画线，在奇数位置画线 xPos=x+r.nextInt(height/2)*2+1; for (int i = y; i < y + width; i++) { blocked[xPos][i] = true; } //竖着画一条线，在奇数位置画线 yPos=y+r.nextInt(width/2)*2+1; for (int i = x; i < x + height; i++) { blocked[i][yPos] = true; } //随机开三扇门 isClosed = r.nextInt(4) + 1; switch (isClosed) { case 1: openAdoor(xPos + 1, yPos, x + height - 1, yPos);// 2 openAdoor(xPos, yPos + 1, xPos, y + width - 1);// 3 openAdoor(x, yPos, xPos - 1, yPos);// 4 break; case 2: openAdoor(xPos, yPos + 1, xPos, y + width - 1);// 3 openAdoor(x, yPos, xPos - 1, yPos);// 4 openAdoor(xPos, y, xPos, yPos - 1);// 1 break; case 3: openAdoor(x, yPos, xPos - 1, yPos);// 4 openAdoor(xPos, y, xPos, yPos - 1);// 1 openAdoor(xPos + 1, yPos, x + height - 1, yPos);// 2 break; case 4: openAdoor(xPos, y, xPos, yPos - 1);// 1 openAdoor(xPos + 1, yPos, x + height - 1, yPos);// 2 openAdoor(xPos, yPos + 1, xPos, y + width - 1);// 3 break; default: break; } // 左上角 genMaze(x, y, xPos - x, yPos - y); // 右上角 genMaze(x, yPos + 1, xPos - x, width - yPos + y - 1); // 左下角 genMaze(xPos + 1, y, height - xPos + x - 1, yPos - y); // 右下角 genMaze(xPos + 1, yPos + 1, height - xPos + x - 1, width - yPos + y - 1); } /** * 迷宫生成外部调用代码，生成一个全联通的迷宫 */ public void genMaze() { resetMaze(); genMaze(1,1,height,width); printMaze(); } public void genMazeDFS() { for(int i=0;i<height+2;i++) { for(int j=0;j<width+2;j++) { visited[i][j]=false; blocked[i][j]=true; } } // 最左和最右两列置1 for (int i = 0; i < height + 2; i++) { visited[i][0] = true; visited[i][width + 1] = true; } // 最上和最下两行置1 for (int i = 0; i < width + 2; i++) { visited[0][i] = true; visited[height + 1][i] = true; } Coordinate start=new Coordinate(r.nextInt(height)+1, r.nextInt(width)+1); // blocked[start.x][start.y]=false; visited[start.x][start.y]=true; Stack<Coordinate> s=new Stack<>(); s.add(start); System.out.printf("add (%d,%d)\n",start.x,start.y); while(!s.isEmpty()) { Coordinate c=s.pop(); int i=r.nextInt(4); int NonBlockedNeighbourCount=0; for(int j=0;j<4;j++) { if(blocked[c.x+direction[i][0]][c.y+direction[i][1]]==false) { NonBlockedNeighbourCount++; } if(visited[c.x+direction[i][0]][c.y+direction[i][1]]==false) { visited[c.x+direction[i][0]][c.y+direction[i][1]]=true; s.add(new Coordinate(c.x+direction[i][0], c.y+direction[i][1])); // System.out.printf("add (%d,%d)\n",c.x+direction[i][0], c.y+direction[i][1]); } i=(i+1)%4; } // System.out.printf("(%d,%d) has %d non block neighbours\n",c.x,c.y,NonBlockedNeighbourCount); if(NonBlockedNeighbourCount<3) { blocked[c.x][c.y]=false; } } } /** * 打印迷宫 */ public void printMaze() { for (int i = 0; i < height + 2; i++) { for (int j = 0; j < width + 2; j++) { if (blocked[i][j]) { System.out.print("* "); } else { System.out.print("0 "); } } System.out.println(); } } /** * 判断一个迷宫中的空位置是否都可达 * * @return */ public boolean isConnected() { int nonBlockCount=0,visitNonBlockCount=0; //统计迷宫中空位置的个数 for(int i=1;i<height+1;i++) { for(int j=1;j<width+1;j++) { if(!blocked[i][j]) nonBlockCount++; } } resetVisited(); Queue<Coordinate> q = new LinkedList<>(); //(1,1)点肯定是空位置 q.add(new Coordinate(1, 1)); visited[1][1]=true; while(!q.isEmpty()) { visitNonBlockCount++; Coordinate c=q.poll(); for(int i=0;i<4;i++) { if(!blocked[c.x+direction[i][0]][c.y+direction[i][1]] &&!visited[c.x+direction[i][0]][c.y+direction[i][1]]) { q.add(new Coordinate(c.x+direction[i][0], c.y+direction[i][1])); visited[c.x+direction[i][0]][c.y+direction[i][1]]=true; } } } return nonBlockCount==visitNonBlockCount; } /** * 判断两点之间是否联通 * @param start * @param end * @return */ public boolean hasPath(Coordinate start,Coordinate end) { if(blocked[start.x][start.y]||blocked[end.x][end.y]) { return false; } if(start.x==end.x&&start.y==end.y) { return true; } resetVisited(); Queue<Coordinate> q = new LinkedList<>(); q.add(start); visited[start.x][start.y]=true; while(!q.isEmpty()) { Coordinate c=q.poll(); for(int i=0;i<4;i++) { if(!blocked[c.x+direction[i][0]][c.y+direction[i][1]] &&!visited[c.x+direction[i][0]][c.y+direction[i][1]]) { if(c.x+direction[i][0]==end.x&&c.y+direction[i][1]==end.y) return true; q.add(new Coordinate(c.x+direction[i][