三维迷宫算法

Question

是否有算法来生成三维迷宫？基本上与2D迷宫相同，但Z轴深度可以穿越？这个想法仍然是一样的，从开始到结束。回溯仍然可以使用？

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

请参阅here。我的意思是说你也可以进入魔方，而不是迭代它的面部。

Answer 1

几年前，我使用Kruskal的算法here制作了2d迷宫。应该没有理由，这不适用于你描述的3D情况。基本上你会认为一个单元是一个立方体，并且有一个大的阵列（对于每个单元），在+/- x，y和z方向上有6个墙。该算法最初以所有墙壁开始，并随机使墙壁消失，直到连接迷宫中的每个单元格为止。

Answer 2

我有用于在所有东西中生成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当量）的支持。迷宫在每个广场被访问后创建。只有一条道路，蠕虫迷宫。

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

Answer 3

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

---

从最初填满墙单元的3D网格开始。

...

开始在网格的边缘上的试剂，该试剂在X沿直线行进，Y，Z，-X，-Y或-Z方向结算壁她行进。

行动'N'发生每一步的几率很小。

当代理前面的单元格是wall并且前面的单元格为空时，会发生操作'M'。

“N”是的一个随机选择：

1. 去除剂
2. 左转或右转90度
3. 并创建在同一正方形的试剂左转90度，向右或两者（两个代理商）。

'M' 是一个随机选择：

去除剂

除去该代理人的正面壁，然后除去该代理

并无所作为，进行

左转或右转90度。

并在同一方格上创建一个代理，向左，向右或两个方向（两个代理）转过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'动作需要5和6才能让迷宫包含死角。

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