Idea: generate a galaxy full of star systems, with connections between them. Stars should be closer together, and have more connections, near the center of the galaxy.
The stars are generated uniformly and then stretched by setting the radius (0.0–1.0) to radius{{stretch}}. This pushes points close to the center closer together and points near the rim farther apart. Idea from Rob Shillingsburg. I haven't yet tried putting in Poisson Disc blue noise points but this jittered grid seemed good enough for a demo (and so easy to code).
Algorithm 0: graph construction
The main algorithm is Delaunay Triangulation. It will connect all the stars together with non-overlapping edges.
I'm using this graph for all the other algorithms. Graph algorithms are well-known and fairly easy to work with, so having a graph here helps a lot to be able to reuse those algorithms.
Algorithm 1: random walk of nodes
To ensure that everything is connected to the center of the galaxy, I run a random walk from the center node to visit every other node. This builds a tree, and prevents disconnected "islands" of stars that can't be reached from the galactic center. I call these the required connections.
Algorithm 2: random edges
The random walk connections alone are a bit too sparse. I add optional connections when distance_from_center < random(). That way near the center they're almost always kept and near the rim they're almost never kept. It makes the center stars feel more connected and the rim stars feel more remote. These are the edges I added; you can see that there are a lot more near the center:
When combined with the random walk, I get:
Unfortunately the random walk sometimes produces two edges that have a narrow angle between them. I attempted to fix these by removing leaf nodes and reattaching them to the closest non-leaf neighbor. This improves most of these bad edges but still leaves some, and introduces a few more.
There are also some issues around the rim of the galaxy. I have some ideas of how to solve them but I haven't implemented them yet. Instead I tried some other algorithms.
Algorithm 3: shortest edges
Pick the shortest edge of each triangle. Then connect up the islands into the full galaxy.
TODO: connect the islands up into the full galaxy.
I abandoned this approach when I realized minimum spanning tree would be simpler.
Algorithm 4: minimum spanning tree
Algorithm 1 used a random walk to guarantee connectivity, but the chosen edges were poor. Algorithm 2 picked good edges, but didn't guarantee connectivity. The minimum spanning tree gives us both. This was my first idea when considering this problem, but I didn't know how to implement it, and I assumed it'd be pretty complicated. It turns out it's more complicated than random walk, but it's less complicated than the added steps to fix up the poor results.
Great! It doesn't guarantee avoiding narrow angles but it's pretty good. (TO DO: there seems to be a bug in my algorithm where a few things near the galaxy rim don't get connected.) Now we need to add back the optional edges:
This has added back some narrow angles. TO DO: make the optional edge algorithm check for narrow angles.
Algorithm 5: non-random optional edges
Idea: instead of picking edges randomly to add back in, add edges based on how much they shorten the graph distance. With minimum spanning tree (and also with random walk) there are places near the galaxy rim where two nodes are very close together in space, but you would have to fly a long way to go between them. Edges that greatly shorten this distance would be more valuable to add.
Algorithm 6: identify key nodes
Articulation Points are graph nodes that separate two parts of the graph. All traffic between one side and the other side must travel through that point. We'd expect that these star systems would be mercantile hubs. I've never implemented the articulation point algorithm but it doesn't look too hard, and it looks like it's incredibly fast.