生成迷宫的好算法是什么？

Question

生成迷宫的好算法是什么？

algorithmmaze

80

假设你想在N x M的网格上创建一个简单的迷宫，有一条路径通过，以及很多死路，但同时看起来“对”（即像是由手工制作而成，没有太多小巧的死路等）。是否已知有方法可以实现这个目标？

- Greg

9个回答

49

从 http://www.astrolog.org/labyrnth/algrithm.htm

递归回溯：这与下面描述的递归回溯解决方法有些相关，并需要堆栈大小为迷宫的大小。在雕刻时，尽可能贪婪，并始终在当前单元格旁边有未制作的部分时进行雕刻。每次移动到新单元格时，将前一个单元格推入堆栈。如果当前位置旁边没有未制作的单元格，则弹出堆栈到上一个位置。当您弹出堆栈中的所有内容时，迷宫完成。该算法会产生河流因子尽可能高但死胡同较少且更长的迷宫，通常具有非常长而曲折的解决方案。它运行得相当快，尽管Prim算法稍微快一些。递归回溯不适用于添加墙壁，因为这样做往往会导致解决路径遵循外边缘，其中整个迷宫的内部都通过单个茎连接到边界。

它们仅生成10％的死胡同

这是通过该方法生成的迷宫示例。

- sysrqb

递归回溯法生成了一个漂亮的河流解决方案，正如所指出的那样。也许更有趣的是Eller算法，它具有类似于随机算法的良好属性（可以给出良好的河流解决方案百分比和死胡同百分比），但运行速度更快。 - Greg

这个答案的示例会给出一个错误信息。 - Alex

33

一个相当简单的解决方案是为图的边分配随机权重并运用Kruskal算法来寻找最小生成树。

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

- Savino Sguera

10

这不仅仅是一个有关迷宫生成的精彩讨论，更是一个技术演示的完美典范。 - Wayne Conrad

2

哇，这是我见过的关于迷宫生成的最好的讨论。多么精彩的演示！ - Omicron

2

由于您的回答，我能够使用讨论来编写一个小程序来完成这个任务，而无需参考源代码。那些链接非常优雅地呈现了材料。感谢您如此精彩的回复！ - Coach Roebuck

10

我最喜欢使用Kruskal算法，但在随机选择一条边进行删除时，根据它所连接的边的类型来加权选择。

通过为不同的边类型变化权重，您可以生成带有许多不同特征或“个性”的迷宫。请参见我的示例：

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

- Matt Timmermans

6

奇怪的是，通过略微改变“规范”规则，并从随机配置开始，康威生命游戏似乎能够生成相当不错的迷宫！

（我不记得确切的规则，但这是一种非常简单的修改，倾向于“密集化”单元格的人口...）

- OysterD

不错的解决方案，如果墙只有一个单元格厚度。 - Johan Buret

3

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

以下是Java实现：

这里的Cell表示2D网格中的一个单元格，cells是Cell对象的2D数组。Cell具有布尔变量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;
    }
}

- Sihat Afnan

2

使用随机化的Prim算法是生成迷宫的一种方法。

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

当列表中有墙壁时:

从列表中随机选择一堵墙。如果对面的单元格还没有在迷宫中:

(i) 将墙壁变成通道，并将对面的单元格标记为迷宫的一部分。

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

如果对面的单元格已经在迷宫中，从列表中删除该墙壁。

- user3628041

1

我更喜欢使用递归分割算法的一种版本。详细描述可以在这里找到。 以下是简要概述：
原始递归分割算法的工作方式如下。首先，从一个空白区域开始迷宫的构建。添加一堵直墙将房间分为两部分，并在该墙上随意开一个洞。然后，在每个新房间上递归重复此过程，直到达到所需的通道大小。这很简单且效果不错，但存在明显瓶颈，使得迷宫易于解决。

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

- Joe Schmoe

1

以下是以伪代码形式书写的DFS算法：

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

while VisitedCells < TotalCells 找到所有保持完整的墙壁的CurrentCell邻居
如果找到一个或多个随机选择一个
拆除它与CurrentCell之间的墙壁
将CurrentCell位置推入CellStack
使新单元格成为CurrentCell
将VisitedCells加1 否则从CellStack中弹出最近的单元格条目
将其设置为CurrentCell endIf endWhile

- Muhammad Hashim Shafiq

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- john_science · Accepted Answer

原来有11种经典算法可以生成“完美”的迷宫。如果一个迷宫只有一个解决方案，那么它就是完美的。以下是每个算法的链接，按我偏好的大致顺序排列。

侧向走廊法（可预测的）

二叉树法（有缺陷的）

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