记得之前和 @eastecho 聊起过 Terraria 中,关于流动的水方块的处理方法。我们跑到 Terraria 做了些测试,发现其在处理连通 U 型管的时候,并不是按照物理处理的,如图:
于是兴起思考了如何处理连通问题,就有了这个算法,分享给大家,欢迎批评指正。
Demo: http://lolwen.tk/g/grid-based-water-simulation/
Github: https://github.com/zsefvlol/grid-based-water-simulation/
简而言之
前提:
- 适用于基于方块构建的游戏,水是作为方块处理的,而不是粒子。
- 水的流动受重力影响。
- 不考虑水花溅出等情况。
对于每个时刻(tick)的基本思路,是分几个大步骤:
- 找到连通的水方块组,并标记。以下针对每个水方块组。
- 对所有接触空气的水方块,计算水向空气方向的压力(后文解释)。
- 找到压力最大的水块及压力方向,并标记其指向的空气块。
- 将绝对高度最高的水方块,移动到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:
查看在线 Demo
查看Github:
看起来效果还是很可以的,真正用的时候将孤立的水块儿用特定的方式处理下就可以了
@eastecho:还有就是半水块或者更多划分的水块,这个算法还是处理不了,我还在思考有啥解决方案……
@eastecho:有些游戏的孤立水块是随机运动的--供参考
@游戏发现:引入随机运动也可以帮助静止在高台上的水块滑落~
今天是泰拉瑞亚专题吗!
@Humble Ray:@XD1990 据说还要继续写Terraria攻略……
@Humble Ray:我看是,哈哈哈~~
Terraria 的好像确实有 BUG, 不过貌似大家没什么怨言. 哈哈哈
很有意思的讨论,其实不少游戏的水流判断都有泰拉瑞拉类似的问题,最近接触的一款叫《缺氧》的游戏也是这样类似的问题。
好棒!学习了!