如何在随机生成的六角形地图中查找岛屿？

我正在为Codigniter和JQuery中的游戏编程风险。我想出了一种方法来创建随机生成的地图，方法是对瓦片进行完整布局然后删除随机地图。但是，这有时会产生我称之为岛屿的情况。如何在随机生成的六角形地图中查找岛屿？

存在风险，您只能攻击一个空间。所以如果一个玩家碰巧拥有一个他们自己的小岛，他们永远不会失去活力。

我试图找到一种方法，我可以在游戏开始查看它是否有岛屿之前检查地图。

我已经想出了一个函数来找出每个空间有多少个相邻的空间，但我不知道如何实现它以找到岛屿。

每个失踪点也被确定为“水”。

我不能使用图片代码： http://imgur.com/xwWzC.gif

来源

2009-08-17 J3nnings

有一个标准名称为这个问题，但我的头顶部以下可能的工作：

随机
颜色选择任何瓷砖它
颜色邻国
颜色的邻居的邻居
将其邻居的邻居的邻居等颜色

完成后（即当所有的邻居都被着色时），遍历所有瓷砖的列表以查看是否有任何静止/留下未着色（如果是的话，他们是一个岛）。

来源

2009-08-17 00:07:45 ChrisW

这肯定会奏效，非常感谢。 – J3nnings 2009-08-17 00:12:15

[笑话：http：//xkcd.com/221/展示了如何随机选择一个瓷砖] – ChrisW 2009-08-17 00:21:49

这将起作用，但描述并不能完全解释问题，特别是，“如果是这样，他们是一个岛”。这可能是最初选择的瓷砖是岛的一部分，无色瓷砖是“大陆”的一部分。如果你在找到一个岛屿时重新生成整个地图，这是可以的，但如果你打算只重建受影响的地区，这可能是一个问题。 – Imagist 2009-08-17 00:41:54

你怎么做随机生成？可能最好的方法是在这个时候解决它。当你生成地图时，如果你注意到你刚创建的地图是不可能的，你可以通过添加适当的元素来解决它。

尽管我们需要知道你是如何做这一代的。

来源

2009-08-17 00:05:07

+1。每次选择一个要删除的图块时，检查是否有从每个相邻图块到相邻图块的路径。 – 2009-08-17 12:05:00

我遇到了与OP类似的问题，并且我同意你修复代码更好。 – Dolphin 2009-08-20 20:19:42

在您的数据集上运行模糊的内核。

治疗六角形格子作为图像（它是，排序的）

值（X，Y）=所有瓦片的平均解决此（X，Y）

这将略微侵蚀海滩，并消除岛屿。

作为练习，学生可以在结果数据集上运行边缘检测内核来填充沙滩图块。

来源

2009-08-17 00:29:46

这是你的基本的深度优先遍历开始随机瓷砖，伪编码在蟒蛇般的语言：

visited = set() 
queue = Queue() 
r = random tile 
queue.add(r) 
while not queue.empty(): 
    current = queue.pop() 
    visited.add(current) 
    for neighbor in current.neighbors(): 
     if neighbor not in visited: 
      queue.add(neighbor) 
if visited == set(all tiles): 
    print "No islands" 
else: 
    print "Island starting at ", r

来源

2009-08-17 04:01:26 hughdbrown

这有望提供另一种解决方案。我使用的术语是“断开的组件”，而不是“孤岛”，因为它只关系到所有瓷砖是否可以从所有其他瓷砖中获得（如果存在不连贯的组件，那么如果他的属地都在一个组件中，则玩家无法通过征服获胜）。

迭代所有'土地'瓦片（容易做到）并为每个瓦片在图形中生成一个节点。
对于每个顶点，将其与一个无向边连接到表示其邻居贴图的顶点（最多6个）。
选取任何顶点并从中运行深度优先搜索（或面包优先）。
如果DFS找到的顶点集合等于所有顶点的集合，则不存在断开的组件，否则存在断开的组件（岛）。

这应该（我认为）在时间O（n）运行，其中n是地块的数量。

来源

2009-08-17 19:01:26 tw39124

最差情况下的时间可能会在O（n log6 n）时间内运行。 – jmucchiello 2009-08-17 19:15:21

如何在随机生成的六角形地图中查找岛屿？

回答

相关问题