我基于 Prim 算法编写了一个迷宫生成器程序:
该算法是 Prim 算法的随机版本。
- 从充满墙壁的网格开始。
- 选择一个单元格,将其标记为迷宫的一部分。将单元格的墙壁添加到墙壁列表中。
- While there are walls in the list:
- Pick a random wall from the list.
If the cell on the opposite side isn't in the maze yet:
- 将墙设置为通道,并将另一侧的单元格标记为迷宫的一部分。
- 将单元格的相邻墙壁添加到墙壁列表中。
- 如果对面的单元格已经在迷宫中,则从列表中删除墙。
(from 维基百科 http://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim.27s_algorithm)
我已经理解了算法,我只是停留在这部分:
“知道相邻单元格是否构成迷宫的一部分”(这意味着,首先获取相邻单元格)
由于单元实际上是树的节点(迷宫,单元的二维数组),而墙壁是这些节点之间的边缘,我认为有必要用一对点(x,y )。我如何知道两个 Cell 是否通过墙连接?
(记住每个单元格有 4 个墙)
我考虑过使用 equals() 函数。我只是要求提供伪代码或您最好的解释,以使事情变得更容易。
我的 Wall 类具有三个属性: bool isWall(确定它是墙还是单元格之间的通道);整数x; int y(标识符)。
如果您认为我需要更多属性,我将很高兴知道。我知道有一个简单的方法,但我只是被困住了;)
谢谢你的时间!
让我们看看我们可以定义什么:
Cell[][] maze; // prepopulate with cells in a rectangular fashion.
// Populate adjacent cells with walls.
{
maze = new Cell[m][n];
for (i = 0 .. m) {
for (j = 0 .. n) {
cell = maze[i][j] = new Cell(m, n);
// fix top wall
if (i == 0) { // first row
cell.wall[0] = new Wall();
cell.wall[0].setIsEdge();
} else {
cell.wall[0] = maze[i-1][j].wall[2]; // my up is last row's down
}
// fix bottom wall
cell.wall[2] = new Wall();
if (i == m-1) { // last row
cell.wall[2].setIsEdge();
}
// fix left wall
if (j == 0) { // leftmost column
cell.wall[3] = new Wall();
cell.wall[3].setIsEdge();
} else {
cell.wall[3] = maze[i][j-1].wall[1]; // my left is last col's right
}
// fix right wall
cell.wall[1] = new Wall();
if (j == n-1) { // rightmost column
cell.wall[1].setIsEdge();
}
}
}
}
List walls = new List();
class Cell {
Wall[] walls = new Wall[4]; // 0 is up, 1 is right, 2 is down, 3 is left (count clockwise)
boolean isInMaze = false;
int x;
int y;
Cell(col, row) {
x = col;
y = row;
}
}
class Wall {
boolean isOpen = false; // open walls are passages
boolean isEdge = false; // edges have nothing on the other side.
Cell[] cells = new Cell[2];
}
Cell aCell = maze[randomx][randomy]; // make sure x,y in bounds
initializeCellInMaze(aCell, null);
while (!walls.isEmpty()) {
aWall = walls.get(randomWall); // in range
if (!(aWall.cell[0].isInMaze && aWall.cell[1].isInMaze)) {
// opposite cell NOT in maze
wall.setIsOpen();
Cell otherCell;
if (wall.cell[0].isInMaze) {
otherCell = wall.cell[1];
} else {
otherCell = wall.cell[0];
}
initializeCellInMaze(otherCell, aWall);
}
walls.remove(aWall); // or use index
}
initializeCellInMaze(cell, wallToSkip) {
cell.setIsInMaze();
for (i = 0 .. 3) if (cell.wall[i] != wallToSkip) walls.add(cell.wall[i]);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)