迷宫:是指一种充满复杂通道的建筑物,很难找到从其内部到达入口或从入口到达中心的道路。在图书、杂志中也会经常出现迷宫的题目作为消遣游戏,而且各种形式的迷宫也被使用在电脑游戏中。
下面介绍一个生成迷宫的算法:
- 首先将迷宫分成若干个正方形的单元格,并随机选中一个作为起始点(start)。
- 将正被访问的单元格标记为已访问,得到它所有相邻单元格。在这些相邻的单元格中随机选择一个,如果这个被选中的单元格没有被访问过, 那么移掉正被访问单元格和被选中单元格之间的墙体,并将这个被选中单元格作为正被访问单元格。如果正被访问单元格的所有相邻单元格都被访问过。 那么在所有被访问过的单元格(这里指迷宫中所有已被访问过的单元格)中随机选中一个作为正被访问单元格,如此递归下去,直到迷宫中所有的单元格都被访问过为止。
- 这样迷宫就生成了,下图即为此算法生成的迷宫。
下面用 Java 实现上文所述算法(也可以下载源码,压缩包中不仅包括了 Java 源码还提供了一个调用的 html 网页):
import java.applet.Applet; import java.awt.Color; import java.awt.Graphics; import java.util.Random;
public class CreateMaze extends Applet { // 迷宫行数 private int mazeRowCount = 10; // 迷宫列数 private int mazeColCount = 12; // 迷宫单元格宽度 private int width = 10; // 迷宫边框颜色 private static final Color WALL_COLOR = Color.black; // 0点位置 private int zeroX = width; private int zeroY = width; private Random random = null; // 已经被访问过的单元格 private Cell[] visitedCells = null; private int visitedCount = 0; private int cellCount = 0; /* * 迷宫 map[列数][行数],就是x轴与y轴 map[x][y] * 坐标0点为画布左上角:0点向右为x正方向,0点向下表示y正方向 */ Cell map[][] = null; public void init() { super.init(); if(getParameter("mazerow")!=null) mazeRowCount = Integer.parseInt( getParameter("mazerow")); if(getParameter("mazecol")!=null) mazeColCount = Integer.parseInt( getParameter("mazecol")); if(getParameter("cellwidth")!=null) width = Integer.parseInt( getParameter("cellwidth")); cellCount = mazeColCount * mazeRowCount; visitedCells = new Cell[cellCount]; random = new Random(); // 初始化迷宫 Cell cell; map = new Cell[mazeColCount][mazeRowCount]; for( int y=0;y<mazeRowCount;y++) for( int x=0;x<mazeColCount;x++) { cell = new Cell(); cell.x = zeroX + x*width; cell.y = zeroY + y*width; cell.col = x; cell.row = y; map[x][y] = cell; } } public void paint(Graphics g) { createMaze(); paintMaze(g); } private void createMaze() { // 随机开始点 initMaze( map[random.nextInt(mazeColCount)][random.nextInt(mazeRowCount)]); // 设置开始结束点 map[0][mazeRowCount-1].walls[Cell.BOTTOM] = Cell.NOWALL; map[mazeColCount-1][0].walls[Cell.TOP] = Cell.NOWALL; } private void initMaze(Cell theCell) { // 单元格全部被访问过,创建完毕 if( visitedCount == cellCount) return; if(!isVisited(theCell)) { theCell.visited = true; visitedCells[visitedCount++] = theCell; } // 得到有效的相邻单元格 int neibCount = 0; Cell[] neighbours = new Cell[4]; // left Cell nextCell; if(theCell.col-1>=0 && !(nextCell =map[theCell.col-1][theCell.row]).visited) { neighbours[neibCount++] = nextCell; } // top if(theCell.row-1>=0 && !(nextCell=map[theCell.col][theCell.row-1]).visited) { neighbours[neibCount++] = nextCell; } // right if(theCell.col+1<this.mazeColCount && !(nextCell = map[theCell.col+1][theCell.row]).visited) { neighbours[neibCount++] = nextCell; } // bottom if(theCell.row+1<this.mazeRowCount && !(nextCell = map[theCell.col][theCell.row+1]).visited) { neighbours[neibCount++] = nextCell; } // 如果临近的单元格都已被访问 if(neibCount == 0) { initMaze(visitedCells[random.nextInt(visitedCount)]); return; } // 随机得到下一个单元格 nextCell = neighbours[random.nextInt(neibCount)]; // 去掉单元格和选择的邻近单元格之间的墙 // neighbour left if(nextCell.col<theCell.col) { nextCell.walls[Cell.RIGHT] = Cell.NOWALL; theCell.walls[Cell.LEFT] = Cell.NOWALL; } // neighbour top else if(nextCell.row < theCell.row) { nextCell.walls[Cell.BOTTOM] = Cell.NOWALL; theCell.walls[Cell.TOP] = Cell.NOWALL; } // neighbour right else if(nextCell.col > theCell.col) { nextCell.walls[Cell.LEFT] = Cell.NOWALL; theCell.walls[Cell.RIGHT] = Cell.NOWALL; } // neighbour bottom else if(nextCell.row > theCell.row) { nextCell.walls[Cell.TOP] = Cell.NOWALL; theCell.walls[Cell.BOTTOM] = Cell.NOWALL; } initMaze(nextCell); } /* * 单元格是否被访问过 */ private boolean isVisited(Cell cell) { if(visitedCount == 0 ) return false; for( int i=0;i<visitedCount;i++) { if(visitedCells[i] == cell) return true; } return false; } private void paintMaze(Graphics g) { for( int y=0;y<mazeRowCount;y++) for( int x=0;x<mazeColCount;x++) map[x][y].paint(g); } class Cell { static final int LEFT = 0; static final int TOP = 1; static final int RIGHT = 2; static final int BOTTOM = 3; static final int NOWALL = 0; static final int HAVEWALL = 1; int state = 0; // 单元格的像素位置 int x = 0; int y = 0; // 单元格在迷宫中的行与列 int col = 0; int row = 0; // 单元格访问标记 boolean visited = false; /* * 单元格墙体状态,0 :无墙,1:有墙。 * 表示顺序是:左、上、右、下,即从左开始逆时针旋转。 */ int[] walls = new int[]{HAVEWALL,HAVEWALL,HAVEWALL,HAVEWALL}; // 根据单元格位置画出单元格 void paint(Graphics g) { g.setColor(WALL_COLOR); int x1 = 0,y1=0,x2=0,y2=0; for ( int i=0;i<4;i++) { if(walls[i] == NOWALL) continue; switch(i) { // left case LEFT: x1 = this.x; y1 = this.y; x2 = x1; y2 = y1 + width; break; // top case TOP: x1 = this.x; y1 = this.y; x2 = x1 + width; y2 = y1; break; // right case RIGHT: x1 = this.x+width; y1 = this.y; x2 = x1; y2 = y1 + width; break; // bottom case BOTTOM: x1 = this.x; y1 = this.y +width; x2 = x1 +width; y2 = y1; break; } // drawoline g.drawLine(x1, y1, x2, y2); } } } } |