title: Adding cycles to a Minimum Spanning Tree without moving the points?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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)</p>
  
  <p><img src="https://i.stack.imgur.com/wwNjc.png" alt="The image"></p>