记得之前和@eastecho聊起过Terraria中，关于流动的水方块的处理方法。我们跑到Terraria做了些测试，发现其在处理连通U型管的时候，并不是按照物理处理的，如图。

于是兴起思考了如何处理连通问题，就有了这个算法，分享给大家，欢迎批评指正。

Demo: http://lolwen.com/g/grid-based-water-simulation/

Github: https://github.com/zsefvlol/grid-based-water-simulation/

简而言之

前提：

- 适用于基于方块构建的游戏，水是作为方块处理的，而不是粒子。

- 水的流动受重力影响。

- 不考虑水花溅出等情况。

对于每个时刻（tick）的基本思路，是分几个大步骤：

1. 找到连通的水方块组，并标记。以下针对每个水方块组。

2. 对所有接触空气的水方块，计算水向空气方向的压力（后文解释）。

3. 找到压力最大的水块及压力方向，并标记其指向的空气块。

4. 将绝对高度最高的水方块，移动到3中指定的空气块。

具体而言

1. 找到连通的水方块组

初始状况如图

由三种类型的方块组成：水方块，墙方块，和空气方块。

对其做连通性检查，结果如下图（在Demo中可以通过点击Connectivity查看连通状况）

这一步相对简单，可以通过简单的遍历标记水块连通状态，相信大家都有各自的实现方法。不多赘述。最终需要将相连通的水方块组分别标记即可。

2. 对所有接触空气的水方块，计算水向空气方向的压力。

这一步是重点。考虑水之所以会移动，是由于重力带来的水压力。因此我们对每个连通的水方块组，计算其中每一格接触空气（即有移动可能）的水的压力。

显然。对于任意一格水，如果它上下左右四个方向都是水或者墙，那么它是不会移动的。

那么出现的情况无非是四种：

水下方是空气

我们定义此时水向下流动的压力是最大值（Demo中使用Number.MAX_VALUE表示）。这会导致下一个时刻，该水块下方必然会有一个水块。

水左/右是空气

此时，每个水方块的压力是

pressure = Δh = 当前水方块高度h - 水方块组顶层高度h0

上图可以看出在不同条件下，水方块存在的对左右方向的压力。

水上方是空气

这个状况即解决连通U型管问题的关键。水方块的压力是

pressure = Δh - 1 = 当前水方块高度h - 水方块组顶层高度h0 - 1

由于向上方移动需要消耗一个高度，所以必须减1。

3. 找到压力最大的水块及压力方向，并标记其指向的空气块。

有了上一步的操作，这步无非是将上述结果中最大值列出即可。这里要注意：

  a. 可能有多个水块符合压力最大值，需要将它们指向的空气块都记录下来，如图中黄色箭头指向的两个空气块

  b. 我们注意到，右侧的2、3两个水块指向了同一个空气块，在算法实现的时候务必要记得去重。

  c. 由于向下的压力是无穷大，水流一定优先向下移动。如果这不是你预期的效果，你可以将向下移动的压力设置为Δh+1。后果是如果水柱很高，低处水的移动可能会阻止高处水的掉落。

  d. 如果最大的压力小于等于0，则意味着没有水方块需要被移动。

4. 将绝对高度最高的水方块，移动到3中指定的空气块。

从最上方的水开始遍历，每找到一个水块，就将其移动到上一步中标记的空气块。

在上图中，可以发现，实际移动轨迹是交叉的，左方的水块移动到右边，右方的移动到左边，为什么这么操作呢？

我们考虑如下特殊情况。

我们显然不希望发生这种水块自己掉下去的情况，我们希望水块能够“拖着”其水方块组一起移动，也就是如下图

那么操作方式是，找到最顶层的一横行水方块，标记其中最靠左的水方块的x坐标x_left，和最靠右的x_right。则我们需要移动的方块必然是这两块之一。

假设当前移动到的空气块的x坐标为x0，则要移动的方块为：

x_to_move = x0<(x_left+x_right)/2 ? x_right : x_left

即，找到顶层水方块的中线，如果空气块在中线左方，则移动最右边的方块，反之左边。

反复执行上述操作，直到没有水块被移动，即可找到稳定状态。

这个算法的描述起来比较简单，遍历次数也是线性的，预期效率问题不大，况且这其中还有很多可以优化的部分（如高效找连通水方块组，高效查找水边缘空气块等）。

不过我没有大规模的验证过，如果有同学实际使用这个算法，希望能一起进一步讨论细节。

再发一次链接，欢迎pull-request

Demo: http://lolwen.tk/g/grid-based-water-simulation/

Github: https://github.com/zsefvlol/grid-based-water-simulation/

==更新==

关于优化部分：

1.@ ∈Φ.威士忌  指出 连通性在一次计算出来后，后续更新，可以通过判定移动后的水块的位置，进行合并。不需要每次计算连通。

这是个很合理的优化方案。同时接触空气的水方块也可以根据前一次计算结果来获得，而不需要每次遍历所有水方块。