4

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

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

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

图片

4

1 回答 1

0

如果我正确理解了您的问题，那么我们正在研究的更多是几何问题而不是图论问题。您在 2d 空间中有具有具体位置的现有点和线段，并且您想要添加不会与现有线段相交的新线段。

为了检查是否可以连接两个节点 node1 和 node2，您可以遍历所有现有边并查看线段node1---node2是否与线段edge.endpoint1 --- edge.endpoint2 相交。检查两条线段是否相交的关键功能可以使用此处找到的任何解决方案来实现：如何检查两条线段是否相交？.

这将花费 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

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

于 2020-11-12T20:27:00.057 回答