用于在2D网格上对膨胀气体进行建模的算法

Question

我有一个简单的程序，其核心是浮点的二维数组，据说代表了气体浓度，我一直在尝试提出一种简单的算法，该模型将模拟气体向外扩展，就像云一样，最终结束整个电网的气体浓度相同。

例如，给定的状态进展可能是：（为简单起见，使用int）

开始状态

0000000000009000000000000

算法通过1次后的状态

0000001110011100111000000

再过一秒钟，应提供一个5x5的网格，所有网格均包含值0.36（9/25）。我已经在纸上进行了尝试，但是无论如何尝试，我都无法绕过算法来做到这一点。

所以我的问题是，我应该如何着手尝试对该算法进行编码？我尝试了一些事情，应用了卷积，试图依次获取每个网格单元并将其分配给其邻居，但是它们最终都产生了不良影响，例如最终最终消耗的气体少于我最初使用的气体，或所有气体运动都在一个方向上，而不是从中心向外扩展。我真的无法全力以赴，也将不胜感激。

Answer 1

如果您不考虑对流，则可能是扩散问题，如果不忽略，则可能是流体动力学/质量转移问题。如果要从头开始求解，则将从欧拉（固定控制体积）视点的质量和动量守恒方程开始。

这是一个短暂的问题，因此您需要执行积分以将状态从时间t（n）提前到t（n + 1）。您显示了一个网格，但没有及时解决问题。您尝试过什么整合方案？明确的？隐含的？ Crank-Nicholson？如果您不知道，说明您无法正确解决问题。

我真正喜欢的一本书是S.W. Patankar的"Numerical Heat Transfer and Fluid Flow"。现在有点过时了，但是我喜欢这种治疗方法。 29年后它仍然很好，但是自从我读了这个主题以来，可能会有更好的文本。我认为对于初次研究它的人来说是可以实现的。

Answer 2

在您给出的示例中，第二阶段的核心为1。通常，扩散需要浓度梯度，因此大多数与扩散相关的技术都不会在下一次迭代的中间更改1（也不会在第一个迭代之后达到该状态，但是一旦您完成，就会更容易看到得到了一个等值的块）。但是，正如您的帖子中的评论者所说，这不太可能是网络变动的原因。减少气体可能是边缘效应，但也可能是舍入误差的问题-将cpu设置为均匀舍入一半，然后累加气体并不时进行校正。

Answer 3

似乎您要为具有Neumann边界条件（边缘绝缘）的热方程实现一个有限差分求解器。关于这种事情有很多文献。 finite difference method上的Wikipedia页面描述了一种简单但稳定的方法，但适用于Dirichlet边界条件（边缘处的密度恒定）。修改边界条件的处理应该不会太困难。

Answer 4

[您似乎想要的是一种类似平滑算法的东西，通常在像Photoshop这样的程序中使用，或者像这种简单的Flame Effect这样的老式演示效果。

无论您使用哪种算法，它都可能会帮助您double buffer您的数组。

典型的平滑效果将类似于：

begin loop forever
    For every x and y
    {
        b2[x,y]  = (b1[x,y] + (b1[x+1,y]+b1[x-1,y]+b1[x,y+1]+b1[x,y-1])/8) / 2
    }
    swap b1 and b2
end loop forever

Answer 5

请参见Tom Forsyth's Game Programming Gems article。看起来它满足您的要求，但是如果没有满足，那么它至少应该给您一些想法。

Answer 6

为简单起见，这里是一维解决方案：

初始设置在原点（）的浓度为9，在所有其他正负坐标的浓度为0。

初始状态：0 0 0 0（9）0 0 0 0

查找下一个迭代值的算法是从与相邻邻居的原点和平均电流集中处开始。原点值是边界情况，并且在考虑原点值及其两个相邻点的同时进行平均值，即在3个值中取平均值。所有其他值均有效地取2个值中的平均值。

迭代1之后：0 0 0 3（3）3 0 0 0

在迭代2之后：0 0 1.5 1.5（3）1.5 1.5 0 0

迭代3之后：0 .75 .75 2（2）2 .75 .75 0

迭代4之后：.375 .375 1.375 1.375（2）1.375 1.375 .375 .375

您可以循环执行这些迭代。每n次迭代输出一次状态。您可以引入一个时间常数来控制多少次迭代代表一秒钟的壁钟时间。这也是整数坐标表示的长度单位的函数。对于给定的硬件系统，您可以凭经验调整此值。您还可以引入稳态公差值来控制程序何时显示“所有邻居值均在此公差范围内”或“两次迭代之间的值变化不超过此公差”，因此该算法已达到稳态解决方案。

Answer 7

给定起始浓度的每次迭代的浓度可以通过以下公式获得：

concentration = startingConcentration/(2*iter + 1)**2

iter是时间迭代。因此，以您为例。
startingConcentration = 9
iter = 0
concentration = 9/(2*0 + 1)**2 = 9

iter = 1
concentration = 9/(2*1 + 1)**2 = 1

iter = 2
concentration = 9/(2*2 + 1)**2 = 9/25 = .35

您可以在每个“时间步长”之后设置数组的值