计算科学 - 使用元胞自动机模拟圆形模具传播 - 代替出现方形 - 吾爱随笔录

我正在尝试使用基于元胞自动机的方法来模拟培养皿中霉菌的传播。感谢我在另一个问题Stochastic cells automata - algorithm limited by 1 cell per timestep中的回答，我正在尝试使用优先级队列的不同方法。

语境

培养皿可以被认为是一个由 1mm x 1mm 正方形组成的网格，每个正方形称为一个 Cell。每个方块都有一个霉菌在该类型食品中的传播率 (RoS) 值，该值可作为经验测量数据获得。对于这个问题，我们假设培养皿都是相同的食物类型，RoS 为 1 毫米/小时。

我们通过说一个特定的细胞发霉了来播种这道菜。然后我们开始迭代。对于每个单元格，我们计算它的 8 个邻居会在什么时候发霉。我们将这些单元格添加到优先级队列中，优先级是它们应该发霉的时间。例如，检查第一步：

第一步，只有一个发霉的细胞。我们可以预期邻居 2、4、5 和 7 会在 1 小时后发霉（对于 1mm/hr 的 RoS，模具需要 1 小时才能传播 1 毫米），我们可以预期邻居 1、3、6 , 8 之后会发霉 $\sqrt(2)$ 小时，因为对角线单元之间的距离不是 1 毫米，而是 $\sqrt(2)$ 毫米。我们可以说一个邻居发霉的时间可以通过一个函数返回 $g(food, distance)$ . 因此，当迭代第一个单元格的邻居时，我们应该期望队列中有 2 个项目：邻居 2、4、5 和 7 将在 1 小时后发霉，而邻居 1、3、6 和 8 将在之后发霉 $\sqrt(2)$ 小时。

至此，我们完成了对所有发霉单元的第一次迭代，我们继续进行队列中的下一项，即迭代所有将在 1 小时内发霉的单元，并计算它们的邻居发霉的时间。算法的快速伪代码可能如下所示

mold_next = PriortyQueue({Initially moldy cells each flagged to t=0})
while mold_next is not empty and t<max_timestep:
  c = pop(mold_next)
  if c is moldy:  # Very important
    continue at next iteration of while loop
  make c moldy
  for all neighbours n of c:
    add n to mold_next at a time drawn from g(food, distance)

问题

我对此的迭代（用打字稿编写并且太复杂而无法发布，甚至无法提取到最小可重复的示例），有一个问题。出现的形状不是人们可能期望的圆形，而是始终是正方形。让我们看一下前几个时间步：

请注意最后几个步骤没有被切断 - 图像边界之外没有发霉的细胞。看一下显示更多时间步长的 gif：

出现的模式是，随着形状的增长，它“长方形”。从第一个细胞的意义来看，发霉的细胞出现在细胞的四个主要方向。然后，角落被填充。然后，发霉的细胞再次从每边中心的四个基本方向出现，并开始向边缘“填充”，直到我们再次有一个正方形。直到一个正方形“完成”后，下一个单元格才会出现在基本方向上。

寻找线索

我试图理解为什么会这样。查看第一次迭代：

假设我们在这种状态下开始迭代：第一个单元生成了它的 2 个队列项，如本问题前面所述。我们现在正在迭代后续队列项，它表示单元格 2、4、5 和 7 将发霉。我们已经让它们发霉了。现在我们遍历它们。有问题的单元格是箭头指向的那个单元格，比如单元格 $C_2$ . 第一个单元生成的 2 个队列项目表明该单元将在 $t_0 + \sqrt(2)$ . 黑色箭头所源自的细胞在 $t_0 + 1$ ，并且他们每个人都将一个项目添加到队列中 $C_2$ ，这将在 $t_0 + 2$ , 但由 $t_0 + 2$ ，这个细胞已经发霉了（在 $t_0 + \sqrt(2)$ )，正如算法所说，if c is moldy, continue at next iteration of while loop。

但不知何故，这种模式创造了一个方形的出现，角落总是先填满。往下看几个时间步：

迭代这些单元格，我希望 $C_n$ 先成型 $C_1$ , $C_2$ ，和 $C_3$ ，但事实并非如此。成型顺序为 $C_1$ , $C_2$ , $C_3$ ，然后 $C_n$ . 我很难理解为什么会发生这种情况。

从根本上有缺陷的逻辑与实施错误？

我的算法设计是否存在根本问题？或者我可能有一个实现错误？我所描述的算法是否应该不会导致出现大致圆形的形状？