没有死角的迷宫生成算法？

Question

我正在寻找一种迷宫生成算法,可以生成没有死角但只有开始和结束的迷宫.像这样:

_{图片来自http://www.astrolog.org/labyrnth/maze/unicursl.gif}

我在哪里可以找到或者去构建这样的迷宫生成算法？

Answer 1

听起来你想要一个伪随机空间填充曲线(例如,参见基于上下文的空间填充曲线-EUROGRAPHICS'2000(PDF格式,1.1 MB))

看看空间填充曲线.

我怀疑你可以应用一些随机性来构建其中一个来实现你想要的.

Answer 2

我会从完全黑色(全)方块开始,并尝试挖掘路径.在挖掘过程中,您可以轻松确保没有死角,只需坚持下去.使用回溯,深度优先搜索算法.做一个"随机游走" - 在每个步骤中,随机决定是保持方向还是改变方向.检查死胡同状态 - 如果你遇到困难,你可以说"好吧,我已经完成了,我已经完成了",或者,如果你认为迷宫尚未挖掘,只需回溯.永远记住你以前做过的事情,并随机尝试其他一些动作.可能会使用一些启发式方法来选择某些方向,例如,在躲避墙壁之前始终保留一些自由空间,首先尝试在墙壁周围走动等等 - 这样您就可以找到所需的解决方案,更快地填满所有方块.

Answer 3

我想我已经找到了另一种方法，但是我还没有对其进行广泛的测试。

请参阅https://twitter.com/tdhooper/status/340853820584230915/photo/1

从左到右：

• 生成一个非单行迷宫，如下所述https://en.wikipedia.org/wiki/File:Prim_Maze.svg，我认为这是 Prim 的算法

• 封锁出口

• 画一条访问迷宫中每个点的路径（即尝试解决它）

• 把这条路变成墙