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

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?

• how are the nodes scattered across galaxy? I mean may I assume that for every point (X, Y) in galaxy there is a node? or at least for most of them or not? Oct 10, 2011 at 17:31
• Not all coordinates will have a node. About 40% I would say. Oct 10, 2011 at 17:45

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.

• +1 since it's a very good answer but I just don't like this kind of generation so I'll be thinking about a better algorithm in next few days! Oct 10, 2011 at 18:04
• Yeah there is no 'right' answer to this, I'm interested to see what others come up with. Oct 10, 2011 at 18:44
• Offtopic, but I was going to link to my answer too! :p Oct 10, 2011 at 19:05
• This way I get points for it, ha! Oct 10, 2011 at 19:06

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.

• Delaunay triangulation is a good idea, but it doesn't create random edges. You could remove edges randomly from the edges created by the Delaunay triangulation, but then you'll risk getting separate graphs again... Oct 11, 2011 at 10:06
• @Bummzack "It doesn't create random edges". Ever heard of graph minors? Once you have the more difficult constraints solved using Delaunay, it is trivial to perform additions or removals on that graph as you like. Oct 11, 2011 at 12:18
• @Bummzack, I just updated it again -- thanks for the feedback. Oct 11, 2011 at 12:38