编程文汇

2D随机地图的生成

#1

1.惯例,先收集文章

这些文章,中文的可以先了解一些基本概念,英文的一般是更完整的算法。

生成成品图:

根据规则生成tilemap:

2.要求

  • 连通性
  • 适中的路面宽度

3.处理过程

最后我选择了 《Procedural Cave Generation tutorial》这篇文章的处理方式,它生成的地图更像rpg的地图。
来看过效果图:
GameLevelGen

处理过程:

  • 定下随机数的种子,在整个生成过程,都使用由这个种子的随机数序列。这样可以保证在使用同一种子时,能够生成相同的图。在客户端和服务器端同步地图的时候,只需要传递这个种子即可,双方可以根据这个种子生成相同的地图,无需传递整个地图的数据。
    • 如果用c++的话 这里不能用std random 库,因为不同编译器的random库实现不同,对于同一个种子,产生的随机数也不同。标准库貌似也不标准了...可以用boost random,这样,就可以在不同平台使用相同的实现,产生相同的随机数。
    • 但是我们还是可以使用std::random_device来产生种子。
    • 根据实际编译测试,gcc std和msvc std,boost产生的随机数序列是一致的:可能它们使用了相同的算法。
  boost::mt19937 rnd;
  boost::random::uniform_real_distribution<ifloat> dist;
  • 生成随机填充0 1的矩阵
  • 根据规则迭代,把地板、墙分别变得更集中。迭代的时候要注意,每次迭代都是依据上次的迭代结果,而不是把当前的迭代结果和上次的混合。所以,要有两个矩阵,上次的,当前的。如果不这样做,收敛的结果很不均匀。不是墙太多 就是地板太多。
  • 连通独立的房间。这是个迭代过程
    • 获取所有独立房间,如果由两个以上的房间。尝试连接最近的房间。
    • 找到距离最近两个房间的最近的点A,B,在两点之间打通用直线通道。
    • 连接方法很简单,循环以AB为顶点的矩阵,查找到线段AB距离小于1的所有点,把这些点置为地板。(距离的计算用矢量的点积、叉积)不算麻烦
    • 重复以上步骤,直至剩下一个房间。
  • 对地图进行修剪
    • 如果一个墙的上下左右4方向,只有一个链接的墙,这个点变成地板。重复扫描五六次。
    • 如果一个孤立的墙,节点小于14,这个墙就不要了,全部置为地板,避免地图变得太零碎。
  • 加宽道路 : 有的道路宽度比较窄,这样在通过时,会有压抑感,需要拓宽它们。
    • 方法很简单,检测每个地板水平、竖直方向的连续地板是否达到一定宽度(我选3),否则,把这个方向上的相邻墙变为地板。
  • 再次修剪。
  • 然后确定怪物分布,这个相对来说比较麻烦,我采用了利用九宫格的方式,切分地图,然后查找里面足够大(3x3)的地面。然后,就根据自己想要分布,去九宫格里 找分布点。
  • 添加边框:现在生成的图,地板会延申到边缘,此时需要在外围增加一定宽度的边框。
  • 完工。

我写了3个版本,每个版本500-800行代码,上面是我最后一个版本的处理过程。如果弄明白了,还是很好写的。这里面的概念我是慢慢明白的,比如连通房间、地图修剪、道路加宽、怪物分布都是我自己慢慢捉摸的。

可能会用到set list map等数据结构,都尽量使用标准库,不要自己写,不然代码就更多了。

0 Likes