1

这不是一个真正的迷宫，但想法是相似的。

我有这个：

在此处输入图像描述

问题是我用红色圈起来的地方。我需要一种方法来摆脱不属于拼图其余部分的矩形。

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

其工作方式是 2D 数组的每个元素代表一个顶点（图形节点）。每个图节点都有一个与之相连的顶点列表。该图是通过从每个顶点到它们的每个连接绘制线来绘制的。

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);
    }
}

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

谢谢

4

1 回答 1

0

我建议找到一个好的图形库。然后，将每个正方形表示为一个节点，如果它们之间有直接路径，则在正方形之间有一条边。最后使用从“入口节点”开始的“连接节点”算法（由图形库提供）。最后，您可以遍历所有没有被连通性算法标记的节点并适当地处理它们。

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

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

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

于 2012-10-06T19:40:28.113 回答