在所有的内容之前，我想向读者介绍一下什么是无限伪随机地图，以及实现其的难度。

无限，指的是地图的范围无限，即只要给出所在点的坐标就能生成当地的地图。（其实还是有上限的，主要是因为计算机计算能力及存储能力有极限。依Python而言，这个极限是10的18次方，对于人来说就算一秒钟走1000格，一生也走不完。）

伪随机，指的是固定的世界种子对应固定的地图，种子不变地图不变，种子变地图变，这就是伪随机。

相信大家已经看出生成的难度了，一个区域内的地图由且仅由这个区域的坐标和世界种子决定，不能有任何其他关联的地方。

我们开始研发无限伪随机地图生成的动机是游戏的背景处在一颗星球上面，为了让玩家有足够的代入感这颗星球必须足够大，而无限伪随机地图能生成任意大的地图。

那么我们该如何讲起呢

我决定从泰森多边形开始讲

一、基础

事实上我一开始想到泰森多边形是受三维建模的启发，三维建模用的是多个多边形，但最终却能呈现出平滑的效果。因此在我看到泰森多边形，并想到泰森多边形可以随机化生成的时候，我就开始思考如何用泰森多变形构建平滑的边界。

在此之前我们就已尝试过多种方法试图生成无限伪随机二维地图，具体看https://indienova.com/home/blogread/28728

这些地图生成算法有显而易见的缺点，如群系形状过于相似，边缘过于毛糙等，但只要用了多边形，一切都会迎刃而解。

我们发现，泰森多边形中的控制点的分布相当不均匀，因此我们将地图划分为大小一致的区块（即把地图划分成大小一致的正方形）

在每个区块内随机选取一个点当控制点，这样均匀程度就得到了有效的控制。

那么我们发现将区块分得越小，泰森多边形就越小，边缘也就越平滑。

但是泰森多边形又小又多，很杂乱怎么办呢？

我们先生成一张大的泰森多边形，小的泰森多边形的颜色由其控制点在大的泰森多边形中的颜色决定，相当于是用小的多边形细化大的多边形的边界。

我推荐选取2的n次方来作为区块大小，比如我的地图生成器是以512*512、128*128、32*32、8*8四种大小不同，呈四倍关系的区块来从粗到细，由表及里地生成地图。

不推荐使用更小的群系（2*2），不仅耗时还会使群系的边缘更毛糙。

泰森多边形生成群系的另一个好处就是生成出来的群系大小相对统一，不会有很大的差别（当然刚好两个同色群系连在一起除外）

效果如上。

之后的图片可能会有缺失，因为时间过于久远（指第一个版本在7月初研发），所以图片只能从电脑里的犄角旮旯翻或是去qq群里的聊天记录找。

二、海陆

那么整个世界只有干燥的陆地显然是不行的，我们要加入海洋。（实际上是因为海洋是最容易加的）

【1】泰森多边形海陆

我们以512*512区块为基础来生成两种颜色的生物群系，其中一种作为海洋，另外一种在128*128区块被细化为更丰富的生物群系，此为陆地。

我们采用512区块生成海洋，128区块生成其他生物群系的原因是海洋群系需要远远大于其他的生物群系。

这样生成的海陆是这样的

其中大片蓝色的是海洋，由于是之后的版本，所以稍微多了一点其他的细节。

【2】噪声海陆

噪声是一种图像处理算法，用于生成柔和、连贯、起伏的图像。（英文就是noise，所以译为噪音或噪声皆可）

由于本篇文章不是讲噪声的，所以这部分略过，想要了解的可以看这些：

https://blog.csdn.net/u011600592/article/details/73162610

https://blog.csdn.net/candycat1992/article/details/50346469

CSDN和知乎上都有很多，可以自己去搜。

噪声长这样

注：此为Perlin噪音

噪声分很多种，我们选择了最基本的Value噪声。

Value噪声的原理是将一个方阵的四个顶点赋上随机的值，然后用一个函数去拟合这些值，用函数插值填充中间的值，使得每一个点对于周围的点的变化都是连续的。

我们发现由于噪声连绵起伏的特性，它特别适合用来生成一些纹理，或是用来模拟同样连绵起伏的地形。

这里我们就是用噪声来模拟了地形，我们将一个点上噪声的值看做是这个点的高度，将一个高度作为海平面，将海平面以下的地方全部归类为海洋，这样就生成了噪声海陆。

顺便还能生成沙滩，将海平面高度以上的一部分高度区间划分为沙滩即可。

具体效果：

蓝色的是海，卡其色的是沙滩（挺抽象的）

或者见题图，题图就是一张用噪声海陆生成的4096*4096的地图。

噪声的好处是可以使生物群系变得更大，在用噪声生成生物群系的前提下，我们可以用512区块来生成生物群系。如果用泰森多边形，则必须将512区块用于生成海陆，128区块才能生成生物群系。

坏处是太慢了，生成一张512*512的噪声图居然需要一秒，后面会做具体的复杂度比较与分析。