迷宫算法：生成最困难的迷宫？

Question

我正在尝试使用递归回溯算法，但它总是生成非常简单的迷宫。请问哪个算法能够生成最难解的迷宫（如果合适，请提供关于编织和偏向方向的信息）？

- John

---

定义“最难的”。 - Oliver Charlesworth

需要人类解决最长时间的问题 :)。 - John

好的，但在你有机会找到算法之前，你需要将其转换为客观指标！ - Oliver Charlesworth

这个问题既宽泛又主观。有各种各样的迷宫类型。最难的迷宫是那些人类无法在一生中独立解决的（例如存在于第四维或更高维度的超级迷宫）。http://www.astrolog.org/labyrnth/algrithm.htm - arkon

Answer 1

量化地定义一座迷宫的“难度”并不容易。所以我会从定性上讲述。

首先，递归回溯法是一种“完美迷宫”算法；它生成只有一个解的迷宫。大多数迷宫生成工作都涉及生成完美迷宫，因此我将限制我的答案在这些范围内。

迷宫算法有许多变种和分支。但实际上，只有12种基本的迷宫算法。我按照我个人（主观和经验）认为最难到最容易的顺序列出了它们：

1. Kruskal's
2. Prim's
3. Recursive Backtracker
4. Aldous-Broder
5. Growing Tree
6. Hunt-and-Kill
7. Wilson's
8. Eller's
9. Cellular Automaton (易)
10. Recursive Division (非常易)
11. Sidewinder (可预测)
12. Binary Tree (有缺陷)

我的清单上前四名的难度差异并不大，很抱歉。可能是你的实现有缺陷。最可能的情况是，你擅长解决迷宫问题。尝试制作更大的迷宫。

- john_science

---

认为完美迷宫更难的假设是错误的。在死路上，你可以返回，如果迷宫中有环路，则相对较少的解决方案会使其更难解决，因为你走圆圈与走入死路不同，前者不那么明显。 - Madmenyo

我其实也在找这个。现在我只是回想起当我开始回溯地图瓦片并稍后切割一些墙壁的时候。它有点管用，但感觉上不是很干净。 - Madmenyo

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - otaku

Aldous-Broder和Wilson算法都能生成均匀生成树，这意味着它们的输出实际上是相同的。 - Daniel M.

@DanielM。这是一个有趣的观点。也许我从未见过我认为产生特别困难/有趣迷宫的威尔逊实现。虽然它们都围绕USTs，但它们是不同的算法，我看到的最终结果似乎有些不同。但我会尝试一下它们，并看看是否我错了。 - john_science

Answer 2

虽然不是直接回答，但这篇关于迷宫生成算法可视化的文章是必看的。

- Ian Mercer

---

为大家总结一下。如果那个链接失效了，你的答案也就无效了。 - arkon

真的吗？你想总结一下可视化吗？你需要每个可视化的文本描述吗？ - Ian Mercer

迷宫深度的高分辨率彩虹可视化非常惊人。 - Nayuki

Answer 3

你可以从这里查看迷宫生成算法：

迷宫分类

- Ahmed Emad

Answer 4

深度优先搜索可以生成非常复杂的迷宫。这里有一个开源的C++实现: https://github.com/corporateshark/random-maze-generator 尝试将 ImageSize 设置为4096，NumCells 设置为2047。结果将会非常困难。

- Sergey K.

Answer 5

洪水填充算法是IEEE推荐的。

有许多版本的此算法。 我在Google上搜寻了洪水填充算法的实现。
但是我没有找到实现。

- user1061392