用Java制作3D迷宫

Question

目标

---

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

算法

---

问题是算法的实际编码:我认为最好的方法是调用一个类MazeBlock,它有六个布尔状态(向上,向下,向左,向右,向内,向外),表示迷宫的方向可以去下一个.使用MazeBlocks 的3D数组,我想填充迷宫,每次迭代填充检查块在左侧,右侧,上方,下方,前方和后方,以查看是否有任何开口到哪一侧附上.

我已经有一个可以制作边缘,将随机开放的槽放在迷宫内部.所有我遇到的麻烦都是实际内部,确保迷宫有一个入口,一个出口和一个解决方案来穿越它(我曾经在弹出书中解决了一个"困难"的3D迷宫,只需要在预定的几步之后方向.

题

---

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

解决方案不得使用外部库.

Answer 1

有许多迷宫生成算法在这里工作得很好,其中大部分是基于在3D网格图中创建某种生成树.

举个例子,让我们假设我们有一个2D网格的单元格(我可以使用ASCII艺术实际渲染!),如下所示:

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

我们可以将其视为一个图形,其中每个单元格是一个顶点,并且单元格之间的每个连接都是边缘.我们的目标是找到一个连接所有节点的树.如果我们这样做,那么所有单元格将彼此可达(因为树已连接),但没有循环(因为树是最小连接的图形).我们可以使用许多不同的树木; 例如,这是一棵树:

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

这是另一个:

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

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

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

希望这可以帮助!