六边形地图查找是否包围了一些网格

Question

我正在通过Unity创建一个简单的数学游戏。确实不是关于统一的。

我从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      ]

我的目标是

检查一个或多个网格是否被另一种类型的网格包围。

定义

包围是指网格或连接的网格组，所有邻居都在它们的不同标志中。

例如，

[      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       ]

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

---

问题

我认为我没有意识到的更聪明的方法，我欢迎任何回答的善良/语言，甚至只是一个想法。可以肯定的

谢谢。

Answer 1

首先，您必须进行严格的定义 - 哪个区域称为"包围"。也许可能的方法是 - 单元格没有免费的方式进入外图边缘。

要以这种方式检查 - 使用任何简单的遍历算法 - 例如，dfs（路径查找算法在这里看起来过大 - 需要最终点）

关于递归 - 您需要标记看到的细胞以避免重新检查。洪水算法没有递归且复杂性良好。

Answer 2

您正在向后进行此操作。您的编码逻辑看起来不错，但逆转了逻辑。

对于每个生存的每个1，请检查其他1个。如果您通过第一个1（到）的1（从）的任何路径返回，那么您已经找到了一个封闭的循环。找到返回路径从重新恢复到第一个1的方向，然后是环路的内部。然后，如果您对任何更深的循环不感兴趣，请标记所有循环中内部（1和0）的所有内容，从进一步的搜索中删除。完成搜索，然后完成搜索后，仅在完成搜索后，将循环内部的所有内部都标记为1（如果那是您想要的）。这样，如果您在循环旁边有循环，那么您将不会一遍又一遍地重新启动。

用于子循环：将所有1视为循环的潜在启动。如果您返回任何前一个1，请找到来自（返回路径）的方向，并考虑循环的内部。

完成所有操作后，您找到了循环，然后进行更改。不要担心循环的内部位置是否为零，因为0是一个有效的大小，只需在您决定时使循环的所有可能内部更改。

谢谢。

b lean