一种 Roguelike 地牢生成算法

文章作者：Mike Anderson

随机生成的地图是 Roguelike 类游戏最独特的一点，它让游戏变得很有乐趣，因为玩家永远要面对新的挑战。

但是随机地图却不是那么容易生成的。在传统的游戏中，一般你都会有一个地图编辑器，可以自由的创建地图。在任何一款称得上是“Roguelike”的游戏中，开发者都要自己创造一个“虚拟地图编辑器”，这样才能随机创建无限的动态地图，从而让玩家在其中流连忘返。

在这篇文章里，我会将自己在开发一款名为 Tyrant 的 Roguelike 游戏中使用的方法记录下来。我怀疑这可能只能算是一个原型，但是我之前也没有见过什么一本正经讲述生成 Roguelike 地图算法的文章。而且，它工作得还是比较令人满意的，所以，我愿意将它分享给大家。

在写任何代码之前，了解自己的目标总是很重要的，这对编程很有帮助，哪怕你随后会做无数的修改。

一个地牢（Dungeon）应该包含以下要点：

最后一点尤其重要。要知道，你的玩家在契而不舍的努力之后，应该能够顺利通过这一层，不要让他们失望。另外，如果放了某个物品到地图上的某个空间，它应该不会被藏在无法到达的地方。

在我写 Tyrant 的时候，我尝试了很多种不同的算法来生成地图，这里所讲的是我能做到的最好的一个，也是目前游戏中使用的那个。

我的灵感来自于此：“如果我是地下城的一个居民，那么我该怎么去建设我的地牢呢？”

显然，我并不会将我的地下城建造成一个一个看起来不错的小房间，然后在中间用长长的通道连接起来。所以，当我需要为我的小怪物们提供更多空间的时候，我应该是拿起我的斧头，挖一个更大一些的洞。这样当他们有所需要的时候就会增加一些新房间——尽管它们看起来可能杂乱无章。

有些地下城主可能想要用吊桥呀、陷阱呀什么的来守护比较“有趣”的房间，但是这些需求都异曲同工。由一个小的地牢开始，慢慢向四周扩散，直到整个地牢形成。这就是我们的计划。

在这个算法里面，“元素”代表着某种地图元素，比如：大房间、小房间、通道、圆形竞技场、保险柜等等。

第 1、2 步很简单。只要你创建好地图就可以去做到。我发现，写一个 fillRect 指令用来填充一个区域是比较有效的做法。

第 3 步麻烦一些。你不能随意的寻找一个方块区域去添加你的元素，因为规则是要将元素添加到当前的地牢当中。这样会使得连接看起来比较不错，也确保了所有的区域都可以到达。Tyrant 的做法是：在地图上随机选择一个方块，直到找到横向或者纵向毗邻一个干净的方块那个。这样做的好处是：它给了你一个近乎公平的方式去选择某一面墙。

第 4 步不太困难。我自己写了一个随机方法来决定建造哪一种元素。你可以自己定义它们，调整某些元素出现的权重，这会让你的地牢有自己的特点和侧重点。一个规划比较好的地牢会有很多规矩的房间，中间有长而且直的走廊连接。而洞穴则可能有一堆打洞以及曲折的小道等等。

第 5 步更复杂一些，而且也是整个算法的核心。针对每一种元素，你需要知道它会占用的空间大小。然后你要去判断它是否和已经有的元素相交。Tyrant 使用了相对简单的一种方法：它会先得到要创建的元素所占用的空间大小，得到这个空间的数据，然后检查是否这个空间由土填满。

第 6 步决定是否创建这个元素。如果这个待确定的空间包含有除了土之外的内容，那么就回到第 3 步继续。注意，大部分元素在这步都会被打回。不过这不是个问题，因为处理时间可以忽略。Tyrant 尝试着将某个元素加入 300 次左右到地牢中去，一般只有 40 次左右会通过这步。

第 7 步会将新元素添加到地图上去。在这步，你还可以增加一些有趣的元素，比如动物、居民、秘道门和财宝什么的。

第 8 步返回去创建更多的房间。确切的次数跟你地牢的尺寸以及其它参数有关。

第 9 步要看个人喜好了。最简单的方法就是随机的去查找方块，直到找到一个空的位置去放置楼梯。

第 10 步就是随机的创建怪兽。Tyrant 在这一步才加入游戏中大多数的怪兽，由少量的特殊怪兽或者生物会在生成房间的时候添加进去。

就这样啦，这里所说的只是算法的规则，具体还要您自己去实现啦。

好了，在看了半天算法之后，我们来一个例子吧：

Key:

1. 第一个房间

2. 随机选择一面墙

3. 为新的通道元素进行区域搜索（包括两边的空间）

4. 是空的，可以添加元素

5. 选择另外一面墙

6. 扫描寻找新的房间所占用空间：

7. 这个地区也可以，那就添加一个新房间，再往里面扔一个宝箱 C（Chest）：

8. 跟前面做法一样，我们增加一个新的通道元素

9. 这一次，我们试着为第二个房间增加一个通道元素

10. 扫描失败了，已经被占用

11. 比较特别的元素，一个菱形的房间

12. 添加一个隐藏的暗门，以及充满陷阱的通道：

13. 继续……

好了，这就是我的算法，我希望它对你有用，或者从一个有趣的角度去看如何解决一个问题。

Java 代码实现 Java 代码实现 你可以通过 Open Processing 在浏览器里面运行它（需要做一些小修改）。它会创建一个图形化的地牢。

Python Curses 代码实现 Python Curses 代码实现

C++ 代码实现 C++ 代码实现

C# 代码实现 C# 代码实现

原文地址：链接