4
\$\begingroup\$

I am at the beginning of the creation of a space 4x and first of all i need to generate a galaxy of stars linked by connecting lines that changes in each new game, I'll add a few pictures to show what i want

endless space

enter image description here

enter image description here

enter image description here

enter image description here

So how can i have a simple 2d map with connected points like these images ? I thought to program each line with a random length and a random angle or program polygons by polygons but it is still unclear.

\$\endgroup\$
5
  • 4
    \$\begingroup\$ Try searching for voronoi diagram. It may get you thinking in the right direction. \$\endgroup\$
    – GaleRazorwind
    Commented Sep 11, 2020 at 3:01
  • 1
    \$\begingroup\$ @GaleRazorwind Yes that was kind of what I was looking for, thank you ! \$\endgroup\$
    – venom007
    Commented Sep 11, 2020 at 3:11
  • 1
    \$\begingroup\$ @GaleRazorwind, would you care to write that up as an answer? \$\endgroup\$
    – DMGregory ♦
    Commented Sep 11, 2020 at 3:29
  • \$\begingroup\$ The naive solution would be to just place stars randomly, measure the distances between all stars and connect them when it's short enough. But that might result in some stars being too close together while others might be orphans, so some post-processing might be in order. \$\endgroup\$
    – Philipp
    Commented Sep 11, 2020 at 8:59
  • \$\begingroup\$ @Philipp As you can see, sometimes there are large empty spaces, it is only possible because several stars are only connected by a single segment. How i can implement this rule ? \$\endgroup\$
    – venom007
    Commented Sep 11, 2020 at 9:55

1 Answer 1

Reset to default
4
\$\begingroup\$

You can scatter points using...

  • uniform random coordinates (prone to uneven clusters and gaps)

  • or a shaken or jittered grid, where you start with a regular lattice of points, then add a small randomized offset to each (prevents big gaps/clusters, but can reveal its structure)

  • or a Poisson distribution (some clever algorithms to generate this can be found here)

Red Blob Games has a page that lets you play with different jittered grid vs Poisson distributions to get a sense of the trade-offs in these algorithms.

If you find your result is too uneven, you can form the Voronoi diagram of your points — generating the convex polygon that's closer to each point than any other — and move each of your points toward the centroid of its polygon. That tends to average out the spacing a little, while keeping things organic.

If you find your result is too even, you can randomly delete some points to introduce gaps, or randomly insert a few with weaker spacing criteria to create clusters.

You can also vary the spacing of your grid or Poisson samples based on an underlying density map that you generate first using noise.

Now for the connections:

To ensure that all stars are connected to the network, so you can't have an island inaccessible from the rest of the galaxy, you can use a spanning tree algorithm.

A minimum spanning tree will give you the skeleton of a constellation that touches all the stars, using the shortest links it can. Then we elaborate on that base, without violating the connectedness guarantee.

  • If you use Prim's algorithm (which adds links one by one), you can add a few extra links after the algorithm finishes to create cycles and alternative pathways.

  • If you use Kruskal's algorithm (which starts with a dense graph and removes links one by one), you can stop the algorithm early before it's weeded out more than x% of the redundant links, or give it a probability of keeping redundant links as it goes.

\$\endgroup\$
6
  • \$\begingroup\$ With your methods I could form star paths forming a dead end like in the last picture ? And thank you for the reply ! \$\endgroup\$
    – venom007
    Commented Sep 11, 2020 at 18:08
  • \$\begingroup\$ Yes, dead ends can occur with these methods, if you want them. (A minimum spanning tree has at least 2 dead ends, if it's a Hamiltonian path, and more dead ends in the general case) If you don't want dead ends, you can modify Kruskal's algorithm to never remove the 2nd last edge touching a star, or modify Prim's algorithm to follow-up and add the next shortest extra edge incident to each dead-end star. This would give you triangles or larger loops at the ends of each connected path, rather than single dead-end stars. \$\endgroup\$
    – DMGregory ♦
    Commented Sep 11, 2020 at 18:14
  • 1
    \$\begingroup\$ Step 1: implement the solution described above. Step 2: if you don't get the results you want, edit your question to show what you tried, what the results were, and how you want them to be different. \$\endgroup\$
    – DMGregory ♦
    Commented Sep 11, 2020 at 20:15
  • 3
    \$\begingroup\$ A minor variant of the jittered grid: if you want the stars in the center of the galaxy to be more dense, like in the first example in the question, you can start with a jittered grid, then take the distance to the center, raise it to a power like 1.5, then adjust the point to the new distance with the same angle. This will make the stars denser in the center. Demo here \$\endgroup\$
    – amitp
    Commented Sep 11, 2020 at 20:15
  • 1
    \$\begingroup\$ I think the examples in that page would be well-worth the added visibility (and vote/accept-ability) of being shared in an Answer, rather than just a comment, @amitp. 🌌😀✨ \$\endgroup\$
    – DMGregory ♦
    Commented Sep 11, 2020 at 20:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .