4

I am generating a dungeon layout for a video game. I have created the rooms, spaced them out using seperation steering, and created a fully connected weighted, undirected graph of the rooms. Then I calculated a MST using Prim's Algorithm, all using GML (GameMaker Language). I miss Python.

My intention is to add additional edges to reintroduce loops, so a player does not have to always return along a path, and to make layouts more interesting. The problem is, these edges cannot cross, and I would prefer not to have to move the points around. I had been given a recommendation to use Delaunay Triangulation, but if I am honest this is completely over my head, and may not be a viable solution in GML. I am asking for any suggestions on algorithms that I could use to identify edges that I could add that do not intersect previously created edges.

I have included an image of the MST (the lines connect to the corners of the red markers, even if the image shows they stop short)

The image

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Timothy Mitcheson
  • 41
  • 2
  • Is this MST rooted? (Is there a node where you can say this is the beginning)? – Yonlif May 25 '20 at 06:52
  • @Yonlif Yes, the root node is always the node closest to the centre (of the circle surrounding all nodes) – Timothy Mitcheson May 25 '20 at 10:04
  • 1
    Cool. How about adding 2 metadata number into the nodes - First the distance from the center. Second for each layer (with equal distance from the center) index them. Than allow passages randomly between only nodes with the same distance from the center and consecutive indexes. You can choose how much but in this way you can promise there will be no intersections. – Yonlif May 25 '20 at 10:23

1 Answers1

0

If I'm understanding your question correctly, we're looking at more of a geometry problem than a graph theory problem. You have existing points and line segments with concrete locations in 2d space, and you want to add new line segments that will not intersect existing line segments.

For checking whether you can connect two nodes, node1 and node2, you can iterate through all existing edges and see whether the line segment node1---node2 would intersect the line segment edge.endpoint1 --- edge.endpoint2. The key function that checks whether two line segments intersect can be implemented with any of the solutions found here: How can I check if two segments intersect?.

That would take O(E) time and look something like

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()])

And you can get a list of valid edges to add in O(EV^2) with something like

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

Of course, you would need to recalculate the valid edges every time after adding a new edge.

Cjp
  • 43
  • 1
  • 6