5

目标

我正在制作一个生成 3D 迷宫的程序，并且在创建算法方面遇到了一些麻烦。为了便于交互，它将是一个有一个入口和一个出口的矩形棱柱。

算法

问题是算法的实际编码：我认为最好的方法是创建一个名为 的类MazeBlock，它有六个布尔状态（上、下、左、右、进、出），表示迷宫的方向可以下一个。使用MazeBlocks 的 3D 数组，我想填充迷宫，每次填充检查块的左、右、上、下、前面和后面，看看是否有任何开口到附上。

我已经有一个可以制作边缘的工具，将随机开放的插槽放置在迷宫内部。我唯一遇到的问题是实际的内部，确保迷宫有一个入口、一个出口和一个穿越它的解决方案（我曾经在一本弹出书中解决了一个“困难”的 3D 迷宫，只需与预期相反的几步方向。

问题

正如我所说，我认为我对算法有基本的想法，但我不知道如何编码。有人可以为此提出一个相对快速地完成任务的Java算法吗？

该解决方案不得使用外部库。

4

1 回答 1

8

有许多迷宫生成算法在这里运行良好，其中大部分基于在3D 网格图中创建某种生成树。

例如，假设我们有一个 2D 单元格网格（我实际上可以使用 ASCII 艺术进行渲染！），如下所示：

*---*---*---*
|   |   |   |
*---*---*---*
|   |   |   |
*---*---*---*
|   |   |   |
*---*---*---*

我们可以将其视为一个图，其中每个单元格都是一个顶点，单元格之间的每个连接都是一条边。我们的目标是找到一些连接所有节点的树。如果我们这样做，那么所有单元格都可以相互访问（因为树是连接的），但没有循环（因为树是最小连接图）。我们可以使用许多不同的树；例如，这是一棵树：

*---*---*---*
|   |   |   |
*   *   *   *
|   |   |   |
*   *   *   *
|   |   |   |
*   *   *   *

这是另一个：

*   *---*   *
|   |   |   |
*---*   *   *
        |   |
*---*---*---*
    |       |
*---*   *---*

如果您正在寻找某种连接迷宫单元的树，一种选择是在图上使用深度优先搜索，随机排序需要访问的边。这种策略是一种众所周知的迷宫生成算法，会产生长而曲折的迷宫，其中充满了死胡同和令人困惑的分支。

另一种通常用于创建迷宫的方法是将其简化为寻找图的最小生成树的问题。特别是，假设您创建了一个图，其中每个单元格都是一个节点，链接到它的每个邻居。为每条边选择随机权重，然后为图构建最小生成树。这棵树没有循环，从每个节点到另一个节点都有唯一的路径，这意味着迷宫有一个唯一的解决方案。此外，该算法非常有效 - 在大小为 nxnxn 的 3D 立方体中，您有 O(n 3 ) 个节点，O(n 3 ) 个边，您可以使用以下方法在 O(n 3 lg n) 时间内找到 MST Prim 算法或Kruskal 算法. 这些也产生了高质量的迷宫，尽管它们的特性与使用随机深度优先搜索创建的迷宫非常不同。

希望这可以帮助！

于 2011-01-14T00:18:02.347 回答