What is a good method to randomly generate edges between graph nodes?

Question

I am doing a random map generator for a 4X space game.

Each node in the game is place at a random (x,y) coordinate on a 2d grid. A node can have one or more bi-directional edges to another node (representing wormholes). All nodes must have at least one wormhole, and all nodes must belong to the same graph.

Ideally, a wormhole should not exceed a maximum length and if possible, wormholes should not cross each other.

My naive implementation is to iterate through all the nodes and have the node link to the closest 3 nodes. However, I end up with numerous sub graphs. What's a good method to generate the edges for the nodes?

Answer 1

Here's a good answer to a similar question.

First make a connected graph, perhaps using a minimum spanning tree as in the link above. He suggests using random edge weights to make the "minimum" tree random. Then you can randomly add more edges so it isn't just the minimum tree. How exactly you add the random edges depends on what sort of graph you want.

---

In fact, if the problem is just in making sure the nodes all belong to the same graph, you could take your current method of random generation (or any other), and apply Prim's algorithm on top of it. If you wanted to make minimal changes to the graph just to be sure the subgraphs are all connected, you could set the edge cost to 0 for edges that are already there.

Answer 2

The major constraints of your problem are twofold: creating a 1-connected graph; and creating it with proximal connections. Philip's answer, while somewhat valuable, does not address all constraints of your problem

Ideally, a wormhole should not exceed a maximum length and if possible, wormholes should not cross each other.

When you naively connect points in a cloud, you run the risk (and a high one, at that) of these conditions not being fulfilled.

So you see, the problem isn't so much one of connectivity as one of proximity on those connections. It is trivial to connect every node in a graph to every other node, but connecting only to those that are closest while maintaining 1-connectedness of the overall graph is a bit more tricky.

This is what a Delaunay triangulation creates, in n dimensions. The first reason to use Delaunay triangulation is that it fulfills both of these implicitly. The second reason is that it is far easier to work backwards from such a graph (subtracting edges and vertices you don't want), than to try to create it in other ways.

1. Randomly create your full point cloud.
2. Delaunay-triangulate it.
3. Construct the graph (connection of points). In this, you can either generate the whole graph (every star) first, and then derive graph as minors representing your wormhole-connected regions, when performing step 4. Alternatively you can work the other way around, generating only the wormhole-connected regions first as supergraph nodes, and then in a second phase, generate individual stars within those regions' bounding volumes (for these I would derive the Delaunay triangulation's graph dual -- the Voronoi diagram in 3 dimensions) as subgraphs. Now you have proximally-connected star clusters, and all clusters are connected by rarer wormholes: your topology and topography make sense to the player.
4. Apply intelligent methods to shape the super- and subgraphs, depending on how you've chosen to treat it in step 3.

It's important to see that this is a hierarchical process. The first level deals with wormhole connectivity; the second deals with distances presumably traversable using a standard ship drive. You can apply Delaunay at one or both levels to satisfy your constraints.

Doing this purely topologically will leave you with wormholes that don't make sense, since they might connect one side of the galaxy to another, in spite of a high density of stars in beween (and perhaps even falling on the wormhole's direct route). Topology is not topography; the latter is a consideration over and above the former. You are concerned with proximity and thus topography.