房间和迷宫:一个地牢生成算法

作者:eastecho
2016-01-25
185 353 17

文章来源

微博上的 @大城小胖indienova 个人资料)向我们推荐了这篇文章,在此表示感谢。

本文的作者是:Bob Nystroms,本文的转载和翻译已经获得了他的授权。

原文地址在:Rooms and Mazes: A Procedural Dungeon Generator,有兴趣的同学可以前往阅读原文。阅读原文是一种良好的习惯,一方面回访原作者增加他的访问量,同时也增加他写文章的动力。另一方面,原文下有些讨论的内容会比文章本身还有价值,非常值得常回去看看。

前言

几个月之前,我承诺要针对之前的一篇针对我的 Roguelike 游戏的 blog:回合制的游戏主循环(turn-based game loops)。然后我就投入到我自己发行的新书《游戏编程模式(Game Programming Patterns)》中去,并且把这件事情彻底忘掉了。我把大家扔在一边了~~

好,今天我终于有时间再思考一下我的 Roguelike 了,那么,忘掉游戏主循环,让我们来研究一下 Roguelike 游戏最有趣也是最有挑战的部分:生成地牢!

点击下面的这个小方块看看最后是什么效果。

Sorry, you need canvas support for this demo.

再次点击可以重新开始

看起来很整齐吧?如果你不想深究,那么代码在这里

我关于计算机最早的记忆之一,就是看到我家 Apple IIe 电脑上运行的一个迷宫生成程序。它先将屏幕用绿色的小方块格子填满,然后不断的在墙上挖洞。最后,所有网格上的方块都被连接起来,屏幕上展现出一个完美、完整的迷宫。

我小小的家用电脑能够创造这么神奇的东西--每个方块都可以同其它的连接--尽管看起来很混乱--它向随机的方向雕刻,所以每个迷宫都不一样。这给我十岁的大脑留下了深刻的印象。直到今天也还会有这种感觉。

什么是地牢?

程序生成(Procedural generation)--让程序随机生成取代手工创作--当它工作正常的时候是非常有趣的。由于每一次都不同,你会获得成倍的重玩乐趣。哪怕作为一个开发者,你也无法预计自己能否通过自己用程序写出来的关卡,甚至会出现你意想不到的惊喜。

有时候,使用程序生成会让人觉得简单。手工制作显然需要投入大量的精力和工作。如果你想要一个游戏有 100 的关卡,那么你将不得不制作 100 个关卡。但是如果你使用了一个随机生成关卡的生成器,那么你将会免费得到 100 关,1000 关,或者 1 百万关!

哈,当然没那么简单。设计这样一个程序比你用手工来设计关卡要难得多。你必须要努力动脑,想清楚怎么做,并且想法子将它转换成代码。你其实是要亲自编写一个模拟体系。

它必须要在技术和审美上取得平衡。对我来说,我将注意集中在:

  • 它需要有合理的性能。生成器只需要在进入关卡前运行,所以它不需要非常快。但我们也不希望要让玩家浪费生命中的好几秒等待着生成。

  • 地牢需要被连接起来。就像在我绿色屏幕的 Apple 上的迷宫那样。这意味着在地牢中的任意一点,都有一条道路--哪怕是迂回的--通往另外一点。

    这是非常重要的。如果玩家领取了一个任务,却无法到达那里,会是很残酷的事情。同时,生成玩家到不了的地方也完全是在浪费时间。

  • 还有,地牢的迷宫应该是不完美的。“完美”的迷宫意味着两点之间只有唯一的一条通路。所有的走廊分布得就像一棵树,它有树叉,但是中间没有交集。而“不完美”的迷宫则有着可循环的通路--从 A 到 B 有多个可选通路。

    “不完美”的迷宫是游戏机制的需要,而不是技术上的需求。你可以造一个基于“完美”的迷宫的 Roguelike,而且确实有不少 Roguelike 是按照这个方法来做的,因为它的实现比较简单。

    但是我发现它们玩起来缺少乐趣。当玩家遇到一个死胡同的时候,必须要回溯回到之前的路线去,然后寻找新的可探索的地方。同时,你也无法绕着敌人转圈儿,或者走一条小路绕过敌人--针对这些情况,如果能实现的话其实都不赖。因为从根本上来说:游戏本来就是一个决定和做出不同选择的过程。所以,“完美”的地牢只给玩家一条路径并不太合适。

  • 我需要有开放的房间。我可以创造出没有房间,完全由狭窄的走廊和过道组成的迷宫。但是这样玩家就无法真对敌人做出合理的躲避,也无从采取策略来对付敌人,这会丧失很多游戏乐趣。

    大的、开放的空间可以让玩家有空间释放法术,或者进行大型战斗。同时,房间也可以通过不同的装饰风格来增强游戏场景的表现力。宝箱、陷阱、深渊、藏宝室等等,这些都需要有房间来表现。所以,房间在游戏中起着至关重要的作用。

  • 我也需要走廊。同时,我也不希望这个地牢完全由房间组成。有些游戏会将房间连着房间生成。它玩儿起来并没有什么问题,但是会有一些乏味。我希望玩家在游戏过程中有不同的感受,走廊会让他们感到封闭感,同时,在面对怪兽的时候,将它们引入到狭窄的走廊里面一个一个干掉也是一种策略,游戏体验会更加丰富。

  • 所有这些应该是可调的。很多 Roguelike 会生成大量的难度逐渐提高的多层地牢,但是除此之外就没有其它的了。我的游戏则不是这样。它有多种不同的区域。每一个区域都有自己的风格和感觉。有些可能很小,感觉很局促,其它的则可能很宽敞而又井井有条。

    我采用了多种不同的地牢生成算法来实现它。户外的区域采用完全不同的生成策略(我可能需要针对这个再写一篇教程。瞧~又一个雄心勃勃的承诺!)但是,从头开始编写一个新的地牢生成器会浪费掉大量的时间。所以,理想的做法是将生成器的一些参数设置成可调,这样我就可以通过同一套代码生成不同风格和感觉的地牢。

看得见风景的房间

我几乎一直在开发这个游戏(还使用了四种不同的语言!),而且我也尝试了多种不同的地牢生成器。我主要的灵感来源是 Angband。我研究这款游戏所花的时间要超过我开发自己游戏所用的时间。

Angband 已经非常老了。在那个时代的电脑上,很难实现快速的地牢生成算法,所以它采用的方法非常简单:

  1. 随机生成一批互不覆盖的房间;
  2. 用随机的通道将它们连接起来。

为了确保房间们不覆盖,我们在每次生成一个新房间的时候,如果发现它跟其它房间有重合,那就丢弃掉。不过这样可能会造成无限循环,所以我限制了生成房间的总次数。当房间越来越多的时候,生成失败房间的几率就会越来越高--最后你会发现只能放这么多房间啦--但是通过调整这个总次数还是会让你对房间的密度有所控制,比如:

Sorry, you need canvas support for this demo.

200

一个黑暗扭曲的走廊

我写的大部分地牢生成器都是从这儿开始的。但是最难的地方在于:如何将它们连接起来。这也是我这篇教程的主要目的--一个优雅完美的解决方案。

Angband 的解决方案粗暴但是却令人惊讶的有效。它选择一对儿房间--完全不管它们距离有多远--然后从一个房间开始一条随机的线路连接到另外一个房间(希望能)。它聪明的使用了不少方法来避免过多的交错和叠加,不过也允许这些线路有机会同房间、走道以及死胡同交错。

我花了不少时间试着实现它,但是从未得到理想的结果(应该是我自己的问题)。我生成的走道总是要么太直,要么就是交错得很难看。

然后,几个月前,我偶然在 reddit 的 /r/roguelikedev 上发现了 u/FastAsUcan 的 地牢生成的描述(description of a dungeon generator),以及他基于 Jamis Buck 地牢生成器的:Karcero。如果你之前有做过地牢生成的代码,你知道--或者你应该知道--Buck 是谁。他在随机迷宫生成方面有着大量的文章。

多年以前,我记得他曾经为纸上 D&D 写过的一个真的地牢生成器。跟他之前的大多数迷宫不同,这一个有真正的房间,而且结果看上去很棒。

但是,在那时候,我不知道它是怎么工作的。它是怎样基于迷宫生成了走廊和房间?我把这个疑问放在脑子的某个角落并且很快忘了它。

FastAsUcan 的帖子提供了解答,它大概是这样工作的:

  1. 创建一个完美的迷宫。有很多算法,都相当直接;
  2. 将迷宫简化。找到死胡同并将它们重新用石头填充;
  3. 选择一些剩余死胡同,然后在毗邻的墙上打洞,让它们连接起来。这样迷宫就不完美了。(记住,这是好事情!)
  4. 创建房间,并且寻找合适的放置处。“合适的”意味着不会覆盖迷宫,但是要接近迷宫,这样才好给它加上门并且连接到走廊。

这里最神奇的部分,也是我没想到的部分,就是迷宫的简化。一个正常的迷宫会把所有区域都覆盖,不会给你留下任何可以放置房间的空间。Jamis 和 FastAsUcan 所做的则是:先雕刻出迷宫,然后再将死胡同“反雕刻”回去。

这做起来其实相当容易。死胡同就是三面都是墙的那个。当你找到一个死胡同的时候,你将它重置回石块就可以了。这样做的结果就是:之前跟它相连的那个走廊块儿就变成了死胡同。这样持续做下去,直到再也找不到死胡同,你会发现就有了大量可以放置房间的空间。

当然,如果你从一个完美的迷宫开始这么做,你到最后会将整个迷宫都“简化”掉!完美的迷宫没有循环,只要你持续这么做下去,所有的走廊都会变成死胡同。Jamis 的解决方案是:不去掉所有的死胡同,只去掉一些。它运行一会儿就停下来,就像这样:

Sorry, you need canvas support for this demo.

1000

一旦你这么做了之后,就有机会可以放置房间了。Jamis 采用的方法很有趣,他生成某种尺寸的房间然后试着将它放到迷宫中的每一个位置去,一旦有重合冲突的房间或者走廊,那么这个位置就被丢弃。剩余下来的位置会进行一个“排序”,排序的依据是距离走廊越近的排名越高。最后,根据排序结果选择最好的位置将房间放到那里。然后再在房间边上放上门来连接走廊。

不断的重复这个过程,最后你就得到一个地牢。

房间,然后是迷宫

我立即按照这个方法开始编写代码。结果看上去还不错。但是我发现最后放置房间的步骤显得非常缓慢。对小面积的纸上游戏来说当然效率还不错,但是针对基于计算机的 Roguelike 显然有些吃力。

于是,我做了些思考和修改。在这上面我的贡献其实很小,但我觉得值得将它记下来。(说实话,我觉得看着地牢动态的生成充满乐趣)

Buck 和 Karcero 都是先从迷宫开始,然后添加房间。我的则是反其道而行。首先,它会放置一堆房间。然后遍历整个地牢,当它发现一个完整的开阔空间的时候,从这里开始生成迷宫。

迷宫生成器持续的雕刻路径,并且避免同现有的开放的空间交错。这样你就可以保证迷宫只有一个解法。如果你让它雕刻进已有的走廊,那你就会得到循环。

让你的迷宫填满房间周围奇形怪状的空隙是很方便的。换句话说,迷宫的生成是一个随机的洪水填充(flood fill) 算法。通过在不连接的空间内进行迷宫的填充,我们就会得到一个地牢:充满了互相不连接的房间和走廊。

Sorry, you need canvas support for this demo.

每个颜色代表一个不同的已连接区域

寻找一个连接

现在剩下来的任务就是将所有这些搞成一个连通的地牢。幸运的是,这很容易做到。因为通过前面的房间和迷宫生成工作,我们可以确定:每一个尚未连接的区域跟它的邻居之间只相隔一个图块(Tile)。

我们可以轻易的找到可能的连接点:

  1. 石块;
  2. 毗邻的两个不同颜色的区域。

高亮显示的连接点:

Sorry, you need canvas support for this demo.

我们使用它们来将不同的区域连接起来。通常,我们会将整个地牢看做一个图(Graph),然后每一个图块(Tile)是一个点(Vertex)。但是我们可以将它抽象到更高的层级。现在我们将每个区域看作一个点,而将连接点们当作它们之间的边。如果我们利用所有的连接点,那么这个地牢的连通状态就会变得非常复杂。这并不是我们想要的,所以,我们只需要雕刻那些连接两个区域的连接点一次。换个漂亮而又专业的说法就是:我们在寻找一个 spanning tree(生成树)

这个过程相当直接:

  1. 随机选取一个房间,将它作为主区域。
  2. 随机选取一个主区域边上的连接点并将其打开。在演示中,我们将其变成一个门,但你也可以将其变成一个开放的走廊、上锁的门或者一个魔法衣橱。看你怎么想了,可以充分发挥你的创造力。


    记住,我们并不知道确定的门或者走廊,它们统一表现为“区域”。所以我们有时可能会直接将两个房间连接起来。当然你可以避免发生这种情况,但是相信我,这会使得生成的地牢更有趣。

  3. 连接好的区域现在跟主区域是一个整体了,合并成为新的主区域。在演示中,我用了 flood fill 算法来将新的主区域填充上颜色,因为这看起来比较醒目。在实际应用中,不需要有这个填充的步骤。只需要创建一个简单的数据结构来表示“区域 X 已经被合并了”。
  4. 移除掉无关的连接点。在两个区域合并后,有很大的可能还存在一些两个区域的连接点。因为不再需要通过它们来连接这两个区域了,而且我们需要的是 spanning tree。所以将它们移除掉。
  5. 如果还有剩余的连接点,那么再次进行 #2 步的操作。因为剩余的连接点表明还有至少一个尚未连接的区域。我们需要循环来将它们合并成最后一个完整的主区域。

前面我说过,我们不需要一个完美的地牢,因为那会玩起来很无趣。但是,既然我们创建了一个 spanning tree,我们反而得到了一个完美的地牢。我们只允许使用一个连接点来连接两个区域,于是它变成了一个树,这意味着地牢中的任意两点之间只有一条通路。

修正这个问题也很简单,在 #3 步,当我们准备移除不需要的连接点的时候,我们可以给这些连接点一个很小的几率来变成开放的,就像这样:

if (rng.oneIn(50)) _carve(pos, CELL_DOOR);

这样我们就会偶尔的在两个区域之间多开放一些连接点。这样我们就会得到有循环、不完美但是更加有趣的地牢。而且这也很容易进行调整,如果我们增加开放额外连接点的几率,那么我们就会得到连通状态更加复杂的地牢。

反雕刻

如果我们现在就停下,那么我们会得到一堆包含了迷宫和走廊的地牢,里面有很多死胡同。这看起来很令人抓狂,不过这并不是我们想要的。我们需要简化它。

我们现在已经将所有房间都互相连接起来了,我们可以移除掉迷宫中的那些死胡同。我们这样做的话,只有那些用来连接房间的走廊会被保留。这样,每一段走廊都会引领玩家去到一个有趣的地方,而不是死胡同。

最后我们得到什么

总结一下:

  1. 放置一堆随机的互相不会覆盖的房间;
  2. 把房间之外的空地用迷宫填满;
  3. 将所有相邻的迷宫和房间连接起来,同时也增加少量的连接;
  4. 移除掉所有的死胡同。

我很高兴我们走到这一步。尽管它并不完美。它致力于在房间之间创造讨厌、曲折的走廊。你可以调整自己的地牢算法,但是如果走廊不够曲折它们就会贴着地牢的边缘,看起来很奇怪。

房间和迷宫沿着边界对齐让事情变得简单,填充贴合得也比较完美,但是这样的地牢看起来反而有些人工的痕迹。不过相比我之前的工作它无疑已经有了很大的进步,而且生成的地牢看上去玩起来应该很有趣。

如果你想要自己看看,那么你可以在浏览器中直接玩这个游戏。演示代码在这里,但是相对比较粗糙。我为了演示而将它们制作成动画,这增加了代码的复杂性。所以,这里是我在游戏中使用的干净的版本。

作为走到这里的奖赏,这里有一个非常巨大的地牢。我觉得非常迷人:

Sorry, you need canvas support for this demo.

源文件下载

演示版源代码

前往 github 下载 演示版

干净版源代码

前往 github 下载 干净版


近期点赞的会员

 分享这篇文章

eastecho 

从前的边城浪子,现在的路人乙 

您可能还会对这些文章感兴趣

参与此文章的讨论

  1. indienova 2016-01-25

    随机生成地图的方法真是各有巧妙不同啊。

    不过这个方法比较标准且实用,演示也很充分。

  2. Terean 2016-01-26

    好文章,建议增加收藏功能

  3. Mootii 2016-01-26

    这篇文章真不错,例子丰富,易懂能实现

  4. HuangWei 2016-02-17

    这里也有篇不错的老文章,不同的生成算法,通过分散、Delaunay、最小生成树实现。
    http://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php

  5. magicd 2016-05-05

    按照思路,用js复写了一遍,然后发现各种有问题,只好参看源代码,发现其实有好多细节要注意。。
    举例。。地图高宽必须是奇数,房间宽度必须是奇数,房间的位置也得是技术,主要原因是flood fill通路的时候,如果是偶数,他目前的算法会有错误,会让道路和房间直接连接。。好的学习还是得看源代码。。我偷懒了。

  6. shitake 2016-05-13

    想知道文章里的那些演示是怎么镶到里面的,还有那个到git下载

    • eastecho 2016-05-14

      @shitake:就是嵌入的 js 啊,git 那个链接是我们自己的 HTML 代码

      最近由 eastecho 修改于:2016-05-14 00:25:46
  7. Hysteria 2016-06-02

    这个演示确实惊艳,我都惊呆了,拜服。

  8. 六翼大叔 2017-08-06 新浪微博会员

    别的不说,这演示简直太帅……

  9. MrGao 2017-08-14

    简直不能更棒

  10. 牧马人 2017-08-23 微信会员

    作者名字不是叫Robert Nystrom嘛,前段时间刚买了他的游戏编程模式…… 自己用js实现了个差不多的,感觉有一定局限性(包括上面的哥们提到的要求奇数),不过还是不错的。

  11. foolfoolerfoolest 2018-04-10

    代码写得很漂亮 不愧是写game programming patterns的大神

  12. Pluto 2019-08-10

    受教了,十分感谢

您需要登录或者注册后才能发表评论

登录/注册