Need help with procedural generation

Hi guys. I'm making an open-world space game. The first step for me is making a procedural universe generator (infinite galaxies, filled with around 1 million stars each which have planet systems). I am definitely not going to create content for everything. So I want to use procedural generation.

I know some of the theory - only loading stars within a certain range and unloading when further away, using a pattern such as the Fibonacci sequence with seeds for the first number and using data from that to generate details such as position, type and name.

What I have currently:
- System that generates positions and names for the galaxies and puts them in an array (will change to lists)
- That's it, really. I have set a galaxy count variable as I am unsure on how to do it infinitely like I want - so it often crashes or gives an out of memory exception when I set something like 1,000,000+.

Please can you suggest how I would only generate when closer without storing it in an array/list and how to make it infinite?

PS: I would also like suggestions/tips on how to make it work with multiplayer

Thanks,
Noxbuds

 

I have seen other people using Mersenne Twister. Would that be worth a try?

 

I suggest you take a look at the Minecraft world generation tutorials and topics. A lot of those ideals can be applied here.

 

Thanks. I will have a look into it

 

I just found out that the Random (https://msdn.microsoft.com/en-us/library/system.random(v=vs.110).aspx) class is a psudo-random number generator o.o

 

For your map you should work with Chunks/Nested-lists and about the random thing there is only pseudo randomness

 

OK. I specifically want pseudo-random - it is going to be multiplayer, so it must generate the same thing every time.
I am working on a number generation extension where you provide it with multiple integers for different things.

 

You can't have non-pseudo-random number generation on a computer, so you're set there

Only use the Mersenne Twister if you absolutely want to be sure that the numbers are uniformly distributed, as it's slower.

If it's multiplayer and you want to make absolutely sure the numbers generated are identical, I'd probably sync it, somehow. Depending on the amount of numbers you're looking at generating, you could make a very long array of random numbers and send that to the client. Then, just check once in a while that you're on the same index.

 

OK. Not sure how I would sync it though. I plan to have millions of stars and thousands of galaxies...

 

Just remember that the experts at Kerbal Space Program only added the local solar system(and while they are doing full simulation, and I assume you will not be), it was quite a feat. How about trying to get one solar system working right now?

 

you dont need to sync any think

if you do

Code (CSharp):

1.         Random.seed = 10;  
2.         Debug.Log (Random.value);

it should give you the same result every time you runn the code (maby different values with different OS like win7x64 or x84)

 

Yes, this works across the Random functionality too. So if you need values above outside the range of Random.value.

Code (CSharp):

1. using UnityEngine;
2.  
3. public class PsuedoRandom : MonoBehaviour
4. {
5.  
6.     private void Start ()
7.     {
8.         for (int i = 0; i < 25; i++)
9.         {
10.             Random.seed = 15454;
11.             Debug.Log (Random.Range (0, 10));
12.         }
13.     }
14. }
15. /*
16. Output:
17. 7 (25 times)
18. */

 

The syncing was more in the context of generating millions of random numbers, and always being on the same index on client and server. If you play for an hour or something, there's probably a chance that they'll get out of sync, which would be "a bad thing".

 

thats the point you dont need to sync it every client will generate the same "galaxy" you just need to sync the position what can be 2 int values i added a small image

 

Exactly. I will probably make it so the server only stores things like currency, positions, ships etc. - not even starports (unless I add player-made ones)
I did try to generate a list of galaxies... I crashed Unity.

First comes Galaxies/Stars. Then planets
First I will make the galaxy map, then use similar methods for the planets. In-game, the player will only get to see/visit the contents of their current star system unless they Hyperspace to the next system.

 

I am thinking of doing it a bit like this:

 

By the way, I did some calculations. I want at least 5000 galaxies, at least 1 million stars each. An Int32 is 4 bytes AFAIK, so 5,000*1,000,000=5,000,000,000. Which means the total size is 5,000,000,000 * 4 bytes or 20,000,000,000 bytes. If we minimize the numbers (divide by 1024 multiple times) we find out that it would mean 18 gigabytes of just Int32s. On top of that, I need space for HD starship models, player avatars, textures, starport attachments, landing pads, space elevators and so on. If I did that, it could easily become over 50gb in size. I do not want that.

EDIT: I realise that 18gb would be on a server, but currently I do not have a server to do that with. I want server interactions to be kept minimal

EDIT EDIT: It cannot possibly get "out of sync". It is generating a number pseudo-randomly based on the same seed. There is no updating the galaxy server-side. The only parts that will be saved will be custom overrides I set (which I probably will)

 

So I'm thinking for the chunks, I run them through my number generator to get positions for stars and multiply/divide based on the distance to the galactic bulge. I am not entirely sure about spirals for the galaxies, but I can think something out

 

And then for the galaxy, I create lines where stars should be. I'll position them around these lines:
(yellow squares demonstrate chunks on a larger scale)

Something like this I think:

Code (CSharp):

1. int x1 = 0;
2. int y1 = 0;
3. int current_rotation = 0;
4. int arm_length = 100;
5. GameObject arm_point;
6.  
7. for (int i = 0; i < arm_length; i+=10) {
8.  
9.     x1 += Mathf.Sin(current_rotation);
10.     y1 += Mathf.Cos(current_rotation);
11.  
12.     Instantiate(armpoint, new Vector3(x1,y1,0), new Quaternion(0,0,0,0));
13.     current_rotation += 50;
14.  
15. }

And then the generator will go from point A to point B, scattering the stars left and right of the arm.
Good idea?

 

That's a lot of stars.

I thought you were going to continually generate the universe over time when playing. Then it would have been a good idea to sync up sometimes, because of race conditions and stuff like that.

 

Ah sorry if I wasn't clear about that.
Basically it will generate 9 chunks, with the middle one as the one the player is in. When he/she jumps outside of the original chunk, it'll move the 9x9 loaded area and unload the previous chunks which are out of range.

I hope for infinite stars by the way

 

Thi

This is making the assumption of an entity being defined by only an Int32. Which is not plausible, unless you have an extremely bland world in which every entity is the exactly the same, or each entity is already stored on the client. This model is not feasible with these numbers.

 

Why so big? I mean, look at our universe. Sure its massive, but so far the only interesting bits we have discovered are confined to outlr small planet here.

Back to the topic at hand, you don't want to solve this with random numbers. This would require holding the entire universe in memory, which is just not practical.

Instead you want to investigate a noise function. The value of noise is you can input a value for your position and et the same result out each time. This allows you to consistently generate the terrain in the chunk of interest, without ever generating chuncks you don't care about. Its also independent of chunk order.

Pelrin is a good place to start.

 

Yes. I am definitely not just going to make it just Int32s. It was to show how big it would get if I did store it in memory.

I've used noise before it is one of my thoughts on making this, another is a bit different though. I plan on making it generate how far down the arm it is, and the distance to the arm in a direction. Based on that, I will place stars on their correct side and distance to the supermassive black hole (I am probably going to do this). Although for planets, I will likely use Noise.

Remember - I want it to look like a galaxy, not just a cube-y collection of stars. I realise noise can probably do this, but just remember - it has to be able to look like a spiral galaxy.

 

And I like big stuff. I need this to happen. One galaxy with a few thousand doesn't satisfy me.

 

There's a pretty big leap from a few thousand to five billion stars, though.

 

Not if it generates based on where the player is/chunks.

 

Then another problem you'd need consider is the size/number of chunks you'd need, and knowing when you're moving from one to the next. If you choose to have your chunks evenly in a grid, you'd end up with a lot of empty grid spaces, so you'd need to partition them in another way(Maybe check out octrees). But realise that this datastructure will probably take even more space than your random numbers.

 

So what I have been thinking of is this:

It recognises that you are in a chunk - I will have Vector3s to setup the boundaries. If the player gets near the edge of the boundary, it'll load the next chunk and when they are far enough from the original, it'll unload the original.
For example, an empty GameObject named chunk. Inside this chunk, it'll have stars as little images or spheres or something for the galaxy map.

Above that, "galactic chunks" based on noise. This will just contain positions of galaxies within the space of around 500kly or something (only like 1 or 2 galaxies in there). If the player gets close enough, it'll generate the arms and space on them cloud billboards (loading all the 1 million stars is inefficient and probably impossible) and repeat the star process.

I am fairly confident about this. I'll probably every 1 or 2 weeks post a devlog on the progress.

I just need to know something: how do I instantiate something client-side only? Or does instantiate already do that?]
Also, how would I make it so that when you are in your ship and you open the galaxy map that you stay there but players can't see that you're opening the galaxy map? And that the galaxy map is an actual 3d map.

Let me give you an example of something similar to what I want:

Obviously I won't show points of interest or anything. Just a nice 3d map which I design but can show without needing to switch scenes

EDIT: Or should I switch scenes but still store the position on the server so that players who go near can see me?

 

How would I implement perlin noise or something similar?

 

There's pseudocode on the wikipedia page for Perlin Noise.

 

Hmm... I'm actually thinking of a galactic chunk containing just one galaxy...
I mean, in a 500x500x500kly area, it won't be easy to have galaxies realistic(-ish) distances apart if they're up to 250kly in diameter.
Thanks for suggesting, though. Always appreciated.

 

At which numbers do floating point problems arise?
Is it -((2^32)/2) and (2^32)/2 ?

 

That would mean you could visit an area of 8,589 x 8,589 x 8,589 chunks, or 4,294,967,296 x 4,294,967,296 x 4,294,967,296 ly which, when shortened, is 4.29 Gly. And the area is 78.9 Gly. I think that is sufficient, don't you?

 

Signed integers can have a value between [-2^31 , 2^31]. Floating point precision is always an issue, as you can't represent infinitely small numbers on a computer.

 

That doesn't really matter if your chunks are just represented by an max and min coordinates, and an array of stars.

 

OK... btw I calculated it would take at least 1205 milennia to go to every possible galaxy and move to the next...
I realise no-one is going to go to the edges, but it's cool to be able to say that. And it isn't an array of stars - that would crash the computer just doing that for 1 galaxy. Just an array of arm positions and cloud billboards to simulate stars.

But that's if 1 unit = 1 ly.
Hmm... may need to recalculate.

 

The array only contains the stars in the given chunk. Something like this:

Code (csharp):

1.  
2. struct GalaxyPartition{
3.     Vector3 min, max;
4.     Star[] stars;
5. }
6.  

 

Right, yes.
And there is a level higher:
"Galactic" chunks. These contain 1 galaxy each and will be either 250x250x250Kly or 500x500x500Kly in size. What will be done there is the galactic core position and the arms with cloud billboards placed on them

 

If each galactic chunk always and only contains a single galaxy, they're reduntant. Either have a bunch of galaxies in each, or just have a list of all the galaxy centers, and do range checks on them.

 

OK. I probably used the wrong word. Rather think of them as a part of the grid, a space for a galaxy and the rest of the space is just spacing between the galaxies. When you zoom out, you will see up to 27 galaxies (9x9x9). Others which are close but not close enough to think about generating the spirals/arms/whatever will be just a bright dot.

Again, it would be insane to use an array with all the galaxy positions. Because of the galaxy count

 

If I'm going to have Humans in-game, what would be a good unit for the Unity units? Or different scenes where units are different?

 

Uhh, excuse me.

 

Ok... I didn't want truly random anyway.

 

I just had to mention it

 

GENERATE truly random numbers in CODE, then.

 

I don't want random numbers

 

I've decided on units. The galaxy map will be 1 unit = 1 ly (hooray, I keep the possibility of 633,618,440,469 galaxies!). Warp (interplanetary) will be 1 unit = 1 ls. Normal space will be 1 unit = 1 m.

Each will be a different scene. The server will store which state (warp/normal space) and will store the position in that state.

 

I added a cube at (500000,500000,500000) and when I focus on it and look around, it bobs really weirdly. Why?

 

Hard to say, but it could be imprecision of the single floating point numbers.