现在我要讲讲如何拼嵌我们的二维高度图数组。

Diamond-Square 算法

正如本文开头提到过的，我先介绍 Gavin S.P.Miller 的论文中随机地形生成的概念。具有讽刺意义的是， Miller 在论文中说 diamond-square 算法是有缺陷的，然后描述了一种完全不同的基于重量平均和控制点的算法。

Miller 对 diamond-square 算法的抱怨阻止他尝试迫使该算法建立一座山，也就是，带有一个山峰，人为增加网格中心点的高度。他让数组中所有的点都随机生成。如果 Miller 简单的只随机生成中心点，那么即使是他也会同意该算法是个经典的地形生成器。 Diamond-Square 算法可以通过给数组播种值来用一个山峰推出一坐山。比数组中心点更多的点得先播种以构造可接受的结果。他也抱怨一些固有皱折问题。但你得自己判断。算法最初是由 Fourniew ， Fussell 和 Carpenter 提出的。

思想如下：你从一个很大的空 2D 数组开始。多大呢？为简化起见，他应该是方的，维数应该是 2 的 n 次方加 1 （如 33X33,65X65,129X129 等）。将四个角设为相同高度。如果你察看所得到东西，它是一个正方形。

取个简单的例子，用一个 5X5 的数组。（本文后面还要参考这图，别忘记了）。图中，图 a 的四个角种上了初始高度值，表示为黑点。

这是递归细分过程的起点，该过程分两步：

diamond 步：取四个点的正方形，在正方形中点生成一个随机值，中点为两对角线交点。中点值是平均四个角值再加上一个随机量计算得到的。这样就得到了一个棱锥。当网格上分布着多个正方形时有点象钻石。

square 步：取每个四点形成的棱锥，在棱锥的中心生成一个随机值。平均角值再加上与 diamond 步相同的随机量，计算出每条边中点值。这又给你一个正方形。

这样，如果已经生成了一个种子正方形并经过单独一次细分过程将得到四个方形。第二次经过该过程得到 16 个方形，第三次得到 64 个方形。增长得很快。方形数目等于 2( 2 + I ) ，其中 I 为递归经过细分过程的次数。