一个水方块流动算法

作者:lol
2016-02-19
15 37 10

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

water

Terraria 连通管

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

Demo: http://lolwen.tk/g/grid-based-water-simulation/
Github: https://github.com/zsefvlol/grid-based-water-simulation/

简而言之

前提:

  • 适用于基于方块构建的游戏,水是作为方块处理的,而不是粒子。
  • 水的流动受重力影响。
  • 不考虑水花溅出等情况。

对于每个时刻(tick)的基本思路,是分几个大步骤:

  1. 找到连通的水方块组,并标记。以下针对每个水方块组。
  2. 对所有接触空气的水方块,计算水向空气方向的压力(后文解释)。
  3. 找到压力最大的水块及压力方向,并标记其指向的空气块。
  4. 将绝对高度最高的水方块,移动到3中指定的空气块。

具体而言

1. 找到连通的水方块组

初始状况如图
pic-1
由三种类型的方块组成:水方块,墙方块,和空气方块。

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

pic-2

连通状况检查

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

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

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

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

pic-3

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

水下方是空气

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

pic-4

水下方是空气

水左/右是空气

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

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

pic-5

水左/右是空气

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

水上方是空气

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

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

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

pic-6

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

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

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

pic-7

标记要移动的空气块

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

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

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

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

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

pic-8

移动水方块

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

我们考虑如下特殊情况。

pic-9

错误的下落方式

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

pic-10

那么操作方式是,找到最顶层的一横行水方块,标记其中最靠左的水方块的 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:

源代码

Github

近期点赞的会员

 分享这篇文章

lol 

弃游戏狂人 

您可能还会对这些文章感兴趣

参与此文章的讨论

  1. eastecho 2016-02-19

    看起来效果还是很可以的,真正用的时候将孤立的水块儿用特定的方式处理下就可以了

    • lol 2016-02-19

      @eastecho:还有就是半水块或者更多划分的水块,这个算法还是处理不了,我还在思考有啥解决方案……

    • 游戏发现 2016-02-19

      @eastecho:有些游戏的孤立水块是随机运动的--供参考

    • lol 2016-02-19

      @游戏发现:引入随机运动也可以帮助静止在高台上的水块滑落~

  2. Humble Ray 2016-02-19

    今天是泰拉瑞亚专题吗!

    • lol 2016-02-19

      @Humble Ray:@XD1990 据说还要继续写Terraria攻略……

    • eastecho 2016-02-20

      @Humble Ray:我看是,哈哈哈~~

  3. meme 2016-02-21

    Terraria 的好像确实有 BUG, 不过貌似大家没什么怨言. 哈哈哈

  4. jtn007 2017-04-20

    很有意思的讨论,其实不少游戏的水流判断都有泰拉瑞拉类似的问题,最近接触的一款叫《缺氧》的游戏也是这样类似的问题。

  5. Kiritow 2017-05-10

    好棒!学习了!

您需要登录或者注册后才能发表评论

登录/注册