Procedural Generation: Programming The Universe

hello it's a new year for one lone coder 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 series of games going way back to the early 80s where the elite games presented an entire universe on a very small machine ie machine with not very much memory and 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 and 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 scroll this way admittedly it's easy to get lost in my universe because I've not put any coordinates on the screen I shall add that to the 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 will all exist in exactly the same place as I move the mouse cursor around I can highlight specific stars so let's click on this one so we can click on this one when we see around the stars that several planets and the planets have several moons let's try a different one let's try a few so some don't have any but they all have something different and again these are persistent so I could go to one side of the universe and come back these will still be here we can test this let's try and find some features I can recognize so here we've got a small cluster of planets let's pick that one in the middle and I'm going to pan all 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 and it doesn't matter how big this universe is there's no search time required it will always generate the same persistent star systems for a given star the size of this universe is limited only by the precision of the integer types I'm using to store the position of the mouse ordinate it is vast and yet can be rendered and interacted with in no time at all you can also see on the right-hand side of the screen here that the universe consumes very little memory as I'm moving around we're not generating more and more planets and stars and so there's no more memory created and 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 executable on disk is about 30 kilobytes so how do we store an 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 knew it and we'll use our mouse 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 roguelikes 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 roguelikes net hacks 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 in take minecraft for example it generates the world in these chunks and what it generated them they mean to be stored they need to be fixed somewhere and recalled when they're required in my mind procedural generation is something a bit different it is generating the resources as a required on-the-fly and 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 games 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 application sensible and in this video I hope to show just that so let's get started 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 and I'm constructing the pixel game engine to be 512 by 480 and each game pixel is 2 by 2 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 tooltips 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 of pseudo random number generation that are available to us via the C++ language and rather than just look at the statistics of the generated numbers I'm going to visualize them instead and I'm going to do that whenever the space key is pressed if you've seen my videos before and 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 it 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 there are two qualities of the random number generator I want to look at the first is how good is the randomness and 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 of the generation I'm going to draw that to the top left of the screen using the pixel game engine to draw string 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 is star to true or false and I'll just simply for now use a single pixel as 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 it's 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 Rand and everybody also knows well at least have been told that round is not a very good random number generator well let's take a look so I'm going to draw a random number between 0 and 255 inclusive and I'm going to check is that value less than 32 so in principle were looking at 1/8 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 spacebar so there we go and on average this told us to generate this field of stars took about 6 milliseconds and the randomness doesn't look too bad at first glance anyway I'll 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 seed the random number generator with some sort of key I'm going to pick a value at random here a thousand so now when I run the application even though I'm pressing the spacebar and 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 under Miss equations how do I do it right now I have to start at the top left and 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 procedurally generate I would 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 to have to generate the universe in advance and storage somewhere in order to interrogate it or assess various components of it what if instead we used a 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 me 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 in 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 to spacebar hmm 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 and in fact this highlights the limitations of using R and given that we're choosing to plot a pixel as white or black based on the first random number generated after setting a seed these patterns suggest that the random number is highly correlated to the seed therefore its burly random at all in fact it's utterly predictable in this instance surrend is 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 and 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'll underpin all of our digital communications and cryptography services and as I've just demonstrated even though we've used Rand plenty of times in previous videos it's great for little bits of randomness in games if you are 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 can somehow 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++ fashioned 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 mesentery stirrer 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 and in this case I'm transferring a uniform distribution so all numbers should have an 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 0 and 255 inclusive and plot the pixel you'll note that I've not included this set up within my time period ideally you'd only need to do this once one final thing just because I forgot where we need some parentheses after the Rd and the construction of the Mersenne twister object so let's take a look so as before I'm going to press the spacebar and well it looks pretty much the same if thing I would say it's a little more evenly distributed than it was using Graham not seeing quite as 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 about 3.8 milliseconds for milliseconds 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 seed generator as before I'm just going to see the missing twister and let's try that space and Wow 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 Mersenne 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 and 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 it sucks we need something that's a good in between so C++ random library Mersenne twister you're out it takes far smarter people and more dedicated people than me to generate a high-quality random number generator so I would suggest to go on finding one and one that's been around for quite some time is the lemma or lemma random number generator I was using this back in the early 2000s as part of a research project I was doing for the University this was before the introduction of the random library where you had easy access to algorithms such as Mersenne twister this algorithm is known as being reasonably robust but the beauty of it and what's going to appeal to us is that it's actually very very quick we're going to need to create a little utility function to generate these lemo random numbers now if it's not pronounced lamb then I apologize to dr. lemma so I'm going to create a small function called lemma 32 because it's going to generate 32-bit numbers most of the algorithms shown for this generate 64-bit numbers and by converting it to 32-bit I've probably completely compromised its integrity as a robust random number generator I'm aware of that it works by maintaining a state variable and each time we draw a random number we're going to change that state in fact that state isn't a random number and even though this will look like gobbledygook that's all there is to it and we can see computationally there's not a great deal going on here we've got some additions where we've got an integer multiplication but then all we've got are shifts and zorse these are all very cheap computational instructions to use and the maths behind this is mostly beyond me but I'm on the understanding that these are some type of specialist prime number and by xoring with these prime numbers and shifting the register we can change the state of our lemma variable in many ways this is very similar to a linear feedback shift register so let's just get stuck in and use it straight away instead of looking at the whole screen this time we're going to look that's just setting the seed value directly to be the lemma States and that's sort of priming the shift register and as we have done exactly before I'm going to draw a random number between 0 and 255 inclusive so let's take a look first space and what we see now is a persistent universe being generated per pixel on the screen with the same performance as Rand and so this is perfect for what we need procedural generation is fundamentally harnessing the properties of probability to generate interesting things so let's just take a very simple one-dimensional example assume I've got a plane of land and I wanted to populate this land with trees in the universe example we're using the location in space as the seed for a random number generator so I'm going to do the same sort of thing here and I'm breaking space up into discrete zones for each zone I'm effectively rolling a die and making a decision based on the output so i can assume with my die example that's a tree exists if my random number is less than 2 in this case there's a 33% chance of a tree existing so we might see one here and one here and one here etc etc if I made this threshold larger let's say if it's less than or equal to 5 so there's only a 1 in 6 chance of it not being a tree we would certainly expect to see a lot more trees in each section to the point where they're all uniformly distributed across the land in order to bias procedural generation to give us plausible results we can't just rely on the probability and harsh thresholds alone in this tree example we may see that if we did have the probability of it being a tree set too high all of our trees would be uniformly spaced it wouldn't look particularly realistic perhaps we want clumps of trees to exist instead well this is just a case of biasing our threshold values on some of the parameters perhaps the threshold value could be based on location so as the location number increases it's going across the screen the probability of it being a tree also increases at which point it's unlikely we'd see a tree here at the start but as we're moving along the screen we may start to see them and we'll start to see them with more frequency so you could use this approach to have sort of a boundary going into a forest for example we can also use lots of other interesting functions to access this threshold perhaps we wanted a clump of trees to appear somewhere in the middle of this land well if we used a threshold value that was biased by some of the function for example a Gaussian curve then in this region it's far more likely we'll see trees than in these extreme regions the beauty of this approach is that our random number has never changed but our understanding of how we want to construct the world as forces to think about how to manipulate there is of that drawn random number and this is really down to us as engineers to devise an appropriate solution set of rules to construct compelling worlds and I'm not arguing that that in itself is easy it's far from it depending on the level of detail you want to go to but fundamentally the random component is at least guaranteed to be consistent and so irrespective of how complicated your generation routine is it will always be the same each time so given that we know we're going to get the exact same sequence for a given seed and that sequence is going to be random I'm going to construct my universe by first checking for that location does a star exist and so that becomes my first random number draw I'm going to draw a maximum up to 20 and I'm going to test is that equal to 1 that will tell me does a star exist so one in every 20 locations will contain a star now it's important I don't reset the seat because I want the sequence of random numbers that are generated to be the same every single time so the seed has been set once and we've generated does a star exist if it does then I'm going to determine the size of the star and again that's going to be some random number generated in this case between 10 and 40 these units are meaningless and they will need to be chosen to suit the application that you're trying to procedurally generate then I'm going to draw another random number for the color of the star and I've got eight possible colors to choose from and then I want to generate how many planets surround the star and then for each planet in order I want to determine some properties of the planet what is its size what is its temperature what is its makeup a what percentage is perhaps covered in foliage what percentage is covered in water how much of it is minerals you can make up all sorts of different parameters what is its population each time we start to create a statistic we always draw some random number from our pseudo random number sequence the sequence is always going to be the same each time that's the real take-home message and what the interesting thing is we can start to not only just use the sequence but we can use the values of parameters we've already chosen so let's say we are also maintaining the distance away from the star or we could use that distance function as part of the temperature calculations we can use the temperature calculations to tell us is it likely there's going to be water on the surface and if there's no water on the surface what's the probability of there being foliage so this is really up to the designer now to start thinking how are all of these things connected but the beauty of this is it's generated when it's needed each time because even though randomness is involved in the definition of the planets and the stars and the system's the randomness is under our control and it's guaranteed to be consistent but the key principle here is we have to generate these random numbers in the same order each time now we've explored the randomness I'm going to remove this code from the application and I'm going to add to the application a new class which represents a star system and the constructor of this class is going to be the thing that does all of the work so a ladder constructor which takes in an x and y coordinate which is the location of this star system in the universe I'm going to take our little random number generator from before and move that over to the class we'll keep those private the first thing this star system needs to do is generate its seed based on its location which as we've just seen before is merging together the X and y coordinates now I'm using a 32-bit system here but I'm only looking at the least-significant 16 bits of the X&Y coordinate that will of course put some boundaries on the universe they will only have a 16-bit the coordinate resolution in each axes so it's not going on forever and hopefully when it does get to one end of the universe it should just wrap round to the other quite nicely of course if we needed larger you versus we would use more bits as we start to procedurally generate the star system we're going to need to store some of its states so here I've added a boolean for whether it exists something that represents the size of the star and the stars color and I'll draw the Stars color from an array of colors which I've defined as a constant expression at the start of the program so these are alpha blue green red in hex I don't always want to draw random numbers of the type unsigned integer 32 now instead I'd rather work with doubles and regular in SATs a bit more convenient and also I want to work with numbers that are within boundaries that are sensible for the things I'm trying to define so I want to create some utility functions where I supply a minimum and a maximum each time so this one will generate a random integer between this minimum and that maximum and this function will return a random double with the same constraints note that they both call the lemma 32 function so going back to our constructor we can start to generate this system firstly does it exist and that's quite important and quite an odd concept because you might think well of course the system must exist we're constructing a class that represents that system well that's not quite true we're actually creating a definition of what exists at that location within the universe so our boolean star exists will be set to true one in 20 times on average if the star doesn't exist I'm just going to abort the construction there's literally no point in doing anything else so very cheaply we have set the seed determined whether the star exists or not and if it does then we go on to create more interesting features if it doesn't then who cares assuming the star does exist then I'm going to generate something that represents its diameter and choose its color from the array above instead of working with the screen in a per pixel basis I'm going to break the screen into sectors which is easily done by taking any location on the screen and integer dividing it by the dimensions of our sector which I'm going to set to 16 by 16 pixels this allows me to then take the size of the star that we've just generated and in some cases we'll have small stars and in some cases we'll have big stars and then we'll have some medium stars but it gives me space to plot them in this little simple demonstration I'm just going to draw a circle of the appropriate color but you could of course procedurally generate images you could create animated graphics the possibilities are literally limitless it just depends how much effort you are prepared to put into generating the detail required for your application in the on user update function I'm going to start drawing our world so now we will clear the screen to black and I'll create two variables and set as X and n sectors Y which tells us how many sectors we've got across and down the screen because you might choose a different resolution and sector size this year I'm going to get into the habit of using the built in vector types in the pixel game engine so here I'm creating a two-dimensional integer vector called screen setter which is going to hold the coordinate of a particular sector on the screen I want to iterate through all of the sectors that are visible on the screen to have two nested for-loops that are just scanning through all of the X&Y coordinates and because our sectors are quite large there aren't that many sectors to process for a given sector location we need to determine what is the star system in that sector so I'll construct a star system object but I'll need to pass in the location which will be used to seed the Lema generator later on at this point I'm only interested if the star actually exists now that will have been set by the procedural generation routine in the constructor of C star system and as you'll see with the rest of this video I'm really just going to hack in the graphics appropriately so here I'm going to draw a circle in the middle of our sector and I've got some hard-coded numbers in here I know I shouldn't but the point of this video is not about the visualization it's about the generation so this will just draw a fill circle based upon the size of the star which already we now know because we have a star system object and the color so let's just take a quick look that's very nice we can see we've got a variety of different size stars not every single sector is populated with a snap and the stars are different colors but right now our universe is very very small because we can't move around in it if we want to move around the universe we need to know where we are within the universe so I'm going to create a 2d vector called galaxy offset this effectively represents the camera location inside our universe and in on user update before we draw anything we're going to handle some user input I'm going to be sensitive to the WUSA and D Keys being pressed to change the value of our galaxy offset vector bias fixed constant speed don't forget in the pixel game engine if we want movement we need to modulate by F elapsed time to make the movement smooth because the frame rate will vary depending on the load of your computer but you want it to move at a consistent visible rate we've done that many times before this galaxy offset vector effectively represents the top left of the screen and are nested for-loops going through all of the visible set is on the screen should be added to that offset to give us the real location in space so to our screen sector variables I'm going to add in our galaxy offset there's x and y now we should be able to move around the universe smoothly so if I move this way and we can see the stars are consistent going back it's actually it's a bit of a bold statement for me to say we can see the stars are consistent because none of us have memories that are that good let's just test the theory so here I've got a big cluster of planets hopefully that should be recognizable in the future let's mentally clock that one in and I'm going to scroll down for quite a while there we go and I'm going to scroll back up and hopefully we should find that cluster of planets again maybe that will demonstrate that it's consistent there it is now we've not stored that anywhere we've generated that cluster dynamically on-demand when we need it but because we've got complete control of our sequence of random numbers it is the same as having generated it previously and stored it because we don't actually care about the numeric value of our seeds the fact that our galaxy offset vector is going negative and positive depending on where we are in the universe doesn't matter it will always generate the same sequence of random numbers now that we've got this vast universe it would be useful to be able to interact with it sensibly we've got billions of planets we don't want to have to search through all of the planets to find which one have we selected what's its location and of course now we don't need to we know where our mouse cursor is going to be within the universe's space so we can just interrogate that sector location and get all of the information procedurally generated immediately for us to use as we see fit so I'm going to add in some mouse user input to going to get the screen space mount's coordinate and divide it by our number of sectors so again now we know which sector across the screen our mouse is in but because we can offset the galaxy we also need to know offset our Galactic mouse cursor so this vector represents the mouse on the screen but this vector represents our mouse within the universe as we're drawing the Stars out on the screen we can highlight which star might be underneath our mouse cursor of course it can only be underneath the mouse cursor if it exists so all I'm going to do is check whether the screens Mouse sector coordinates is the same as the sector coordinate we're currently drawing to and if it is I'm going to draw a circle around that sector let's take a look and though we can see a nice yellow circle around starts and it only appears where they exist so I've not had to do any searching in this instance and I say pound the screen across we can see occasionally we get that the circle popping up has accidentally put the cursor over a star system but it doesn't matter where we are in our universe it can immediately determine whether a star exists there universe is with just stars in are all well and good but not very realistic star systems need to contain other bodies so I'm going to create a structure called s planet and this is going to contain all sorts of different information about the planets and I'm not interested and I'm not even going to implement most of it I'm just leaving it here is an example that actually you can create this as detailed as you like you've just got to follow this process of always generating your random numbers in the same order and each planets not only is it going to have a bunch of material properties it may have a ring and it's going to have a selection of moons in our star system constructor there is no need to keep generating things if we know that we don't need them for example when we determine that a star didn't exist we immediately aborted the construction this means we could easily put gates within our system that will generate only up to the level of detail that we require so I'm going to add a boolean as a simple example up here generate full system when we're in the galaxy map view which we've just been scrolling around I don't care whether the stars have planets or not all I care about is whether the star exists it's only when I select one of the stars do I then need to go and generate a star with all of the planets and so if I don't care about generating the full system I'm just going to return immediately all I cared about was generating what does the star look like but now I do care what the planets look like and we'll get through this pretty quickly because I think we're getting to the point where I'm just repeating the same point over and over but to generate a planet I'm going to choose a random distance from the star because they don't all exist at the uniform distances from stars and I'm going to generate how many planets there might be okay it's a for loop to then go who all of these planets worn by one and for each planet I'll create my planet structure and I'll start to populate it with some of the information so each time I'm drawing more and more randomness from our sequence of pseudo-random numbers none of these numbers really are going to make any difference to this demonstration although it did occur to me that if you wanted to describe the makeup of a planet like this as percentages then you can't go over 100 percent so we probably want to normalize those numbers all of this is utterly irrelevant to procedural generation but I wanted to sort of demonstrate that once you start generating these very random bases you can manipulate this randomness as you see fit based on real-world equations based on previously drawn random numbers you could even go as far as to generate modifications to these random numbers based on the neighboring stars in the system if they exist or not you can also do interesting things with the probability distribution so here I've chosen a population value and it's choosing a random integer between oddly - five million and 20 million now you can't have a negative population but by using the max function in conjunction with this some planets just will have no population so sort of doing a two-in-one calculation with the probability here if we wanted to look at percentages like we did with these whether the star system exists or not does this planet have a ring well will draw a random integer and see if the value is equal to one so there's a 10% chance in this case of the planet having a ring perhaps the planet has been moons well in the same way as we've done the population by taking the maximum of a range which can go negative and take making sure that the maximum is always greater than zero we can generate a proportion of planets that have moons and a proportion that don't so in this case it's approximately 50/50 whether the planet will have at least one moon and therefore if it does have moons we'll create a loop that goes through all of the moons and all I'm interested in is the size of the moon nothing stopping you then going creating more and more planet bodies to the moons have their own unique mineral systems and properties that you want to try and generate once we've fully populated a planet I'll add it to the star systems vector of planets which we'll need to add as one of its variables back in the on user update function let's display the star system for a selected star to handle mouse clicking I'm going to be sensitive to the left mouse button being clicked if it is I'm going to generate the star system object based at the location of the mouse coordinate in the galaxy and if it exists I'm going to record the fact that it has exists by setting a flag to true I also want to cache that particular location at the moment I don't care about the planets and the moons so I've not instructed the star to be constructed with all of its planetary detail if the star at that location didn't exist I'll set my selected flag to false I'll just add these variables into the class as my star selected and my star selected vector now that we know we've got the system selected and we know its coordinates we can go about drawing it on the screen and I'll quickly go through this but I'm not interested in demonstrating the actual drawing routines want to display on the screen the entire system now and we know that we only need to do that if our star selected value is true but now I am interested in generating the full system you'll see a lot of magic numbers creep in now these are just to position things on the screen nicely they're actually unimportant to any of this algorithm but firstly I want to draw a window the blue window that's going to hold the information for our star and I also want to draw the star on the left hand side of the window so all of these coordinates and scaling factors are just to make it appear on the screen in a pleasing way let's take a quick look to see if things are working so far so I can select a star and then we've got our blue window and we see the star is the same color as the star chosen in the universe and if we choose a bigger star it's a bigger rendered star in our blue window let's choose this little tiny star over here and as before we can move to anywhere in the universe and continue doing the same thing if we select somewhere where a star doesn't exist the window disappears once we've drawn the star we want to draw the planets that orbit the star and so here I've got a little Auto for loop that's going through the vector of planets associated with the star system and again things are scaled and positioned accordingly the planet may have some moons in which case we need to then have another for loop that goes through the vector of moons for that particular planet all of my planets are just drawn as filled circles and so let's take one final look there's a universe to choose a system we can see the planets with associated moons of different sizes around those planets there's all sorts of variety and we know even though I've not visualized that these planets have different properties - about the composition and makeup and because we've used procedural generation with a high quality random number generator that's very fast we're guaranteed that we can always come back to a known position in the universe and it will be generated exactly the same way and so there we have it a persistent and procedurally generated universe all stored within about 200 lines of code and some fancy random number generation this has been a very simple demonstration of this concept but I'd like to go back to a point I made at the start that it's not necessarily the same as for example the Minecraft procedural generation routines nothing here is persistently stored it's always generated as in ways needed and this does cause some problems of its own how do we change the state of this universe in Minecraft for example the player will go and change the state of the blocks that are created that's quite tricky here and I think that's definitely going to be the topic for a future video as always the source code for this video is available on github from the link in the description below it's got a few more comments and a bit more material inside it if you've enjoyed this video please give me a big thumbs up have a think about subscribing perhaps come and have a chat with me and many others on the discourse server big thank you to all of my patrons or patreon is depending on where you from and I'll see you next time take care

Channel: javidx9

Views: 158,117

Keywords: one lone coder, onelonecoder, learning, programming, tutorial, c++, beginner, olcconsolegameengine, command prompt, ascii, game, game engine, pixelgameengine, olc::pixelgameengine, procedural generation, pgc, universe, elite, elite dangerous, star systems, content creation, asset generation, random numbers

Id: ZZY9YE7rZJw

Length: 41min 57sec (2517 seconds)

Published: Fri Jan 24 2020

Reddit Comments

[u/Gruddie]

I didn't want to watch the whole thing, but am curious; did he make it so it can be saved, or is it just a one shot generation?

[u/geldonyetich]

I'm not sure I agree with how he defines "procedural generation" and "automated generation" he talks about around 3:40. He says that if your algorithm is not simply generating things, on the fly, without any persistence, then it's not "procedural" it's "automated." Semantic quibbling enough? Odd that he doesn't think "automated generation" games like Minecraft are sufficiently "procedural," as it does have seeds that produce consistent results.

Speaking of semantic quibbling, I also find it a little confusing how he speaks as though he simultaneously wants to be random but also consistent with his results. Technically, then, not actually random. Of course, true randomness is fairly impossible on a computer, we can just get something that is "random enough" by seeding it with something unpredictable (he talks more about this at around 11:20, and I learned a bit about the importance of "robust" random number generators). Instead, what he wants is for it to appear random to the players.

At about the 18-20 minute mark, we get into some nice theory about how to use the robust pseudorandom numbers he's generating to make things look good. The rest of the video is pretty much a demonstration of how he breaks down his random generation into tables that do that. (About the 32-minute point he discusses how to translate a mouse vector, which is indeed another hurdle encountered with this strictly "procedural generation" method.) In my experience, once you have a suitably robust random number tied to coordinate shifts, you can pretty much do with it whatever you want, this part is easy.

However, for the purposes of a game, this is sort of the wrong way to go about it. (But a common approach - I would say that the vast majority of games that utilize procedural generation will do this to a middling-to-great extent.) Yes, it's easy enough to take random numbers and funnel them through some tables that you populate roughly on your understanding of how often various elements should be visible, and the result looks good to the human eye. However, my objection to utilizing this method is that generating things to look good is not the same as generating things to play good. It is a simple slip-up in core game design methodology that utilizes procedural generation incorrectly by forgetting the reason why you are using it: to create something the player plays.

If you do your procedural generation with the wrong priority first, you're stuck with it, it will be subtly undermining your game. Elite's universe generation (which this tutorial is based on) is actually a bit of a textbook example of this, as the universe structure does more to inhibit gameplay than enable it: it's big, and provides plenty to explore but, aside from being something to find, there's little rhyme or reason to its role in the gameplay. Thus, I somewhat interpret this video as an extremely well-done tutorial explaining how to emulate a method that misuses procedural generation, though the bit about the importance of "robust" random number generators was good.

[u/viewable2]

His stuff is extremely good

[u/thatdustyghost]

It's a very good video. I have used it to make something like this in Godot . :)

[u/skeeto]

He showed the Wikipedia page for a Lehmer generator, created a function called lehmer32, but what he implemented isn't Lehmer at all. It's an improperly-coded 64-bit splitmix generator. (Just as he speculated: His changes do compromise the integrity of the algorithm.) Wondering where he got this from, I did a search for his constants, but it only turns up his code. So did he copy this from some old, mistaken notes?

Fortunately for him, an actual Lehmer generator wouldn't have solved his problem, and the result would look more like his experiment with rand(). However, at the core of splitmix is an integer hash function, which is what he really needed, at least initially, not a PRNG.

[u/InuDefender]

His other videos are also very interesting. He made a tutorial for building a NES emulator.

[u/i-think-its-ok]

Thanks so much for your informative reply skeeto! I’m learning so much.

Regarding my “between 0 and 1” comment: I dint understand % as the modulo operator. I typed multiply in my code. I thought he was getting a random number by multiplying a maximum value by a fraction of one. I see now that he is using modulo. Very cool.

Thanks for the python code line. I couldn’t get it to work. I added “import math”, so that is not the problem. Splitmix64 throws a nameError.