当前位置：文江博客话题详情

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

发布于 2024-07-05 21:47:43 字数 1835 浏览 9 评论 0原文

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

挽清梦 2024-07-12 21:47:43

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

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

它们仅产生 10% 的死胡同

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

回复收藏 0 原文

二智少女 2024-07-12 21:47:43

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

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

回复收藏 0 原文

滥情哥ㄟ 2024-07-12 21:47:43

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

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

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

回复收藏 0 原文

羁客 2024-07-12 21:47:43

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

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

回复收藏 0 原文

如痴如狂 2024-07-12 21:47:43

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

这是一个 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;
    }
}

Recursive Backtracking is the easiest algorithm to implement.

Here's a Java implementation:

Here Cell is a class representing a cell in a 2D grid and cells is a 2D array of Cell objects. Cell has boolean variables top, bottom, left and right to indicate whether a cell has walls on these sides, a boolean variable visited to check whether we have traversed it and two integer variables row and col to indicate its position in the grid.

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;
    }
}

回复收藏 0 原文

殊姿 2024-07-12 21:47:43

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

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

回复收藏 0 原文

听你说爱我 2024-07-12 21:47:43

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

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

从列表中随机选择一堵墙。如果对面的单元格尚未进入迷宫：

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

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

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

回复收藏 0 原文

不喜欢何必死缠烂打 2024-07-12 21:47:43

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

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

当 VisitedCells < 时细胞总数
找到 CurrentCell 的所有邻居且所有墙壁都完好无损
如果找到一个或多个
随机选择一个
推倒它和 CurrentCell 之间的墙
将 CurrentCell 位置推送到 CellStack
使新单元格成为 CurrentCell
将 1 添加到 VisitedCells
别的
从 CellStack 中弹出最新的单元条目
使其成为当前单元格
万一
结束时