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.