It's a new year for one lone Koda.

So let's have a nice simple video to get started.

Let's procedurally generate the universe.

Now, To those of you that frequent the discord server, you will know that I'm a big fan of the elite Siri's of games going way back to the early eighties, where the elite games presented an entire universe on a very small machine.

I am machine with not very much memory, Andi.

Over the Christmas period, I've been playing elite, dangerous and loving every minute of it, and it has a vast universe.

In fact, it has a universe so large it can't all possibly be stored on the computer.

And so I've decided to create a small application here, which tries to emulate that effect on As you can see, I'm panning around well, a very simplistic looking universe of different star systems.

So each of these circles represents a star.

The first thing to note is that the universe is actually persistence.

If I scroll this way, it will look the same as I school this way.

Admittedly, it's easy to get lost in my universe because I'm not put any coordinates on the screen natural at that, too.

Their to do list.

But please don't misunderstand.

This universe is vast.

It's huge.

It will go on for billions and billions of stars.

And they were all exist in exactly the same place as I move the mouse cursor around, I can highlight specific stars.

So let's that cook on this one.

You can click on this one, and we see around the stars that several planets and the planets have several moons.

Let's try a different one.

Try a few so some don't have any.

But they all have something different on again.

These are persistent, so I could go to one side of the universe and come back.

These will still be here.

We contest this.

Let's try and find some features I can recognize.

So here we've got a small cluster of planets that's pick that one in the middle on.

I'm going to panel the way this way for a few seconds, and then I'm going to pan all the way back and try and find that cluster.

There it is and click on the same one we see.

We get the same results on it doesn't matter how big this universe is.

There's no search time required.

It will always generate the same persistent star systems forgiven star.

The size of this universe is limited only by the precision of the interview types I'm using to store the position of the mouse coordinate.

It is vast and yet can be rendered on dhe interacted with in no time at all.

You can also see on the right hand side of the screen here that the universe conceals very little memory.

As I'm moving around, we're not generating more and more planets and stars that so there's no more memory created on.

Nothing is cashed out to disk that would be far too slow, and you'll just have to take my word for it.

But the size of the executed well on disk is about 30 kilobytes.

So how do we store on entire persistent universe and access it so quickly on my computer?

Well, hopefully, it's obvious that we can't store the entire universe on my computer.

Instead, we're going to use an elaborate series of equations to generate the universe as we need it on.

We'll use our mouths coordinates X and Y as the input parameters to this equation.

This technique is called procedural generation.

We see it quite a lot in games like Minecraft or Road likes.

Now I'm going to take a little bit of an issue with that, and I'm expecting some debate in the comments about this.

I think games like Road likes net tax and Minecraft and all of those games that generate random content.

I don't necessarily consider those to be procedural generation.

I think about Moore's automated generation because take my craft, for example.

It generates the world in these chunks on.

Once it generated them, they need to be stored.

They need to be fixed somewhere on recalled when they're required.

In my mind, procedural generation is something a bit different.

It is generating the resources as required on the fly on consistently each time.

I don't think either term is incorrect, but in my mind it makes sense to make a distinction between the two.

That gangs that automatically generate resources and assets are not quite the same as games that procedurally generate resources and assets At the heart of all procedurally generated applications lies, randomness or, in the case of a computer, pseudo randomness.

Because we can't realistically generate true random numbers.

But randomness on its own is not enough to create compelling resources.

We need to control that randomness in such a way that makes our applications sensible.

In this video, I hope to show us that.

So let's get stuff as usual.

I'm going to start with a skeleton pixel game engine project, so it's got nothing in the on user created on user update functions on I'm Constructing the Pixel game engine to be 5 12 by 4 80 onder each game pixel is to my to screen pixels.

Now.

I've also moved over to Visual Studio 2019 and I'm still learning what it's going to be doing with tool tips and things popping up all over the video.

So I apologize if they get in the way.

Fundamentally, Procedural Generation is about controlling randomness, and so I think it's worth spending a few minutes just exploring the available options off pseudo random number generation that's available to us with c++ language.

And rather than just look at the statistics of the generated numbers, I'm going to visualize them instead on I'm going to do that whenever the space key is pressed if you've seen my videos before him, we've looked at things like noisy images on the screen.

It's always caused the YouTube algorithm to completely collapse when it's displaying the video.

So by making its sensitive to the space bar being released, I should hopefully be able to retain the integrity of the image, which is going to be necessary to understand whether a random number generator is good for us or not.

The two qualities of the random number generator I want to look at the first is how good is the randomness on the second is how fast can it generate the random number?

So I'm putting in too little time points so I can measure the duration off the generation.

I'm going to draw that to the top left of the screen, using the pixel game engines drawstring function.

My intention here is to go through every pixel on the screen and for each pixel we're going to draw a random number, and depending upon value of that random number, I'm going to set a flag B s star to true or false, and I'll just simply for now use a single pixel is the star.

It's either white or black.

And the only reason I'm drawing the Black Stars, even though I've previously cleared the screen appear to all black is to just make sure that the timing is consistent.

For example, if the random number generator generated a few white stars, it's going to give the appearance that is performing better.

So I need to make sure that the drawing of the star is not factoring into the timing of the randomness functions.

So let's start with the random function everybody knows round.

And everybody also knows well least have been told that Rand is not a very good random number generator.

Well, let's take a look.

So I'm going to draw a random number between zero and 255 inclusive on I'm going to check.

Is that value less than 32?

So, in principle, we're looking at an eighth of the screen being stars or white.

In this case, let's run the application now to get any stars to appear.

I need to press the space bar, so there we go on.

On average, this told us to generate This field of stars took about six milliseconds on dhe.

The randomness doesn't look too bad at first glance anyway.

Keep pressing space.

I can regenerate more and more stars, and the time to do so is well.

It's roughly always the same.

A handful of milliseconds.

The problem is, I want to control the randomness.

It's no good to me to just have genuine randomness here.

I need some way of shaping that randomness into a universe.

If I always wanted to generate the same universe each time, I would need to see to the random number generator with some sort of key.

I'm going to pick a value at random here, 1000.

So now when I run the application, even though impressing the space bar on, we can see it's generating it.

The universe is the same each time, so knowing that we can set the seed of a pseudo random number generator is going to be really important for maintaining persistence.

Across the assets were procedurally generating, but there's a problem here in order to know whether a pixel is black or white.

I need to have generated them in this specific sequence from the top left all the way to wherever my cursor is.

So yes, I can always check what color the pixel is under the cursor.

But if I wanted to derive that based on our randomness equations, how do I do it right now?

I have to start at the top left on Generate the sequence precisely because of the set seed all the way until the point that I need it.

This could be very slow, particularly if I've got an entire universe to procedure, regenerate out, have to generate the universe up until the point that it is under my mouse cursor.

And this is exactly what I'm not trying to do.

I don't want have to generate the universe in advance and store it somewhere in order to interrogate it or cess various components of it.

What if instead, we used to seed that was based on the spatial location within the universe.

So instead of setting the seed once at the start, I'm going to set it for every single star that we generate.

But there's no point in using a fixed number all the time, because then the entire universe would be the same.

Instead, I'm going to take the X and Y position of the screen and sort of squash that together into a seed value and use that as my seed.

This approach guarantees that the seed is different for every pixel on the screen.

Yet regardless of the location, it should consistently generate the same sequence of random numbers for that location.

Let's take a look.

It's best this baseball well, it's certainly generating numbers, and it's plotting stars, and it's taking a little bit more time now that we're setting the seed.

But something tells me that's not quite random.

Perhaps I'm just getting very, very unlucky with the distribution.

So let's change that to a 50 50 distribution.

Well, that's not changed very much on.

In fact, this highlights the limitations of using Rand.

Given that we're choosing to plot a pixel as white or black, based on the first random number generated after setting a seed, thes patterns suggest that the random number is highly correlated to the seed.

Therefore, it's burly, random at all.

In fact, it's utterly predictable.

In this instance, it's around his rubbish.

We're going to need something better than round.

Modern C++ actually provides a good random library as part of its standard library, generating high quality and robust random numbers is well beyond the scope of this video.

It's a complete computer science and mathematics field in its own right.

There's a lot of research and dedicated effort going into generating high quality random numbers simply because they underpin all of our digital communications and cryptography.

Service's as I just demonstrated, even though we've used round plenty of times in previous videos, it's great for little bits of randomness in games.

If you're really relying on its integrity to generate random numbers, it could probably very easily be hacked.

I think generating random numbers on computers is a fascinating topic.

I don't know if it will ever be solved until we get dedicated hardware which concerned how exploit the environment in order to generate some random numbers.

But until then, we've got what we've got in good old modern c++ fashion.

Using the random library is a little bit wordy.

First, we have to choose some sort of random device.

This is meant to be the seed that will be generated randomly from my machine.

Then we need to choose what kind of random number generation engine do we want to use, and in this case, I'm going for the mise en Twister.

It's reasonably accepted as being one of the most robust random number generators out there.

At least a lot of research has gone into it.

I can't just draw a random number like before.

I need to specify a distribution on in this case.

I'm testifying a uniform distribution so all numbers should haven't even probability of being drawn.

So this time, let's include the standard random part.

And just as we did before, we'll do the same test.

I'm going to draw a random number between zero and 255 inclusive and plot the pixel.

You'll know that I've not included this setup within my time period.

Ideally, you don't you need to do this once.

One final thing just because I forgot where we need some parentheses after the RD in the construction off the mise en twister object.

So let's take a look.

So as before this press the space bar and, well, it looks pretty much the same.

If anything, I would say it's a little more evenly distributed than it was using Rand Not seeing quite a cz many clusters or line artifacts, you might just be my eyes playing tricks on me.

But it does seem to look better, and it's taking approximately the same time.

At 3.8 milliseconds, Formula seconds there generate a few more, so that's fine.

But again, we've got this problem of We've just set the seed once for the entire universe.

Now we need to set it per star.

Well, using the same scene generators before I'm just going to see the mise en twister.

Let's try that space And while oh dear, I mean, it looks great.

It's perfect what we want, but it's taking about 400 milliseconds.

395 400 milliseconds to generate the screen.

It looks like seeding.

The mise en twister algorithm is quite slow and probably far too slow for our needs.

However, it has generated a very nice random universe, so I could place my mouse cursor anywhere in this scene on converting its coordinates to use as a seed for the random number generator will tell me whether the star exists or not is the pixel white or black.

And so the quality of the random number is brilliant here in this case, but the performance of its sucks we need something that's a good in between.

So C++ random library mise en twister, you're out.

It takes far smarter people on more dedicated people than me to generate a high quality random number generator.