How can I efficiently load huge volumes of star systems?

Question

I am working on a space exploration and combat game, and I can create galaxies, nebulas, solar systems, and load and unload them procedurally as needed. Meaning the stars that the player can see are exactly where they are. I have a coordinate system set up with meter-precision, meaning it's sufficient to map quite several galaxies, but also tiny missiles.

For now, I created a galaxy with 10.000.000 solar systems, and my SQLite database reached 5gb. It takes ~30 minutes to generate it, and I notice a slow-down as the size of the database increases in loading times. I did a lot of optimization, and while everything is running fine and well now, I seek to reach 200-300m solar systems if possible. The database would be stored locally on the user's drive, rather than downloaded from a server. I use a GlobalX/Y/Z (int64) and LocalX/Y/Z (double) for coordinates, and only the GlobalX/Y/Z is used to find large objects like stars and planets (I also use multiple chunk systems).

Elite Dangerous manages to store the data of 400 billion solar systems and has no issues with loading times, somehow. How can they display many stars in the background? How do they manage to store a lot more data than I already do?

For now, my data is quite minimalistic and comparatively minuscule in number, but they must have quite a lot of data for each stellar object even. What technical "tricks" can I employ to solve this problem in my game?

Answer 1

The trick Elite likely uses is that they don't pre-generate the whole galaxy and store it in a database. They likely generate most of the galaxy at runtime when it is needed.

I would do this using a pseudorandom but deterministic algorithm which can generate the properties of every object in the galaxy at runtime just from its position.

So when a player zooms into a section of the galaxy, then the galaxy chunk generation algorithm is run, which takes the chunk coordinates as input and outputs a list of stars with position, color and size. Same input always results in the same output, so when another player zooms into the same chunk later, they get the same results. You might have different algorithms for different zoom levels which each take the output of the previous algorithm into account and add more detail to it. So the algorithm on the lowest zoom factor only generates the largest stars (so you can quickly generate a view which shows the whole galaxy at once), and the closer the player zooms into any part of the galaxy, the more additional small stars get generated in that area.

Then, when the player clicks on any of these stars to zoom into its star system, the star system generation algorithm is run. Its input are color, size and galactic position of the star. Its output is a list of planets with their types, sizes and orbital parameters. It too is a deterministic algorithm so it always generates the same planets for the same star.

And then you can do the same thing with planet surfaces, cities on the planet surfaces, houses in those cities and rooms in those houses. So you end up with a galaxy with a level of detail which would take an exorbitant amount of data to store all at once. But you don't need to store it all, because any of that data can be re-calculated on demand.

A really neat tool for procedural generation algorithms like that are noise pattern algorithms like Simplex Noise or Worley Noise. You can sample them at arbitrary locations to get reproducible results. Another are standard pseudorandom number generators which can be initialized with a seed value and then always generate the same sequence of numbers for the same seed value.

All you really need to store in a database is data which can not actually be re-generated on demand:

• Parts of the galaxy which you want to design by hand
• Changes to the galaxy which are the result of player actions

First you check if any such datasets exist in your database for the requested data, and when they don't, you generate the data using the algorithms.

__

Now you just need to come up with algorithms which generate interesting and varied results and then with game mechanics which provide an engaging and interesting game experience which benefits from all that content variety. I am looking forward to playing what you will come up with.

Answer 2

In addition to the points that have been made about not actually generating all the data there's another factor: You can't actually draw 10,000,000 stars. Nobody has a display that can handle it. Therefore, there's no need to have 10,000,000 stars loaded.

Select X, Y, Brightness, Color, ID from StarTable Where X > CurrentX - 200ly And X < CurrentX + 200ly And Y > CurrentY - 200ly And Y < CurrentY + 200ly.

Select X, Y, Brightness, Color, ID from BrightStarTable Where X > CurrentX - 2000ly And X < CurrentX + 2000ly And Y > CurrentY - 2000ly And Y < CurrentY + 2000ly.

That will be a tiny fraction of your total stars, but it is sufficient to draw anything you can see out the window of your starship. I would store all the details on the stars in a separate table accessed by the StarID as you only need those details when examining a particular star.

You can cut the loaded data down even more by having a DimStarTable with an even shorter query range. Most stars will be in this table.

Another option also comes to mind: Define a new variable: Sector. Sector = (int)(x/100ly) + (int)(y/100ly) * 10000. You load the sector you are in and the 8 adjoining sectors. The select would run faster. (Likewise, the bright star table would have 1000ly sectors.)

Answer 3

Philipp already gave a great answer, but I'll address your question about how Elite Dangerous operates their database.

Elite Dangerous manages to store the data of 400 billion solar systems and has no issues with loading times, somehow. How can they display many stars in the background? How do they manage to store a lot more data than I already do?

1. Elite Dangerous stores the star map data that isn't procedurally generated on a server, not locally. They presumably have one or more very powerful servers, optimized for big data, with the database always loaded and running. When the player scrolls around the map or visits a new star system, the game client sends a request to the server, the server queries relevant data from the database and sends it back to the game client. Because the database is on a server, it could potentially be many terabytes in size without causing any issues for the players. They probably have very big and expensive servers developed over years by backend specialists, so this approach is unlikely to be feasible for an indie team.

2. Elite Dangerous absolutely has loading times, they just cleverly mask it with in-game mechanics. This is educated guesswork, but based on my play experience I think it works like this:

   1. When you activate the hyperdrive, there's a progress bar while the hyperdrive warms up. I think this is the stage when the game client sends the request for data for the system you're about to jump to. Occasionally, this takes much longer than normal for no explicable reason - probably because the server was slow to respond to the query.

   2. During the actual hyperspace jump, the game is loading/procedurally generating the next star system, including the background skybox, based on the data it received from the server. The animation you see of your ship hurtling through hyperspace is just a very fancy loading screen.

Answer 4

If you have a deterministic algorithm that uses a seed, like how PRNG's work, you can store almost nothing and generate the star's positions on the fly, only keeping those that you currently need. Think how demoscene demos work.