迷宫生成prim算法并非遍历所有细胞

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

• 从充满墙壁的网格开始。
• 选择一个单元格，将其标记为迷宫的一部分。 将单元格的墙添加到墙列表中。
• 虽然列表中有墙：
  • 从列表中选择一个随机墙。 如果细胞在另一侧
    尚未进入迷宫：
    • 使墙成为通道，并将对面的细胞标记为迷宫的一部分。
    • 将单元格的相邻墙添加到墙列表中。
  • 如果对面的单元格已经在迷宫中，请从列表中移除墙壁。

删除一些实现细节，我的实现如下所示：

Cell[][] maze 

是带有细胞的矩阵。 每个单元格都有左/右/上/按钮墙。 边界墙标记为boolean frontier ，并不是实施的一部分，因为我想保持我的迷宫框架。

 public Cell[][] prim(){ List walls = new ArrayList(); //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; } 

我的问题是我的迷宫没有完成，并没有遍历所有的细胞。 有时只有几个细胞遍历，几乎所有细胞都已完成。 我相信我错过了什么bur无法弄清楚是什么。

请帮忙。

部分遍历的迷宫见下图。

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，这是问题所在。