Polygonal Map Generation for Games-用于游戏的多边形地图生成法

Polygonal Map Generation for Games

用于游戏的多边形地图生成法

前言

原文地址：

http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation

翻译不当之处请大家不吝指出。

    我想生成有趣的地图，不受实际地图的限制，另外我想尝试一些我之前没有试过的技术。我通常使用一个不同的结构制作瓦片地图。我怎么处理1000个多边形而不是1000000个瓦片？清晰的玩家可分辨的区域对游戏设置是非常有帮助的：城镇的位置，探索区域，领土征服或者攻陷，地标，寻路路径点，困难区域等等。我使用多边形生成地图，然后光栅化瓦片地图，看起来就像这样：

    大多数程序地图生成器，包括一些我以前的项目，使用噪声函数（中点位移法，分形，diamond-square算法， perlin噪声，等等）生成一张高度图。我在这里不这样做。相反，我使用一个图形结构模拟游戏设置中包含的东西（高程，路，河流流量，人物地点，怪物类型）以及用噪声函数模拟各种各样不包含在游戏设置中的东西（海岸线的形状，河流位置，树的位置）。

    有三个主要的功能我想在这个项目中实现：良好的海岸线，山脉以及河流。对于海岸线，我想制作一个海岛被海洋包围，这样我就不用处理人走到地图边缘的问题。对于山脉，我想从简单的东西开始：无论如何山脉都是远离海岸线的，所以你可以一直向上走到达顶峰。对于河流，我从简单的东西开始：从海岸线到山脉画河流，这样你可以沿着河流一直到达海滩。

    首先，试试这个Demo演示！（Flash）往下读，学习它是如何工作的，或者得到源码。这里是流程的概述：

1、从一个制作多边形的图形结构开始

2、标注

3、输出多边形或者可以选择输出瓦片地图

    每个项目都有自己的游戏约束。对于这个项目，游戏约束有一部分取自Realm of the Mad God（狂神国度），一个多人角色扮演游戏，玩家开始独自在沙滩上玩，然后一起在山顶上对抗boss。海拔直接对应于难度，必须单调递增，这在游戏中是一个关键约束。海拔在Minecraft不是相同的约束方式，所以噪声函数适用于他们的游戏。在多人游戏帝国时代中，资源位置受到约束，玩家之间需要平衡；在Minecraft中资源的分布不受限制。当编写自己的地图生成器时，想想哪些地图样貌受限于游戏设计，哪些又是可以随意变化的。这篇文章中的每一个想法可以在你自己的地图生成器项目中单独使用或者一起使用。

多边形

第一步是生成一些多边形。最简单的方法是使用一个六角网格然后扰动它使它看起来有点不规则。这是可行的（这篇文章中的技术同样可行，如果你使用扰动格子的方法），但是我想要比这更不自然的东西，所以我选择生成随机点并且生成维诺多边形，它能用于很多事情，包括地图。在维基中的维诺说明不完整，但是它有一些有用的背景知识。我使用nodename的as3delaunay库，它有一个Fortune算法的实现(Fortune算法，又称Plane sweep平面扫描算法，是一种维诺图的实现算法)。

    这里有一个随机点（红色）和多边形的例子：

    多边形形状和大小有一点不规则。随机数比预想的要更成块状。我想要更接近半随机的“blue noise”，或者准随机的，不是完全随机的点。我通过使用一种变体的Lloydrelaxation算法来近似，这是一个相当简单的调整，使他们更均匀随机地分布位置。Lloydrelaxation替换每个多边形的质心的点。在我的代码中，我仅仅只平均了角（见improveRandomPoints）。这里是运行了两次近似Lloyd relaxation算法的结果：

    比较运行一次和五十次的区别。迭代越多，获得越普通的多边形。运行两次能够给我一个比较好的结果，但是每个游戏有它自己不同的需求。

    多边形的大小可以通过移动多边形的中心点得到改善。同样的方法适用于改善边的长度。移动角顶点用于平均附近的中心点产生更匀称的边长，虽然偶尔会破坏多边形的大小。在代码中，查看improveCorners函数。然而，移动角顶点将会失去维诺多边形的属性。这些属性并不用于这个地图生成器，但是如果你想要在游戏中使用到这些属性，请牢记这一点。你能够得到更好的边长或者你可以保持维诺多边形的属性。

使用维诺多边形增加了一些复杂度所以如果你想要从一些简单的开始，可以尝试正方形或者六边形格子（你可以在这个演示中看到这些）。这篇文章剩余的技术能够在格子上工作。可选地，随机扰乱格子的顶点能够使它看起来更自然。

地图表示

　　我将地图表示为两个相关的图：节点和边。第一个图保存了每个多边形的节点，边在相邻多边形之间。它表示为Delaunay三角网，Delaunay三角网对任何涉及相邻的问题都很有用（例如寻路）。第二个图保存了每个多边形角的节点，边在角顶点之间。它保存了维诺多边形的形状。它对于任何涉及形状的问题都很有帮助（例如渲染边）。

　　这两张图是相关联的。每个Delaunay三角网中的三角形对应于一个维诺图中的多边形角顶点。每个维诺图中的多边形对应一个Delaunay三角网的角顶点。每个Delaunay图的边对应一个维诺图的边。你可以看看下图：

    多边形A和B是彼此相邻的，所以在邻接图（这里的邻接图指Delaunay三角网）中有一个边（红色）位于A和B之间。因为他们是相邻的所以必定有一个多边形的边在他们之间。在维诺形状图中蓝色多边形的边连接了角1和2。每个在邻接图中的边实际上对应了形状图（指维诺图）中的一条边。

    在Delaunay三角网中，三角形A-B-C连接了这三个多边形，并且能被角2所表示。因此，在Delaunay三角网中的角顶点是维诺图中的多边形，反之亦然。这里有个大的例子展示了这种关系，维诺多边形中心用红色表示，角用蓝色表示，并且维诺图的边用白色表示，Delaunay三角网用黑色表示：

    这种对称性意味着我可以同时表示这两种图。有多种方法可以结合两个图的数据。特别是，边可以被共享。在一般的图中每条边指向两个节点。我让边指向四个节点：两个多边形中心点和两个角顶点，而不是在两个图中分别表示两条边。事实证明，这种方法对于连接两个图非常有用。

    通过这种联合表示，现在我可以在我的网格文章中使用“网格各部分之间的关系”作为章节名。他们不是网格所以我不分配网格坐标，但是许多用于网格的算法也可以用在这里，并且用于图的算法也可以用在这里（两个图都可以）。

　　在代码中，graph/directory目录下有三个类：中心点，角顶点以及边：

l  Center.neighbors 是一组相邻多边形

l  Center.borders 是一组边界边

l  Center.corners 是一组多边形角顶点

l  Edge.d0 和 Edge.d1 是连接Delaunay边的多边形

l  Edge.v0 和 Edge.v1 是连接维诺边的角顶点

l  Corner.toucher 是与这个角顶点相关的一组多边形

l  Corner.protrudes 是与这个角顶点相关的一组边

l  Corner.adjacent 是与这个角顶点相连的角顶点

岛屿

    第二步是画海岸线。地图的边界应该是水，但是你可以把其他多边形标记水或者陆地，使用任何你想用的方法。海岸线是所有陆地和水相接的边。

这里有个例子将世界划分为陆地和水：

    在代码中，Map.as 包含了核心地图生成代码。IslandFunction函数返回True，如果一个地方是陆地，False则表示水。有四个陆地相关的函数包含在演示中：

l  Radial 使用正玄波生成一个圆形的陆地

l  Perlin 使用柏林噪声控制形状

l  Square 使用陆地填充整个地图

l  Blob 画出我的blob图标

    你可以使用任何形状，（甚至披萨盒的污点）。在这个项目的未来版本中我希望添加一个绘图工具让你绘制你自己的形状。 

    对多边形中心和角分配水/陆地的代码：

1.基于IslandFunction，通过设置Corner.water将角顶点赋值为水/陆地。

2.如果一部分角顶点设置为水，则通过设置Center.water将多边形赋值为水/陆地。

一个简单的从地图边界开始的种子填充可以确定哪些水域是海洋（与边界相连）和湖泊（被陆地包围）。

    在代码中，种子填充算法在多边形中心上运行，然后我们可以决定角顶点会发生什么事：

1、将所有与穿过水多边形的地图边界相连的多边形设置为Center.ocean。如果Center.water被设置了但是.ocean没有被设置，那么它就是一个湖。

2、如果一个多边形是一个陆地但是它有一个海洋的边，设置为Center.coast。海岸线区域将随后被绘制成沙滩。

3、如果角顶点被海洋多边形所包围就设置成Corner.ocean。

4、如果角顶点与海洋和陆地多边形相接触，就设置成Corner.coast。

5、如果与周围的区域都一致，则重置为Corner.water。

海拔（高程） 

    最现实的方法是先定义高程，然后高程到达海平面的地方定义为海岸线。然而，我开始时带着一个目标，即生成一个好的海岸线，然后从那里反过来工作。我设置高程为到达海岸线的距离。起初我试着设置多边形中心点的高程，但是设置角顶点的高程产生的结果更好。角与角之间的边可以作为山脊和峡谷。计算好角顶点的高程后(Corner.elevation)，多边形的高程(Center.elevation)是所有角顶点高程的平均值。查看函数Map.assignCornerElevation和Map.assignPolygonElevations。

    水多边形不计入距离。这既是因为我希望湖泊是平的而不是倾斜的，也是因为这样易于建立山谷包围着湖泊，它有助于引导河流流向湖泊。

    由于简单定义而产生的一个问题是一些陆地有太多的山而其他的太少。为了解决这个问题，我重新分布了高程以达到期望的分布，低海拔的陆地（海岸线）比高海拔的陆地（山脉）要多。首先，我根据高程来排列角顶点，然后我重置每个海拔的X为期望的累积分布的反数：y(x) = 1-(1-x)^2.在Map.redistributeElevations函数中，y是指在排序表中的位置，x是期望的分布。使用这个二次公式，我可以解出x。这保证了排序使得高程总是从海岸线增加到山上。

    对任意一个位置，走下坡最终将到达海洋。这个图标显示了每个角的最陡峭的下坡方向，存在inCorner.downslope中：

    顺着任意一个下坡方向，我们最终将到达海洋。这对于河流很有帮助，但也可以用于计算流域和其他特性。

    对于高程我有两个目标：

1、生物群落类型：高海拔有雪，岩石，苔原；中等海拔有灌木，沙漠，森林和草地；低海拔有热带雨林，草原和沙滩。

2、河流从高海拔流到海岸。海拔总是随着远离海岸而增加，这意味着没有局部最小值，使得河流的生成复杂化。

    此外，游戏可能定义他们自己的海拔数据的使用。例如，狂神国度使用海拔来分布怪物。

这个高程计算适用于简单的陆地，对狂神国度而言，这是它所需要的。对大陆的生成，你可能想要改变这个步骤，生成一个或多个不一定在中心的山脉，以及孤立的火山。

河流

    河流和湖泊是两种我想要的淡水功能。最现实的方法是根据风、云、湿度、降雨来定义降水量，然后根据哪里下雨来定义河流和湖泊。然而，我开始时带着一个目标，即创建一个好的河流，然后从那里向后开始工作。

    岛的形状决定了哪些区域是水，哪些是陆地。湖泊是水多边形而不是海洋。

    河流使用前面所示的下坡方向。我在山上选择一个随机的角顶点位置，然后顺着Corner.downslope路线流到海洋。河流从角顶点流向角顶点：

    多边形的中心和角顶点我都尝试过，但是发现角顶点的图生成的河流更好看。同时，为了保持湖泊平坦，湖泊附近的海拔往往更低，所以河流很自然的流向湖泊并流出。多条河流可以共享他们路径的较低部分。每次一条河流流过一条边，我让水量增加1并保存在Edge.river中。在渲染的时候，水面宽度是水量的平方根。这个办法很简单而且效果很好。

湿度（降雨量）

    因为我是向后工作的，我不需要从河流获取湿度值。然而，湿度对于定义生物群落很有用（沙漠，沼泽，森林，等等）。因为河流和湖泊应该在高湿度的地区形成，我定义湿度为随着距离淡水越远值就越低。Corner.moisture赋值为a^k，其中a<1（例如0.95），然后k是距离（离淡水的距离）。不幸的是有一些调整参数在Map.assignCornerMoisture中，我调整它们直到地图看起来比较合理：

    考虑到海拔，我重新分配湿度以达到期望的分布。在这个例子中，我想要干燥和潮湿的区域大致相等。所需的累积分布函数是y(x)=x，所以重新分配的代码非常简单。我根据湿度进行排序，然后将每个角的湿度设置为角在排序列表中的位置。参看Map.redistributeMoisture中的代码。

    在这个地图生成器中，湿度仅仅只用于生物群落。但是，游戏可能会发现湿度数据的其他用途。例如，Realm of the Mad God(狂神国度)使用湿度和高程来分配植被和怪物。

生物群落

    同时，高程和湿度提供了不错的种类数量用于定义生物群落类型。我使用高程替代温度。如果这是一个大陆生成器，纬度可能是温度要考虑的一个因素。同时，风，蒸发和雨影（高地背风面降雨极少的干燥区域）对水分运输也影响很大。然而，对这个生成器来说，我让它保持简单。生物群落首先取决于它是水还是陆地：

l  海洋是指任何与地图边界相连接的水多边形

l  湖泊是任何与地图边界不相连的水多边形，或者是冰湖如果湖泊位于高海拔地区（低温），或者是沼泽如果它在低海拔地区。

l  沙滩是任何与海洋相邻的陆地多边形

    对所有的陆地多边形，我从使用维特克图开始，然后使它适应我的需求：

这是结果：

    这些生物群落在地图生成器demo中看起来很不错，但是每个游戏都有它自己的需求。举例来说，Realm of the Mad God（狂神国度）忽略了这些生物群落并使用自己的（基于高程和湿度）。

边的噪声化

    对一些游戏来说，多边形地图就足够了。然而，在其他游戏中我想要隐藏多边形结构。我使用的主要办法是使用一个嘈杂的线来替代多边形边界。如果我想要隐藏它，为什么我要用多边形结构呢？我认为游戏机制和寻路会从底层结构中获得好处

    回想之前有两个图：一个是维诺角顶点（如下图1、2所示）和边（蓝色线条），另一个是多边形中点（A，B）和Delaunay边（红色的线）：

    我想使这两种线都进行噪声处理而不让他们跟其他多边形相交。我也想让它们尽可能的噪声化。我意识到点A、1、B和2形成了一个四边形，我可以限制四边形线段的抖动：

    我进一步将这个四边形分为四个四边形。两个使用红色（Delaunay）的边，另两个使用蓝色（维诺）的边。只要这些线段呆在他们分配的空间中，除了会在中点相遇，他们不会与彼此相交。这样就能约束他们。注意四边形不能是凸的；为了正确分割它，我在维诺边的中点分离它们，而不是维诺和Delaunay边的交点。

    整张地图可以被划分为这些四边形区域，没有剩余空间：

    这就确保了线段的噪声化不再受到其他非必要的限制。（如果这些四边形对游戏机制有帮助，我会非常惊讶。）

    我能使用任何符合这些约束的线段噪声算法。我决定递归地细分这些四边形，然后在小四边形中缝合这些线段以形成一整条边。这个算法的代码在NoisyEdges.as中，位于buildNoisyLineSegments。结果是多边形的边不再笔直：

有三个地方可以调整噪度：

1、当线段小于某个长度时，递归函数结束。我有线段长度为7,4和1的例子（链接见原文）。在地图演示中，对于河流和海岸线我使用线段长度为1，分隔生物群落的线段长度为3，其他地方为10.

2、有个权值参数用于调整红色四边形（Delaunay边）和蓝色四边形（维诺边）之间的空间。我设置NoisyEdges.NOISY_LINE_TRADEOFF为0.5.

3、有个范围随机数NoisyDeges.subdivide。在这个demo中它的值是0.2-0.8，但是它可以是0.0-1.0.此外，随机数不需要一定是线性选择。如果你避免空间约等于0.5你就会得到更多视觉噪声结果。

    边的噪声化对地图样貌产生很大的影响，尤其是河流和海岸线。

更多的噪声

    在游戏艺术中，我通常是个噪声迷，同样我想要对这些地图添加一点噪声。在一个真正的游戏地图中，噪声能表达植被和地形的细小变化。在demo中（mapgen2.as），我用一个随机噪声纹理来填充屏幕。在这个阶段，我也通过混合两个相邻多边形的颜色来平滑边界：

    这里有一个使用16000个多边形，噪声化边，叠加了一个噪声纹理和简单光照的渲染图：

平滑生物群落的过渡

    另外一种在多边形边界上混合生物群落的方法是使用高程和湿度在每个角顶点建立梯度值，然后逐像素地赋值生物群落：

    如果游戏不需要整个多边形都是相同的生物群落，这个方法对制作更多有趣的边界很有帮助。

扭曲生物群落的过渡

    另外一种使地图看起来不那么多边形化的方法是扭曲高程和湿度地图：

1、对每个像素的高程和湿度，添加一个柏林或者随机噪声。

2、对点的附近使用柏林或者随机噪声取样来改变坐标。

    这里有个这样做的例子：

    对高程和湿度添加噪声会使得在过渡边界的附近区域产生“抖动”。使用噪声对附近点进行采样会扭曲边界的形状。

演示

    我写了一个flash演示程序来考察生成的地图：

试试这个演示程序！

http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/demo.html

源代码

    我为AS源码设置了MIT许可证；它可以在github上下载。

https://github.com/amitp/mapgen2

如果你能阅读java或者Javascript，我认为你阅读AS脚本没有困难。我不指望我的代码会立刻对所有人有帮助，但它可能是一个有帮助的起点，如果你想使用这些技术来做自己的游戏地图。

l  Map.as是核心地图生成系统

l  Graph/*.as 是图的表示（多边形，边，角顶点）

l  Mapgen2.as 是演示，包含了渲染和UI界面

l  Roads.as 是一个沿着轮廓线添加道路的模块

l  Lava.as 是一个为高海拔边添加火山裂缝的模块

l  NoisyEdges.as 在demo中用于创建噪声化的边

    这篇文章中的图是由300个多边形创建的，demo默认使用2000个多边形，允许最多使用8000个。一些用于生成图的代码并没有检查过，因为它是快速而肮脏的代码，仅仅知识为了生成这篇文章的图，通常不是有用的。

    如果你发现这些代码和想法对你很有帮助，我会很高兴听到这些。