题

目标

我想提出一个程序产生一个3D迷宫和我有一点麻烦建立算法。为了便于的相互作用，这将是一棱镜的一个入口，一个出口。

算法

问题是实际编码算法：我想更好的路要走，这是使一类称为 MazeBlock, ，其中有六布尔国(上、下，左，右，出的)，这意味着在这个方向的迷宫可以走下一步。用3D列 MazeBlocks我想要填补的迷宫，每次迭代，填补检查街区到左边，右，上，下，在前面的，并且它的后面，看看是否有任何开口的那一侧为其附上。

我已经有一个，将使边缘，将随机打开插槽向内部的迷宫。我所有的麻烦是在实际室内，确保迷宫有一个入口，一个退出，一个解决方案穿越它(I一旦解决了一个"困难"3D迷宫在弹出书的通过只有几步之相反的意向。

的问题

因为我siad，我认为我们的基本思想的算法，但是我不知道如何编码。有人可以拿出一个Java算法为此完成的任务比较快？

该解决方案必须不使用外部图书馆。

有帮助吗？

解决方案

有许多迷宫的代算法，相当不错的工作在这里，其中大多数是基于创建某种 生成树 在线3D电网。

作为一个例子，让我们假设，我们有一个2D网格单元(这其实我可以呈现采用ASCII艺术！) 看起来是这样的：

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

我们可以认为这一图表的每一单元是一个顶点和每个之间的连接细胞是一个边缘。我们的目标是找到一些树，连接所有的节点。如果我们这样做，那么所有的细胞可从另一个(由于一棵树被连接)，但是没有循环(因为一个树是一个最低限度的连图)。有许多不同的树木，我们可以使用；例如，这里的一棵树：

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

这里是另一个：

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

如果你是在寻找某种树连接的迷宫的细胞，一个办法是使用一个 深先搜索 在图表中，随机定购的边缘，需要访问。这一战略是一个众所周知 迷宫代算法 并产生长的、曲折迷宫充满死亡的结束和混乱branchings.

另一种方法通常用于创建的迷宫，是减少它的问题找到一个 最低生成树 曲线图。特别是，假设创建一个图里的每一个细胞是一个节点链接到其每个邻国。随机选择的权重每个人的边缘，然后建造一个最低生成树形图。这棵树已经没有周期，并有一个独特的道路，从每个节点的每一个其他节点，这意味着迷宫有一个独特的解决方案。此外，算法是非常有效-在一个3D立体的尺寸x n n x n,然后你必须O(n3)节点，O(n3)的边缘，并且你可以找到MST在O(n3 lg n)时间的使用 Prim的算法 或 验的算法.这些还产生高质量的迷宫，虽然它们的性质非常不同的迷宫创造了使用随机的深度第一次搜索。

希望这可以帮助!

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top