在我的世界之旅中，我需要在这样的景观上生成半现实的河流。
造河基本上涉及根据当地地形对水流进行建模：我们从山区开始，逐渐将水收集到越来越大的溪流和河流中，直到最终到达海岸。 这听起来非常简单-实际上是流量计算。 但是最大的障碍是山谷的存在，即当地的极小值：流动的水将被困住而无处可去，从而切断了河流的形成。 必须以某种方式填满山谷。 我尝试了几种方法，下面将进行讨论。
- 加勒特：案例研究和心理概况
- Fortnite和Apex Legends可以教给您有关产品管理的知识
- 有时您想去每个人都知道您（屏幕）名称的地方
- 2064：只读内存评论
- 如何在Bless Online中快速升级？
这是我逐步解决问题的尝试的一部分：如果您想跳到工作模型的细节，请放心。
模拟水滴法
一种解决方案是对每块瓷砖上的水单元进行建模，以使它们自然移动并堆积在草皮和草皮中，最终将它们填满，并使更多的水以新的路径流出。 就像您可能想像的那样，这是计算密集型工作：您必须跟踪所有水，并根据其位置在每个时间步长重新计算流向。 如果您尝试不使用微分方程式离散地执行此操作，由于流动的水无法均匀地追赶其自身，您还容易产生振荡和棋盘图案。
我最初实施了这种类型的系统，但是由于速度和另一个无法预见的缺点，我想找到一个替代方案：随着水从山上流到海岸附近的低洼地区，水会趋向于分散成沼泽。 这在某种程度上是现实的，但结果是河流通常不到达海岸。 一种解决方案是对流速和水动量进行建模，但这是复杂性的主要增加。 相反，我想解决第二种主要方法-这也很简单，但是比第一种方法需要更大的设计智慧。
填充前方法
如果仅以主流量指数计算一次流量，则河流模型可能会快得多，这样，每个时间步长中的水流总是以相同的方式流动。 缺少的是水流过山谷的方法。 您可以看到，这样的幼稚模型在地形很少的地图陡峭部分上效果很好，但在低洼或崎areas不平的区域上效果不佳：
在不重新计算流量的情况下，我们需要在其余模型执行之前显式处理谷值。 简而言之，我们必须检测出山谷，然后将其填充到正确的高度。 通过这种方式，山谷变成了具有平坦表面的湖泊，河流便可以流过。 这种方法需要更多的前期处理，但是很快。 它更像是一种自上而下的（现象学的）方法，对结果的兴趣比对模拟过程的兴趣更大。
检测微小的微谷非常容易：找到（正交的）八角形以上的所有细胞，然后选择最低的邻居值并填充到该高度。 此方法不适用于任何较大的东西，但是可以想象得到一个大致等效的过程：它将需要找到更大的山谷并找到应该填充的高度。
失败的方法：隔离每个山谷
我最初的尝试是自上而下的，必须放弃。 我以为我会识别并存储每个山谷的范围，然后填充它们，而替代方法是仅将规则应用于图块，而不是完全不正式绘制山谷。
我首先确定本地流量，然后使用它为每个瓷砖最终找到水的位置找到一个“最终目的地”。 任何不是海洋的目的地，我都将其视为山谷的底部-瓷砖被倾泻入其中，我就像是一个分水岭。 这似乎很聪明，但实际上我只有片片分水岭，通常是同一山谷的一部分。
这些切片将需要合并。 之后，需要将其填充…但是要达到什么高度？ 大概是最低的相邻瓦片不是山谷的一部分。 但是山谷可以很容易地彼此邻接。 它们甚至可以完全被另一个山谷包围或包含在另一个山谷中。 是否应将两个山谷合并为一个山谷，实际上取决于其中的水量：如果水位足够低，则每个山谷都将形成一个湖泊。 足够高，它们互相溢出，合并成一个湖。 因此，合并山谷时没有简单的规则。
前进的唯一途径似乎是集中在水的高度上，而不是集中在山谷本身上，而是集中在水将流向何处。
使用二维隐喻
在考虑更简单的二维岛情况下，我将首先考虑如何手工解决问题，这是一个更加自下而上的方法-在这里，我们首先要考虑的是海拔剖面，而不是鸟瞰。 至少在幼稚的第一遍中，人们可以在不同高度的景观上绘制一系列线条。 它们从海洋开始，到与地形相交的任何地方停止，在山谷所在的地方留下空白。 这基本上是产生谷值的倒数。
一幅画多少条线（或3d层）？ 由于我的景观是连续的高程，并且不限于整数值，因此需要无穷多个。 显然，思想实验必须完善。
关键的认识是，不需要在任意高度绘制线：地形本身提供了输入线可以或不能交叉的临界阈值。 因此，当从海洋中抽出一条线时，我们只能调整其高度以匹配地形。 特别是，我们将允许它向上但不向下调整高度：
唯一的例外是，当一条线从另一侧进入另一条线时：那么，在给定点上，首选两者中的较低者。 这样可以使排水区域的水位尽可能低-但是，如果没有排水沟比地面低，它就会填满。
这是我们可以在纸上使用的好方法。 它可以相当容易地扩展到三个维度。 但是，我们必须用控制单个单元格的规则来表达算法，而不是我们要绘制的规则。
成功的填充算法
基于单元的算法的规则非常简单，但是我将首先以英语描述该过程以及每个步骤为何重要。
- 我们将追踪已知哪些细胞最终会排入海洋。 最初，只有海洋瓷砖自己会。
- 我们将使每个单元格找到其邻居的最低值，并填充到该新值。 （相当于画线的高度。）我们重复此过程很多次。
- 但是细胞只考虑排入大海的邻居。 调整后的任何像元也将保证也要排空，因为其新高度必须与一个像元一样（并且我们会相应地调整其状态）。
- 这种保证意味着我们将从海岸开始，逐渐向内陆发展（就像我们绘制的线一样）。 我们正在处理的单元中的水将始终有一条通往海洋的路径：因此，只有在有必要建立该路径时，我们才会调整填充高度。
- 我们一直在检查所有与排水相邻的单元，而不仅仅是新排水的单元，因为可能会“发现”一条较短的通往海洋的路径（通过从另一个方向工作），这将使这些单元将其填充高度降低至一个低等级。 这样我们就可以避免山谷被过度填充。
- 我们可以迭代此过程，直到不再进行任何更改或执行一些步骤为止。 所需的时间取决于景观的复杂程度，但是对于大多数景观而言，它是在地图的线性长度内完成的（如果是矩形，则在其侧面较大的范围内）。
这是输出：
伪码
编码人员的快速版本：
elev = a 2-d numeric array
fill = elev
drains = boolean array, where elev == 0
timestep loop
for every cell
find neighboring cells and store fill values
set neighbor values to NULL where drain = 0
get max neighbor value
if max is higher than self fill
set fill to max
set drains to 1
output fill 输出的有趣特征
我们可以考虑模型在示例岛上的工作方式，作为提醒，这里没有水：
填充/湖泊
您可以在此处看到填充地图和原始地图之间的差异。 有少量填充的单细胞喷雾，可平滑有效表面。 还有四个大湖，与洼地明显对应。 其中之一实际上很深，因为周围的地形也相当高，因此需要大量的填充物才能找到通往海洋的通道。
积水
我根据流过每块砖的总水量计算出最终的河砖； 或者换种方式说说流程图中上游的切片数。 显示中的任意阈值允许用户排除小河，但在这里我们可以一次看到所有水。 特别有趣的是山脊线，它几乎是黑色的，暗示着不同的分水岭。
分水岭
在这里，我们看到水从不同的区域排入海洋。 沿海地区有许多较小的区域，但我们可以任意限制，以查看较大的内陆区域。 在此，也有效地勾勒出了脊线。 我也喜欢它，因为它使人想到这样一个建议，即与生态相关的市政当局将具有与其流域相匹配的边界，而不是任意的界限或主要障碍。
路径计算
此图显示水必须行进才能最有效地流到海洋的距离。 如果我们认为水在寻找路径，这说明了搬入相邻砖块的成本：一条河会喜欢可用的最深色砖块； 颜色不连续表示流动障碍。
实际上，我并非专门使用此地图来确定河流的流向：首先，考虑局部地形（陡度），并将此寻路beind用作平局（此后，使用任意单元索引）。
结论
关于谷值检测算法（以及山脊检测）的学术著作很多，因为它在图像处理中有很多用途。 我知道地理学家还开发了许多用于计算流量的工具，并且小规模的草皮填充是其中的一部分。 我只是出于实际需要而开发了该解决方案，这是为了快速创建河流，以及对如何完成此项目的好奇心。 该算法可能已经存在，我很高兴经历了独立生成它的过程。 可能也没有，在这种情况下，我希望它对其他人有用。
使它与众不同的一件事是它取决于任意的起点， 即海洋。 在很多情况下，可能无法使用通用图像处理或没有任何意义。 因此，我可以预见到该算法是专门为DEM建模量身定制的。 它的伸缩性相当好（我将在第二天进行基准测试）并产生漂亮的功能。 它不能像液滴方法那样很好地用于侵蚀建模，但是对于在人工生成的地形上简单地创建河流和湖泊也是如此。
