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 网格中的单元的类,而cellsCell对象的 2D 数组。单元格具有布尔变量topbottomleftright来指示单元格在这些边上是否有墙,布尔变量visited来检查我们是否已经遍历它,以及两个整数变量rowcol来指示它在网格中的位置。

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 回答