MAZE_TEST.zip_Java中maze_maze_maze java 迷宫_maze stack java_迷宫 jav

package com.maze.core; import com.maze.utl.LinkQueue; import com.maze.utl.LinkStack; public class Maze implements Runnable, MazeInterface { MazeCell mazeCell[][]; // 存放每个小格的信息 private static int cells[]; // 是否连通 private int rows; // 有多少行 private int cols; // 有多少列 private MazeUIInterface mazeUI; // 用来跟界面交互 private int delayTime = 1000; // 每画一小段路径要延时多久 private int currentStepNum = 0; // 记录当前已经走了多少步 private boolean runFlag = false; // 是否运行/继续运行 private boolean algorithmFlag = true; // 默认是广度优先 private boolean pauseFlag = false; // 默认不暂停 private boolean refreshInfoFlag = true; // 是否需要更新行列数量 String dir[] = { "right", "down", "left", "up" }; // 用于调试时输出方向 public void setPauseFlag(boolean pauseFlag) { this.pauseFlag = pauseFlag; } public void setAlgorithmFlag(boolean algorithmFlag) { this.algorithmFlag = algorithmFlag; } public MazeCell[][] getMazeCell() { return mazeCell; } public Maze(int rows, int cols) { // 构造函数 this.rows = rows; this.cols = cols; refreshInfoFlag = true; // 需要更新 } public void setMazeInfo(int row, int col) { // System.out.printf("before rows = %2d, cols = %2d\n", this.rows, // this.cols); // System.out.printf("needto rows = %2d, cols = %2d\n", rows, cols); if ((this.rows == row) && (this.cols == col)) { refreshInfoFlag = false; } else { this.rows = row; this.cols = col; // System.out.printf(" after rows = %2d, cols = %2d\n", this.rows, // this.cols); refreshInfoFlag = true; // 需要更新 } // System.out.printf("after rows = %2d, cols = %2d\n", this.rows, // this.cols); } public void setDelayTime(int delayTime) { this.delayTime = delayTime; } public void setMazeFrame(MazeUIInterface mazeUI) { this.mazeUI = mazeUI; } public void setRunFlag(boolean runFlag) { this.runFlag = runFlag; } public void delayed() { try { Thread.sleep(delayTime); // 延时指定的时间 } catch (InterruptedException e) { e.printStackTrace(); } } public void init() { if (refreshInfoFlag) { // 需要更新 MazeCell tempMazeCell[][] = mazeCell; int tempInt[] = cells; do { mazeCell = null; mazeCell = new MazeCell[rows][cols]; cells = null; cells = new int[rows * cols];// 输出更新后对象的地址 if ((tempMazeCell != mazeCell) && (tempInt != cells)) break; } while (true); tempMazeCell = null; tempInt = null; } for (int y = 0; y < rows; y++) { for (int x = 0; x < cols; x++) { cells[y * cols + x] = -1; if (refreshInfoFlag) { mazeCell[y][x] = new MazeCell(x, y, false, false); } else { mazeCell[y][x].setDoor(false, false); } } } mazeCell[0][0].setDoor(MazeCell.LEFT, true); refreshInfoFlag = false; } private static final int TYPE_NEVER = 0; private static final int TYPE_VISIT = 1; private static final int TYPE_SAVE = 1; // 深度优先 public void solveUseStack() { currentStepNum = 0; // 步数归零 int count = 0; int colorPointer=0; int tempX=0, tempY=0; XY tempXY = null; LinkStack<XY> preLinkStack = new LinkStack<XY>(); LinkStack<XY> nextLinkStack = new LinkStack<XY>(); preLinkStack.push(new XY(0, 0)); tempXY = new XY(0,0); while((runFlag)){ colorPointer = (++colorPointer) % MazeUIInterface.colorCount; tempXY = preLinkStack.pop(); //判断四个方向是否已访问，未访问的话是否可达，可达的就画路径，画完之后入栈 count=0; //上边可达 if((tempXY.y != 0)&&(mazeCell[tempXY.y-1][tempXY.x].getVisited() == TYPE_NEVER)){ if(mazeCell[tempXY.y][tempXY.x].getDoor(MazeCell.UP)){ count++; mazeUI.drawPath(MazeUIInterface.pathColor[colorPointer], MazeCell.DOWN, tempXY.x, tempXY.y, tempXY.x, tempXY.y-1); preLinkStack.push(new XY(tempXY.x, tempXY.y-1)); if (!runFlag) { break; } delayed(); while (pauseFlag && runFlag) { try { Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } } } } //右边可达 if((tempXY.x != cols-1)&&(mazeCell[tempXY.y][tempXY.x+1].getVisited() == TYPE_NEVER)){ if((mazeCell[tempXY.y][tempXY.x+1].getDoor(MazeCell.LEFT))){ count++; mazeUI.drawPath(MazeUIInterface.pathColor[colorPointer], MazeCell.LEFT, tempXY.x, tempXY.y, tempXY.x+1, tempXY.y); preLinkStack.push(new XY(tempXY.x+1, tempXY.y)); if (!runFlag) { break; } delayed(); while (pauseFlag && runFlag) { try { Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } } } } //下面可达 if((tempXY.y != rows-1)&&(mazeCell[tempXY.y+1][tempXY.x].getVisited()==TYPE_NEVER)){ if(mazeCell[tempXY.y+1][tempXY.x].getDoor(MazeCell.UP)){ count++; mazeUI.drawPath(MazeUIInterface.pathColor[colorPointer], MazeCell.UP,tempXY.x, tempXY.y, tempXY.x, tempXY.y+1); preLinkStack.push(new XY(tempXY.x, tempXY.y+1)); if (!runFlag) { break; } delayed(); while (pauseFlag && runFlag) { try { Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } } } } //左边可达 if((tempXY.x != 0)&&(mazeCell[tempXY.y][tempXY.x-1].getVisited()==TYPE_NEVER)){ if(mazeCell[tempXY.y][tempXY.x].getDoor(MazeCell.LEFT)){ count++; mazeUI.drawPath(MazeUIInterface.pathColor[colorPointer], MazeCell.RIGHT,tempXY.x, tempXY.y, tempXY.x-1, tempXY.y); preLinkStack.push(new XY(tempXY.x-1, tempXY.y)); if (!runFlag) { break; } delayed(); while (pauseFlag && runFlag) { try { Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } } } } //四个方向都不可达，则将当前格子设置为已访问，退后一格，重复此过程 if(count == 0){ mazeCell[tempXY.y][tempXY.x].setVisited(TYPE_VISIT); tempXY = preLinkStack.pop(); } } if ((tempXY.x == cols - 1) && (tempXY.y == rows - 1)) { mazeUI.drawEnd(); runFlag = false; // System.out.printf("currentX = %2d, currentY = %2d\n",currentX, // currentY); } printStack(preLinkStack); mazeUI.changeRunningStatus(false); // System.out.println("tcghvjhbj"); // printStack(preCellList); } public void solveUseStack2() { currentStepNum = 0; // 步数归零 int colorPointer = 0; int nextNum = 0; // 记录当前节点可达的后节点个数 int preX, preY; // 前节点坐标 int currentX = 0, currentY = 0; // 后节点坐标（当前节点） XY previousXY, currentXY = new XY(0, 0); int from = MazeCell.LEFT; // 初始化方向，表示从左边走到（0，0） LinkStack<XY> preCellList = new LinkStack<XY>(); // 前节点栈 LinkStack<XY> nextCellsList = new LinkStack<XY>(); // 后节点栈 LinkStack<Integer> dirList = new LinkStack<Integer>(); // 记录方向（与前节点同步） mazeUI.drawStart(); // 画起点 // 根据方向(from)找出与当前节点相邻的所有节点 nextNum = checkNextUseStack(nextCellsList, dirList, preCellList, from, currentX, currentY); if (nextNum > 1) { preCellList.push(new XY(currentX, currentY)); } delayed(); while ((runFlag) && (!nextCellsList.isEmpty()) && (((currentX != (cols - 1)) || (currentY != (rows - 1))))) { if (nextNum == 0) { //遇到死胡同，返回上一个分岔口 colorPointer = (++colorPointer) % MazeUIInterface.colorCount; previousXY = preCellList.pop(); //上一个分叉口出栈 preX = previousXY.getX(); preY = previousXY.getY(); System.out.printf("pop x = %2d, y = %2d