java - Prim 生成迷宫的算法 : Getting the neighbour cell

Question

我正在基于 Prim 算法的迷宫生成器程序:

该算法是 Prim 算法的随机版本。

1. Start with a grid full of walls.
2. Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
3. While there are walls in the list:
   1. Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:
      1. Make the wall a passage and mark the cell on the opposite side as part of the maze.
      2. Add the neighboring walls of the cell to the wall list.
   2. If the cell on the opposite side already was in the maze, remove the wall from the list.

(来自 Wikipedia)

我已经理解算法了，我只是停留在这部分:“知道相邻单元格是否构成迷宫的一部分”(这意味着首先获取相邻单元格)由于单元格实际上是树的节点(迷宫，单元格的二维数组)而墙壁是这些节点之间的边缘，我认为有必要用一对点(x，y ).我如何知道两个 Cell 是否由墙连接？(记住每个单元格有 4 面墙)

我考虑过使用 equals() 函数。我只是要求一个伪代码或您最好的解释，这将使事情变得更容易。

我的 Wall 类有三个属性:bool isWall(判断它是墙还是单元格之间的 channel )；诠释 x; int y(标识符)。

如果您认为我需要更多属性，我会很高兴知道。我知道有一个简单的方法，我只是被困住了；)感谢您的宝贵时间!

Answer 1

让我们看看我们可以定义什么:

 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]);
 }