生成迷宫的算法

Question

我想生成一个看起来像这样的迷宫： 也就是说，它由单向路径组成，然后相互连接。我试图寻找一种算法来生成这样的迷宫，但没有成功。

具体来说，我不想要这样的迷宫： 因为它不只是“沿着一个方向”运行。

此外，如果此迷宫的解决方案需要玩家“回溯”，那将是很好的。也就是说，玩家不只是一直向上移动。

- rlbond

---

你能澄清你想要的迷宫和不想要的迷宫之间的区别吗？除了密度和第一个迷宫有多个解的事实之外，这并不明显。你所说的“单向路径然后连接在一起”的意思是什么？ - Adrian McCarthy

你是指像这样的东西吗？（我创建的已编译(.net)），http://pages.videotron.com/spirch/FredGames/Fred-Games.zip，默认情况下迷宫是混乱的，请查看菜单以更改行为。 - Fredou

@Adrian：上面的迷宫有长水平线和短竖直线。下面的迷宫没有方向偏差。 - rlbond

那么，您可以使用传统的迷宫算法，并倾向于在选择随机方向时优先水平移动吗？ - Adrian McCarthy

第一个迷宫好像丢失了？ - andrew cooke

Answer 1

好玩极了！我呈现出完整的ASCII艺术输出...

█    ██████    █████████████████████    █
█    █                             █    █
█    █                             █    █
█    █    ██████████████████████████    █
█                                       █
█                                       █
██████    ██████    ███████████    ██████
█    █    █              █         █    █
█    █    █              █         █    █
███████████████████████████████    ██████
█                                       █
█                                       █
██████    █████████████████████    ██████
█                             █         █
█                             █         █
██████    ███████████    ███████████    █
█              █                   █    █
█              █                   █    █
█████████████████████    ██████    ██████
█         █              █              █
█         █              █              █
███████████████████████████████    ██████
█                                       █
█                                       █



    private struct Cell
    {
        public bool visited;
        public bool right;
        public bool top;
    }

    static void Main(string[] args)
    {
        Random Rand = new Random();

        int size = 8;

        var maze = new Cell[size,size];

        for (int x = 0; x < size; x++)
            for (int y = 0; y < size; y++)
            {
                maze[x, y] = new Cell() { right = true, top = true, visited = false };
            }

        int count = size * size;

        int positionX = Rand.Next(size);

        // mark space below (outside matrix)

        for (int y = 0; y < size; y++)
        {
            maze[positionX, y].top = false; maze[positionX, y].visited = true;
            count--;

            // move left or right n spaces
            int n = Rand.Next(size);                    // random left or right by an amount n
            int direction = (Rand.Next(2) == 0) ? 1 : -1; 
            while (positionX + direction > 0 && positionX + direction < size -1 && n-- > 0)
            {
                // moving sideways
                if (direction == -1)
                {
                    positionX += direction;
                    maze[positionX, y].right = false;
                    maze[positionX, y].visited = true;
                    count--;
                }
                else
                {
                    maze[positionX, y].right=false;
                    positionX += direction;
                    maze[positionX, y].visited = true;
                    count--;
                }
            }
        }


        // Now pick a random place we have visited and extend into new territory
        while (count > 0)
        {
            int x = Rand.Next(size);
            int y = Rand.Next(size);
            if (!maze[x, y].visited) continue;      // not visited yet

            // We are on a visited node, where can we go from here?

            // Pick a direction to break down a wall - favor left right
            if (Rand.Next(4) > 0)
            {
                if (Rand.Next(2) == 1 && x < size-1 && !maze[x+1,y].visited )
                    { maze[x,y].right = false; maze[x+1,y].visited = true; count--;}
                else if (x > 0 && !maze[x-1,y].visited)
                    {maze[x-1,y].right = false; maze[x-1,y].visited = true; count--;}
            }
            else
            {
                if (Rand.Next(2) == 1 && y < size - 1 && !maze[x, y + 1].visited)
                    { maze[x, y].top = false; maze[x, y+1].visited = true; count--; }
                else if (y > 0 && !maze[x, y-1].visited)
                    { maze[x, y-1].top = false; maze[x,y-1].visited = true; count--; }
            }
        }

        // Dump the maze
        for (int y = 0; y < size; y++)
        {
            Console.Write("█");
            for (int x = 0; x < size; x++)
                Console.Write((maze[x, y].top) ? "█████" : "    █");
            Console.WriteLine();

            for (int repeat = 0; repeat < 2; repeat++)
            {
                Console.Write("█");
                for (int x = 0; x < size; x++)
                {
                    Console.Write(maze[x, y].right ? "    █" : "     ");
                }
                Console.WriteLine();
            }
        }

- Ian Mercer

Answer 2

1. 创建一个从点A到点B的随机路径
2. 随机添加墙壁，直到满意为止，但不能覆盖路径

- Kornel Kisielewicz

---

我认为在添加每堵墙之前，您应该检查一下，以确保它不会封闭迷宫的某些区域。 - Justin Peel

当 (!user.IsSatisfied) 时，添加随机的墙壁。 - Ian Mercer

Answer 3

如果我理解正确的话，您想让您的解决方案永远不会崩溃（当入口在底部，出口在顶部时）。

我认为一个简单的方法是先生成一个简单的水平地图，在每一层中选择一个随机洞口，就像这样：

+--------------- +
+                +
+--- ------------+
+                +
+-------------- -+
+                +
+-------- -------+
+                +
+ ---------------+

现在你已经定义了解决方案路径的位置。现在只需要做一些混淆：随机删除某个水平边缘，然后添加一个垂直边缘，防止其使用，在新孔的上面或下面的行中，随机选择孔和真正解决方案之间的位置。（您需要确保不要删除解决方案路径的两个部分之间的水平边缘。）

我认为这会很有效。虽然它可能不会轻易生成大型（多行）的错误路径。

- Keith Randall

Answer 4

只需使用 A* 搜索算法，确保您始终可以找到通往终点的路径，然后为每一行添加二十个随机放置的墙壁。如果在放置新行后 A* 无法到达终点，则使用回溯算法重新生成一组新的墙壁，直到成功为止。也许不是最高效的方法，但我认为它在大多数情况下都能够工作得相当不错。

- Robert Massaioli

---

有很多更好的迷宫生成算法。 - LarsH

Answer 5

这里还有一个：

1. 在房间的边界上添加墙壁。
2. 在边界和房间中央选择几个随机点。对于每个点：
3. 如果从该点出发，存在尚未建造墙壁的方向，则选择一个随机的空闲方向并“生长”一堵墙。否则将此点从列表中删除。
4. 给它20%的机会发芽，如果是，则将该点添加到列表中。
5. 如果列表中还有更多的点，请选择下一个点并转到＃2。否则进入＃5。
6. 如果还有剩余的空闲点，请将它们全部放入列表中。对于每个空闲点：
7. “建造”一堵墙，使其朝向最近的墙壁，以便它们相遇。

- sbi

Answer 6

使用Eller's algorithm算法，并在水平方向引入偏差。

- BlueRaja - Danny Pflughoeft