Mathematical question: procedural generation of a

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

Can't you just SHA1 the galaxy ID, EG:

Galaxy 1

Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab

Galaxy 2

Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0

Galaxy 3

Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb

You can then segment the code, IE:

First 4 Chars = Number of planets

356a
da4b
77de

You would need some sort of string to number algorithm, one simple one would be to take the ASCII code of every non numeric character, and then multiply them all together or something.

So now we know how many planets are in our galaxy, how about galaxy x,y,z dimensions?

Next 9 chars = Galaxy Dimensions (x,y,z)

Same principle as above, turn the code into a large number. Have some sensibility checks as well, you don't want a galaxy thats 10milesx10milesx10miles with 20 million planets in it. Have some sort of weighted algorithm, like minimum size is # of planets * 10000. You will need to play with the numbers to make sure the ranges are all compatible and the selected chars from the hash actually give you a reasonable range.

Or, instead of this, you can have a random number pick a number between the min and max size of the galaxy, but use a constant RNG seed, such as the galaxy ID! This way the galaxy sizes are essentially 'random' for the observer, but they will be the same every time.

Etc etc!

That's one way of getting properties of your Universe, but what about planet properties? Like population and other stuff?

If you have Galaxy 1 with 20,000 planets, you can do:

Sha1('1:340') = bc02ab36f163baee2a04cebaed8b141505cc26b5

That is, galaxy one, planet 340. You can then just splice up that code however you want. The benefit of using a hash is that every planet should have a totally unique code.

Answer 2

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

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 5

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 6

I suspect the biggest problem you're going to face is having a naming system to name all these objects in a way that's consistent and meaningful to the player -- although we do have schemes for naming real objects systematically. I forget whether Elite's naming convention broke down after a certain point ...