自然的“水”流过节点网络

Question

希望这一点足够清楚。

我有一张由瓷砖制成的二维地图，我想要“水”通过这张地图。它从管道中流出到特定的瓷砖上，然后需要像水一样填满所有的瓷砖才能到达另一个瓷砖。我目前已经将地图输入到游戏中，每个瓦片都是一个节点，每个节点都连接到周围所有合适的瓦片。我将节点存储在一个排序的数组中，首先按x排序，然后按y排序。此外，一些瓦片是“门”瓦片，这可以阻止水通过它们。这些是相同的节点瓦片网格的一部分，并且在激活时只是被标记。

问题是我如何分散水。

最初，我让每个管道(滴水)记录一个“当前”和“满”水瓦的列表，它会直接将水分散到“当前”瓦片上，然后在适当的时候将它们切换到它的“满”列表。“当前”列表通过获取已经“当前”的磁贴的周围磁贴来扩展。在任何情况下，这都很好用，水也很好地流动，但我不知道如何让它与闸门一起工作，这样水的流动就可以停止，并重新允许(然后再次停止，等等)。在特定的点上。

现在我有它的地方，水倾倒到一个并且只有一个瓷砖，然后当一个瓷砖有太多的水，它逐步推动水到随机相邻的瓷砖(除非瓷砖是一个活动的门)。这样做的问题是，水在已经填满的瓷砖周围“晃动”，而不是“向外”流动。它最终会到达那里，但流程要不自然得多。

我的两难境地到此结束。

代码是用python编写的。

编辑:新想法。我可以让管道在节点中搜索合适的空闲瓦片，以便在每次更新时放置水，但这似乎效率非常低--特别是在多个管道的情况下。

Answer 1

这在游戏开发中经常出现--已经有很多关于这个主题的GDC演讲和Gamasutra/Game Developer杂志的专题文章。我认为对你来说最好的是来自2003GDC的Jos Stam的"Real-Time Fluid Dynamics for Games“。

他描述了一种通过线性回溯执行平流的简化方法，该方法存在一些问题，但对不可压缩流体非常有效(也就是说，它对水比对气体更有效)。线性回溯基本上意味着他在空间中的每个点(这是你的瓷砖)建立了一个表示流体密度的网格，然后对于每一帧访问每个点并询问，“基于周围点的压力，流体可能来自哪里？”事实证明，这比用另一种方法解决它更容易(“从这一点开始的流体要去哪里？”)。

Gamasutra的Mick West's article on fluid dynamics在某些方面扩展了Stam的论文，可能会提高性能，所以你可能想从那里开始。

也有a recent Intel-sponsored GameDev article that offers a more complete solution，但它相当复杂，更侧重于3d的图形渲染方面。

你可以在“矮人堡垒”中找到一个瓦片二维流体力学的例子，但他的解决方案似乎有一堆处理快速流动或加压流体的问题；有时他的水移动得比你想象的要慢得多，或者被困在积木和角落里。

这些论文总结了数学和算法，比我塞进Stack Overflow盒子要好得多，但我也想提出两个一般性的观点：

1. 水模拟的计算量非常大。由于您使用的是Python，这可能会导致真正的性能问题--一定要设置一些分析算法的方法来查找热点，以防您的循环花费太长时间而导致帧率下降。你可能不得不求助于Numeric Python来获得更快的基于C的数组operations.
2. There在游戏开发中比大多数人预期的要数学得多！

Answer 2

关于假设的一些启发式方法：

在给定的瓷砖上，水永远保持不超过一层的高度。

• F211<<>>

对于每个水坑，维护一个边框列表，并在边框旁边打开方框。

当障碍消失时

amend the lists of edge and open squares for any puddles that were touching it

当障碍物升高时

if (it was covered)
    pick a non-wall square next to it at random, and add the drop from the barrier there.
amend the lists of edge and open squares for any puddles next to the block

添加drop时：

if (the square "under" the pipe is empty)
   fill it
else
   consult the list of edge square associated with the pool under the pipe, and select the one closest to the pipe (if more than one is closest, choose from the candidates at random), and fill it.  
amend the lists of edge and open squares for the puddle (be prepared to merge with neighboring puddles if necessary)

当你移除一滴水时

 find the edge (not open!) square farthest from the sink (or randomly select from the equivalent candidates), and empty it
 amend the lists of edge and open squares for the puddle

(这里提供的折边是使“最远的”与其他水槽的距离相等，这样如果水坑中间的正方形在水槽之间，它们就会变成空的。)

这不是很现实，也不会给你带来任何动力，但会在滴水管道下保持连续的水坑，并在提供足够滴水的情况下填满可用的空间。

Answer 3

您的模型是否包含电位差或压力的概念？

假设一个空瓷砖的压力为零，一个满瓷砖的压力为10，如果两个瓷砖之间有一条管道，那么水就会流动来平衡压力，一个闸门就会关闭一条管道，所以什么都不会流动。