Voronoi 图，舍弃马尔科夫后的第二个选择

    为什么我们要舍弃马尔科夫？基础的存在值得歌颂，但付出的高额代价由谁支付呢？当国王的书记官无力根据仅有的信息去创造完美的地形特征与概率分布时，是时候介入图形学的范畴了。       一旦迈入基于图形学的地图生成，全新的区块范围特征逐渐出现，沃洛诺伊图便浮出水面，表明我们确实应该试试去使用它。事实上，很多地图都在使用各种沃洛诺伊图，游戏制造行业在这一描述上所下的功夫相当充足，大量的游戏（尤其是沙盒）在广泛使用。虽然其并不能像柏林噪声等算法来进行细节上的刻画，但是其在大块特征描述上，特别是描述我们正在解决的生物群落上，有着非常出色的表现。       当我们使用它时，将地图进行网格化，然后按照邻接的规律和地形的分布进行染色，很快就能看到一片模糊的鸟瞰图。近视眼的人摘下眼镜观察更佳。这时，这些分好区域的地形特征就能很好地指导我们具体应该如何去具体生成这些地形。       同时，使用较多并不代表有异常成熟的方法帮助我们来使用这一工具。它仅仅作为数学工具的一种，具体的使用时更容易受到很多细节的影响。在算法上，随机点的生成采用泊松过程来控制多边形边数趋近于6，劳埃德松弛等方法使区块更加均匀平滑。在实践上，小而凸的多变形更加强调块和块之间的衔接，特殊的形状要求如何通过扭曲核心点的位置来产生影响。这些都是和最终的地图成品效果挂钩的选择。       当我们将效果表现出来时，就不得不考虑优化的问题。相信我，过于庞大的数据集不是你想要的。比如我所使用无优化的德劳内三角剖分在将两万个点连成三角形需要花费十分钟的时间，这显然不是我们想要的效果。一个可能的方案是既然我们采用了翻转的算法，我们完全可以将庞大的地图分成较小的大块，各个大块间独立进行生成，然后进行链接。因为一个比较直观的现象允许我们这么做，因为随着远离边，三角形的最小角会急速增大。这需要我们付出一些小的额外开销，但绝对是很值得的。       那么我们应该如何染色呢？事实上这很简单，我们根据事物出现的特征对其进行描述，就能知道如何去染色。其一是我们存在这大范围的描述，比如海陆分布奠定了最基础的一个分块。做好第一步，就可以去标明下一层的描述，某些带有特征的地区就可以以此完成对应的染色。比如某个充斥着神秘色彩的南极，某个开阔的非洲平原，某个庞大的山系，某片深海。赋予其生物群落的特征，然后赋予他们一个喜闻乐见的名字。比如说喜马拉雅，比如科迪勒拉。       这个时候，整个世界得到了一份具体的分割。分析这些分布，因为这些特征仅仅提供了关于地形的特征，我们需要在大致的地形确定后再对其进行其他特征的补充，比如温度等情况。海洋等可能由洋流产生温度交换，使其不那么像我们对维度上一贯水温的认知。陆地往往又会很容易受季风的影响，这也让我们无法在地形生成时就敲定温度等特征。将现象抽象，其描述了存在一些影响是非独立的，甚至是块间强关联的。这代表我们需要一些脱离于地图地形的复杂特征系统，像季风和洋流一样。       当然，我们并不需要将其表现的很完美，因为我们并没有做一个现实世界，我们甚至在一个魔法世界中耕耘。换言之，继续抽象，将影响的模式抽象出来一些简略版本，给予它们一些魔幻的名字，比如什么生命潮汐，亡灵涌动等。当我们在地形上存储的特征经受住这些影响，就可以结束这一层的生成了。       从这一层开始，往下所有的层数和细节都开始具备实际价值。海陆范围太过于庞大和粗糙以致于我们对其的使用往往是多余的，而且其生命周期仅仅存在于生成时，因为新的地形特征暗含了海陆分布，且其是完全和地图网格剖分相互绑定。地图上活动的官员们第一眼看到地图的时候，他们可以清晰地看到这一个地形块是山脉还是平原，这一个地形块属于喜马拉雅还是科迪勒拉，这一个地形块是否在经受着亡灵涌动的影响等。       可能这里省略了一些细节的方法，比如喜马拉雅山脉究竟要穿过哪些地形块，比如季风的影响到底要穿过哪些地形块。我们需要提供一些数学模型来表明这些信息如何被敲定。一些概率手段可以帮助我们决策，而最后的数值指定一个较为贴合预期效果的函数。       而有分割好的地形块并不代表接下来的工作会是很好进行的。事实上，块是凸的，块的边数是趋近于六的，这都决定了我们的地形是很难独立的，甚至是强相关的。而地图是很庞大的，这可能导致一个横跨大陆的山脉可能覆盖了数以千计的地形块，一条显而易见的山脊也可能跨越了几十个地形块。这可能有点不太合理，这有点让地图过于庞大，或许我们应该将规模稍微下降一些。（至少当我们使用分而治之的算法帮助我们减少了不少急速膨胀的信息量处理）       而有了足够的细节信息，我们就可以在地形块上创造新的指导生成信息，这些信息可能是一些包含特征的点线结合，也可能描绘了一小片特征，或者是一份新的三角分割。       比如一个较小型的山脉，通过给出山顶和山脊线和山谷线，就可以很好地提供所需要的信息，而大型一点的山脉，就需要提供一些描述鞍部的形状。而考虑水的情况就需要提供可能的溪流，瀑布还有泉水，显然，这些可以用点和连线就能解决，而一小块湖泊就需要我们提供一个块。       有了足够的指导信息，就可以帮助我们来生成更细节的地形。我们可以选择继续分块，完善地图信息。也可以直接使用这些信息来进行生成，指导信息的完善已经可以帮助我们确定所有的地形信息，比如使用经典的柏林噪声就可以利用这些信息来确定一个实际的块应该被填入空气还是一个方块。       当我们完成针对地形和生物群落的确定，就需要补充实际地形的情况。让沙和泥土落于岩石之上，让不同的石头混杂，让矿脉在地形中生长。一些新的空洞在地形中产生，一些参差不齐的石头开始交错。一些事件的源头开始扩散影响。显而易见地，大量的处理需求来源于地下，不受表层地形影响的地方更需要提供充足的信息。       创建一些穿透地形的地标，这些地标需要提供一个深度信息来标明它的3D位置。但反过来想，我们在最初为表层地形描述的时候也提供了高度信息，这在本质上是有一些相似处的。不同的是在更深层的地方不再是像表面这样如何创建都只有一个面，在深处更有可能形成3D的网格。       出于多方面考虑，3D并不能作为一个很好的选择，可能的情况将通过结合平面地图和竖直地图的方式来制造一个伪3D的情况。最后的时候，我们将得到一沓泰拉瑞亚式的地图，玩家就可以在这些地图间相互穿梭。