18
\$\begingroup\$

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?

\$\endgroup\$
14
  • 4
    \$\begingroup\$ reddit.com/r/EliteDangerous/comments/55u07s/… good comments in here like the galaxy is not made -- it is there in potential, based on the rules of the system. FD does not have a database of 400 billion stars. They likely only have a database of bodies discovered and scanned. The rest can be created as needed.. I haven't got any hard evidence to make this an answer yet, but procedurally generated as it is discovered seems quite likely. \$\endgroup\$ – lozzajp Feb 10 at 10:54
  • 4
    \$\begingroup\$ Elite Dangerous famously doesn't store the data. It's how the original Elite managed to fit 4096 star systems into 360 kilobytes of space. \$\endgroup\$ – Mark Feb 10 at 22:10
  • 3
    \$\begingroup\$ I'm with Philipp - don't use a database if you don't have to. If you're really determined to use one and its performance is the question here, then this quickly becomes a DB optimization question and not a GameDev one. You said you did a lot of optimization... what does that mean? What data are you storing in which tables? Can you break things out into smaller tables? You certainly don't need to store missiles in there with solar systems! What indexes do you have on your tables? Have you profiled your queries? Are you making lots of separate small queries when one large resultset would do? \$\endgroup\$ – A C Feb 11 at 1:37
  • 2
    \$\begingroup\$ @Battle I just meant that procedural generation is a good way to do this; that way you don't have to store anything (you just recompute it). Also, that way you get to skip the boring database optimization and focus on making your game ;-) \$\endgroup\$ – A C Feb 11 at 8:59
  • 2
    \$\begingroup\$ @Mark much less than 360kb - it ran on systems which only had 48k available RAM. \$\endgroup\$ – pjc50 Feb 11 at 9:57
32
\$\begingroup\$

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.

\$\endgroup\$
9
  • 4
    \$\begingroup\$ Now I want to implement a galaxy generator like that. But I must restrain myself. Starting your game project by making a procedural generation system when you didn't create the actual game yet is a bad idea. You won't yet know what content your game actually needs. And when you don't know that, then your procedural generation will end up creating plenty of content which doesn't actually do much to help the game mechanics to shine and instead just result in a bland and boring game experience. Elite:Dangerous suffered a lot from that. \$\endgroup\$ – Philipp Feb 10 at 15:18
  • 7
    \$\begingroup\$ No Man's Sky was infamous for overuse of procedurally generated content resulting in overly repetitive gameplay. \$\endgroup\$ – Darrel Hoffman Feb 10 at 21:21
  • 4
    \$\begingroup\$ According to this, the Frontier team started with the 160,000 known star systems and then uses a system they developed called Stellar Forge to generate the rest based on first principles of astrophysics theory. \$\endgroup\$ – Nathaniel Jones Feb 11 at 2:44
  • \$\begingroup\$ This is a great answer and very helpful. I am already in the process of learning how to apply Procedural Generation. I think it's indeed a better way to do all of this, and allows me to easily have multiple galaxies with way more solar systems. As of the monotony problem - I already have a possible solution for that. A mix of random factors making solar systems quasi-unique as they peak, and presets that set up a special constellation at baseline, like a resource rich planet dangerously close to a star, or a star emitting excessive amounts of lethal solar flares. \$\endgroup\$ – Battle Feb 11 at 8:10
  • 3
    \$\begingroup\$ Take a look at this video, it explains the concepts in Philipp answer in a very simple and very clear way: youtube.com/watch?v=ZZY9YE7rZJw \$\endgroup\$ – Davide Gualano Feb 11 at 14:20
2
\$\begingroup\$

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.)

\$\endgroup\$
2
  • 2
    \$\begingroup\$ The "Select" looks rather troublesome. I'd expect an octree instead. \$\endgroup\$ – MSalters Feb 12 at 8:32
  • \$\begingroup\$ @MSalters He said "database". Assuming there are indexes on X and Y that select should be fast. \$\endgroup\$ – Loren Pechtel Feb 12 at 21:02
1
\$\begingroup\$

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.

\$\endgroup\$
-6
\$\begingroup\$

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.

\$\endgroup\$
3
  • 11
    \$\begingroup\$ This seems to be the same point made in Philipp's existing answer, but with much less detail. Would you consider editing this answer to expand on it? \$\endgroup\$ – DMGregory Feb 10 at 21:23
  • \$\begingroup\$ @DMGregory No, you have all you need to get started. \$\endgroup\$ – Robert Mesa Feb 11 at 18:07
  • \$\begingroup\$ SE's more about contributing and building information. If an answer is effectively saying the same as another, it's not as useful. If the answer was fleshed out a bit to differentiate it from the main answer, it might be more welcome. \$\endgroup\$ – TankorSmash Feb 15 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.