渐进式连接元件标记

Connected Component Labeling 找到所有“开”组件的算法。通常,但并非总是,只有一个“开”组件。

我希望构造一个算法,将一个开/关单元格矩阵、一个组件标签(可能格式化为单元格哈希集列表)和一个自标签形成以来已更改的单元格列表作为输入,并输出一个新的标签。显而易见的解决方案是从头开始重新计算,尽管这并不高效。通常,已更改的单元格列表将很小。

Groups G;
Foreach changed cell C:
  Group U = emptygroup;
  U.add(C);
  Foreach Group S in G:
    if (S contains a cell which is adjacent to C)
      G.Remove(S);
      U.UnionWith(S);
  G.add(C);

但是,如果更改包含任何已关闭的单元格,我不知道该怎么办。请记住,细胞上的所有细胞必须是同一组的成员。因此,一种解决方案是将与新脱离单元相邻的每个单元取出来,看看它们是否彼此连接(例如,使用*寻路)。这将产生1-4个连续组(除非该单元是其组中唯一的单元,因此有0个相邻单元要检查,在这种情况下,它产生0个组)。然而,这只比从头开始好一点,因为通常(但不总是)将这些相邻的正方形连接在一起和仅仅找到一个相邻的组一样困难(除非有人有一个聪明的方法来这样做的建议)。另外,如果有很多细胞发生了变化,那就有点可怕了……尽管我承认通常没有。

一条规则 Nurikabe 谜题是你可能只有一组连续的墙。上面是我试图解决的一个问题的简化,以提高速度(并玩寻路游戏)。基本上,我希望检查连续墙,而不浪费从以前的此类测试中获得的信息。我试着看看我的解算器中有多少地方可以利用以前的信息来提高速度,因为当一个O(f())算法足够时,使用O(f(N))算法似乎有点痛苦(N是拼图的大小,是自上次运行算法以来所做的更改)。

剖析 做

注: 我省略了解释我当前的算法,但它基本上是通过基于堆栈的方式工作的 Flood Fill 算法首先在正方形上找到,然后检查是否有更多的正方形(这意味着有多个组,它不费心检查)。

:增强想法:Yairchu和John Kugelman的建议在我的脑海中结晶成了这个改进,实际上它本身并不是这个问题的解决方案,但可能会使这部分代码和其他几段代码运行得更快:

foreach (Square s in m.Neighbors[tmp.X][tmp.Y])    
{
    if (0 != ((byte)(s.RoomType) & match) && Retval.Add(s)) curStack.Push(s);
}

改进思路:

foreach (Square s in m.NeighborsXX[tmp.X][tmp.Y])    
{
    if (Retval.Add(s)) curStack.Push(s);
}

这将需要维护几个m.NeighborsXX实例(每种需要增强的匹配类型对应一个实例),并在正方形更改时更新它们。我需要对此进行基准测试,看看它是否真的有帮助,但它看起来像是用一些内存换取一些速度的标准案例。