Mathematical question: procedural generation of a galaxy

Question

I'm going to make a space/trading/combat game that is completely procedurally generated. But, I know that storing all of the details of the whole galaxy in memory is unfeasable. As a result, I've been think that I can use a seed to generate a solar system, and from that solar system, you can use jumpgates to travel to other solar systems. The problem is that if I jump to another solar system from the starting one, I need to be able to get back to the exact same starting solar system with the exact the same features (planets, asteroids, etc.).

Essentially, I need to be able to generate a whole galaxy from one number. And from that one number, which generates one solar system, I need to be able to generate all of the other solar systems that link from the first one and all of the solar systems that link from those, and so on. And each solar system has to stay exactly the same feature-wise, if I return to them. Also, the number of links from each solar system can be either random, or fixed, your choice. Random would be better though.

Answer 1

If you're feeling brave, you could do worse than look at how Ian Bell did it for the original version of Elite

Answer 2

I can vaguely recall this being done before. During the early 90's fractals were all the rage and I remember one company offering worlds to game programmers. The had created a whole infinite universe full of galaxies with suns and planets, event down to the valleys and textures of places on the planets. They were offering to find suitable virtual real estate to game developers. The game developers would get the software to render and use this, together with the exact coordinates to their propery in this fractal universe.

I've googled for a few minutes for "fractal game world planet universe" and such, but haven't found them. It might have been Pandromeda, but I can't quite remember.

You should study fractals for this idea. All you need is a continous field of numbers that you can recreate from a seed and then present those numbers as stars, planets and satellites with different properties.

Answer 3

You could build a pseudo random number of N digits from a certain seed (the "mother number"). Then, you divide the digits into groups and use them for answering your questions.

Example: N=20

-> one digit: how many additional jump gates?
-> three digits: seed for generating the respective lengths of each available jump
-> six digits: seed for generating this solar system
-> ten digits: seed for generating a new 20 digit seed for each linked solar system

Then recurse. Each system (with stable orbits etc.) gets generated at time 0, and you will have to calculate how it looks now.

Of course, this approach, starting from a mother system, would mean that the farther the current system is from the mother system, the longer it takes to generate its data. Also, this way makes a tree, not a net (which I would expect).

I think that it would be better to generate coordinates - use polar coordinates in the plane, and perhaps an ellipsoid in three dimensions.

Answer 4

If you really want to return to a fixed state, i don't think procedural generation from a single value is the right way to go.

Let's assume, you have a fixed grid of 256x256 systems in each plane and 16 planes in the universe. Each plane has up to 512 trading stations and up to 8 links to other planes. All trading stations and links are on a fixed position. Your initial seed value has to be at least 2^76 to encode all possible universes. Add some more objects (planets, ships,...) and the number grows exponentially.

Edit: It's a bit less if you don't allow more than one trading station or link in each system. I'd use some permanent storage, maybe an embedded database like Firebird or sqlite. Incidentally i'm currently developing such a game.

Answer 5

Check out this series on Gamasutra:

A Real-Time Procedural Universe, the first four links

Also, this: Algorithms for an infinite universe

Answer 6

Here's what I have come up with. Dunno if it will be the final version though.

Imagine a hexagonal grid, and at each vertex, a solar system. Since, we're on a hexagonal grid, there are only three lines going from any vertex. One is always horizontal, and the other two are diagonals. If we give the starting seed a value of n, we can give the solar system that is horizontally connected to the starting point a value of n+1, the others get values of n+2 and n-2.

Oh crap. We wont necessarily get a grid. Damnit. Lets try again.

Answer 7

I don't think there is really all that much information in a "galaxy" that you couldn't store it on today's computers. Let's assume a galaxy has 100 stars, and that each star has 10 planets, and that each planet has 3 moons. That's 100 stars + 1,000 planets + 3,000 moons you have to keep track of, which is 4,100 bodies.

Here's the things we may want to keep track of for a planet.

Mass X,Y,Z position Length of day (time to rotate on it's own axis) Length of year Population Amount of resources for 50 different resources

Assuming each value requires a double to store it, and we have 57 values to store (lets round it up and say 100), then we have 100 values * 8 bytes * 4100 bodies = 3,280,000 bytes. Now, thats 3 megs of data. That may seem like a lot but it's really not that much. Also, I don't think that you'd really want to have so many stars in a single galaxy. The game would really be just too big to explore, and would probably get unmanageable large to try to actually simulate all the stuff that's going on in a given galaxy.

Look at it this way. If you take a game like SimCity, and look at each square on the city grid as a potential planet, and then you realize just how much information can be stored in a small file, so that you don't have to randomly generate anything.

Answer 8

The point of the game is to make you feel reeeeeely small. I know a player would never be able to explore all of the game world, but the fact that you the player can makes this game worth making.

Also, I wont be actually keeping track of any events that are taking place in each solar system. They will be random happenings that occur when ever a player enters a system. For example, I can simulate the changes of a market on a planet by calculating the initial conditions (with the solar system seed) and randomizing the prices.

Thanks for your time.

Answer 9

Here's the basic idea as I understand it. Say you've arrived in star system #42 and you need to find out what's in it. It has nplanets planets -- a number between 0 and 10, say:

>>> star_system = 42
>>> nplanets = hash('nplanets%d' % star_system) % (10 + 1)
>>> nplanets
4

OK, so over by planet #2, how many space stations are in orbit there at the start of the game? Find a number between 0 and 3:

>>> planet = 2
>>> nstations = hash('nstations%d/%d' % (star_system, planet)) % (3 + 1)
>>> nstations
1

And so on. The numbers are each a hash function of the indices (star system #42, planet #2, in this case), reduced to the appropriate range. Since hash functions are deterministic but 'random', it's the same each time, but random-looking to the player.

Of course, hashing strings with long sequences like 'nstations' in them isn't the fastest possible way to go about it, but it shows the idea.

Answer 10

If you use a pseudo random number generator, you can guarantee that each random number you generate will appear in the same order from a given seed. The code to generate a system seeded by a given number will appear the same each time you generate it.

Use the first number from the pseudo random number stream to generate the number of "gates". Go through each gate and get a value from the number stream to assign to and seed each target system.

Generate the featurs of each system based on that seed.

There are several known algorithms for generating random seeds.

Give the Mersenne twister a crack

Answer 11

A random seed for each solar system is a viable solution but I have a feeling you're barking up the wrong tree here.

Can the player do anything to change what's there? (Say, build something, mine a depleatable resource etc?) If so, you'll have to save the state anyway.

Can the player look up what the place was like without actually having to go back there? (And if he can't, why not?!) Are you going to look it up or are you going to regenerate the entire solar system just to find out a piece of information about it? (the PRNG solution doesn't permit you to obtain only part of the solar system, you have to make the whole thing.)

Just how much detail is there anyway that you need to save?

Answer 12

Take a look at the original Worms game. I think it claimed to have about 4 billion possible levels. Each level was generated based on short seed string of maybe 20 characters. This determined

• the theme of the level (arctic, forest, etc...)
• the shape of the landscape
• the slipperiness of the ground
• the placement of prebuilt level details (snowmen, rocks...)
• the placement of your team of worms, landmines and weapon crates.

If you enjoyed a level, you could write down the seed string, and use it to regenerate the same level at a later date.

This is an example of a very complex, but deterministic function, with a single input parameter. I think this is the essential concept of what you need.

Answer 13

@the above guy: Any persistent change will not be recorded in any solar system object. If that was so, I would have to keep them in memory, which is something I'm not willing to do. As an alternative, I am going to keep changes in a separate object. Each time a player enters a solar system, the game will check if there are any changes made in that planet, and act accordingly.

Answer 14

As long as you call srandom() with the same seed, you'll get the same values out of random(). So, just base everything in a star system off a single call to srandom()... Then, you'll only need to store 1 integer (the seed) for a whole star system. Now thats compression!

Answer 15

This is my second, improved solution. The player will start out in a randomly generated solar system. Each system is connected to between 1 and 4 other systems. Think of them as north, south, east and west systems. If a player were to move through the north jumpgate, he will be taken to a system whose seed is one more than the system before. If he goes south, the seed for that system will be one less. 2+ and 2- for east and west respectively. The distances to those systems (in parsecs or lightyears or whatever) are calculated with the systems' seed and the direction from which you are arriving. This way, the size of the galaxy is only limited by the max and min of the number used to hold the seeds.

Warp holes to go to other galaxies will be placed a certain distance from the starting system. The next galaxy will just be like a continuation of this galaxy in that the seed numbers will be incremented in the same way and that the system that is on the other end of the galactic warp hole will just be an "east" or a "north" connection from the starting system.

By the way, this use of incrementing seeds leads to a web, unlike the above solution. Also, you can see that this method uses quadrilaterals while the above solution used hexagons, which made it impossible to create a web.

Of course, all of this is based on the assumption that all of the seeds will generate a random sequence of numbers that is different from any other sequence. This makes it so that each system is unique.