转载说明

本文在思想上是这篇文章¹的转载，且所有代码也均改编自它。

因此笔者放弃任何(可能会有的)权力，一切权力属于Bob Nystroms。

英文原文在此：Rooms and Mazes: A Procedural Dungeon Generator。

本文生成地牢所用的脚本在这里，点击链接下载，里面有附使用说明。还提供了两个在线生成器在文章最后。

在电脑端阅读以取得最好的阅读体验。

前言

没什么前言，我只是觉得生成一个迷宫真是太他妈酷了，想想看一个个房间被放置、走廊和墙壁填满每一寸土地，然后想象你的角色走在其中，得到宝藏。

所以不多废话。这是一个示例，点击它可以再运行一遍²：

地牢和迷宫的区别

不同于迷宫，地牢作为一种不“纯粹”的谜题³，它更多的在于“探索”这一过程而不仅仅是找到出口这么简单⁴。因此地牢比迷宫多了一项元素：房间。你可以在房间里布置一个真正的迷宫或是别的什么其它谜题，也可以什么都不布置，只是单纯的放一个宝箱⁵在那里。

除此之外，地牢通常是有回路的，它不像完美迷宫那样严格要求所有路径可达且没有环路。

另一个不同的点在于：地牢通常不会有死胡同⁶。

地牢的要素

那么，地牢究竟是什么样的？

Bob Nystroms认为：

• 地牢的任意两点之间应该是相互可达的。
• 地牢不应该是完美迷宫。
• 地牢需要有房间和走廊。

除此之外，从技术上来说，一个地牢生成程序应该：

• 对性能和时间的消耗是很小的，至少不应让玩家等很久。
• 具有大量可调参数，以实现个性化布局。

很简单，对不对？尤其是以现在机器的性能⁷⁸，几乎不需要考虑生成所需要的时间，只要大胆发挥自己的创意就好了，让我们开始吧！

随机创建一些房间

第一步是放置房间。为了确保房间不覆盖，我们在每次生成一个新房间的时候，如果发现它跟其它房间有重合，那就丢弃掉。不过这样可能会造成无限循环，所以限制了生成房间的总次数是很有用的一种方法。

这是尝试200次的结果。下面是尝试2000次的结果：

虽然确实比200次尝试所产生的房间要多，但是远远没有我们所预想的那么多，对吧？这是因为随着成功放置的房间越来越多，剩余空间越来越小，满足新房间的概率也就越小。所以越是尝试放置新房间，失败的概率就越大；到最后，由于房间最小是2*2且互不相连邻，已经不可能再放置新房间了。

蔓延走廊

这是最难的一部分，你可能想到了不少其它的方法，不过我仍然建议你来看看这个：

1. 创建一个完美的迷宫；
2. 找到死胡同并将它们重新用石头填充；
3. 选择一些剩余死胡同，然后在毗邻的墙上打洞，让它们连接起来。这样迷宫就不完美了；
4. 在空地上放置房间。

请注意，当我们执行第二步的时候，不需要将所有死胡同都堵起来⁹，而是随机的填充一部分。

不过对于第4步，就像我们上面所说的那样，你可能没办法将房间放在你想要的地方，甚至你可能连一个房间都放不下。所以我们不妨换位思考，先放置房间，再布置迷宫，就像下面这样：

这里需要另外提一嘴它是怎么工作的：

• 首先，遍历地图。
• 由于走廊与走廊之间不能相邻，所以我们可以得出所有的奇数坐标点¹⁰都应该有走廊或房间。
• 如果现在遍历到了一个没有走廊或房间的奇数点，说明这是一块新区域。
• 用DFS在这块区域生成迷宫。
• 生成完毕后，接着遍历。

这样我们就能保证所有区域都会有迷宫到达，即使放置房间使它们之间不再相连。

连接！

我们已经有了房间，也有了走廊，那么只剩下连接它们了。遍历房间和房间、房间和走廊、走廊和走廊，寻找潜在的连接点，同时还要注意两个连接点不能相邻。考虑所有条件后，这些连接点看起来像是这样¹¹：

不要死胡同

死胡同是很讨厌的，除非你放一个巨大的宝箱在它的尽头。

我们遍历每一个走廊，如果一个走廊3面都是墙，那么我们就把它删掉；如果这个死胡同连接着某个房间的门，那就连门也一同删掉。

下面是一个演示。为了凸显效果，我提高了出现死胡同的概率。

成果

这是一个非常大的地牢：

以及你可能想自己试试各种参数，看看下面这两个页面：

最后的最后

文中所有展示都是为了使读者看清而故意放慢的。实际上地牢迷宫的生成过程是这样（点击它）：

这里还有另外一篇文章，它采用”扩散式“的思路来创建迷宫。

简单概括就是：

1. 将整个地图填满土
2. 在地图中间挖一个房间出来
3. 选中某一房间（如果有多个的话）的墙壁
4. 确定要修建某种新元素
5. 查看从选中的墙延伸出去是否有足够的空间承载新的元素
6. 如果有的话继续，不然就返回第 3 步
7. 从选中的墙处增加新的元素
8. 返回第 3 步，直到地牢建设完成

看起来就像这样：

以及其它因为种种原因没能添加到这篇文章里的文章：

• Procedural Dungeon Generation Algorithm – 地牢程序生成算法 | indienova 独立游戏：先生成大量房间，在利用物理系统使房间不重叠。适合大量房间与少量走廊的迷宫，如现代楼房布局。
• 洞窟类地牢生成 | indienova 独立游戏：基于随机生成墙壁+元细胞自动机的方法生成看起来自然的洞穴地图。
• Dead Cells 的随机地图生成 | indienova 独立游戏：文中介绍了Spelunky和死亡细胞的地图生成思路，不涉及具体代码。其中对于死亡细胞生成地图的描述很有意思：房间分为不同的种类，相同种类的房间在结构上也是相似的，且可以控制这类房间出现的地方。这种在布局上随机化但是涉及到具体要素时又遵循预制规则的思路值得借鉴。
• 开发日志：游戏中的地图生成 | indienova 独立游戏：适用于非网格化的开放地图生成，如水陆图与河流分布。
• 基于 Unity 的 Roguelike 随机房间生成的方法 | indienova 独立游戏：仅涉及到生成房间的部分。
• 随机迷宫生成算法整理分析 | indienova 独立游戏：生成完美迷宫的几种算法。

1. 感谢eastecho的翻译与转载。 ↩︎
2. 本文中其它示例也是如此。 ↩︎
3. 对于像我这样的路痴而言，两者区别也并没有那么大（笑）。 ↩︎
4. 实际上，本文所讲述的地牢压根就没有出口这个概念。 ↩︎
5. 或者是宝箱怪……？ ↩︎
6. 不如说，为什么要有？死胡同是很讨厌的，除非你放一个巨大的宝箱在它的尽头。 ↩︎
7. 笔者在写完这篇文章后从手机上查看该网页，发现速度确实比在PC端慢了不少。 ↩︎
8. ……等等，好像是QQ内置浏览器的问题，换个浏览器就流畅很多了。 ↩︎
9. 如果你这么做的话，你最终会把整个迷宫填满！ ↩︎
10. 如（13，13）、（7，5）这种x、y都是奇数的坐标点。 ↩︎
11. 实际上连接点应该填满所有的空隙才对，但是由于代码限制，我在这里只能提前考虑“两个连接点不能相邻”这一条件；而这一条件本该是“选择相邻点”这一步才会考虑的。 ↩︎