70

假设你想要一个 N x M 网格上的简单迷宫，有一条路径，有很多死角，但这看起来“正确”（即，就像有人手工制作的那样，没有太多小的死角等等）。有没有已知的方法可以做到这一点？

4

9 回答 9

63

事实证明，有 11 种经典算法可以生成“完美”迷宫。如果迷宫只有一个解决方案，它就是完美的。以下是每种算法的一些链接，按我的偏好粗略排列。

  1. 克鲁斯卡尔的
  2. 普里姆
  3. 递归回溯
  4. 奥尔德斯-布罗德
  5. 生长的树
  6. 猎杀
  7. 威尔逊
  8. 埃勒的
  9. 递归除法 （可预测）
  10. 响尾蛇 （可预测）
  11. 二叉树 （有缺陷）

有关更多信息，请查看GitHub 上的mazelib，这是一个实现所有标准迷宫生成/求解算法的 Python 库。

于 2014-05-15T15:00:07.393 回答
44

来自http://www.astrolog.org/labyrnth/algrithm.htm

递归回溯：这与下面描述的递归回溯求解方法有些相关，并且需要堆叠到迷宫的大小。雕刻时，尽可能贪婪，如果当前单元旁边有一个未制作的部分，请始终雕刻成未制作的部分。每次移动到一个新单元时，将前一个单元推入堆栈。如果当前位置旁边没有未制作的单元格，则将堆栈弹出到上一个位置。当您从堆栈中弹出所有内容时，迷宫就完成了。该算法导致迷宫具有尽可能高的“河流”因子，死角更少但更长，并且通常是一个非常长且曲折的解决方案。它运行得相当快，尽管 Prim 的算法要快一些。递归回溯不能用作墙加法器，

他们只产生 10% 的死胡同

是由该方法生成的迷宫的一个示例。

于 2008-09-01T22:04:39.747 回答
28

一个非常简单的解决方案可能是为图边分配随机权重并应用Kruskal 算法来找到最小生成树。

关于迷宫生成算法的最佳讨论：http ://www.jamisbuck.org/presentations/rubyconf2011/index.html （几天前在 HN 上）。

于 2011-09-30T14:31:57.810 回答
9

我最喜欢的方法是使用 Kruskal 算法，但是当随机选择要删除的边时，根据它所连接的边的类型对选择进行加权。

通过改变不同边缘类型的权重，您可以生成具有许多不同特征或“个性”的迷宫。在此处查看我的示例：

https://mtimmerm.github.io/webStuff/maze.html

于 2017-01-15T00:35:50.500 回答
5

奇怪的是，通过稍微改变“规范”规则并从随机配置开始，康威的生命游戏似乎生成了非常漂亮的迷宫！

（我不记得确切的规则，但这是一个非常简单的修改，倾向于“密集”细胞群......）

于 2008-09-01T22:00:57.620 回答
3

递归回溯是最容易实现的算法。

这是一个Java实现：

这里的Cell是一个表示 2D 网格中的单元的类，而cells是Cell对象的 2D 数组。单元格具有布尔变量top、bottom、left和right来指示单元格在这些边上是否有墙，布尔变量visited来检查我们是否已经遍历它，以及两个整数变量row和col来指示它在网格中的位置。

Cell current = cells[0][0] , next;
    current.visited=true;
    do{
        next = getNeighbour(current);
        if(next!=null){
            removeWall(current , next);
            st.push(current);
            current = next;
            current.visited = true;
        }
        else {
            current = st.pop();
        }
    }
    while (!st.empty());


    private Cell getNeighbour(Cell cell){
    ArrayList<Cell> ara = new ArrayList<>();
    if(cell.col>0 && !cells[cell.col-1][cell.row].visited)
         ara.add(cells[cell.col-1][cell.row]);

    if(cell.row>0 && !cells[cell.col][cell.row-1].visited)
         ara.add(cells[cell.col][cell.row-1]);

    if(cell.col<col-1 && !cells[cell.col+1][cell.row].visited)
         ara.add(cells[cell.col+1][cell.row]);
    if(cell.row<row-1 && !cells[cell.col][cell.row+1].visited)
         ara.add(cells[cell.col][cell.row+1]); 


    if(ara.size()>0){
        return ara.get(new Random().nextInt(ara.size()));
    }else{
        return null;
    }
}
private void removeWall(Cell curr , Cell nxt){
    if((curr.col == nxt.col) && (curr.row == nxt.row+1)){/// top
        curr.top=nxt.botttom=false;
    }
    if(curr.col==nxt.col && curr.row == nxt.row-1){///bottom
        curr.botttom = nxt.top = false;
    }
    if(curr.col==nxt.col-1 && curr.row==nxt.row ){///right
        curr.right = nxt.left = false;
    }
    if(curr.col == nxt.col+1 && curr.row == nxt.row){///left
        curr.left = nxt.right = false;
    }
}
于 2020-05-07T20:08:00.227 回答
2

生成迷宫的方法之一是 Prim 算法的随机版本。

从一个充满墙壁的网格开始。选择一个单元格，将其标记为迷宫的一部分。将单元格的墙壁添加到墙壁列表中。虽然列表中有墙：

从列表中随机选择一面墙。如果对面的牢房还没有进入迷宫：

(i) 使墙壁成为通道，并将对面的牢房标记为迷宫的一部分。

(ii) 将单元格的相邻墙添加到墙列表中。

如果对面的牢房已经在迷宫中，则将墙从列表中删除。

于 2014-06-03T11:45:40.600 回答
1

这是用伪代码编写的 DFS 算法：

创建一个 CellStack (LIFO) 来保存一个单元格位置列表
set TotalCells = 网格中的单元格数量
随机选择一个单元格并将其命名为 CurrentCell
设置 VisitedCells = 1

当 VisitedCells < TotalCells 找到 CurrentCell 的所有邻居，如果找到一个或多个墙，则所有墙都完好无损
，如果找到一个或多个随机选择一个，
则将其之间的墙
推倒 CurrentCell 在 CellStack 上推送 CurrentCell 位置
使新单元 CurrentCell
向 VisitedCells 加 1 否则弹出最近的CellStack 的单元格条目
使其成为 CurrentCell endIf endWhile

于 2015-04-11T04:20:56.083 回答
1

我更喜欢递归除法算法的一个版本。这里有详细描述。

我将简要概述一下：
原始递归除法算法的工作原理如下。首先，从迷宫的空白区域开始。添加一堵直墙将房间一分为二，然后在墙上某处放一个洞。然后，在两个新腔室中的每一个上递归地重复此过程，直到达到所需的通道大小。这很简单并且效果很好，但是有明显的瓶颈使得迷宫很容易解决。

该变体通过绘制随机的“弯曲”墙而不是直墙来解决这个问题，从而使瓶颈不那么明显。

于 2019-10-29T23:29:01.060 回答