1
$\begingroup$

I am tring to find the simplest method of generating a random minimum spanning tree.

My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a grid which all connect together in a random way.

One method I have come across is to generate random points on a grid and run a Randomized incremental Delaunay triangulation algorithm (Explained quite nicely here) on it with the weights of the nodes being determined by their distances from eachother. Couple this with Kruskal's algorithm and then I will have my minimum spanning tree.

I'm relatively new to this field of Maths and was having trouble creating the Delaunay algorithm (and even more trouble understanding some libraries out there) and thought perhaps there is a simpler method to get the same result.

One method that came to mind was to create a fully connected graph of random points (much simpler for me to do) and then run Kruskal's algorithm on that, However my intuition tells me that this would not be so efficient even though I am only talking about a maximum of 10 or 15 nodes for my intended use.

Are there any other methods I should consider to generate such a graph? I've come across the Prüfer sequence which seems incredibley simple, however with my current understanding of it I do not see how I can take into account the positions of the Rooms/Nodes on the grid or perhaps even chose where to place the nodes on the grid.

Improve this question
$\endgroup$
7
  • $\begingroup$ Questions related to a specific programming language are off-topic here. $\endgroup$
    – Yuval Filmus
    Dec 30, 2018 at 20:25
  • $\begingroup$ As Yuval mentioned, you might as well remove the reference to C++ as that raises a red flag to all experienced users here. Your question at this stage is, in fact, largely independent of the programming language. $\endgroup$
    – John L.
    Dec 30, 2018 at 20:30
  • $\begingroup$ Can you clarify that "$n$ amount of fixed sized rooms" are on the same plane? That is, are we talking about planar graph and Euclidean distance or Manhattan distance or some similar metric distance? $\endgroup$
    – John L.
    Dec 30, 2018 at 20:33
  • $\begingroup$ @Apass.Jack Ah my bad, I thought if someone knew of a relevant library I could dissect that it would be relevant $\endgroup$
    – Isabella
    Dec 30, 2018 at 20:34
  • $\begingroup$ @Apass.Jack The nodes will be on a grid, but I intended for the weights of the graphs to just be their Euclidean distances, after all the connections will just be there to say what to connect later with corridors etc in a grid space $\endgroup$
    – Isabella
    Dec 30, 2018 at 20:40

1 Answer 1

Reset to default
1
$\begingroup$

Since there are just about 10 random points, the following simplest algorithm is should be fast and easy enough for your need.

  1. Generate random points $p_i$, $0\le i\le9 $ in the grid, in whichever way you prefer.
  2. Compute all Euclidean distances between each pair of points. (In fact, I believe for your purpose, the Manhattan distance should be fine as well. What is nice about Manhattan distance is that it is much easier to code and compute. The MST generated will be roughly the same.)
  3. Compute the MST of the points with the distances between them.

There are many existing libraries that computing MST. You can just select any popular one that is convenient for you. I guarantee you that they will be fast enough for your need.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Since MST is determined by the sorted order of the distances, you do not have to compute the actual Euclidean distance even if you choose to use Euclidean distance. You can use the squares of Euclidean distances, which can be computed without taking square root. $\endgroup$
    – John L.
    Dec 31, 2018 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.