3

我正在尝试实现 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;
}

我的问题是我的迷宫没有完成，并不是所有的单元格都被遍历了。有时只遍历了几个单元格，几乎所有单元格都完成了。我相信我错过了一些无法弄清楚的东西。

请帮忙。

部分穿越的迷宫见下图。

在此处输入图像描述

4

1 回答 1

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

于 2012-07-12T22:06:24.543 回答