在开发游戏时，我们经常需要用到随机生成的地形，而河流是其中不可或缺的一部分。本文章将探讨如何在地图上生成河流。

河流生成的自然原因

高山积雪，地下水，雨水是河流发源的主要原因，而由于雨水形成的小水流并不大，很容易在连续晴天后消失，并不稳定。而高山积雪和地下水，都可以看作是河流从某个固定的地方开始，到汇入湖泊或海洋结束，这正是我们需要研究的地方。

正如在自然中所见，河流从来都是蜿蜒曲折而非笔直的。

简单的解释就是河床两侧的土壤并不完全一样，有的坚硬，有的柔软，甚至会有动物在河床旁开凿洞穴改变河床一侧的土壤结构，如此下来，河流会蜿蜒曲折也就不足为奇了。

在顶点上沿边生成河流

这是河流生成的一种方法，如下图，蓝色的地块表示海洋，绿色的地块表示陆地，颜色越浅，地势越高，而白色地块表示山顶。

在RebBlobGames的一篇文章中写道：在确定每个地块和地块顶点的高度后，我在山顶地块的边缘随机找出一个顶点作为河流的发源地，从这个顶点开始，随机选择与自己临近而地势比自己低的一个顶点作为下一个河流所在顶点，而两个顶点所在边就是河流的一部分。如此往复，直到汇入湖泊或者海洋。

值得注意的是，这样的多边形地块并不是随机生成的，否则河流很有可能仍然近似笔直。

RLGUY在他的github文章里面给出了说明：

首先使用泊松盘分布采样生成一些点，这些点的距离不会太近，如下图右，作为对比，下图左是真正随机生成的一些点。

然后使用Delaunay三角剖分连接这些点

最后再生成Voronoi地图，如下图右，这样的地块更加漂亮。而左边是利用随机生成的点。

具体算法很容易搜索到，这里不再赘述。

在地块上生成河流

另一种方法则是直接在地块上生成河流。

基本方法与之前一种也是一样的，河流会从地势高的地块流向地势低的地块。但问题是，我们计算地块地势高低的数据，一般都是根据地块的某一固定点来计算的，例如正六边形地块的中心点，如上图，或者Delaunay三角形的外接圆中心点，如下图：

很多点同时在一条直线上的情况经常发生，Martin O'Leary在他的文章中也说到了这个情况。

而解决办法，就是我们可以将河流分成几段，每一段固定起点和终点，保证起点比终点高，而让中间的那些点自由选择流向，而忽略地势高低，这样会生成漂亮的效果。

另一种方法则是一篇论文里提出的利用三角形地块生成河流的方法里提出，利用三角形分形地块生成河流的方法。

步骤如下：先生成一个大三角，确定河流的大致流向，例如下图左，虚边代表河流流进，粗边代表河流流出，细边代表普通边。

然后将大三角形分形，分成四个小三角形，那么此时原来的进入边变成一条进入边和一条普通边，流出边也是如此，这时候河流就有四种可能的具体流向，见上图右。这时再随机选择一种，继续迭代下去。

下图是一种效果。

其他方法

板块漂移运动

这篇文章利用随机生成的板块及板块的运动方向来确定哪里会出现河流湖泊，哪里会出现高山。红色表示板块挤压，容易形成高山，蓝色表示板块相离，容易形成河流。

随机分形

Mandelbrot在他的分形著作《大自然中的分形几何学》也介绍过利用树状结构生成河流的一种方法。

生成河流需要保证河流不会与自己相交。利用树形结构是一种很好的方法，如下图，事先确定好河流可能流经地的树状结构，让河流只能从上面一层到下面一层随机一个节点上。

而之前提到的利用地势高低，或者将大三角形分形成小三角形也都用到了类似方法。

参考

1. http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
2. rlguy/FantasyMapGenerator
3. http://algorithmicbotany.org/papers/mountains.gi93.pdf
4. http://eveliosdev.blogspot.com/2016/06/plate-tectonics.html
5. http://mewo2.com/notes/terrain

欢迎在我的知乎专栏里查看这篇文章！