Java深度优先遍历算法随机生成迷宫

package maze; import javax.swing.*; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.BasicStroke; import java.awt.BorderLayout; import java.awt.Color; import java.util.Random; import java.lang.Object; class drawMaze extends JPanel{ /** * @author peanuo */ private static final long serialVersionUID = -8136524965355601090L; public static MazeUnit[][] pos2; public static int mx,my; Object[] pathx; Object[] pathy; public drawMaze(int mx,int my) { pos2 = new MazeUnit[mx][my]; pathx = new Object[(mx-2)*(my-2)]; pathy = new Object[(mx-2)*(my-2)]; } public void getData(MazeUnit[][] pos4,Object[] path1,Object[] path2,int dx,int dy) { System.arraycopy(pos4, 0, pos2, 0, pos4.length); System.arraycopy(path1, 0, pathx, 0, path1.length); System.arraycopy(path2, 0, pathy, 0, path2.length); mx = dx; my = dy; } //根据输入的数组数据绘制迷宫图 public void paint(Graphics g) { super.paint(g); ((Graphics2D) g).setStroke(new BasicStroke(3.0f)); g.setColor(Color.BLACK); for(int i=1;i<mx-1;i++) { for(int j=1;j<my-1;j++) { int cx = 30*i+50; int cy = 30*j+50; for(int w=0;w<4;w++) { if(pos2[i][j].wall[w] == 1) { int x1,y1,x2,y2; x1 = y1 = x2 = y2 = 0; switch(w) { case 0: x1 = cx-15; y1 = cy-15; x2 = cx-15; y2 = cy+15; break; case 1: x1 = cx-15; y1 = cy-15; x2 = cx+15; y2 = cy-15; break; case 2: x1 = cx-15; y1 = cy+15; x2 = cx+15; y2 = cy+15; break; case 3: x1 = cx+15; y1 = cy-15; x2 = cx+15; y2 = cy+15; break; } g.drawLine(x1, y1, x2, y2); } } } } //绘制两个出口的路径 ((Graphics2D) g).setStroke(new BasicStroke(1.0f)); g.setColor(Color.RED); for(int i=0;i<pathx.length-1;i++) { if(pathx[i+1] == null){ break; } int[] tempwall = new int[4]; MazeUnit temp = new MazeUnit(false,tempwall,true); temp = (MazeUnit) pathx[i]; int x1 = 30*temp.x+50; int y1 = 30*temp.y+50; temp = (MazeUnit) pathx[i+1]; int x2 = 30*temp.x+50; int y2 = 30*temp.y+50; g.drawLine(x1, y1, x2, y2); } g.setColor(Color.BLUE); for(int i=0;i<pathy.length-1;i++) { if(pathy[i+1] == null){ break; } int[] tempwall = new int[4]; MazeUnit temp = new MazeUnit(false,tempwall,true); temp = (MazeUnit) pathy[i]; int x1 = 30*temp.x+55; int y1 = 30*temp.y+55; temp = (MazeUnit) pathy[i+1]; int x2 = 30*temp.x+55; int y2 = 30*temp.y+55; g.drawLine(x1, y1, x2, y2); } } } public class CreateMaze { public static int x,y,nx,ny,dir;//x、y为当前单元坐标，nx、ny为相邻单元的坐标，dir为当前单元的墙的方向 public static void initialize(int mx,int my) { MazeUnit[][] pos = new MazeUnit[mx][my];//mx、my为行数、列数加2 //初始化迷宫单元数组 int i,j; for(i=0;i<mx;i++) { for(j=0;j<my;j++) { int[] wall = new int[4]; for(int w=0;w<4;w++) { wall[w] = 1;//将所有迷宫单元用墙隔开 } pos[i][j] = new MazeUnit(false,wall,true); pos[i][j].x = i; pos[i][j].y = j; } } //设置可访问性数组的值，创建外围边界 for(i=1;i<mx-1;i++) { for(j=1;j<my-1;j++) { pos[i][j].accessible = true; } } i=0; for(j=0;j<my;j++) { pos[i][j].accessible = false; } i=mx-1; for(j=0;j<my;j++) { pos[i][j].accessible = false; } j=0; for(i=0;i<mx;i++) { pos[i][j].accessible = false; } j=my-1; for(i=0;i<mx;i++) { pos[i][j].accessible = false; } //生成入口和两个随机出口 Random randx = new Random(); int endx = randx.nextInt(mx-2)+1; Random randy = new Random(); int endy = randy.nextInt(my-2)+1; pos[1][1].wall[0] = 0; pos[endx][my-2].wall[2] = 0; pos[mx-2][endy].wall[3] = 0; IArrayStack path = new StackImpl(mx-2,my-2); path.push(pos[1][1]); x=y=1; nx=ny=0; dir=0; Object[] pathx = new Object[(mx-2)*(my-2)]; Object[] pathy = new Object[(mx-2)*(my-2)]; while(countIsVisited(pos,mx,my) < (mx-2)*(my-2)) { randway(); //记录两个出口的路径 if((x == endx)&&(y == my-2)) { pathx = path.copyArray().clone(); } if((x == mx-2)&&(y == endy)) { pathy = path.copyArray().clone(); } if(isBlock(pos,x,y) == false) { breakwall(pos,path); } else if(isBlock(pos,x,y) == true) { pos[x][y].isVisited = true; path.pop();//将当前单元出栈 int[] tempwall = new int[4]; MazeUnit temp = new MazeUnit(false,tempwall,true); temp = (MazeUnit) path.top();//将前一单元转换为当前单元 x = temp.x; y = temp.y;//将坐标转换为前一单元的坐标 } } JFrame win2 = new JFrame(); win2.setTitle("随机生成迷宫"); win2.setSize(mx*30+80, my*30+80); win2.setLocationRelativeTo(null); win2.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); drawMaze pic = new drawMaze(mx,my); pic.getData(pos,pathx,pathy,mx,my); win2.add(pic, BorderLayout.CENTER); win2.setResizable(false); win2.setVisible(true); } //随机选择一个相邻单元 private static void randway() { Random rand = new Random(); dir = rand.nextInt(4); switch(dir) { case 0: nx = x-1; ny = y; break; case 1: nx = x; ny = y-1; break; case 2: nx = x; ny = y+1; break; case 3: nx = x+1; ny = y; break; } } //当前迷宫单元随机选择一个相邻的单元进行破墙 private static void breakwall(MazeUnit[][] pos,IArrayStack path) { if((pos[nx][ny].accessible == true) && (pos[nx][ny].isVisited == false)){ pos[x][y].wall[dir] = 0; pos[x][y].isVisited = true; pos[nx][ny].wall[3-dir] = 0; path.push(pos[nx][ny]); x = nx; y = ny; } else { randway(); breakwall(pos,path); } } //判断当前迷宫单元是否堵塞 private static boolean isBlock(MazeUnit[][] pos1,int x,int y) { int block=0; for(int w=0;w<4;w++) { int nx=0,ny=0; switch(w) { case 0: nx = x-1; ny = y; break; case 1: nx = x; ny = y-1; break; case 2: nx = x; ny = y+1; break; case 3: nx = x+1; ny = y; break; } if((pos1[nx][ny].accessible == false) || (pos1[nx][ny].isVisited == true)) { block++; } } if(block == 4) return true; else return false; } //计算已访问的单元个数 private static int countIsVisited(MazeUnit[][] pos3,int mx,int my) { int num = 0; for(int i=1;i<mx;i++) { for(int j=1;j<my;j++) { if(pos3[i][j].isVisited == true) { num++; } } } return num; } }