多边形游戏地图的生成 #1

Amit 对多边形地图生成也颇有研究，本系列教程是其研究成果的结晶。

这里的 indienova 译文版参考了 ivan 博客的许多内容，他还非常慷慨地分享了自己制作的多边形地图生成器 unity 实现，在此特意表示感谢。

由于原文篇幅较长，分为多篇推出，本教程是该系列中的第一篇。

ivan 的 unity 实现

感谢 ivan 的授权分享，他 fork 了一个 Amit 之前开源的 unity 实现，发现这是个未完工的项目，仅实现了基础的架构。于是计划以其作为基础打造一个更全面的地图生成插件 nmap，免费共享出来。希望最终制作一款可以按照用户需求完全随机生成2D或者3D地图的工具。由于工作繁忙，目前只是在原来的基础上添加了一个 tutorial 场景，并增加了对应文章章节的代码渲染输出，可供大家对照学习这篇文章。

nmap 的 github 地址是：
https://github.com/losetear/nmap

Amit 的教程译文

我想要生成一些不受现实束缚，充满趣味的游戏地图，并且想尝鲜一些于我而言全新的技术。通常，我会制作瓦片地图(tile map)，但会使用截然不同的结构。如果我试着用1000个多边形来替代1百万个瓦片会怎么样呢？独特的、可供玩家识别的区域对游戏机制的设计来说大有裨益：用于城镇位置，任务地点，可征服或定居的领地，地标，寻路坐标，难度标示区域等等。我使用多边形来生成地图，然后将其栅格化成瓦片地图(tile map)，参考下图：

多数程序生成地图，包括我以前的一些项目，都会使用噪声函数(比如 midpoint displacement, fractal, diamond-square, perlin noise 等)来生成一张高度图。这里我并不这样做。相反，我用图结构来为一些在游戏机制的约束下定型的游戏内容(譬如海拔，道路，河流，任务点，怪物类型等)建模，并使用噪声函数将一些不受游戏限制的变量(譬如海岸线形状，河流的位置，树的位置)建模。

我为这个项目定下了三个主要的目标：漂亮的海岸线，山脉与河流。说起海岸线，我想创建的是一个被海洋环绕的岛屿地图，这样，我就无须再处理人物走到地图边缘的情况。至于山峰的部分，我先从一些简单的处理开始着手：不管什么情况，山都是距离海岸线最远的，这样，你永远能够沿着上坡到达顶峰。而河流的部分，同样先从简单的实现开始：河流源于海岸、终于山峰，这样你始终可以循着河流来到海滩。

首先，试试 Demo ！ （Flash 文件）请仔细阅读，了解它是如何工作的，或者获取并查看源代码。下面是其处理方式的概述：

每个游戏项目都受自己的游戏机制约束。就本项目而言，游戏机制约束部分取自《疯神国度》(Realm of the Mad God)，这是一个多人RPG，玩家一开始独自在海滩玩耍，之后汇合其他玩家前往山顶征伐Boss。海拔和难度直接对应，并且必须单调递增，所以，这是游戏设计中的一个关键约束。海拔在《我的世界》(Minecraft)中就并不受这种约束，因此，噪声函数的方法就十分契合。在多人模式的《帝国时代》 (Age of Empires)中，资源的位置受游戏平衡性的制约;而在《我的世界》(Minecraft)中，资源分布也并不受玩法的限制。着手编写自己的地图生成器时，你需要考虑的问题有些随设计而定，有些随地图变化。这篇文章中的每一种想法都可以单独或者一起用于你自己的地图生成器项目中。

多边形

第一步我们先生成一些多边形。最简单的方法是使用六角网格，然后加入一些随机性，使它看起来不那么规则。这种方法没什么问题（如果你使用的是一个随机处理过的网格，也可以配合本文中的技术来使用），但我还想让地图变得更加地不规则，所以我选出了一些随机点，用它们来生成泰森多边形(即所谓 Voronoi 图)，它可以用于呈现包括地图在内的许多事物。泰森多边形的专用百科 VoroWiki 内容虽说还不完善，但也能提供一些有用的背景知识。我这里会使用 nodename 编写的 as3delaunay 库，它实现了扫描线算法(Fortune’s Algorithm)。

下面是使用(红色)随机点生成多边形的一个例子：

这些多边形的形状大小都显得略微不规则。随机数的分布会比人们预想中的更容易“扎堆”。我希望它们的分布更接近半随机的“蓝噪音”，或者准随机化 (quasirandomness)，而非完全随机的点。通过使用劳埃德松弛算法(Lloyd relaxation)的一个变种(这种算法会对使用相当简单的方法调整随机点的位置，使它们分布得更为均匀)，我初步实现了这种效果。劳埃德松弛算法 (Lloyd relaxation)会将每个点的坐标替换成多边形质心。在我的代码中，我只是算出了拐角坐标的平均值（查看 improveRandomPoints ）。下面是运行劳埃德松弛算法(Lloyd relaxation)变种两次后的结果：

对比执行一次算法和执行50次之间的区别。迭代越多，地图就会变得越规整。运行两次足以满足我目前的需求，但游戏不同，具体的需求也会千差万别。

多边形的大小可以通过调整多边形的中心位置来优化。调整边长也能达成同样的目标。通过求出附近中心点的平均值来移动顶角位置，可以让边长更加统一，尽管这样偶尔会破坏多边形的大小。可以参考代码中的 improveCorners 函数。然而，移动顶角位置，会丢失泰森图的属性。我们正在编写的地图生成器实际上不会用到这些属性，但是，请留意这一点，以防你有朝一日会希望将它们用在你设计的游戏之中。优化边长或者保留泰森多边形的距离属性，鱼和熊掌，不可得兼。

使用泰森多边形会让项目复杂许多，因此，如果你想要从较为简单的方法开始入手，可以试试方形网格或者六角网格(在 demo 中你也能看到它们)。这篇文件还会介绍一些其他的网格处理技术。还介绍了供有兴趣的朋友选学的部分内容：如何随机调整网格的顶点，使其看上去更加自然。

地图的表示

我使用了两个相关的拓扑图：分别用节点与边来表示地图。第一张图拥有为每个多边形以及相邻多边形之间的边都会创建节点。它表示为德劳内三角化 (Delaunay Triangulation)方法，可以用于处理任何具有相邻关系的事物(譬如说路径搜寻算法)。第二张图，会为每个顶角与顶角之间的边创建节点。它包含了泰森多边形的形状，可以用于处理任何与形状有关的事物(譬如说边界渲染)。

两图密切相关。每个德劳内三角都对应泰森多边形中的一个顶角，每个泰森多边形都对应德劳内三角的一个顶角，每条德劳内三角的边都对应一条泰森多边形的边。下图中展示了这些对应关系：

多边形 A 与 B 彼此相邻，因此，在图中，它们之间有一条(红)边。由于它们的相邻关系，所以在二者之间也必然存在一条泰森多边形的边。多边形边（蓝）连接了泰森图中的顶角1和顶角2。邻接图中的每条边都对应于形状图的边。

在德劳内三角图中，三角形 A-B-C 连接了三个多边形，并且可以用顶角2来表示。因此，德劳内三角中的顶角也可以用来表示泰森图中的多边形，反之亦然。这里不妨再举一个稍微复杂的例子来演示这种关系，泰森多边形的中心点用红色标识，顶角用蓝色标识，而泰森多边形的边用白色标识，德劳内三角则用黑色标识：

这种双重性意味着我可以同时展示这两种图。有一系列方法可以整合这两种图的数据。具体来说，边的数据就可以共享。一般来说，图中的边都连接着两个节点。与其独立地在两种图中分别呈现两条边，不如让一条边对应四个节点：分别连接两个多边形中心和两个顶角。容易证明这是有效整合两种图数据的方法。

整合这两种表示方法后，我可以将之前在网格系列教程中总结的许多处理网格要素间关系的方法付诸实践。由于它们并非网格，因此网格坐标相关的知识也就派不上用场，但仍然会有很多算法能有用武之地(在上面提到的任意一种拓扑图中)。

在代码中，graph/ 路径下有三个类：Center，Corner 和 Edge：

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

Center.borders 是一组相接的边；

Center.corners 是一组多边形顶角；

Edge.d0 和 Edge.d1 是由德劳内三角的边相连接的多边形；

Edge.v0 和 Edge.v1 是由泰森多边形的边相连接的顶角；

Corner.touches 一组与该顶角相接的多边形；

Corner.protrudes 是一组与该顶角相接的边；

Corner.adjacent 是一组与该顶角相连的顶角；

岛屿

第二步我们来绘制海岸线。地图边缘处必须是水域，至于其他多边形是哪种地形则无关宏旨，随意标记都好。所谓海岸线，是陆地、海洋接壤的边的集合。

下面是将一个将世界分为陆地与水域的例子：

在代码中，Map.as 包含了核心的地图生成代码。如果当前位置为陆地，IslandFunction 函数会返回 True，而 False 则说明当前位置处在水域中。Demo 中包含四种岛屿的形状函数：

Radial 采用正弦波算法生成圆形岛屿；

Perlin 使用培林噪声算法来控制形状；

Square 会将整个地图填充为陆地；

Blob 能够绘制了我的 blob logo；

你可以使用任意形状，(这里甚至有一张匹萨盒地图)。我以后会考虑为本项目开发一款绘制地图形状的工具，这样你就能定制出任意想要的形状。

代码会将陆地/水域的属性同时赋予给多边形的中心点和顶角：

- 通过基于 IslandFunction 的 Corner.water 方法赋予顶角陆地/水域的属性。

- 根据顶角的地形属性，通过 Center.water 方法来赋予多边形陆地/水域属性。

从地图边缘开始，使用简易的洪水填充算法来决定哪些水域是海洋(与地图边界相连)，哪些水域是湖泊(被陆地环绕)：

在代码中，对多边形的中心点使用洪水填充算法，以此决定顶角的属性：

- 将任意连通地图边缘的水域多边形标记为海洋(Center.ocean)。如果中心点已被标记为水域(Center.water)，但又没有被标记为海洋，则说明它是湖泊。

- 如果多边形是与海洋接壤的陆地，则将其设为海岸线(Center.coast)。海岸线多边形会被绘制成海滩。

- 如果顶角四周都是海洋多边形，则顶角属性也被设置为海洋。(Corner.ocean)

- 如果顶角同时与海洋/陆地多边形相接，则顶角属性为海岸线。(Corner.coast)

- 重设顶角的水域属性(Corner.water)，使其保持同周围区域一致。

高度图

通常来说，比较踏实的方案是先定义高度图，再将海岸线所在位置设定成海平面高度。这里我们没有采用这种办法，我们一开始就得到了这种方案想要生成的漂亮海岸线，可以从它来倒推计算高度图。我将海拔高度定义为与海岸线之间的距离。我本来希望用多边形的中心点来计算高度，但后来发现用顶角效果更好。顶角间的边可以视为山脊与峡谷。计算出顶角高度(Corner.elevation)后，求顶角高度平均值就能算出多边形的高度(Center.elevation)。参看函数
Map.assignCornerElevations 和
Map.assignPolygonElevations。

水域多边形无需计算距离。这既因为我期望中的湖面应当是平坦无梯度的，也因为我希望能做出环绕湖水的溪谷，它会将河流汇聚到湖泊之中。

使用这种简单的界定方式也会造成一个问题：有些岛屿会拥有太多山峰，而有的却寥寥无几。为了解决这个问题，我会重新调整高度的分布来达到预期效果，让低海拔的陆地(海岸线附近)更多，高海拔的陆地(山峰)更少。首先，我会按高度对顶角排序，接着，我会按 y(x) = 1 - (1-x)2 的反函数来重设高度 x 的顶角的高度。在函数
Map.redistributeElevations 中，y 表示排序后的列表中的位置，而 x 则是期望的海拔。运用完全平方公式我们可以求出 x，这样就能够保持原有序列，一遍从海岸线到山峰海拔高度单调递增。

对于任何位置，一直下坡都会到达海洋。此图显示了从每一个角落的下坡方向，存储在Corner.downslope ：

无论处在那个位置，沿着山坡往下终究会抵达海洋。下图展示了每个顶角的下坡方向，这些数据存储在 Corner.downslope 中：

从任意位置出发，跟随下坡箭头我们都最终能抵达海洋。计算河流时这些数据就可以派得上用场，此外，它们也可以用于计算分水岭等其他地形特征。

对于海拔，我有两个主要目标：

生物群落类型：高海拔地区会下雪，岩石，苔原;中海拔获得灌木，沙漠，森林，草原，低海拔获得雨林，草原，和海滩。

河流从高处流到海岸。其海拔总是和海岸的距离相反，意味着不会有局部的小且复杂的河流产生。

计算高度图时，我的两大主要目标如下：

- 生物群落类型：高海拔地带白雪皑皑，暴露的岩块上覆盖着荒芜的苔原；中等海拔的地区则会覆盖有灌木丛，沙漠，树林和草地；低海拔地区生有雨林，覆盖着草原和海滩。

- 河流：从高处流向海洋。由于海拔高度总是随着同海岸线的距离增加，这样就不会导致局部地区出现小而复杂的河流。

此外，游戏还能定义自己的高度数据。譬如，《疯神国度》(Realm of the Mad God)利用高度图来分布怪物。