35

我正在寻找一种迷宫生成算法，它可以生成没有死角但只有开始和结束的迷宫。像这样：

迷宫

图片来自http://www.astrolog.org/labyrnth/maze/unicursl.gif

我在哪里可以找到或着手构建这样的迷宫生成算法？

4

8 回答 8

17

听起来您想要一个伪随机空间填充曲线（例如，请参阅基于上下文的空间填充曲线 -EUROGRAPHICS '2000（PDF 格式，1.1 MB））

看一下空间填充曲线。

我怀疑你可以对其中一个的构造应用一些随机性来实现你想要的。

于 2011-09-10T07:16:15.617 回答
5

我建议从完全黑色（完整）正方形开始并尝试挖掘路径。在挖掘过程中，您可以轻松确保没有死胡同，继续前进。使用回溯，深度优先搜索算法。做一次“随机行走”——在每一步中，随机决定是保持方向还是改变方向。检查死胡同情况——如果你被卡住了，你可以说“好吧，我已经完成了，我已经到了终点”，或者，如果你认为迷宫还不够挖掘，就原路返回。永远记住你以前做过的事情，然后随机尝试一些其他的动作。可能会使用一些启发式方法来偏爱某些方向，例如，在躲避墙壁之前始终保留一些空闲空间，首先尝试在墙壁周围走动等 - 这样您就可以找到所需的解决方案，从而更快地填满整个广场。

于 2011-09-10T06:45:37.960 回答
4

我想我找到了另一种方法，但是我还没有对它进行广泛的测试。

见https://twitter.com/tdhooper/status/340853820584230915/photo/1

从左到右：

于 2013-06-01T15:35:38.873 回答
2

Ahh - I've found a much easier way of generating a unicursal maze.

Start with a blank grid, and fill it with small 2x2 loops. If the grid is odd-by-even, you'll need to mix in some 2x3 loops, and if it's odd-by-odd, you'll have to leave a single square free - I normally leave a corner unfilled.

Next, arbitrarily join the loops together to form larger loops - so (for example) 2 2x2 loops become a single 4x2 loop. Keep doing this, making sure you don't join a loop back to itself.

Eventually you'll end up with a single loop that uses up all the cells occupied by the original farm of loops. Break this loop at any position, and you've got a unicursal maze, where the start and end locations are next to each other.

You can now move the end points around the grid by forming and breaking small loops - hook the end into another point in the maze, and then break the T-junction on the opposite side to re-form your single piece of string with a new end location.

If you're working on an odd-by-odd maze, use this last technique to worm one of your ends over to the unfilled corner to complete your maze.

于 2012-07-04T21:43:41.903 回答
2

在您给出的示例中，从开始到结束只有一条实际路径。如果这就是你想要的，我想你可以使用随机游走！

这个概念很简单：给定迷宫的外部边界、起点和终点，编写一个函数以从起点生成随机游走，最终在终点结束。条件是我们的“随机步行者”只能从前一个方格向上、向下、向右或向左移动，并且不能进入先前经过的正方形的一个方格内（这会产生墙）。

在我看来，这里有两个算法挑战。首先是确定我们是否在先前遍历的正方形的一个正方形内（碰撞）。也许我们可以维护一个遍历的方块（它们的坐标）和迷宫边界的列表，并为每个新方块评估与列表中每个方块的距离。不过，这听起来不是很有效。

另一个挑战实际上是通过我们的随机游走到达终点。如果与之前经过的方块的碰撞不是问题，我们最终肯定会到达终点，但是有了它们，我们就有了一个问题，就是我们可以将自己与终点隔离开来。避免这种情况的方法是检查并避免循环进入。如果我们避免进入由遍历路径和/或迷宫边界形成的循环，那么我们将保持一条可能的路径到终点。至于实际确定我们是否处于循环中……嗯，这有点难。

如果您已经有迷宫求解算法，则可以在可能发生碰撞时运行它，以查看是否存在从当前方块到端点的路径。当你运行它时，让它认为所有以前穿过的正方形都是墙，以及它们的边界。

于 2011-09-10T07:00:23.793 回答
2

我还没想好，只是一个想法：

  • 不要专注于道路，而要专注于墙壁
  • 从黑色的外方块开始
  • 在与现有墙块相邻的任意位置逐步添加墙块，保持从头到尾仍然存在路径的条件
  • 当没有路径单元有两个以上的路径邻居时，你就完成了

新墙的“任意”选择过程可以开始尝试“生长”垂直于外墙的直线部分，然后在某个阶段尽可能切换到填充。

如果卡住，它可能需要回溯的能力。

可能效率不是很高。

于 2011-09-10T06:29:41.287 回答
1

当“行走”时，将每一步所做的更改保留在堆栈中，这样你就可以向前看 x 步，然后在每个阶段，这样你就不能再采取进一步的步骤（走进角落或像步行一样的螺旋）弹出堆栈直到你有一条可行的步行路径，然后继续从那里步行直到堆栈为空（即你将堆栈一直弹出，因为在前面的每一步都没有可行的邻居）。然后将转换应用于迷宫数据结构。

于 2012-06-27T11:46:01.853 回答
1

我现在正在研究这个......从一个边缘开始，我随机穿过一个方形阵列，当我通过它们时用路径长度标记单元格。

当你被卡住时（你会卡住的），创建一个 T 形路口，形成一个与你相邻的最近路径的循环（但见下文）。然后我沿着现有路径返回到 T 形路口的另一侧，并在那里打破循环。然后，这个悬垂的尾巴形成了你随机游走的新“头”（记住从路径源重新计算你的路径长度），你可以继续。

实验表明，通过这样做，它不会（或还没有 - 见下文）进入创建新尾巴的循环，只要你的新“尾巴”被困住，你就不会只是无脑地重新形成如果它是最新的，则与您刚刚断开的单元格的链接 - 在这种情况下选择第二个最近的。

终止的情况是当您“卡”在边缘元素上，并且您已经填充了数组（您的路径长度与数组的区域相同） - 您完成了。你的起点通向你的终点。

这似乎有两个可能的低效率和潜在的打嗝（我现在正在使用算法） - 有时你会走到一个角落，继续的唯一方法是用一个重新形成循环链接你刚刚坏了。然后该序列回溯到您之前所做的所有循环，直到您最初卡住的点。如果这不能去其他任何地方（它是另一个角落），那么你只会在两者之间反弹。有一些方法可以解决这个问题，但这意味着保留某种循环单元列表，只有在你真正铺设一些新路径时才清除它。

另一个是它似乎很容易留下一个未填充的奇数方块，特别是当您的数组是奇数时。我还没有完全调查为什么会出现这种情况，而正是在这种情况发生时，之前的角落问题似乎特别普遍。工作继续……

于 2012-07-02T23:15:30.180 回答