java - 摆脱网格迷宫中断开的矩形

Question

这并不是真正的迷宫，但想法很相似。

我有这个:

问题出在我用红圈圈出的地方。我需要一种方法来去掉不属于拼图其余部分的矩形。

我创建了一个适用于正方形的简单算法:

其工作方式是二维数组的每个元素代表一个顶点(图形节点)。每个图节点都有一个与其连接的顶点列表。该图是通过从每个顶点到它们的每个连接绘制线条来绘制的。

private void removeDisconnectedSquare(int x, int y)
{
    GraphNode topLeft = getNodeAt(x, y);
    GraphNode topRight = getNodeAt(x + 1, y);
    GraphNode bottomLeft = getNodeAt(x, y + 1);
    GraphNode bottomRight = getNodeAt(x + 1, y + 1);

    if(topLeft != null &&
       topRight != null &&
       bottomLeft != null &&
       bottomRight != null &&
       !hasNodeToLeft(topLeft) && hasNodeToRight(topLeft) && 
       !hasNodeAbove(topLeft) && hasNodeBelow(topLeft) &&
       hasNodeToLeft(topRight) && !hasNodeToRight(topRight) && 
       !hasNodeAbove(topRight) && hasNodeBelow(topRight) &&
       !hasNodeToLeft(bottomLeft) && hasNodeToRight(bottomLeft) && 
       hasNodeAbove(bottomLeft) && !hasNodeBelow(bottomLeft) &&
       hasNodeToLeft(bottomRight) && !hasNodeToRight(bottomRight) && 
       hasNodeAbove(bottomRight) && !hasNodeBelow(bottomRight))
    {
        removeVertex(x, y);
        removeVertex(x + 1, y);
        removeVertex(x,  y + 1);
        removeVertex(x + 1, y + 1);
    }
}

是否有一种算法或方法可以检测顶点路径是否不是大连通顶点路径的一部分？有时这会产生一条小路径。

谢谢

Answer 1

我建议找到一个好的图形库。然后，将每个方 block 表示为一个节点，如果方 block 之间有直接路径，则方 block 之间有一条边。最后从“入口节点”开始使用“连接节点”算法(由图形库提供)。最后，您可以循环遍历所有未由连接算法标记的节点并对其进行适当的处​​理。

例如，如果您使用 C++，则可以使用 Boost Graph Library Connected Components algorithm 。其他好的图形库应该有类似的支持。

您还可以推出您自己的此类算法版本；例如，将未标记的邻居节点压入堆栈，标记访问过的节点，然后从堆栈中弹出一个节点，直到完成。但是，拥有一个好的图形库对于解决您在此类项目中可能遇到的其他问题很有用，并且 IMO 比您自己构建更好。

还值得注意的是，您可能会更改迷宫生成算法以始终生成连通图，从而无需在事后清理断开连接的组件。