迷宫生成算法，我可以选择入口和出口点

Question

什么是一个很好的迷宫生成算法，开发人员可以任意选择入口和出口点（当然，它们都应位于边缘）？一段伪代码或任何语言的实现将是最有帮助的。

Answer 1

虽然不完全是算法，但我在这里描述了创建迷宫的一些步骤。这些步骤中的每一步都需要转换为代码，但我认为它们是一个很好的起点。

步骤0：最初，矩阵中的所有正方形都将其边框标记为墙。

稍后，这些墙壁中的一些将被切割，例如创建路径。在下图中，将切割将与路径相交的每个墙;所有未被任何路径切割的墙都将被保留.

第1步：我们从以下方式开始：在入口点和出口点之间创建最简单的路径;该路径将仅由一条水平线和一条垂直线组成。

接下来，因为这条路太简单了，我们试图让它更复杂（更扭曲，有更多转弯）;我们通过逐渐替换现有路径的片段来实现这一点，矩形的三个边（与移除的片段一起，将代表整个矩形）;我们会根据需要多次重复此步骤，只关注路径不会相交。

第2步：现在我们有一条相对复杂的路径连接迷宫中的入口和出口点。然而，矩阵中仍有细胞，四面都有围绕它们的墙壁。我已经找到了一些迷宫的例子，我注意到迷宫中的每个细胞都可以从入口点进入，即使它是死路一条。 （换句话说，迷宫中的所有路径都形成一棵树）。

我们现在需要做的是将迷宫中的所有剩余单元连接到现有路径。作为惯例，我将“主路径”称为我们刚刚从入口到出口点创建的路径;分支出来的所有其他路径将被命名为“辅助路径”。那么我们如何创建次要路径？通过在迷宫的大区域中挑选一个未被主路径遍历的随机点，以及主路径上的另一个随机点。然后以与我们对入口和出口点类似的方式链接这些点：用尽可能最简单的路径链接它们，稍后使这条路径变得更复杂 - 通过用3个段替换一个段来构成矩形的补码。我们不需要多次重复此步骤，因为辅助路径不需要比主路径更复杂。

第3步：现在我们通过将迷宫中的一些随机点与主路径相关联，创建了几个辅助路径。仍然有一些区域无法进入，但它们很小。因此，对于这些单元格，我们可以将它们与直线连接到主路径或辅助路径中的最近点，就是这样。迷宫中的所有方块都可以访问。我们现在需要做的就是移除任何与路径相交的墙壁，并保留所有其他墙壁。

Answer 2

有许多算法用于生成迷宫：我希望您可以通过一些小工作来更改它们以允许指定起点和终点。

我对迷宫的最佳参考是Jamis Buck的Mazes For Programmers。 Jamis blogs about many things software-related，在他的帖子中你可以找到很多迷宫算法。以下是对他博客上的内容的回顾：

• Eller's algorithm 将第一行的单元格初始化为每个单元格存在于它们自己的集合中。 现在，随机连接相邻的单元格，但前提是它们不在同一个集合中。当连接相邻单元时，将两组的单元合并为一组，表示两组中的所有单元现在都已连接（存在连接集中任意两个单元的路径）。 对于每个集合，随机创建向下到下一行的垂直连接。每个剩余的集合必须至少有一个垂直连接。这样连接的下一行中的单元必须共享它们上面的单元集。 通过将任何剩余的单元格放入它们自己的集合中来充实下一行。 重复，直到到达最后一行。 对于最后一行，连接不共享集合的所有相邻单元格，并省略垂直连接，您就完成了！
• Kruskal's algorithm 将图表中的所有边缘扔进一个大麻布袋中。 （或者，你知道，一套或什么的。） 以最轻的重量拉出边缘。如果边连接两个不相交的树，则加入树。否则，扔掉那边。 重复，直到没有剩余边缘。
• Prim's algorithm 从G（图形）中选择一个任意顶点，并将其添加到某些（最初为空）集合V. 从G中选择具有最小权重的边，将V中的顶点与不在V中的另一个顶点连接起来。 将该边添加到最小生成树，并将边的另一个顶点添加到V. 重复步骤2和3，直到V包含G中的每个顶点。
• Recursive Division 从空场开始。 用水平或垂直的墙隔平场。在墙上添加一条通道。 用墙壁两侧的区域重复步骤＃2。 递归地继续，直到迷宫达到所需的分辨率。
• Recursive Backtracking 在该字段中选择一个起点。 在该点随机选择一条墙并雕刻通道到相邻的单元格，但前提是尚未访问相邻的单元格。这成为新的当前单元格。 如果已访问所有相邻单元格，则返回到具有未雕刻墙壁的最后一个单元格并重复。 当进程一直支持到起始点时，算法结束。
• Aldous-Broder algorithm 选择一个顶点。任何顶点。 选择顶点的连接邻居并前往它。如果尚未访问邻居，请将行进边缘添加到生成树。 重复步骤2，直到访问过所有顶点。
• Wilson's algorithm 随机选择任何顶点并将其添加到UST。 选择UST中尚未存在的任何顶点并执行随机游走，直到遇到UST中的顶点。 将随机游走中触及的顶点和边添加到UST。 重复2和3，直到所有顶点都添加到UST。
• Hunt-And-Kill 选择一个起始位置。 进行随机游走，将通道雕刻到未访问的邻居，直到当前单元格没有未访问的邻居。 进入“搜索”模式，您可以在其中扫描网格，查找与访问过的单元格相邻的未访问单元格。如果找到，在两者之间划出一条通道，让以前未经检查过的单元成为新的起始位置。 重复步骤2和3，直到搜索模式扫描整个网格并找不到未访问的单元格。
• The Growing Tree algorithm 设C为单元格列表，最初为空。随机添加一个单元格到C。 从C中选择一个单元格，然后将该通道划分到该单元格的任何未访问的邻居，并将该邻居添加到C中。如果没有未访问的邻居，请从C中删除该单元格。 重复＃2直到C为空。
• Binary Tree algorithm 对于网格中的每个单元格，随机地向北或向西雕刻通道。 对，就是那样。
• Sidewinder algorithm 逐行完成网格，从0,0处的单元格开始。将“运行”设置初始化为空。 将当前单元格添加到“运行”集。 对于当前的单元格，随机决定是否雕刻东方。 如果刻有一个通道，则将新单元格设为当前单元格并重复步骤2-4。 如果没有雕刻通道，请选择运行集中的任何一个单元格并向北刻一条通道。然后清空运行集，将行中的下一个单元格设置为当前单元格，然后重复步骤2-5。 继续，直到处理完所有行。

祝你好运。

Answer 3

对于从任何平面图生成随机迷宫的实现，请查看this web app。对于稍微不同的看法，以及双图的一般描述，我也把a presentation放在一起。

请注意，进入或退出的概念是我根本没有解决的问题。但是，如果定义明确的迷宫，您可以随时将入口和出口点放在任何位置。 （当然，有些可能导致琐碎的遍历作为解决方案。）在任何迷宫中，你应该总是能够在任何两点或“房间”之间旅行。

在给定特定迷宫的情况下找到导致有趣或足够复杂的解决方案的进入和退出点可能只是确保具有足够长度的解决方案的问题。如果您想预先指定一个条目作为任意图形的退出点，那么也可以非常简单地完成。

如果你有一个图表并想要添加一个起点或终点，你需要做的就是在周边添加一个“房间”。这个房间必须可以到达迷宫的其他部分，只能通过拆除它与迷宫的其余部分之间的墙壁才能到达。这个想法如下所示，开始和结束房间为左上角和右下角的三角形：

.

图中的随机迷宫如下：