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