algorithm - 在不移动点的情况下向最小生成树添加循环？

Question

我正在为视频游戏生成地牢布局。我创建了房间，使用分离转向将它们隔开，并创建了房间的完全连接的加权无向图。然后我使用 Prim 算法计算了 MST，全部使用 GML(GameMaker 语言)。我想念 Python。

我的目的是添加额外的边以重新引入循环，因此玩家不必总是沿着路径返回，并使布局更有趣。问题是，这些边缘不能交叉，我宁愿不必移动这些点。有人建议我使用 Delaunay Triangulation，但老实说，这完全超出了我的想象，并且可能不是 GML 中的可行解决方案。我正在寻求关于算法的任何建议，我可以使用这些算法来识别我可以添加的不与先前创建的边相交的边。

我已经包含了 MST 的图像(线条连接到红色标记的角落，即使图像显示它们停止了)

Answer 1

如果我正确理解了您的问题，那么我们更多地关注的是几何问题而不是图论问题。您在二维空间中有具有具体位置的现有点和线段，并且您想要添加不会与现有线段相交的新线段。
为了检查是否可以连接两个节点，node1 和 node2，您可以遍历所有现有边并查看线段 node1---node2 将与线段相交 edge.endpoint1 --- edge.endpoint2 .检查两条线段是否相交的关键函数可以使用此处找到的任何解决方案来实现:How can I check if two segments intersect? .
这需要 O(E) 时间，看起来像

def canAddEdge(node1, node2):
    canAdd = True
    for edge in graph:
        canAdd = canAdd and not doesIntersect([node1.location(),
          node2.location(), edge.endpoint1.location(), edge.endpoint2.location()])
      

你可以得到一个有效边的列表，用类似的东西添加到 O(EV^2) 中

def getListOfValidEdges(graph):
    validEdges = []
    for index,firstEndpointNode in enumerate(graph.nodes()):
        for secondEndpointNode in graph.nodes()[index:]:
            if (canAddEdge(firstEndpointNode, secondEndpointNode)):
                validEdges.append([firstEndpointNode, secondEndpointNode])
    return validEdges

当然，每次添加新边后，您都需要重新计算有效边。