Let there be light

Every project needs a good “Hello World” to start off, so let’s dive right into it. First, we boot up our copy of Unity. The first task on our list to accomplish is to create a galaxy to explore. Simple enough to start!

There we go! An elliptical galaxy by randomly picking points in a circle. However, some of the stars are way too close together, they’ll cause problems later. So, we have to come up with a way to make sure stars aren’t placed that closely.

By using a physics collider & restraining float, I was able to check if any stars already exist in the area we’re attempting to place a star. Here, I ran into two problems. First, the Unity Editor just crashed on me, and it dawned that without an exit condition, eventually we’ll get stuck attempting to place stars forever. Then, I noticed that stars were still being placed within the physics colliders, as you can see in the above image. No more than one star should exist in any particular sphere.

I found this was a quirk related to the fact that this generation of objects was being done on one frame, the physics system wasn’t detecting the new stars correctly. Manually syncing transforms immediately fixed this second issue, leaving a elliptical galaxy with nice separation between stars!

But a grey background looks pretty boring, as do the white stars. Looks a lot better with randomly generated colors on a black background! Lets also allow stars to get a little closer for our photo op.

Halfway to anywhere…

Well, now I have a functional galaxy, filled with stars! Now, I need a way to make connections between the stars which would form the basis of our hyperlane travel systems, I knew there had to be a better way to do it, but I started off with my favorite friends, spherical physics colliders!

First, I limited each star’s maximum connections to 4, preferring closer neighbors (found with blue sphere) to far ones (found with red). By tweaking the radius of each search, I was able to get radically different connection appearances.

It kinda worked. Most of the stars are connected. That’s something. I took a few days off at this point to learn about how to connect nodes together.

At this point, I learned about spanning trees, specifically Prim’s Algorithm - just what I needed! Although, I wasn’t able to get it working for a bit. Turns out I was too restrictive with what stars were considered options to be neighbors. A quick fix later, and they’re definitely connected!

At this point, I re-implemented the maximum connections, resulting in a nice graph! However, it wasn’t without issue, as sometimes there would be islands of stars with acceptable numbers of connections, but not connected to the main graph! Oh no! I decided on a brute force approach to fix this problem. Since I need pathfinding anyway, I implemented some A* for this graph, attempting to reach every star from the first star we create. In theory, as long as we can reach every star, while starting from a consistent point, we can be sure that every star is connected to the graph. If a star can’t be connected, it finds its closest neighbor that can be reached, then tries again. Sure enough, that connected the island!

Next plans

Now that there’s a galaxy of stars, let’s put stuff in it! These stars seem lonley, so let’s give them some planets to keep them company.

But, that will have to wait for another time.