我正在通过 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 提供奖励。
谢谢。
最佳答案
首先你必须做出严格的定义——什么区域被称为“包围”。也许可能的方法是 - 单元格没有通往外部 map 边缘的自由 channel 。
要以这种方式检查 - 使用任何简单的遍历算法 - 例如,DFS(路径查找算法在这里看起来有点矫枉过正 - 他们需要最终点)
关于递归 - 你需要标记看到的单元格以避免重新检查。有 floodfill无递归且具有良好复杂性的算法。
关于algorithm - 六边形 map 查找是否有一些网格被包围算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53878497/