关于Voronoi图

正如最近博客中所写，我在《 Dragons Abound》游戏中努力获得正确的海岸线细节。 在实施隔离岛期间，我感到失望。 为了创建最窄的岛，我将它们的位置宽了-在下图中，每个位置都是一个Delaunay三角形：


这是非常不愉快的-既因为岛很破损，又因为零件太大。 似乎随着Delaunay三角形数量的大幅增加（即，尺寸的大幅减少），这个问题将得到解决-但是我需要的三角形密度导致浏览器崩溃。

我通过从位置的内部表示中分离出土地的轮廓解决了这个问题。 这使我可以绘制任何大小或形状的岛，而无需考虑基础位置网格如何：


这样问题就解决了！ 这使我能够绘制障碍岛，并且由于不再需要海岸线遵循基本网格，因此如有必要，可以按常规方式创建更详细的海岸线，然后添加细节。

但是...我们如何向海岸线添加细节？ 这并不像您想的那么容易。 由于我想创建分形海岸线，因此我考虑使用分形为海岸线添加细节 ：


对设置进行了试验，我能够为海岸线添加许多细节和有趣的东西。 但是，系统无法创建类似于此类地图的内容：


Perlin的噪声可以使用足够详细的基础网格创建这种地形，但是可以在不以期望的分辨率将高程高度存储在基础网格中的情况下完成此操作吗（毕竟，我知道这会破坏我的代码）？ 直到我弄清楚该怎么做。 海岸线本质上是一条穿过Perlin噪声函数为零的所有点的路径。 尽管我们可以直接从Perlin噪声函数中了解特定位置（X，Y）上的值，但是我们无法找到（说）“该函数值为零的所有位置”。 也就是说，很难看到没有基本网格的情况下如何绘制高度轮廓。

更糟糕的是，我问阿米特该怎么做，他也不知道答案。 我不能说这是一回事，但是即使是这样一个聪明的人也不能给出答案时，我开始认为这是无法做到的。 真伤心 我可以给海岸线提供所需的任何形状，但是如果没有非常详细的基本网格，就无法获得所需的形状。

那么如何在不破坏代码的情况下获得高分辨率网格呢？

我想到的一种解决方案让我想起了Azgaar在他的卡片生成器中所做的事情-可变大小的Voronoi单元。 主要思想是增加沿海岸线的基础网格的密度（并减小其尺寸），并在海洋和其他不需要细节的区域中保持较低的密度。 使用此选项，我将仅在需要细节的区域中具有许多网格单元。 这种变化在Dragons Abound中将很难实现，但是我想考虑一下。 另一方面，Azgaar本身对此方法并不满意 ，因此也需要考虑这一点。

同时，我想调查处理大量三角形时浏览器崩溃的原因。 Chrome中的开发人员工具为我提供了详细的性能信息。 我绝不是使用这些工具的专家，但是许多功能很简单，任何人都可以理解。 如果您想找出程序中使用的内存总量，则“内存”选项卡包含有关当前已用容量的信息：


在这种情况下，我打开了Azgaar网页，它只占用了20 MB的内存。 您可以使用此工具找出Dragons Abound占用的内存量，并确定选项卡何时崩溃。

控制Dragons Abound中基础网格的分辨率的基本参数巧妙地命名为“ npts”（点数）。 对于地图的每个单位区域（我通常用作示例的区域地图的面积为1单位），“ 龙腾腾”会创建给定数量的基础网格位置。 我通常对npt使用16K（16384），这意味着每个网格位置在标准缩放比例下对应于屏幕的大约70平方像素。


当然，实际使用的内存量取决于存储卡，但是对于上面显示的具有16K点的存储卡，您大约需要92 MB：


这比我预期的要少，老实说，这是一个相当适中的数字。

如果将基本网格中的点数加倍，则内存容量将增加到138 MB：


占用内存的大小尚未增加一倍，因为该内存的一部分被大小不变的资源和其他数据结构占用。 16K的额外点“称量”大约50 MB的内存，也就是说，每个点大约占用3 KB的内存。 这超出了我的预期，但总体而言，销量仍然很小。 在具有64 GB内存的计算机上，几乎看不到150 MB。

在进行了几次双打之后，我发现带有Dragons Abound的选项卡通常会在大约128K点崩溃。 如果我们在飞出之前抓住它并检查内存，我们将看到以下内容：


我以为该标签页由于占用的内存而崩溃，但通常问题不在内存中。 标签页为什么会崩溃？ 唯一的线索是，该选项卡在地图完成之前不会崩溃，这可能表示在渲染过程中发生了崩溃。

逻辑上假设我创建的SVG由于其大小或复杂性而使浏览器渲染器过载。 首先，我可以找出我创建了多少个SVG元素。 在D3中，我可以获得使用svg.selectAll('*').size()创建的SVG元素的总数。

从16K点开始运行并检查SVG元素的数量，我看到了以下内容：


32K点具有65457个元素，128K点具有258823个。添加到基础网格中的每个点都会向地图添加两个元素。 我想我发现了不幸的根源。

由于Dragons Abound渲染土地（和水）的方式，基本网格中的每个点都添加了SVG元素。 通过将每个基本位置渲染为填充的多边形，然后将它们全部模糊，来渲染土地。 这样， Dragons Abound可以为土地提供漂亮的图案，或使用土地的高度用3D阴影渲染土地，如下所示：


您可以关闭陆地和海洋的可视化功能，以检查创建了多少个SVG元素。 在256K点处：


哇，SVG元素的数量大大减少了。 如我所愿，现在地图已渲染而不会崩溃！ 也就是说，如果避免使用网格渲染土地和水，则可以创建比以前更密集的网格。

现在，我有了一个更密集的Voronoi网格，我想检查一下它是否允许我生成所需的陆地救济元素，例如沿海岛屿。 Voronoi的密集网格会带来其他问题（尤其是河流问题），因此我将关闭除海岸线以外的所有内容，以加快测试速度并专注于这些问题。 这是一些具有256K像素和标准噪点的海岸线的原始渲染：


事实证明，该地图渲染效果很好，并且已经创建了更加美丽的海岸线。

即使没有仔细调整，结果也要好得多。 噪声产生了我在上图所示的分形海岸线和沿海岛屿的类型。

以下是增长300％的岛屿：


随着这种增加，您可以从基础网格中注意到三角形的假象，但是即使如此，岛也可以创建有趣的形状。 您可以使用抗锯齿功能（就像我在当前版本的地图上所做的那样）来摆脱一些最明显的三角形伪像。 在标准放大倍率下，海岸线不那么崎rug，但也消除了一些小细节：


您可能必须调入中间立场。

大多数程序寿司发生器都使用Perlin噪声来创建高度图。 我们需要找到适当的噪声参数，选择一个种子，然后使用每个位置（x，y）的噪声值来设置土地质量。 制作土地的一个便利方面是，如果您需要海岸线上的更多细节，则只需调整噪声参数即可。

但是，《 无尽的巨龙》不会以这种方式创造土地。 （或者至少它能创造出更多的东西。）《 龙腾传奇》使用许多不同的方法来制作寿司。 尽管它们都在某种程度上使用噪声，但是很少有噪声直接造成土地。 例如，游戏具有创建孤岛的过程，该过程为该孤岛创建一个遮罩（通常为椭圆形），使用噪声使椭圆形更自然，然后应用不同的噪声以近似填充蒙版。 每个特定的地图通常是通过几种不同过程的组合来创建的。 因此，通过调整Dragons Abound的噪声参数来添加细节不是很合适。

就我的目的而言，最好从稍微不同的角度解决问题。 如果我有一个定义地块的特定高程图，那么如何在这些地块的边缘添加细节？ 这可能导致我们想到需要识别地块的边缘并遮盖地图的其余部分等的想法。 但是，另一方面，我一点也不反对在地图的其余部分添加其他细节。 如果陆地稍微不平坦或海底更粗糙，那么这是正常的。

向海岸线添加细节意味着什么？ 海岸线只是轮廓线，其中高度图的值为零。 （该值是任意的，但是在每个过程性土地生成器中都使用了这样的原理。）要使这条线更加详细，您需要在该轮廓线旁边略微上下移动土地，以使简单的海岸线变得更加复杂，部分土地突出到海洋中并变成岛屿等等。 但这不应该是偶然发生的，我希望更改看起来很自然。 我们总结了所有这些内容，似乎开始需要向整个地图添加少量噪波。 实际上，这正是我在上面显示的原始示例中所做的。

当然，必须小心地做，以免消除所产生的土地块并造成其他问题。 本质上，我需要配置三个参数。

首先是噪声的规模。 标度只是该噪声的值的间隔。 在我们的情况下，我想降低一些区域，然后升高一些区域，因此值的范围应该从负到正。 但是，我不想添加新的山脉或在远离现有海岸线的地方创建海洋，因此我将使噪声的最大（绝对）值占标准陆地高度的一小部分。

第二个参数是噪声的主要频​​率。 频率确定噪声在位置内变化的速度。 低频噪声的变化非常缓慢，因此带有低频噪声的正区域可以（例如）覆盖整个地图。 高频噪声变化迅速，因此带有高频噪声的正区域可以（例如）具有小岛的大小。 在我们的案例中，主要噪声频率决定了我们将在噪声中看到的最大浮雕元素。 也就是说，如果我想让噪声在地图上添加（例如）小岛（但没有比它们大的小岛），那么我需要选择一个小岛大小的主频率。

您可能认为这很容易做到（只需测量一个小岛，然后将此大小分配给主频率）。 但是，频率是在噪声函数的坐标中测量的，而不是在地图坐标中测量的！ 典型的噪声函数在每个坐标中的间隔可以为0到255，而地图在每个坐标中的间隔可以为-1到1，更糟糕的是，噪声坐标会崩溃，许多使用噪声的用户甚至都没有意识到这一点。 从一个单元到另一个单元的转换以及确定合适的频率会造成混淆，因此通常最简单的做法是仅对频率间隔进行实验，然后选择一个可以创建大小合适的卡元素的单元。

第三个参数是噪声的八度音阶数。 八度音阶是额外的噪音层。 每层通常使频率加倍，而噪声等级减半。 也就是说，每个新层添加的浮雕元素比前一层少两倍，但也要弱两倍。 也就是说，您需要选择能够提供所需元素最少的八度音阶数，为此，您可能需要调整噪声标度，因为它在最高八度音阶中仍然足够强，无法显示在地图上。 由于我有意这样做以使海岸线非常复杂，因此我将使用许多八度的噪声。

让我们开始设置。 首先，我将生成一个没有附加噪音的示例地图：


显然，这是一条无聊的海岸线，线条流畅，只有几个大岛。 这是与原始噪声样本相同的海岸线：


噪音极大地改变了地图的形状，将大片土地变成了海洋，反之亦然。 还出现了许多岛屿，包括远海。 所有这些都表明噪声等级太大。 噪声添加的最大的单个浮雕元素应该是原始地图的小岛的大小。 这可能是元素的最大新尺寸，证明了噪声的主频率已正确选择。 最后，出现了许多小的细节，直到显示尺寸的极限，这表明有足够的八度。 （但是，八度的数量可能会超过必要的数量。这不会影响卡的外观，但是效率很低。）看来，您基本上需要调整噪声等级。

调整噪声是一个相当复杂的操作，因为我希望该噪声主要影响高度为0的轮廓线处的土地和水域。也就是说，我需要一个相对较小的比例，但是尚不清楚如何选择正确的数字，因为在不同的地图中，高度的分布会有所不同。 解决方案是即时找到合适的比例尺。 您可以获取地图上所有高度的绝对值，对其进行排序，然后找到用于选择（例如）选择零附近位置的10％的截止点。 所有这些位置都落在间隔内（例如）[-0.05，0.05]，然后我可以使用值0.05来确定增加的噪声的大小。

（我之所以写“ definitions”，是因为出于各种原因，您不能仅使用0.05。首先，您需要将土地变成水，反之亦然。将0.002添加到-0.05不会对地图进行任何可见的更改。也就是说，间隔应大于0.05如果我想将高度为-0.05的位置的很大一部分从水转换为陆地，其次，噪声函数不是均匀分布的 ，因此，如果尺度为0.05，则噪声函数实际上将永远不会返回值0.05！实际上，困难在于规模应该更大 比我们想经常看到的最大值要大得多。）

经过试验，我发现了一个值，该值增加了海岸线的复杂性，同时又没有显着改变它们，并且还创建了少量的岛屿：


像往常一样，游戏中的这些参数可以取一个值的间隔，因此我可以获得各种各样的地图：从具有相当平滑的海岸的地图到具有破碎和复杂河岸的地图。 让程序选择值，我得到以下结果：


海岸线较为平坦，但中等规模和足够数量的新岛屿仍然增加了大部分复杂性。

实施分形海岸线时，我意识到可以使用噪声函数控制分形化程度，因此某些区域的海岸会很平滑，而另一些区域的海岸会很复杂。 我认为这将极大地增加地图的兴趣，并且看起来不太“生成”，因此我将在此处添加此功能。 这个想法非常简单-在将海岸线噪声添加到地图上之前，我将其乘以第二个噪声函数的输出，该函数的范围为0到1。如果此函数很小，则将小细节添加到海岸线。 接近1时，将附加所有详细信息。 选择第二个噪声函数的比例，该比例在整个地图上缓慢变化，我将获得一些海岸线复杂的区域，一些海岸线简单的区域，以及它们之间的逻辑过渡：


在这里，我将沿海参数设置为较大，以便可以更清楚地看到差异。 我们在东北看到狂野崎wild的海岸，在西部则看到平坦的海滩。

因此，我们大大改善了海岸线的生成，但是我仍然无法完全生成包含这么多Delaunay三角形的地图。 我仅显示轮廓图，因为许多其他地图元素已损坏。 它需要修复。

该程序的其余部分不适用于这么多的Delaunay三角形（当前设置为256K）。 主要问题在于，《 龙腾传奇》通过绘制所有单独的三角形来绘制土地和水域，因此许多SVG元素都会导致浏览器崩溃。 因此，我不得不完全禁用寿司渲染。 可能有解决此问题的方法，但三角形太多会导致其他问题。 例如，程序的某些部分必须处理整个地图。 在256K位置，它们每个都变得比16K位置慢16倍。 另外，在代码中，有些部分（例如，新的降水量模型）在使用多个三角形时会中断。 从创建如此详细的位置网格开始，我们什么也没得到-在生成海岸线之后，增加的复杂性没有任何改善。 因此，尽管我可以查看程序并修复大量位置会减慢或破坏代码太多的区域，但是在创建海岸线后降低地图网格的分辨率似乎更容易。

如上所述，Azgaar已经进行了更改地图底下Voronoi网格分辨率的工作 。 他意识到在生成过程中即时更改网格分辨率的可能性，也就是说，他可以（例如）增加沿海岸位置的密度。 但是，局部的密度变化有其缺点-特别是它会在边界上生成奇怪的三角形。 Azgaar后来提出 ，该系统过于复杂，不值得付出努力。 Azgaar通常知道他在说什么，因此我会信守诺言，并且不会尝试重新包装完成的网格。

相反，我创建了具有所需（较低）分辨率的第二个网格，然后将高程图复制到该新网格。 （不要忘记， Dragons Abound现在将海岸线与网格分开存储，因此，在创建海岸线之后，它们不再依赖于网格的确切拟合。这样做有点复杂。由于原始网格的分辨率比新网格高得多，因此原始网格的位置很多这些源位置的每个位置在高度图上都有不同的高度，我该如何复制它们？使用平均值还是最大（最小）高度？

首先，我只选择一个随机位置即可查看新网格是否适用于该程序的其余部分：


一切都出乎意料地好。 当新位置未正确标记为陆地，海岸或水域时，会出现一个小错误，但是在解决了此问题后，地图生成工作正常。 您需要清理一些细微的缺陷（例如，从水面上冒出来的Palmanor标签），但总的来说看起来不错。 即使是小岛也很美丽。

最后，我决定随着Voronoi网格的分辨率降低，每个位置将是基本位置的平均值。 这似乎是一个明智的决定，如有必要，可以随时进行更改。 此图显示了如何将海岸线从完成的网格中分离出来：


总结一下：在Dragons Abound中 ，生成高度图时使用了非常高分辨率的Delone三角形网格。 完成后， Dragons Abound通过跟踪高度图中从负值到正值的过渡来定义海岸线。 然后，游戏将高分辨率网格复制到分辨率低得多的网格，将落入新网格的一个位置的位置平均。 接下来，将丢弃高分辨率网格，而其余过程的生成和可视化将继续在低分辨率网格上进行。 一个有趣的问题是，在此阶段使用Delaunay网格是否有任何价值？ 它可能只是值得复制到六边形或类似形状的网格上。