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.

Sexagenarian

It sounds like you need a PRNG that can go backwards and forwards. I wrote an implementation of the Mersenne twister some time ago that can go backward and forward. It's not all that hard, really. – Ganja

Just be careful. If you divide by zero we might all disappear! – Trochanter

Whats the question here? – Marielamariele

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

Wax

I have to admit I was inspired by the sheer immensity of the possible Elite universe. :) – Sexagenarian

In Elite 2, it was even a whole galaxy (a small one, but nevertheless), and the whole game fit onto a floppy (1.44 MB). – Eskil

I can't read C code as well as I would like; would some one explain to me how he did it? – Sexagenarian

@Dove: Fibonacci sequences - you can encode/generate a boundless range of integer variables from a seed of just two. It's the ultimate compression :) – Wendel

Answer 2

Check out this series on Gamasutra:

A Real-Time Procedural Universe, the first four links

Also, this: Algorithms for an infinite universe

Paramatta

Answer 3

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.

Saphena

Answer 4

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.

Officiate

Answer 5

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.

Gentianaceous

Answer 6

I think it is worth noting, that

1. a generator that produces the same random-looking output for the same input is called a pseudo random number generator, "PRNG". Typically you give it one "seed" input number at the very beginning and then just pull random numbers from it, calling it without further input. Note: you cannot "go back" to an earlier number, at least not without starting at the beginning.

2. a PRNG-like function that is called with coordinates as input of each call is typically a "noise" function. Here you do NOT have the "cannot go back" problem - just call with the "earlier" input again. A noise function uses a PRNG (as a backend; or at least it could) which still can be seeded at the very start, so you do not lose your "universe out of one number" feature.

3. While you could just use a PRNG and combine the galaxy coordinates to a "seed" each time, you would only get "white noise" at best, with no further attributes. A noise function is a much better fit for the job, as it can be chosen or even adjusted to give you tileable/smoothed/spiral-like looking/etc. results. For examples search texture images that were made using perlin noise. I expect you to see that with the same noise function you may create e.g. thousands of random clouds, but by adjusting the noise function to your needs (not just the seed or coordinates), you may get lava or galaxies instead. Adjusting it may not be trivial though.

4. The number of input coordinates for each call determines the number of dimensions of the noise function, so for a two dimensional map (or texture etc.) you could use a 2-dimensional noise function. Then you call it like noise2d(x,y) each time.

In your situation I would try a 3-dimensional simplex noise function (simplex is from the author of perlin noise, recommended as being better).

Each star system coordinate-triplet then gives you one result number. Next decision would be: what does the number represent? To put the smoothing feature of the simplex noise to good use, I would map lower numbers to emptier solar systems and higher numbers to systems with more mass. Or, maybe better, for each system call simplex noise multiple times with sub-coordinates. Medium sized result numbers then are planets, small numbers are vacuum or asteroids. Big numbers stars, etc.

The topic is not active and it is old but searches may end up here, as mine did.

Lipsey

Answer 7

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?

Latitudinarian

Answer 8

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.

Saracen

100 stars is not even a noticable fraction of a galaxy. Elite 2 had a galaxy of about 5000 lightyears diameter and fit on a 1.44 MB floppy. – Eskil

The Amiga version of Frontier - Elite II was made of a single executable file, approx. 700 KiB in size. The game featured something in the like of 10^12 star systems, everyone composed by multiple bodies (multiple stars, planets, moons, asteroid and, if inhabited, space stations and space ports). – Vulgate

A real galaxy won't fit into a computer, though, since they have billions of stars ... for big galaxies, an 32bit int won't be enough to even enumerate all stars ... – Harbird

While "I don't think there is really all that much information in a "galaxy" that you couldn't store it on today's computers." is true (depending on level of detail), but assumed numbers are absurd. See en.wikipedia.org/wiki/Galaxy (" Galaxies range in size from dwarfs with just a few hundred million (10^8) stars to giants with one hundred trillion (10^14) stars") – Imitable

Answer 9

I use the Mersenne Twister. It is PRNG that accepts as its seed array of any length.
For example, I want to generate galaxy on coordinates x=25,y=72. I re-init twister with seeds [25,72].
If I want to generate 1138th planet in this galaxy, I use [25,72,1138].
Country? [25,72,1138,10]
City? [25,72,1138,10,32]
and so on.
With this method you can generate billions of trillions of zillions of objects using just one number (the one before x coordinate, in our case before 25).
There are some projects now that use it.
Noctis: anynowhere.com/
Infiniverse: http://www.infiniverse-game.com/

Denial

Answer 10

Suppose you start with a seed for the galaxy, i.e. 1234, take this seed, and generate 10000 random numbers, each one represents a star system. When you approach the star, you take the star's random number, and you it as a seed for a new random function. Generate a random number for the quantity of celestial bodies orbiting the star, and the generate one number for each body (always using the second random function)and so on. I dont know if this helps you, but you need to remember that the random functions, are internally chaotic, for a initial condition, the whole function changes.

The seed for the stars in the galaxy must produce always the same stars, the seed of the stars must produce the same bodies, etc.

You can always turn things more interesting using statistics, density calculations, improving the results. Check always that the functions will produce the same result for the same input.

Sorry if my english sucks, i'm from Argentina, and english language is not one of my trained qualities :p

PD: I'm doing the same type of game ;)

Outface

Answer 11

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.

Crossjack

Answer 12

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.

Eskil

I think the web part is crucial. Maybe I should take a top down approach. – Sexagenarian

Answer 13

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.

Honesty

Not if you use a pseudo random generator. – Kierakieran

...so two random 64-bit values will be more than enough to hold that information, right? – Rufinaruford

Answer 14

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.

Sexagenarian

Answer 15

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

Kierakieran

Answer 16

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!

Tutt

Answer 17

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.

Sexagenarian

But you won't know the random sequence is unique unless you store all of the other random sequences and compare them. Otherwise, you're just playing the odds. – Sollows

Yes, I'm counting on the fact that each number will give me a unique sequence of numbers. But still, if there are a hundred billion solar systems, even if there are repeats, I doubt the player would ever see them. – Sexagenarian

Answer 18

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

Lepage

Answer 19

Mathematically, you want to randomly / pseudo-randomly generate an Undirected, Connected Graph. In this graph, each node would be a solar system and each edge would be a jump gate.

1) Create N nodes and randomly assign each a spatial coordinate. These nodes will eventually become your solar systems.

2) Generate edges using Deluanay triangulation algorithm. I suggest Deluanay triangulation because it will create a fairly nice looking map without any gates intersecting each other, but you can actually use any algorithm you want. I don't really know what you're looking for.

3) If you used Deluanay triangulation, I suggest that you eliminate a certain number of edges to create "sparseness". This will make the map more interesting as certain locations will become transport hubs, while others are simply pit stops.

4) Save this graph. This is your universe. Do not misplace or throw out your universe. Store it as efficiently as you want, but do not delete any information.

5) Assign each node a seed, and use this seed to generate each solar system.

6) Congratulations, you now have a universe with an arbitrary number of Solar Systems and Jump Gates.

Natika