Intro #
This is the first devlog for my upcoming Sci-Fi trading game - Trade Anchor.
It will cover something fundamental to the entire experience: the galaxy generator. This thing is the engine that creates the procedural universe you’ll be exploring, and creating it has been quite a journey.
Basics #
When I started, I knew this was going to be a heavy task for the CPU. So, right from the beginning, I built most of the generator using Jobs and Burst Compile, Unity’s tools for high-performance code. The first version worked pretty well for small test maps, but as soon as I tried to scale up, it got slower and slower.
So, what exactly is happening under the hood to create a galaxy? It’s a multi-step process:
-
Star Placement: First, we procedurally generate positions for all the stars. The goal is to keep them from being too clumped together, but also not so perfectly spaced that it feels unnatural.
-
Star Systems: For each star, we generate a star type and a planetary system. This is also where we lay the groundwork for the galaxy’s economy, determining what resources and populations each planet has.
-
Empire Start Points: Next, we find starting positions for all the alien empires, making sure they’re a respectful distance from each other.
-
Empire Expansion: This is where things get interesting. The generator simulates alien empires expanding from their starting systems into nearby habitable stars. It does this over and over, anywhere from one to three hundred rounds of expansion, depending on the galaxy size. Each alien race has its own unique expansion rate, adding a layer of complexity.
-
Trade Routes: Finally, we create the essential trade routes between star systems. This is based on proximity, of course, but also economic factors like resource availability.
Now, all those connections are a mess, so the generator has to clean them up. This is another multi-step cleanup process:
- We get rid of connections that cross over each other.
- We check if a route from star A to B passes close to star C and, if so, we split it into two, making A-C and C-B.
- We upgrade or downgrade trade route types based on the connections around them.
- And we fill in any gaps between nearby systems that were missed.
As you can imagine, that is a lot of work.
Performance #
Unsurprisingly, my first pass at this, while fine for a test map of 400x300 light years with a few hundred stars, took literal minutes once I tried to expand to something like 500x500. Remember, everything grows quadratically. A 400x300 map is 120,000 square light years, but a 500x500 map is 250,000—more than double! Going to 1000x1000 would quadruple that again to a million square light years. The number of stars and connections explodes, and the calculations along with them.
For a map over 500x500, you’re dealing with more than a thousand stars. Let’s look at the expansion process again with that in mind: If we have 10 alien factions, in the first round, each needs to check for nearby stars to expand to. To find those neighbors, it needs to check the distance to all 1,000+ other stars. That’s 10,000 distance calculations. In the next round, they’ve expanded, so maybe it’s 30 systems to check, leading to 30,000 calculations. By round 10, we’re at several million. You can see how this quickly spirals out of control.
Yeah, it was taking five minutes or more.
So, the obvious point to optimize was reducing those distance calculations. The classic solution? A Quadtree. Think of it like this: the galaxy map is repeatedly divided into four smaller and smaller sections, a process that continues until each section, or “quad,” only contains a few stars. This data structure lets me query for nearby stars by only checking the same quad and its neighbors. Instead of a thousand distance calculations, I’m now doing about twenty.
I also added a second optimization: I realized that stars deep within a faction’s territory had already checked all their neighbors multiple times. They had nowhere left to expand. So, I implemented a system to limit how many times a star system tries to expand, saving a huge number of redundant checks.
Together, these two were a game-changer. The time to generate a 500x500 galaxy with over a thousand stars, all their planets, the factions, the economy, and the trade routes dropped from minutes to a jaw-dropping 3 seconds.
Of course, the next logical step was to see how far I could push it.
I tried a 1000x1000 galaxy. That’s a million square light years with 4,500 stars, 2,500 of them inhabited, and almost 4,000 trade routes. The result? 8 seconds. Wow!
A 2000x2000 galaxy? 4 million square light years. Over 16,000 stars, over 10,000 inhabited, 15,700 connections… 63 seconds. Okay, we’re pushing the limits, but still completely playable.
A quick note on those numbers: you’ll notice not all stars get inhabited. The way the expansion works, some systems—like those with only a few low-resource planets, brown dwarves, or black holes—simply aren’t worth the effort for the factions to colonize. They’ll mostly stay uninhabited, unless they happen to be a strategic point for a space station.
I did try a 3000x3000 map, which is a massive 9 million square light years and 40,000 stars. It crashed. I was expecting it, but this time I think I hit a hard memory limit—a single temporary data structure needed over 2GB of memory. So, I called it a day and set the new galaxy size limit to 2000x2000. Frankly, I’m happy with that.
15,000 or so stars is far more than you’re likely to visit in a single playthrough. We don’t need No Man’s Sky numbers. The genre-defining ancestor of all trading games, the original Elite from 1985, had only 256 stars in each of its 8 galaxies.
So yeah, I’m happy.
That’s the state of the galaxy generator right now. The video linked below includes a few animations of some of the galaxies it has created.
Continued in devlog 2 - Stars and Planets.