3D 迷宫算法

Question

有没有算法可以生成三维迷宫？本质上与二维迷宫相同，但Z深度轴可以遍历。然而，想法仍然相同，即从起点到终点。能否仍然使用回溯算法？

我应该使用哪个算法来生成3D迷宫？

请参见这里。我的意思是你可以进入立方体内部，而不仅仅是遍历其表面。

- jmasterx

---

你需要一个解决迷宫的程序，还是一个生成迷宫的程序？ - Clockwork-Muse

你可以在网格上创建一个二维迷宫，为了使其变成三维，每个网格单元将代替为具有“高度”的盒子。 - danca

我不仅仅想要一个高出的迷宫。 - jmasterx

也许您可以更详细地解释一下您想要创建的迷宫类型？ - danca

对于[二维/三维]迷宫，我建议使用Kruskal算法。DFS太简单了，Prim则有点奇怪。二维演示。 - Mateen Ulhaq

Answer 1

我几年前使用Kruskal算法制作了二维迷宫，可在此处查看具体内容。你描述的三维情况也应该适用这种方法。基本上，你需要将一个单元格视为立方体，并创建一个大数组，每个单元格都有6面墙分别位于+/--x、y和z方向上。该算法初始时所有单元格都被包围，然后随机删除墙壁直到所有单元格相互连接。

- Ben Goodrich

---

+1 对于Kruskal算法。 :) - Mateen Ulhaq

我喜欢这个基本的想法，但也许目标不应该仅仅是让迷宫中的每个单元格都相连，而是除此之外，连接还应该是无环的(在图论术语中称为"树")。这将强制迷宫的解决方案是唯一的。这要求某些内部墙壁的随机选择消失会被拒绝，只要它们会在连接中引入环路。同样地，这些“被拒绝”的选择是不会减少图中连接组件数量的选择。 - hardmath

hardmath; Kruskal's算法会处理这个问题。我没有用过度简化的解释来解释这个问题。基本上，只有当墙连接了两个新区域时，它才会被删除。它通过检查墙两侧的单元格是否属于不同的集合来实现这一点。使用不相交集数据结构可以高效地完成这个操作。维基百科链接对此有更好的解释。 - Ben Goodrich

Answer 2

我一段时间前设计了一个用于正方形网格上的2D迷宫的算法，没有理由这个算法不也适用于立方体网格上的3D迷宫。

---

从一个初始完全由墙细胞填充的3D网格开始。

...

在网格的边缘启动一个代理，代理沿X、Y、Z、-X、-Y或-Z方向直线行驶，并在行驶过程中清除墙壁。

每一步都有一定几率发生“N”操作。

当代理正前方的单元格是墙，而其前面的单元格为空时，“M”操作会发生。

“N”是以下选项的随机选择：

1. 移除该代理
2. 向左或向右旋转90度
3. 并在同一方块上创建一个代理，向左、向右或两者同时旋转90度（两个代理）。

“M”是以下选项的随机选择：

4. 移除该代理
5. 删除该代理正前方的墙，并随后移除该代理
6. 什么也不做，继续进行
7. 向左或向右旋转90度。
8. 并在同一方块上创建一个代理，向左、向右或两者同时旋转90度（两个代理）。

---

迷宫是独特的，通过调整“M”触发器（与有效交叉口有关）和调整1到8出现的机会，其特性非常灵活。您可能想要删除一两个动作，或者引入自己的动作，例如制作一个小空地或向侧面移动一步。

“N”的触发器也可以是另一种随机性，例如下面的示例可用于创建相当分支的迷宫，但仍具有一些长直部分。

float n = 1;

while (random_0_to_1 > 0.15)
{
    n *= 1.2;
}

return (int)n;

---

从我的简单描述中需要进行一些小的调整，例如触发动作'M'的触发器还需要检查相邻的单元格，具体取决于所需的交叉口类型。

迷宫中需要5或6个循环，至少需要一种替代'M'动作来避免死路。

某些机会/动作和'M'触发器的选择可能会导致迷宫无法解决或充满空单元格或墙壁，但许多选择可以产生一致好的结果。

- alan2here

Answer 3

我有生成2D迷宫的代码，使用的是RPGLE语言（这是我在学习该语言时进行的自我练习）。由于我编写的方式，一般算法所需的唯一更改就是将Z维度作为附加维度添加...

整个代码长达20页（尽管包括输入/输出），因此这里只提供一些代码。您应该能够将其翻译成您需要的任何语言：我将其从意大利面条式BASIC代码翻译过来（这里使用了太多的goto，但这是一个有趣的练习）。

//set out maximum maze size
maximumMazeSquareCounter = mazeHorizontalSize * mazeVerticalSize + 1;
// generate a starting horizontal positiongetRandomNumber(seed : randomNumber);
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1;
currentVerticalPosition = 1;
mazeSquareCounter = 1;
// generate the top row of the maze (with entrance)
mazeTopRow = generateEntrance(currentHorizontalPosition);
//write to the printer file
writeMazeDataLine(mazeTopRow);
mazeSquareCounter += 1;
//set the first position in the maze(the entry square
setPathPoint(currentHorizontalPosition : currentVerticalPosition);
//do until we've reached every square in the maze
dou mazeSquareCounter >= maximumMazeSquareCounter;
//get the next available random direction
mazeDirection = getNextRandomDirection(getNextAvailableDirection(currentHorizontalPosition : currentVerticalPosition));
//select what to do by the returned results
select;
//when FALSE is returned - when the maze is trapped
when mazeDirection = FALSE;
//if not at the horizontal end of the maze
if currentHorizontalPosition <> mazeHorizontalSize;
//add one to the position
currentHorizontalPosition += 1;
//else if not at the vertical end of the maze
elseif currentVerticalPosition <> mazeVerticalSize;
//reset the horizontal position
currentHorizontalPosition = 1;
//increment the vertical position
currentVerticalPosition += 1;
//otherwise
else;
//reset both positions
currentHorizontalPosition = 1;
currentVerticalPosition = 1;
endif;
//when 'N' is returned - going up (other directions removed)
when mazeDirection = GOING_NORTH;
//set the point above current as visited
setPathPoint(currentHorizontalPosition : currentVerticalPosition - 1);
//set the wall point to allow passage
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_NORTH);
//change the position variable to reflect change
currentVerticalPosition -= 1;
//increment square counter
mazeSquareCounter += 1;
endsl;
enddo;
//generate a random exit
// get a random number
getRandomNumber(seed : randomNumber);
// set to the horzontal position
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1;
//set the vertical position
currentVerticalPosition = mazeVerticalSize;
//set wall to allow for exit
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_SOUTH);

整个程序的支撑是两个二维数组（RPG等效）：一个用于占据“方块”的墙壁，另一个用于记录该方块是否被访问过。迷宫在每个方块都被访问后创建。保证只有一条路径，蠕虫转弯迷宫。

要使其成为三维的，请使用三维数组，并添加必要的维度索引。

- Clockwork-Muse