Orbital Object Generation
SDxWiki

DWM This is an idea for generating objects within a solar system in a deterministic, repeatable way, while minimizing database storage for them. This idea is probably not original; it may spring from descriptions of similar techniques I've seen elsewhere. I'm no expert on orbital mechanics, so I'll be glossing over details which someone else can hopefully fill in. My intent at this point is to describe the overall approach that I have in mind.

First, a short review of the characteristics of pseudo-random number generators.

Pseudo-random number generators are labelled pseudo because they're actually deterministic and repeatable. These characteristics are important to the algorithm described on this page. A typical generator takes a seed value, and produces a pseudo-random number and a new seed on output. (If memory serves, the value and new seed are usually the same value.) Given the same initial seed, repeated invocations of a generator will produce the same sequence of random numbers.

Frank_Swierz Dan, one of my favorite space sim games called StartFlight did exactally this to generate an entire universe. And this was for a game that fit on only one or two floppy disks! I know that Age Of Empires also does something similar when creating random terrain. In fact the game lets you type in the seed number to generate a repeatable landscape. Perhaps you could use this feature to share with your friends. Anyway, my point is that since it seems to be used by other game makers, it's probably a preferred solution. Otherwise we wouldn't see it so much.

DWM Yeah, I thought I'd seen this elsewhere. I'm getting so old I can no longer separate my own original thoughts from all the stuff I've seen. Oh, wait, a friend told me that there are no original thoughts... :-)

Istvan I'm confident the original Elite / Elite Plus / Elite II: Frontier also used this approach to storing data on a very large number of visitable star systems.

Since the generator that we use must produce the same results on each game node, it will have to be provided by us. The generators provided with language libraries are often of poor quality anyway. (See 1.)

Solar System Element Hierarchy

A solar system's components are considered hierarchically. The first level of the hierarchy includes the body or bodies associated directly with the system's center of mass. The second level of the hierarchy includes anything that can be considered as an entity that 'independently' orbits the primary. Each subsequent tier in the hierarchy associates satellites of such an entity with their parent. (Note: with modern data, secondary stars and even some massive planets will be dictated externally to the generation algorithm, assuming we intend to simulate local space. How will we integrate any such predefined external data with generated data? Also, for systems of four or more stars, it may be easier to handle them as two binary systems in close proximity, as the mutual orbital motion of the pairs will occur on a timescale much larger than the scope of the game. However, simply handling all stars independently is precluded, because many close binaries will have planetary bodies that orbit the pair, rather than one of the elements, and we will want to handle those bodies. Lastly, if the volume of space included in the environment is either (A) small, or (B) very slowly extended to more star systems, new systems can be built "by hand" rather than generated with the algorithms we are attempting to define here.)

Hierarchical terminology

We need to speak the same language to make the hierarchy generic and rational.

The hierarchy to completely define potential solar systems must be N-level, with object type merely an attribute. Child objects may be of their parent's type, or of a lesser type. For example, a satellite of a star might be a star, a planet, or an asteroid. A satellite of a planet might be another planet, or an asteroid. All other terminology is either descriptive, or refers to aggregate objects.

DWM In light of previous discussion on binary (and n-ary) start systems, perhaps the top of the hierarchy should simply be 'system', with attributes pertaining to the system as a whole, seen from afar: position (center of system), radiative (and thus including visual) characteristics, perhaps 'number of stars', and seed (if assigned). That's all that's really needed by a far-away outside observer, and it gives us a uniform 'top' node. This makes it easier to build and work with the static database, which is then tailored to the task of generating background star fields. It also neatly sidesteps the problem of unary vs. n-ary systems; any stars are merely internal elements of the system. The algorithm that 'generates' the star(s) from the system's seed would also look at the system's overall characteristics so that (a) star(s) with the correct characteristics, and in the correct number, is (are) created. (OK, that was awkward phrasing. Sorry.) Istvan: But it made excellent sense.

Typical generic system hierarchy

Descriptive Examples:

Second-order objects:

Jupiter, planet, orbits Sol, star Ceres, asteroid, orbits Sol, star Third-order objects Dactyl, asteroid, orbits Ida, asteroid, orbits Sol, star Luna, planet, orbits Terra, planet, orbits Sol, star Fourth-order objects (none known in Sol system) (fictional example)asteroid, orbits planet, orbits planet (gas giant?), orbits star

Istvan- Notes:

  1. Asteroid "fields" of any sort will come in limited forms. They will either orbit a Lagrange point and thus be ellipsoidal volumes (cf. Trojan asteroids), or they will be "ring arcs" - ellipsoidal volumes elongated by statistical processes along a mutual orbital path segment (cf. comet dust, only larger particles).
  2. On Quantum Black Holes: These are theoretical but potentially common exotic objects. They represent a "fun factor" by creating "gravity terrain" in solar system spaces. They could be rare or as common as asteroids. QBHs have asteroidal masses, but otherwise follow all the expected characteristics of black holes: sharp gravity wells, potential navigational hazards. They could also potentially be used as exotic resources, as well as terrain, but I'll describe that elsewhere if interest exists. Frankly, if such objects were made common in the environment, many aspects of the game, including certain aspects of travel, could be based on them.
  3. Lagrange points: We may have to specifically include these as "bodies", rather than relying on the physics engine to create them, depending upon the spohistication of the physics engine.

DWM I was assuming that each star basic parameters (including position) would be stored in the static database mentioned below, so that we could use this database to generate a static star field background for a player based on his gross position. But of course a binary star system could be treated as a single entry in this database, with the position being at the system's center.

Interesting that you should mention LaGrange points. IWar's jump system requires jumps to be made between LaGrange points, with the backstory being that gravitational fields prevent or inhibit jump, so a near-null gravity zone is needed. Strangely, you have to enter the jump zone from a particular direction. Go figure. :)

Istvan: I'd use entry direction if and only if the realspace vector was directly related to the jump vector - making hitting the target system at the far end a real difficult proposition requiring precise astrogation to hit the jump point exactly right.

DWM Good justification. Maybe that was the intent in IWar, but if so, it wasn't explained anywhere.

Your points raise some questions about how accurately we want to model orbital physics and gravitational fields. On the one hand, a high degree of realism would be cool (as long as autopilots help a lot with the hard bits). On the other, we want to build a space game, not an orrery, and there's only so much computational power to go around. I have no idea how this will fall out -- we may just have to get a physics model up and running and see what kind of processing loads we're talking about.

Istvan I can't agree more. The many-body problem is supposed to be a cast-iron bitch, and frankly we may have to actually build a literal orrery for each system - not a pure orrery as you mention, in which most of the processing power is involved handling orbital mechanics, but rather an orrery in that all natural objects "run on rails".

DWM Hehe. I like that analogy. Dave Hettmer this may seem like an echo of Dan's point (orrery vs space game), but perhaps not because the main part of Dan's point references computational requirements. Anyway, here's my thought: How would we make the nuances of doing business in an 'exotic' system relevent to gameplay? Would it make travel to/from/within difficult and dangerous such that it becomes attractive to underworld types as a hideout? Are the challenges so extreme that the system becomes unusable? Or is the overall effect essentially identical to that of a garden-variety system like Sol, making the whole thing moot? I think the answers to my questions depend a lot on other as yet unanswered questions, like how we resolve the mechanics of flight and just what exactly is the point of the game. In any case, we will likely find ourselves approximating reality in some places and making stuff up in others just to make the game flow well. Istvan I think that you raise a real valid point, Dave. Honestly, I'm an advocate of gameplay over "gee-whiz" cool effects, and I wouldn't object to a game design in which we looked at what we wanted to do and tried to literally strip out all bits unnecessary to gameplay. That minimalist extreme is obviously impractical because a lot of gamers want excellent graphics and "local color" in their games. But the point remains that if something that requires major work also fails to improve the game experience, we need to take a hard look at why we are adding it. I'm supporting this concept of a game that spans potentially many, many star systems, but as it happens I do think we could build an excellent, marketable game with scope limited to our star system alone. On a similar note, I'd advocate very simple polygon models (like in Elite) for all "manmade" objects until late in the design and testing cycle, allowing artwork time to build up while the game environment programming proceeds. These comments are leaving the scope of this page's topic, however, and I'd welcome them being moved to a more appropriate area of the discussion.

The Algorithm(s)

Objects are generated starting from the inital seed. The parameters of the primary sun are stored in a static, globally available (possibly replicated) database. When objects in a solar system need to be modelled, the first thing that's needed is a seed value for the solar system. The first time that a seed is needed, it will itself be randomly selected, and then persistently associated with this solar system. From then on, the same seed value will always be used for that solar system. (Possible variation: Pre-calculate all seed values for all stars in the base astrophysical database, along with other star parameters such as spectral type and position.)

The primary sun's seed is used to generate a sequence of random numbers that are used to determine the number and type of all elements in the first tier of the hierarchy, as well as essential parameters of each element. The algorithm for this can take into consideration the parameters of the sun itself, so that, for instance, certains types of suns will tend to have certain types and numbers of internal elements. The exact parameters needed for each element will depend on the element's type; they might typically include orbital parameters, size, albedo. In addition, a new seed value is associated with each element.

When more detail is needed on an element -- for instance, a player approaches an asteroid field and can being to resolve internal details -- then the element's seed is used to drive a similar process for generating the details of the internal components.

This algorithm deterministically regenerates the internals of a solar system, regardless of player action. Since seeds for each tier are provided by the its parent, the order in which elements are 'visited' and expanded does not matter.

Concerns

Istvan I can describe a procedural method that will build random realistic systems, and which I think either already does or can be easily altered to handle multiple stars. Integrating the probabilities in this random generation method with a seed value algorithm is beyond my present understanding. Perhaps the algorithm can be reverse-derived from knowledge of probabilities in the procedure? It's also just dawned on me that the method I am thinking of was designed in the mid-80's and that our knowledge of near-star planetary families now has some empirical data that really should be integrated with the generation model - which I know did not account for the close-orbiting large gas giants we've been finding in the last five years.

DWM (I'll do this here rather than via email -- we can move it to a subpage if it causes too much clutter.)

Most algorithms incorporating randomness use a pseudo-random number generator to get a supposedly random number, then use this value to calculate either the occurence of an event, or map it onto some range appropriate to a parameter that must be generated. Each time a random number is requested from a generator, the generator changes state. This state may be either hidden or explicit. As an example, the standard C library function rand() takes no arguments, so the state is implicit. Each time you call rand(), it returns a new 'random' number, and the generator changes state, so that it can give you a new random number the next time that you call it.

Because pseudo-random number generators are deterministic algorithms, the initial state completely determines the sequence of 'random' numbers that a series of requests will yield. If you control the initial state, then you control the sequence. Ideally, the sequence is impossible to predict without knowing the exact algorithm and initial state -- hence appearing random. But if you know these two things, then there's no longer a Santa Claus -- you can predict the number sequence, because you can calculate the numbers the same way that the generator algorithm does.

The standard rand() function returns a new integer in the range 0 to (2**31)-1 each time it is called. The numbers should be uniformly distributed, on average. The sequence will eventually repeat itself, if it's long enough -- one of the measures of 'quality' for a generator is the length of this period. There are also generators available that will give you non-uniform distributions.

Most generators let you explicitly control the initial state, so that you can repeat a 'random' program run -- very important for testing purposes. The standard C library function srand() is used to set the state of the rand() generator -- you supply the 'seed', which is what defines the state.

So the repeatability I describe above rests on our ability to use the same generator each time (controlling the algorithm), and to set the generator to a given state at the start of generating a sequence of objects (controlling the initial state). That's why we must provide our own generator (which we'll snarf from somewhere), and store a seed value for each system.

Since the algorithms to generate objects consume a sequence of random numbers from the generator, it's also important that the order in which objects are generated is not affected by anything but the sequence of random numbers! (Although other outside data is OK, as long it is unvarying from one run to the next -- for instance the primary star type.) That's why I describe the tiered approach above. As each tier is expanded, it runs through an algorithm to generate objects at that level, and the seeds for the generators that will be used to expand each of the objects. (Insofar as those objects in fact can be expanded.) Since you do this all at once without being affected by outside varying data, you can guarantee that you'll get the same seeds for each of the objects being generated -- which in turn means that the expansion of that object will be similarly under your control.

So, I doubt that you will have to change much about your algorithms, except perhaps to rearrange them a bit to honor the tier-at-a-time expansion order.

The 'pre-generation' of seeds for systems mentioned above is a minor detail. It simply recognizes that you don't need the initial seed for a system until the first time that it is visited. If you wanted a completely recreatable universe, you would have to pregenerate all these seeds -- or, of course, always generate them in the same order, using the same generator, and the same initial generator seed.