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

Question

我正在 Codigniter 和 JQuery 中编写一个类似风险的游戏。我想出了一种方法来创建随机生成的地图，方法是制作完整的图块布局，然后删除随机的图块。然而，这有时会产生我所说的岛屿。

在危险中，你只能攻击一格。因此，如果一名玩家碰巧拥有一座属于自己的岛屿，他们将永远无法失去。

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

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

每个缺失的点也被识别为“水”。

我不允许使用图像标签： https://i.sstatic.net/DgI7c.gif

Answer 1

这个问题有一个标准名称，但在我的脑海中，以下可能会起作用：

• 随机选择任何图块，为
• 为其
• 它的邻居着色，
• 邻居的邻居着色
• ，为邻居的邻居着色，等等。

当你完成后（即当所有邻居都着色时），循环遍历所有图块的列表以查看是否有任何仍然/未着色的（如果是这样，它们是一个岛屿）。

Answer 2

你如何进行随机生成？或许这个时候最好的办法就是解决。当你生成地图时，如果你发现你刚刚创建的地图无法到达，你可以通过添加适当的元素来解决。

不过我们需要知道你是如何进行这一代的。

Answer 3

这是从随机图块开始的基本深度优先遍历，用类似 python 的语言进行伪编码：

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

Answer 4

这有望提供另一种解决方案。我使用术语“断开连接的组件”而不是“岛屿”，因为它只影响所有图块是否可以从所有其他组件到达（如果存在断开连接的组件，那么如果玩家自己的领土都在一个组件中，则玩家无法通过征服获胜） 。

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

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

Answer 5

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

将六角网格视为图像（它是某种图像）

值（x，y）=此（x，y）周围所有图块的平均值

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

留给学生的练习是在结果数据集上运行边缘检测内核以填充海滩图块。