生成一个没有检查板的迷宫-Eller的方法/对列/行的递归BackTracking

Question

我试图用递归回溯算法/eller的方法创建迷宫，其中包含对列和对线。如果列/行是对的，就有一个问题。例如，如果我有一张4*4的地图：

X***
****
****
***X

左上角是起点，另一个是终点。基本上，我不能像5*5迷宫那样创建一种“棋盘”(或者我想的任何奇数)。

X|X|X
-----
X|X|X
-----
X|X|X

因为它适用于4*4：

X|X|
----
X|X|
----

(知道我必须从左上角到达右下角)。算法是否与此paterne一起存在，还是我必须找到一种方法将这些paterne包含在递归回溯/eller方法中。

此外，路径的宽度可以超过一个单位。

一个12 *4的例子：* = empty cells X = walls

1*XXXX****XX
X****X*X**XX
X*XX***XX***
X*XXXX***XX2

入口是1，出口2

4*4的另一个例子：

1*XX
X**X
***X
XX*2

入口点和出口总是相同的，路径的宽度可以是一个或多个，这并不重要。

谢谢！

Answer 1

如果您的数据结构要求网格单元格用于墙壁，那么确实必须确保网格的宽度和高度是奇怪的。如果有递归过程，则必须确保子网格也具有此属性(奇数行和列)。两个相邻的子网格需要共享一列或一行。因此，请确保正确划分递归过程的网格。

例如，如果您想应用迭代Eller算法生成以下示例：

1*XXXX****XX
X****X*X**XX
X*XX***XX***
X*XXXX***XX2

然后，您需要将每个字符看作一个单元格(也是X单元格)，而不是一个墙。墙壁在细胞之间。因此，您可以在下面的“语法”中描绘上面的网格：

┌───────┬───────────────┬───────────────┬───────┐
│ 1     │ x   x   x   x │               │ x   x │
├───┐   └───────────┐   │   ┌───┐       │       │
│ x │               │ x │   │ x │       │ x   x │
│   │   ┌───────┐   └───┘   │   └───┐   └───────┤
│ x │   │ x   x │           │ x   x │           │
│   │   │       └───────┐   └───────┼───────┐   │
│ x │   │ x   x   x   x │           │ x   x │ 2 │
└───┴───┴───────────────┴───────────┴───────┴───┘

所以在这里，带"x“的区域并不是真正的墙--它们是无法到达的外壳。上述所引用的算法不会发生这种情况，因为这些步骤如下：

添加至少一个垂直连接

...and：

..。最后一排。这一次，我们必须连接所有相邻的(但不相交的)单元。

如果省略了这些要求，就可以创建这样的附件。这个语法中的墙壁(被引用的算法使用)是分隔(行)，它们要么是水平的，要么是垂直的。他们不会在你的符号中把自己翻译成"X“。

Answer 2

我最终决定使用递归回溯算法，因为创建迷宫更加优化，就像C(我用来创建迷宫的语言)一样。使用Eller的方法，我应该创建一个整数数组，然后切换到char数组。

要解决对列/行的问题，下面是技巧。

假设我有一个4*4迷宫(包括墙壁)。因此，在开始时，它将呈现为

XXXX                                                 1XXX
XXXX                                                 XXXX
XXXX -> Let's add the entry point (1) + exit (2) ->  XXXX
XXXX                                                 XXX2

我们目前还没有给墙壁下定义，因为在我们的情况下，墙壁是一个细胞。我们要做的是从一开始每两行设置一次墙。

1|X|
---- --> - and | are walls
X|X|
---2

我们现在可以使用递归回溯算法，但我们将每次前进两个单元而不是一个。然而，由于出口点被认为是一道墙，你永远不会到达出口。只需在算法开始时随机设置一个空单元格，直到出口或左边。

1XXX       1XXX
XXXX       XXXX
XXX*  OR   XXXX  --> * = empty cells (reachable in the maze)
XXX2       XX*2