algorithm - 六边形 map 查找是否有一些网格被包围算法

Question

我正在通过 Unity 创建一个简单的六边形几何数学游戏。这确实与 Unity 无关。

我借了Image来自 https://catlikecoding.com/unity/tutorials/ , 为了说明这个问题，它很大，所以我把它放在链接中。

---

背景

与提供的链接中的教程相同，我使用数组来保存数据，为了简化它，就像:

[      0, 0, 0, 0,    
        0, 0, 0, 0,
       0, 0, 0, 0,
        0, 0, 0, 0,
       0, 0, 0, 0      ]

我的目标是

Check if one or more than one grids are surrounded by another type of grid.

定义

Surrounded means for a grid or group of connected grid, all neighbors are in different flag of them.

例如，

[      0, 1, 1, 0,    
        1, 0, 1, 0,
       0, 1, 1, 0,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

//Should become

[      0, 1, 1, 0,    
        1, 1, 1, 0,
       0, 1, 1, 0,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

对于这种情况，我什至不需要算法，这很简单，因为我可以引用它的邻居来创建网格，比如

class grid{
    grid[] neighbor;
    int flag; //0 or 1
}

所以，当我需要检查一个网格是否被包围时，我只需要循环它的neighbor。

---

问题

但是，这种方法在以下情况下变得乏味

[      0, 1, 1, 1,     
        1, 0, 0, 1,
       0, 1, 1, 1,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

所以，我现在还需要检查它的邻居的邻居，比如

foreach (grid i in neighbor){
   bool is_surrounded = false;
   if (grid.flag == 1) {
       //Good
   } else {
       //Check its neighbor, if every neighbor except i is 1, then return True. 
   }
}

它对 2 个工作正常，但如果有 3 个空白网格怎么办。递归是不行的，因为当网格没有被包围时

[      0, 1, 1, 1,     
        1, 0, 0, 1,
       0, 1, 0, 1,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

然后我将循环整个 map 以检查大约 8^n 次。

---

问题

我认为有一种我没有意识到的更聪明的方法，我欢迎任何类型/语言的回答，甚至只是一个想法。可以肯定的是，我会为工作 ans 提供奖励。

谢谢。

Answer 1

首先你必须做出严格的定义——什么区域被称为“包围”。也许可能的方法是 - 单元格没有通往外部 map 边缘的自由 channel 。

要以这种方式检查 - 使用任何简单的遍历算法 - 例如，DFS(路径查找算法在这里看起来有点矫枉过正 - 他们需要最终点)

关于递归 - 你需要标记看到的单元格以避免重新检查。有 floodfill无递归且具有良好复杂性的算法。