6

是否有生成 3 维迷宫的算法？本质上与2D迷宫相同，但Z深度轴可以遍历？这个想法仍然是一样的，从头到尾。还可以使用回溯吗？

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

见这里。我的意思是你也可以进入立方体，而不仅仅是迭代它的面。

4

3 回答 3

8

几年前，我在这里使用 Kruskal 算法制作了 2d 迷宫。没有理由这不能与您描述的 3d 案例一起使用。基本上，您会将一个单元格视为一个立方体，并且有一个大型阵列，该阵列（对于每个单元格）在 +/- x、y 和 z 方向上有 6 个墙。该算法最初从所有墙壁开始，然后随机使墙壁消失，直到迷宫中的每个单元都连接起来。

于 2011-12-10T00:35:41.907 回答
0

我有在 RPGLE 中生成 2D 迷宫的代码（我在学习语言时做了一些自我练习）。由于我编写它的方式，一般算法所需的唯一更改是将 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）支持：一个用于占据“广场”的墙壁，另一个用于该广场是否已被访问。迷宫是在每个广场被访问后创建的。保证只有一条路径，蠕虫转向迷宫。

为了使这个三维，使它使用三维数组，并添加必要的维度索引。

于 2011-12-10T00:36:26.223 回答
0

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

从最初充满壁单元的 3D 网格开始。

...

在网格边缘启动一个代理，代理在 X、Y、Z、-X、-Y 或 -Z 方向沿直线行进，并在她行进时清空墙壁。

动作“N”每一步发生的可能性很小。

当代理前面的单元格是墙壁并且前面的单元格是空的时，会发生动作“M”。

'N' 是一个随机选择：

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

'M' 是一个随机选择：

  1. 删除该代理
  2. 拆除该特工前面的墙，然后拆除该特工
  3. 什么都不做，继续
  4. 向左或向右旋转 90 度。
  5. 并在同一个正方形上创建一个代理，向左、向右或两者旋转 90 度（两个代理）。

迷宫与众不同，通过调整“M”的触发器（与有效路口有关）以及调整 1 到 8 出现的机会，它们的特性非常灵活。您可能想要删除一两个动作，或引入您自己的动作，例如做一个小清理或回避一步。

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

float n = 1;

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

return (int)n;

从我的简单描述中将需要一些小的调整，例如动作“M”的触发器将需要检查与它检查的单元格相邻的单元格，这取决于需要什么样的连接点。

迷宫包含循环需要 5 或 6，并且迷宫包含死端需要至少一个替代 5 和 6 的“M”动作。

一些机会/动作和“M”触发器的选择往往会导致迷宫不起作用，例如无法解决或充满空或壁单元，但许多会产生始终如一的好结果。

于 2018-01-19T16:26:01.623 回答