迷宫生成Prim算法并非所有单元格都被遍历

Question

我正在尝试实现Prim迷宫生成算法：

• 开始时，建立一个全是墙的网格。
• 选择一个单元格，将其标记为迷宫的一部分。将单元格的墙添加到墙列表中。
• 当列表中有墙时：
  • 从列表中随机选择一面墙。如果另一侧的单元格还没有在迷宫中：
    • 将墙变成通道，并将另一侧的单元格标记为迷宫的一部分。
    • 将相邻单元格的墙添加到墙列表中。
  • 如果另一侧的单元格已经在迷宫中，则从列表中移除该墙。

删除了一些实现细节后，我的实现看起来像这样：

Cell[][] maze 

迷宫是由单元格组成的矩阵。每个单元格都有左、右、上、下四面墙。前沿的墙壁被标记为 boolean frontier，但不是实现的一部分，因为我希望保持迷宫的边框。

public Cell[][] prim(){
    List<Wall> walls = new ArrayList<Wall>();

    //Pick a cell, mark it as part of the maze
    int initialCellI = rnd(sizeX)-1;
    int initialCellJ = rnd(sizeY)-1;
    Cell randomCell = maze[initialCellI][initialCellJ];
    randomCell.setPartOftheMaze(true);

    //Add the walls of the cell to the wall list.
    if ((randomCell.getLeft() != null) && (!randomCell.getLeft().isFrontier()))
        walls.add(randomCell.getLeft());
    if ((randomCell.getRight() != null) && (!randomCell.getRight().isFrontier()))
        walls.add(randomCell.getRight());
    if ((randomCell.getButtom() != null) && (!randomCell.getButtom().isFrontier()))
        walls.add(randomCell.getButtom());
    if ((randomCell.getUp() != null) && (!randomCell.getUp().isFrontier()))
        walls.add(randomCell.getUp());

    //While there are walls in the list:
    while (!walls.isEmpty()){

        //Pick a random wall from the list.
       Wall randomWall = randomElement(walls);
       //pick the cell opposite to this wall. 
       Cell opositeSideCell = getNeightbourCell(randomWall, maze);
       if (opositeSideCell.isPartOftheMaze()){
           //If the cell on the opposite side already was in the maze, remove the wall from the list.
           walls.remove(randomWall);
       }
       else{
          // Make the wall a passage and mark the cell on the opposite side as part of the maze.
           this.removeWall(randomWall, maze);
           opositeSideCell.setPartOftheMaze(true);

            //Add the walls of the cell to the wall list.
            if ((opositeSideCell.getLeft() != null) && (!opositeSideCell.getLeft().isFrontier()))
                walls.add(opositeSideCell.getLeft());
            if ((opositeSideCell.getRight() != null) && (!opositeSideCell.getRight().isFrontier()))
                walls.add(opositeSideCell.getRight());
            if ((opositeSideCell.getButtom() != null) && (!opositeSideCell.getButtom().isFrontier()))
                walls.add(opositeSideCell.getButtom());
            if ((opositeSideCell.getUp() != null) && (!opositeSideCell.getUp().isFrontier()))
                walls.add(opositeSideCell.getUp());   
       }
    }
    return maze;
}

我的问题是我的迷宫没有完成，也没有遍历所有的单元格。有时只遍历了几个单元格，几乎所有的单元格都已经完成了。我相信我缺少了一些东西，但是无法弄清楚缺少什么。

请帮忙看一下下面部分遍历的迷宫图片。

- danny.lesnik

---

让我想起了一个 C++ 项目 :) - Sully

@D3mon-1stVFW 特别是基于 Ajax 的客户端 :) - danny.lesnik

有没有可能isFrontier代码中存在错误，导致迷宫只被部分遍历，因为isFrontier返回True的次数比应该的多？ - Peter de Rivaz

@PeterdeRivaz，我不这么认为，因为isFrontier只是getter，而布尔型frontier的默认值为false。 - danny.lesnik

嗯，在这种情况下，我会非常仔细地检查你的 getLeft、getRight 等实现。由于你的迷宫中没有向上或向左的路径，所以我怀疑这些函数返回了错误的答案，这意味着你的迷宫只能在初始种子点的右侧和下方扩展。也许你可以发布一下代码？ - Peter de Rivaz

Answer 1

好的，我解决了这个问题。 这是一个纯Java问题，与算法无关。我比较了两堵墙。

public class Wall{

    Point p1;
    Point p2;
    }

    public class Point{
    int x;
    int y;
    }

如果我使用p1和p2实现Wall类的equals()和hashCode()，那么在leftCell.rightWall将等于rightCell.leftWall，这就是问题所在。

- danny.lesnik