Approach #1:

Start with all the nodes and no edges at all, then incrementally add nodes and edges to the graph until all nodes are connected.

Just start with an initial graph by one arbitrary edge between two nodes. The outer boundary of that graph are all nodes which currently do not belong to the graph, but have a connection in your Delauny triangulation to it by one edge. Pick one of the nodes of the boundary randomly, and one of the edges which can connect it to the graph, then add both to the current graph. Now repeat this procedure until your graph is complete.

If the graph is "not connected enough" for your purpose, you might add further edges afterwards randomly - for example, to reduce the number of dead ends.

Approach #2:

Start with no edges. Keep a list of all "connectivity components" (the nodes forming a connected subgraph). At the beginning, each component contains only one node.

Then, add edges randomly. When adding an edge between two nodes in different components, merge those two components - all the nodes are now connected. The number of components will be reduced by one in this case. When the total number of components reaches 1, the algorithm can stop.

Approach #3

Start with the full graph, cull edges randomly and then check for connectivity - but try to do this efficiently.

When you remove one edge between node A and B from a connected graph, you usually don't have to run a connectivity scan for the full graph. It is sufficient to test if there is still a route from A to B. For this, you may use something like the A* algorithm. As long as there is a route from A to B, you can expect the algorithm not having to visit all nodes and edges. When there is no such route, it will, however, have to visit all nodes inside the connectivity component where the starting point belongs to.

There is a loss function that this use case seeks to define.

Let "distance" measure the shortest path through the graph connecting a pair of nodes.

Let "distance ratio distribution" describe what that looks like across all node pairs, normalized by crow flies distance (L2 norm Euclidean distance). It is a measure of how inefficient the shortest graph path is, relative to the shortest flight of a crow. No node is more important than any other, since we choose them uniformly at random.

this leads to quite densely connected maps; there are convenient routes literally everywhere to everywhere.

Put another way, the distance ratio distribution is too compact. Its min, median, average, and max are all just slightly above unity. We have constructed a very small world planar graph.

I'd like some places to be "harder" to get to, ... I'd like less "connection density".

In a "large" Delaunay triangulation, essentially all nodes are interior nodes. Such nodes have degree >= 5. We will consider nodes of lesser degree to be peripheral nodes.

Controlling the degree of interior nodes impresses me as your central issue.

build a graph

Mark nodes in your Delaunay triangulation as "peripheral" or "interior".

Choose a max_degree threshold parameter of degree 3. The degree of most nodes will not exceed the threshold.

Initialize a new graph with no edges. Produce a set of connected components. We will stop adding edges when there's a single connected component. Keep track of number of nodes in each component.

Iterate over all peripheral nodes, assigning each one a single new edge. Merge connected components as you go.

Now loop until we have just one component. Choose a candidate (empty) edge at random, and examine its two nodes to see if we should add it. Perform several rejection tests, looping back if any test fails:

• both nodes are in same component? --> reject
• compare the sizes of each node's component
• • equal sizes, and both nodes have degree >= max_degree? --> reject
• • node in smaller component has degree >= max_degree? --> reject

The idea is there will be one growing giant "rich get richer" component that peripheral components will need to attach to. So as an escape valve, a few of its nodes may need a slightly elevated degree. We might limit them to max_degree + 1. Also, using probabilistic comparisons, against max_degree + random, would offer a further tuning knob.

Having connected all nodes in that way, you can now compute the distance ratio distribution to see if you're happy with it, choosing to start over if not.

Pick a geographically central node. Then you can compute average distance to peripheral nodes. You can also compute standard measures like graph diameter. Both of these will matter to your players if they have resource constraints like a fixed-size vehicle gas tank.