Yes, two more, but they will be towards end of February, mappers, and then one on finishing the audio. I felt the channel needed a break from NES as not everyone was interested, especially as you start getting to parts 7 & 8, which demands huge commitment from only the most die-hard of viewers, but also I needed a break, as I'd done nothing but NES emulation for almost 9 months XD I get that for those following along, a small wait is frustrating, but from my perspective, the series will be around forever, so all those in the future watching will be able to watch the whole thing. During my time off, Ive been working on a couple of small non-NES related projects so I'm gonna show those, then complete the series.
@@javidx9 great, I don't mind the wait - I've been thinking about getting back into C++ again, and think following along from the beginning will be a good brush-up 😀
It was also necessity for early games, wasn't any storage to be had! Starflight is another great example of using procedural generation to create a vast universe.
I think the word you're looking for is: Deterministic. The PRNG will generate a sequence of pseudo-random numbers, and that sequence will be deterministic. I like your distinction between procedural generated and automatically generated. I don't know if this is the common understanding of the term, but it seems useful and so will adopt it.
I am launching my channel in the next few weeks covering live development of a chaotic ;-) procedurally generated game i'm making - including all aspects from C#, Unity, 3d modelling, design, algorithm details, decisions, theory - the whole thing - not hiding anything, in the hope of it becoming community driven with design decisions. It will cover some basic ideas around procedural generation and show how I did it in detail. I use a simple method and build on it a little bit but it will give a decent practical example nonetheless. It might be worth checking out if you have an interest and offers at the very least my take on a very varied (random ;-) topic).
Best idea about creating the universe is creating the idea of the universe. Meaning knowing how it looks is always the most important part of the creation otherwise it wouldn't be experience in our view. There's a huge amount of thought that goes into the creation of the placement of the objects, but it's quite importantly the most complicated thing to recreate simply because of overlap, but with the right theories, you can create what is called a fractal norm which is perceivably the closest thing to proper representation. With the correct correlating variables, the fractal norm can be diluted into a more visible form which will create a resulting overlap of equations and understandings using numerical constant values for a particular time in space. That being said … thanks for making the thing that I asked you to do.
I really like your videos, not that it means much, but I think you are clear and articulate and actually have a personality so salute sir keep going, I love them..
in the video you had mentioned that you hope in the future there will be hardware based random number generation, this already exists! Its called RDRAND, c++ even has intrinsic functions for processers that support it!
Concerning the distinction between procedural generation and automatic generation, I'm reminded of a classic PC game that did both: Starflight. Resources like fuel, minerals, and life forms were automatically generated, but the terrain itself was procedurally generated, and as far as I know, is one of the first games to do so. For the same reasons described here: the game had to fit on one floppy disk, and there was no other way to "store" the terrain data for over 600 planets in such limited space. The resource data was only stored for a much smaller area in the vicinity of the player's ship, and became "forgotten" and re-generated as the player explored.
It may be more appropriate to use a hash function (like xxhash) instead of an RNG (random number generator). In this small example it doesn't matter, but you might run into problems if you try to make a full game with this RNG approach: - The universe size is constrained to 2¹⁶×2¹⁶ because the star position is used as RNG seed, and the seed is a 32-bit integer. A hash function maps _any_ number of input bytes to a random number, so a practically boundless 2⁶⁴×2⁶⁴ universe would pose no problem at all. - If you want to create a different world every time a new game is started, you must provide the RNG with additional input; simply generate a random "master seed" before the game starts, and use it as input. So for example, to determine if an (x,y)-coordinate contains a star system, you would use [masterSeed,x,y] as input rather than [x,y] alone. A hash function makes it trivial to add extra input, but the 32-bit RNG seed has no room left. - The star generator is sensitive to changes because the RNG is seeded once, and then used to generate a _sequence_ of random numbers. So if you were to change the order of rnd*() calls (or add/remove calls in the middle), you'd end up with a different universe. You could instead use the hash of [masterSeed,x,y,1] to determine the star radius, [masterSeed,x,y,2] to determine the number of planets, [masterSeed,x,y,3,planetIndex,1] to determine the number of moons for a given planet, and so on. This is more robust against changes, because the output depends only on the input, not the order of calls.
Thank you very much. I'm setting this up in Unreal and am really struggling to normalize the lattice with my coordinate offsets. Yep, I discovered the same thing (and why Minecraft is so weird with its directional biases lol) I lose total generation volume for every additional axis I add to nProcGen because earlier values must be made sure to be larger than other values after the bitwise or. UINT64_t u64_h; u64_h = UINT64_MAX / 2; seed1/2/3 = u64_h + (offset x y or z); was promising until realizing the uints are just overflowing after bitwise and still nullifying. Not to mention, I cannot for the life of me, get Unreal to play nice with uint128 for lehmer64. Anyways, again, thank you very much for sharing your knowledge! Edit several hours later: Yeah, his units increment by 50 and mine increment by 'double', so normalization isn't a problem for the 2D demo because (I think) the base movement unit is larger than sector size. So with double, normalization just takes the floor of the quotient 'PlayerPos/n' where n is 'static ... RenderBase/SectorBase'. And now, I'm having fun flying around exploring a procedural infinite lattice of debug spheres that gets weird super fast so I definitely have to implement XXH3 😆
or* godmother lol I'll reply with the title to reference near its release, and you definitely get a free copy (Steam-key (best for updates), raw-build, -console port,- whatever works best for you). In addition to the personal free copy/key, the game will also be free on Steam for the first day or so 😄
@@defeatSpace Awesome if it turns out to be useful :D It doesn't have to be xxhash, just anything that takes an arbitrary-length sequence of data and turns it into something "sufficiently random". If performance isn't important, then something like md5/sha1 works great :-)
That was a facsinating discourse. I've played elite dangerous horizons many times and am amazed at the extent to which you can keep zooming in right down to individual stones and pebbles, and they are still there when you come back. I don't pretend to understand the mathematics but the principles are clear to me now. I bet George Boole would have been glued to the screen every second.
"How do we change the state of this universe?" Anyone else watched 41:18 out of 41:57 waiting for that question? lol. only to be teased and left with no answer. my disappointment is immeasurable and my day is ruined. also 10/10, will watch again.
@@____uncompetative Yeah. You generate a planet and save it to disk. Then if the player blows it up you store something like "planetABCExists: false" in the save file. Then when the player comes back, you generate the planet again and then apply the changes from the save file
@@ShadowGaro You actually don't have to store the planet to disk as soon as it's generated. That's what he means by the the difference between automated and procedural generation. Generating from a single stream of random numbers and then storing it is automated generation, while procedural generation means you only store the differences from what the algorithm produces repeatedly, each time you reload the asset. There is, however, no reason why Minecraft couldn't just store the differences. Might be an efficiency thing. Disk space is cheap, after all and it saves processor time. There is even some derived data, like lighting information and height maps for viewing from a distance in the savegame.
@@____uncompetative Right, a technique like event sourcing. Store info about the changes that happened over time and you can replay that from any point. Basically generate the universe and then record its history
bluescanfly1981 Imagine a clock face which is segmented into twelve compartments you have two coloured hands which can be freely rotated to point to any compartment. These don't represent hours and minutes, don't move according to real time, and the movement of one doesn't have a side effect on the other. Now imagine a brick wall in a First Person Shooter and the player firing a bullet from their gun at it. The game would be more realistic if the brick wall is damaged by being shot. We don't need full collapsing destruction, just minor damage to be recorded otherwise it will seem oddly impervious and lack verisimilitude and break our player's immersion. So, we need to mark a bullet hole on the wall that we will just make a cavity rather than something we can see through. This means we aren't going to bother with bullet penetration and working out the reduced velocity and damage it might then cause another player behind the wall. This is a simple conceptual example. So, we have the player fire their gun and create one cavity in the brick wall. What happens if we continue? Can we reasonably store every cavity formed by all the ammunition used in the entire match. Well, that would be the brute force solution and is possible and would look the most convincing, but with limited memory it is very common to optimise this and hope no one stands infront of a wall spraying bullets in the hopes they can write their initials. The clock face of twelve compartments will contain the maximum number of X, Y coordinates on the wall texture at which to place a cavity. After twelve bullets have been fired the thirteenth needs to find space to be stored, but HELP! we only budgeted for twelve, so what do we do? Well, the solution is to overwrite the first cavity we stored and hope no one notices. If you continue to fire then the fourteenth bullet takes the compartment that was used for the second cavity formed, and so on, all around the clock face until the cycle repeats. So, new bullet cavities erase the earliest still remaining cavity. This can be implemented very simply in a 12 row x 2 column array (with each row providing a pair of compartments in each of the two column spaces to store the X and Y coordinates of the bullet cavity) which has an integer variable that initially refers to the 1st row and is then incremented by 1 to advance around the clock face. You don't need IF / THEN logic to determine what to do when you run out of rows to store X, Y pairs in columns as you actually store the X, Y pair at the the new value of the variable which is determined by the old value of the variable + 1 modulo 12, ensuring that it never hits 13 as it will wrap around back to 13 - 12 = 1. See this article for details: en.wikipedia.org/wiki/Modular_arithmetic A professor would probably teach you to use a double-ended queue (which would be far more flexible, and could expand and contract in scope according to dynamic need, but this would also need to be garbage collected, which could prove slow, and why do we even need to bother when we only need to store 12 bullet cavities in 24 storage cells, and leave this static data structure alone at a fixed location in memory and reuse it whenever we need, pairing it with the wall texture so that additional walls can gain their own accumulated signs of damage and shots fired on wall B by one player do not erase the bullet cavities another player sees in front of them on wall A. The major downside of just simply reserving a pair of cells for storing an X, Y bullet cavity for every bullet that could theoretically be fired in a PvP match, is that this approach breaks down when you have something open ended like a PvE campaign that could be played for four hours at a stretch. So many bullets are fired, on all sides, that this would be a large allocation of static memory to store all of this. Genuinely possible for a single level of a campaign. You could also store all the corpses created and then make the player backtrack at the end to the extraction zone and see the damage they wrought on advancing to the defended objective and blowing it up, but then you look at a game like _No Man's Sky_ with 2^64-1 planets and you realise that there is not enough storage on all the PCs in the world combined to record everything you could do to modify things, so the notion of erasing trivial stuff you did so long ago in the past you can't remember doing it becomes essential. You can also have multiple data structures storing these "memories" and keep the more significant actions around far longer, but balance this by making them less trivial to accomplish in game (such as collectively destroying a space station with your friends and returning to see that the X, Y, Z, T space-time coordinates of that "huge event" had been added to a checklist so that it would regenerate the star system procedurally entirely deterministically and then go "Oh, wait... we don't have that space station as it was destroyed last Tuesday" and get rid of it (then work on having it rebuilt if the local economy has need of another and can afford it, and have it also have features of the affected economy E, C, S, R so it can model the recovery of trade and reconstruction of the Station whilst you are away, as some process that could be procedurally derived from the time it happened T (compared to the time you later return, T2) in which interval you can determine if it has been rebuilt or is still under construction. Alternatively, you can store another four cells (which you would definitely need to do if modelling a background server based economy even based off a probabilistic approximation of all trade taking place in the entire galaxy). However, this is getting into complex territory and may not even be necessary if not a focus of the gameplay experience.
Good morning, Javid! You read my mind in this video, for I have been musing about the very same programming challenge as of late (though for a terrestrial setting, not a stellar one). I can't watch your entire video right now, so I will come back to it in installments.
I recommend to have a look at perlin noise and its derivates. It is usually used to generate terrain and textures. The way I understand it, multiple, randomly generated, smooth curves are overlaid on top of each other to simulate mountains ranges (large scaling factors), single peaks and valleys (medium scaling factors) and the single rocks etc. (small scaling factors).
Such a serene narrative, quite hypnotic actually. No debugging necessary. We are moving quite casually from A to B to Z. Of course, rand is rubbish and the mersenne-twister is slow. That is why everybody chooses Lehmer random numbers ... Keep up the great work :)
I'm completely honest, the first I came on to your channel, I was mostly pissed of, because I searched for things like algorithms and procedural generation. But I was completely new to programming (which I'm still) and needed those things in Java... :) And your videos "blocked" the RUclips search page, whilst they gave a lot of information about how to do in theories but still not showing how to implement it in Java... (Yeah I'm dumb to judge a channel about C++ by not showing stuff in Java). Complete misjudgment... Your videos are by far the best about algorithms and so you can find on RUclips. And really want to thank you for your effort!!!!
What a happy coincidence, I've been dabbling in my own procedural universe for little over a year now. Your excellent explanations would have saved me a lot of headaches early on as I was learning programming and experimenting with procedural generation. I love your videos, they keep me motivated and I find them very helpful even though my main focus is Unity w/ C#.
Thanks Zorbaq, I try to show things in a language agnostic way. You could take a technique like that shown and implement it in whichever platform you prefer, I just find C++ simple and convenient.
ideally there should be a function to check if there had been player interaction with the world in order to avoid bloating up memory, since a portion of playing minecraft comes down to crossing massive oceans or roving across reaches of land that often provide no unique reason for players to interact with them
@@Gogglesofkrome But just being in a chunk in minecraft will change it since there are mobs moving and plants growing and as soon as a chunk is created that process is started and the state of it is changed from before. So yes some chunks might not be changed in a visual way, but still there often are changes. This was discussed in detail in a video regarding one anarchy server where hacked clients are used to find player bases by identifying how much each chunk had changed from the original creation, thereby allowing the searcher to see how long the player had been there. So, in theory you might save a bit of space but that was not the primary priority.
@@davidmartensson273 Most biomes don't have anything growing while you pass through them, and mobs aren't dedicated to memory so long as they haven't been fed or tagged, with the only exception of the enderman, which is the only mob that changes the environment without user interaction. If you're running through the landscape and not touching so much as a thing on your way through it, then it would be effectively identical to a fresh map gen, and as such if the developers were more storage optimization focused, this generated data wouldn't be saved. The reason it is saved is to spare the processors the repeated effort of regenerating the same areas over and over again.
@@Gogglesofkrome the problem is speed. Generation causes lag in Minecraft because procedural generation takes time. So if chunks weren’t saved to memory, every time you cross over a chunk you’d have to generate it again. A lot of this is due to the fact that Minecraft is not multithreaded. If chunk generation were on a separate thread you could do it this way.
@@fpsoftdev this issue of speed is generally what I was referring to when I was talking about the generation being used to spare the processors the repeated effort of regenerating the same areas over and over again. It's too bad minecraft came into existence within that time period that multithreading had only just become widely available; otherwise a lot of the issues of performance on a general level wouldn't exist.
Great topic! I was thinking about just this sort of thing recently. I think the biggest problem for me was how do you know what you are selecting and I love your solution and how simple it is. That was also a great example of the default random generator. I honestly never really cared about the whole random number problem, but that demonstration really opened my eyes. ... Although Minecraft does store the world, it does add to it as you play, it generates a larger and larger world as you explore, but then saves it. It uses a fixed seed to create the same world, which I have tested from seeds I have seen online. I am not sure if you could get away from saving something in a game like Minecraft where the world is altered by the player so drastically. Perhaps you could just save what you alter, so it is procedurally generated, then the changes are loaded in? Could be a solution. You would still be saving something, but only what has been altered. Great topic anyhow, if you have a solution where nothing would need to be saved (except perhaps a user defined seed) I would like to see it. I suppose it depends on the game itself. Certainly SOMETHING has to be saved in a persistent universe where the player is changing, building etc.
Yeah I think that is the only feasible way to store a universe this large quickly enough, difference maps are definitely the way forward if anyone were to continue this idea.
Cheers Javid for another great video. Can't wait to give up real life so I can spend all day playing with code. One day. There's another channel that does a series called coding adventures that does game related programming exploration and mathematical modelling. Between the two of you I plan to build a library of skills and techniques and begin my own journey to make dumb programs and games. That's my dream, and it's enabled thanks to you Javid. Thank you.
Minecraft is procedural in the data generated for a given seed, but once that level data is put in motion it needs to be saved. Fire, water, and NPC's can alter the generated data. If your universe had a Deathstar that destroyed planets you'd need to store that information somewhere as well. No Man Sky works this way as well. Modern processors do have a "real" random number generator, but it's "slow" and should probably only be used for seeding a quality PRNG. Thank you for the wonderful videos! [just finished the video - you mentioned the above at the end] :P
What you want is a hash function, or even a set of hash functions, not an RNG. The technique is to hash the "key" value (your coordinates, for example) and use the bits of the hashed result for your "randomness." You don't need a crypto-strength hash either.
After learning the generation method, i'm really interested in the storing process of interactions with procedural entities, glad you'll make a video about it :)
Just store the changes in a hash table with the sector as the key. Then retrieve that entry when you need the data. Store the hash table along with the seed to disk to get a save file. Tada!
Cryptography actually requires both real random numbers (which are generated in hardware) and pseudorandom numbers. Using your star system as a parallel: It is important that if two people determine the information about a star system at the same coordinates, they get the same results. However it is also important that given the properties of a star system (but not its position in the grid) it very hard to deduce the original seed (or grid position) used.
Another excellent video. Very concise, and lends a very practical description. I have an entire book on procedural generation that might make more sense now. Thank you!
Short, sharp, funny, and to the point…a bit like impaling really 🤣 I always look forward to your videos and I even manage to understand some of it still. Thank you!
I've always had sort of a vague idea of how this works, but seeing is really cleanly (and simply!) laid out has inspired me to open up a code editor for the first time since new-year! Also, not sure if I'm wrong or if this is just a nitpick, but I'm fairly sure Minecrafts world is procedurally generated, since the game does have the concept of seeds that will re-create an identical world every time it's input (even on another machine etc). It does also generate new chunks on demand. I think the reason it's stored on disk is because it's faster, due to the sheer amount of generation that is done per chunk, it's faster to read-back from disk after creating it once. So, the storing to disk part is not critical to the creation of the world, but rather convenience and speed, and as you alluded to at the end, to store changes to the world. But maybe that's what you meant? And, I'm really looking forward to seeing how persistent changes can be implemented! I'm imagining it comes down to basically storing the changes to disk, rather than storing universe chunks. That way, you only need to store the changes the user has actually inflicted on the world, which in comparison to the entire universe is obviously tiny... But interested to see the details of that.
As far as I know, Minecraft procedurally generates all the chunks except for the ones which were updated by a player. However, even in this situation, only the changes are stored while the chunk is regenerated on load. Loading from a disk will always be hundreds of times slower than generating even the biggest of terrains.
@@MrAlaxUA I'm not sure that's true, every chunk that MC generates is stored and compressed to disk in its entirety: minecraft.gamepedia.com/Chunk_format Including lots of extra data like precomputed light data etc. But this happens regardless of whether the player makes changes to the world or not; it's still loaded and saved to disk after initial generation. The CPU load from generating chunks is actually really significant, so loading from disk is preferable, because its not resource intensive (each chunk is only about 50MB or so). This frees the CPU to actually be busy drawing and simulating the loaded chunks rather than regenerating them on the fly every time, which when you think about it, would be a colossal waste of processing power - why re-generate every time you load a chunk, when you can just do the work once, and store it? The MC world is incredibly complex, so it makes sense to do it that way. If the world is trivial though, its faster to do it on the fly. Up to a point, at least.
@@Mythricia1988 Exactly, in some modern games we can even hear about generating terrain/chunks etc on GPU because generating them on CPU would not be fast enough for real time game (for example games with voxel terrain where you can make holes etc in terrain).
The chunks that are modified must be stored to disk otherwise the changes that the player made will be reverted. Procedural generation creates worlds but does not track the changes on them. You can be smart and just track the changes themselves though. For example block(0,0) is dirt, block(10,12) is air, etc.
This is one of the best, if not the best, channel I've ever discovered. It is useful from start to finish... also to improve my English. Thank you to exist sir.
I dont think it was a random number generator which put this video in my recommended feed. No, it was meant to be. I dont code but Ive been wanting to watch people code and talk about what they think while they do, so I really appreciate your video and like your style of guiding it along. New subscriber!!!
Excellent video. You briefly touched on gaussian distributions but I'd like to expand on it. You can actually very easily create gaussian distributions by summing multiple random numbers. For example rand(6)+rand(6) will have a maximum of 10, a minimum of 0, but values will concentrate around the middle. In some cases this can be more realistic, for example heights of humans. You can also create unbounded distributions. Consider the following code: int nMoons=0; while (rand(2)==0) ++nMoons; There's a 50% chance of no moon, 25% chance of 1 moon, 12.5% chance of 2, 6.25% chance of 3, and so on to infinity. As you explore you will find planets with more and more moons, and even the developer won't know what planet has the most moons unless he writes code to search for it.
This brought back fond memories of Elite:Frontier, which was the first one I played and loved, and how it had a whole frickin' universe to explore in glorious A500 colors while only occupying one single 3.5" disk. That blew my mind back then. Countless cargo shipments to and from Barnard's Star wasn't that fun, though, haha!
As others have noted, Minecraft is based upon deterministic seed world generation. That's why Minecraft speedrunners search for seeds with a particular world generation.
I disagree with your definition of procedural generation at the start of the video ... or maybe only with the given examples. Minecraft does procedurally generate it's world, it only needs to store the information to save the changes made in a chunk, it will always generate the exact same initial world state given the same seed and version of the game. It's not just random and needs to be saved to be persistent, if that would be the case then i would agree with you, but neither Minecraft nor most modern rogue likes work this way. Most, if not all of the ones i know, can perfectly recreate the whole world/dungeon based on nothing more then the seed and a location, for every player in the exact same way. Daily runs are a popular thing in modern rogue likes and they stem from the fact that every player will generate the exact same level just by using the same seed, so developers only need to define a daily seed so that every player can run the same level and competing for the daily highscore.
Superb content. The idea is quite clever imo, I had only vaguely known about some of the very basic concepts. It is much clearer to me now. Can't wait for more.
My first thought for changing state in such a system, if change occurs, generate and store changes, check for changes at the coordinates selected as you select.
I loved this. It was like watching that show a few years back with a secret magician explaining how a bunch of magic tricks actually work. Thank you :)
One of the best tutorials for procedural generations or as i like to call it (seeded random number generator with rules) starters ...... much luv mate. Keep up the good work. Would love to hear more.
You should extend this example at some point, I would love to see how you handle seeds for stuff generated on a planet. like give them each a world map of countries, each with information about them, then you can view cities in that country, then buildings in each city, rooms in each building, characters in each room.
I use 480p to save bandwidth and in this video, it was fun to watch how youtube is struggling to compress the video :). super fascinating subject, but still I'm lacking some c++ knowledge to fully understand the code, but every day less and less. Regards everybody
Rand was actually twice slower than the later generators! 0.006 vs 0.003. Awesome video. If you love Elite - consider trying it with a head tracker (or high res vr)
41:20 that question came to my mind few minutes before you asked it and i gave it a thought. Probably i would use some map, where key would be taken from generation algorithm and value would be difference between generated state and current state. This solution breaks your definition of procedural generation, but quite simple.
I always enjoy your videos. I have spent my whole career in IT but from a business programming perspective. Always wanted to code in Graphics, i find it fascinating. This was very refreshing. I will be trying this soon... Thanks.
@@javidx9 thanks for the reply. I too have been a follower of Elite. I have one question, trying to get olcPixelGameEngine working in VS2019. I have the include statement in the code but it cannot seem to find the file. I have included it in the project linker general additional library directories. Any thoughts? Regards Dave.
@@davidchapman3228 The easiest way is to just have the .h file in your project folder, and include it as necessary. there is nothing to actually link. This may help: ruclips.net/video/eTGSTTxR-Ss/видео.html
One mistake that many make with procedural generation is to make things completely random. But a screen showing white noise (completely random content) is just as boring as a blank one. What hat allows you to stare at art for hours but not photographs or ingrain wallpaper are new patterns: 1. You don't already understand what's going on (nontrivial/novel) 2. You sense there is something to be understood (structured/tractable)
A few random ideas: - Procedurally generate short strings of words (extracted from a dictionary), then use those words to search google images, and display the top image as the background of the players position in a game. For consistency, prepend a constant or pre-generated sequence. e.g. "'New York Street' scarf tram baby", "'New York Street' blob accountant time" - As above, but use a restricted dictionary of things like texture names, or peoples names, or other elements of a game. - As above, but use those as a prompt into GPT2. - Use the seed as a lat long, limited to a high population area (e.g. NY, LA, etc...) and then convert that into a street address, and use that as a prompt into GPT2. The point, in general, is to use apparently random values (but which are actually procedural seeds) as prompts into real world databases.
I once wrote a "less random" random (something like Perlin or Simplex, where a small change between input values facilitates a small change in the output) in Blitz3D by using the seed. It would get the random values at each corner of a cell (by seeding using the X and Y of that cell) and then linearly interpolate inbetween them. It was an interesting approach, and it worked pretty well for the purpose of a game written in Blitz3D. In C++, I'm guessing rand() stores the old seed, randomizes the seed and stores it, and then returns the old seed. It'd probably work after another call to rand(), but that'll essentially halve performance. Of course, half is relative. However, I think at that point, you might as well just copy the random generator code and have the seed be a constant value that's combined with the X and Y bits. That's how I would approach spatially-consistent (if that's even a term) randomness at a low level with pretty good performance. Distribution should be good (if the core RNG routine is also pretty good) but gradient leaves room for imagination, but you can solve it with what I did in Blitz3D.
Just discovered your channel and this was the first video I’ve watched. Awesome stuff, definitely interested in the universe “persistent state” and modifications you alluded to at the end. Now to go back to some of your earlier stuff. I’m not a c++ man so will need to jump a few steps back now
To be clear, for a different universe I could have a seed # which together with position gives me the same Galaxy with the same Galaxy seed every time. I could potentially do a 3D cube of stars and check each cubic light year, then randomly locate a star within that lyr^3. So for Galaxy 731 I could warp to a hundred lyr cube at 5300 by 11300 by -100 lyr and quickly check 5332 by 11321 by -123. If it exists, I can further use randomness generated from the seed for that location to place it at 5333.31 by 11321.53 by -123.02
This is extremely interesting and fascinating content. I enjoy a lot that restrictive definition of procedural generation, it carries elegant design ideas. I wanted to know more about this subject, so, thank your very much for that
For my project i had to use random to know where flowers should be, it was the same as with your planets I used a hash library called xxhash, because it's very fast, and i can hash the seed and the output will be consistant, and looks like random!
I'm actually making a game with this as a premise. I wanted a huge world, with the player being able to change some things in some places, but creating each effect by hand would be just about impossible. So i implemented a similar'ish' method to calculate the effects each time the vicinity is loaded. It's still a work in progress, so much that i won't make any part of it public, but maybe someday.
The interest of PRNG is to produce long sequences of random numbers from a seed. Generating only one seemingly random number from a seed is better done using a hash function.
Well if you wanted to manipulate your universe after it's been generated then you have to save either the changes on disk and load them as the universe is generated. Or you would have to save all of what was generated on disk with your changes and load those parts of the universe from disk to maintain level persistence. But at the core of that system, you still have to generate a level though a procedure rather than manually creating the level by hand. And yes, I did watch til the end of the video. A procedure is a procedure
i've been a fan of elite since i got hooked on the zx spectrum version in the early 90s. i also spent some time on elite: dangerous in recent years, though not active anymore. and although i always knew what procedural generation was, this is still a very enlightening video.
Linux provides /dev/random which is a virtual device providing truly random numbers. The system uses every random thing it can to generate these numbers and turns out there's not much randomness inside computers. Common sources of randomness are voltage in circuits and user input. These are very slow sources so is the generation of truly random numbers. The funny thing about it is that if you provide enough input, by moving cursor for example, /dev/random becomes noticeably faster.
Some people can draw near-perfect circles on chalkboards; but at 19:36, it appears that other people can draw near-perfect Gaussian curves instead. With a little practice, you could be one of them!
I think it is wrong to think Minecraft automatic generated because the reason why it store it's chuck because the player interact with those chunk so it need to note down what has changed. With the same seeds, Minecraft can recreate the exact copy of the world just like the one you have here.
Any lookup with the random generator should be preceded by a lookup in a table. If the entry in the table isn't found, proceed with the random generator, else use the result in the table and ignore the random generator for that lookup. That way you can have the table represent the state after the player has interacted with the world.
Sorry for asking, but is the last videos about the NES emulator still on the drawing board? :)
Yes, two more, but they will be towards end of February, mappers, and then one on finishing the audio. I felt the channel needed a break from NES as not everyone was interested, especially as you start getting to parts 7 & 8, which demands huge commitment from only the most die-hard of viewers, but also I needed a break, as I'd done nothing but NES emulation for almost 9 months XD I get that for those following along, a small wait is frustrating, but from my perspective, the series will be around forever, so all those in the future watching will be able to watch the whole thing. During my time off, Ive been working on a couple of small non-NES related projects so I'm gonna show those, then complete the series.
@@javidx9 great, I don't mind the wait - I've been thinking about getting back into C++ again, and think following along from the beginning will be a good brush-up 😀
@@javidx9 please make copy Agar.io
So, instead of storing something in memory, we store it in the algorithm. That's really smart.
That's exactly it Dante, wonderfully phrased!
@@javidx9 Thanks
It was also necessity for early games, wasn't any storage to be had! Starflight is another great example of using procedural generation to create a vast universe.
Until you want to modify that thing..
Mind Blown 🤯
As someone who *REALLY* loves procedural generation and wants to get into it,you have no idea how valuable this is,thank you so much!
Carl Sagan: "If you wish to make an apple pie from scratch, you must first invent the universe."
javidx9: "say no more fam"
31:34 And there it is again, the "cluster of planets" (stars actually). He scrolled left and right, down and up, and found his way back!
J: Let's procedurally generate the universe"
Me: * spits tea everywhere *
I think the word you're looking for is: Deterministic. The PRNG will generate a sequence of pseudo-random numbers, and that sequence will be deterministic.
I like your distinction between procedural generated and automatically generated. I don't know if this is the common understanding of the term, but it seems useful and so will adopt it.
I love this procedural generation topic! Always wondered how it's done, this is a great video. Thanks for sharing!
I am launching my channel in the next few weeks covering live development of a chaotic ;-) procedurally generated game i'm making - including all aspects from C#, Unity, 3d modelling, design, algorithm details, decisions, theory - the whole thing - not hiding anything, in the hope of it becoming community driven with design decisions. It will cover some basic ideas around procedural generation and show how I did it in detail. I use a simple method and build on it a little bit but it will give a decent practical example nonetheless. It might be worth checking out if you have an interest and offers at the very least my take on a very varied (random ;-) topic).
Best idea about creating the universe is creating the idea of the universe. Meaning knowing how it looks is always the most important part of the creation otherwise it wouldn't be experience in our view. There's a huge amount of thought that goes into the creation of the placement of the objects, but it's quite importantly the most complicated thing to recreate simply because of overlap, but with the right theories, you can create what is called a fractal norm which is perceivably the closest thing to proper representation. With the correct correlating variables, the fractal norm can be diluted into a more visible form which will create a resulting overlap of equations and understandings using numerical constant values for a particular time in space. That being said … thanks for making the thing that I asked you to do.
I really like your videos, not that it means much, but I think you are clear and articulate and actually have a personality so salute sir keep going, I love them..
Hey thanks Gleem!
in the video you had mentioned that you hope in the future there will be hardware based random number generation, this already exists! Its called RDRAND, c++ even has intrinsic functions for processers that support it!
Concerning the distinction between procedural generation and automatic generation, I'm reminded of a classic PC game that did both: Starflight. Resources like fuel, minerals, and life forms were automatically generated, but the terrain itself was procedurally generated, and as far as I know, is one of the first games to do so. For the same reasons described here: the game had to fit on one floppy disk, and there was no other way to "store" the terrain data for over 600 planets in such limited space. The resource data was only stored for a much smaller area in the vicinity of the player's ship, and became "forgotten" and re-generated as the player explored.
Your lack of adherence and therefore respect for customary use of seed value 42 in the making of universes is appalling. Shame, sir. Shame.
But then you'd just get the Hitchhiker's Guide to the Galaxy universe, which lots of people have seen already. Wouldn't you rather see something new?
In the beginning the Universe was created.
This has made a lot of people very angry and been widely regarded as a bad move.
42 is what you make of it.
YES! A new Javid video! I haven't watched it yet but I always get so excited. Guess what I'm going to use my weekend with? Visual Studio and Javid! :D
A whole weekend programming! Bliss!
It may be more appropriate to use a hash function (like xxhash) instead of an RNG (random number generator). In this small example it doesn't matter, but you might run into problems if you try to make a full game with this RNG approach:
- The universe size is constrained to 2¹⁶×2¹⁶ because the star position is used as RNG seed, and the seed is a 32-bit integer. A hash function maps _any_ number of input bytes to a random number, so a practically boundless 2⁶⁴×2⁶⁴ universe would pose no problem at all.
- If you want to create a different world every time a new game is started, you must provide the RNG with additional input; simply generate a random "master seed" before the game starts, and use it as input. So for example, to determine if an (x,y)-coordinate contains a star system, you would use [masterSeed,x,y] as input rather than [x,y] alone. A hash function makes it trivial to add extra input, but the 32-bit RNG seed has no room left.
- The star generator is sensitive to changes because the RNG is seeded once, and then used to generate a _sequence_ of random numbers. So if you were to change the order of rnd*() calls (or add/remove calls in the middle), you'd end up with a different universe. You could instead use the hash of [masterSeed,x,y,1] to determine the star radius, [masterSeed,x,y,2] to determine the number of planets, [masterSeed,x,y,3,planetIndex,1] to determine the number of moons for a given planet, and so on. This is more robust against changes, because the output depends only on the input, not the order of calls.
Interesting. Curious to see the result
Thank you very much. I'm setting this up in Unreal and am really struggling to normalize the lattice with my coordinate offsets. Yep, I discovered the same thing (and why Minecraft is so weird with its directional biases lol) I lose total generation volume for every additional axis I add to nProcGen because earlier values must be made sure to be larger than other values after the bitwise or. UINT64_t u64_h; u64_h = UINT64_MAX / 2; seed1/2/3 = u64_h + (offset x y or z); was promising until realizing the uints are just overflowing after bitwise and still nullifying. Not to mention, I cannot for the life of me, get Unreal to play nice with uint128 for lehmer64. Anyways, again, thank you very much for sharing your knowledge!
Edit several hours later: Yeah, his units increment by 50 and mine increment by 'double', so normalization isn't a problem for the 2D demo because (I think) the base movement unit is larger than sector size. So with double, normalization just takes the floor of the quotient 'PlayerPos/n' where n is 'static ... RenderBase/SectorBase'. And now, I'm having fun flying around exploring a procedural infinite lattice of debug spheres that gets weird super fast so I definitely have to implement XXH3 😆
Sqax, you're the godfather of an imminent cultural phenomenon.
or* godmother lol
I'll reply with the title to reference near its release, and you definitely get a free copy (Steam-key (best for updates), raw-build, -console port,- whatever works best for you).
In addition to the personal free copy/key, the game will also be free on Steam for the first day or so 😄
@@defeatSpace Awesome if it turns out to be useful :D It doesn't have to be xxhash, just anything that takes an arbitrary-length sequence of data and turns it into something "sufficiently random". If performance isn't important, then something like md5/sha1 works great :-)
That was a facsinating discourse. I've played elite dangerous horizons many times and am amazed at the extent to which you can keep zooming in right down to individual stones and pebbles, and they are still there when you come back. I don't pretend to understand the mathematics but the principles are clear to me now. I bet George Boole would have been glued to the screen every second.
"How do we change the state of this universe?" Anyone else watched 41:18 out of 41:57 waiting for that question? lol. only to be teased and left with no answer. my disappointment is immeasurable and my day is ruined.
also 10/10, will watch again.
Revan Johnson
You create a list of differences which are made to revert back to the procedurally generated state over time so only a little is stored.
@@____uncompetative Yeah. You generate a planet and save it to disk. Then if the player blows it up you store something like "planetABCExists: false" in the save file. Then when the player comes back, you generate the planet again and then apply the changes from the save file
@@ShadowGaro You actually don't have to store the planet to disk as soon as it's generated. That's what he means by the the difference between automated and procedural generation. Generating from a single stream of random numbers and then storing it is automated generation, while procedural generation means you only store the differences from what the algorithm produces repeatedly, each time you reload the asset. There is, however, no reason why Minecraft couldn't just store the differences. Might be an efficiency thing. Disk space is cheap, after all and it saves processor time. There is even some derived data, like lighting information and height maps for viewing from a distance in the savegame.
@@____uncompetative Right, a technique like event sourcing. Store info about the changes that happened over time and you can replay that from any point. Basically generate the universe and then record its history
bluescanfly1981
Imagine a clock face which is segmented into twelve compartments you have two coloured hands which can be freely rotated to point to any compartment. These don't represent hours and minutes, don't move according to real time, and the movement of one doesn't have a side effect on the other. Now imagine a brick wall in a First Person Shooter and the player firing a bullet from their gun at it. The game would be more realistic if the brick wall is damaged by being shot. We don't need full collapsing destruction, just minor damage to be recorded otherwise it will seem oddly impervious and lack verisimilitude and break our player's immersion. So, we need to mark a bullet hole on the wall that we will just make a cavity rather than something we can see through. This means we aren't going to bother with bullet penetration and working out the reduced velocity and damage it might then cause another player behind the wall. This is a simple conceptual example.
So, we have the player fire their gun and create one cavity in the brick wall.
What happens if we continue? Can we reasonably store every cavity formed by all the ammunition used in the entire match. Well, that would be the brute force solution and is possible and would look the most convincing, but with limited memory it is very common to optimise this and hope no one stands infront of a wall spraying bullets in the hopes they can write their initials. The clock face of twelve compartments will contain the maximum number of X, Y coordinates on the wall texture at which to place a cavity. After twelve bullets have been fired the thirteenth needs to find space to be stored, but HELP! we only budgeted for twelve, so what do we do?
Well, the solution is to overwrite the first cavity we stored and hope no one notices. If you continue to fire then the fourteenth bullet takes the compartment that was used for the second cavity formed, and so on, all around the clock face until the cycle repeats. So, new bullet cavities erase the earliest still remaining cavity. This can be implemented very simply in a 12 row x 2 column array (with each row providing a pair of compartments in each of the two column spaces to store the X and Y coordinates of the bullet cavity) which has an integer variable that initially refers to the 1st row and is then incremented by 1 to advance around the clock face. You don't need IF / THEN logic to determine what to do when you run out of rows to store X, Y pairs in columns as you actually store the X, Y pair at the the new value of the variable which is determined by the old value of the variable + 1 modulo 12, ensuring that it never hits 13 as it will wrap around back to 13 - 12 = 1. See this article for details:
en.wikipedia.org/wiki/Modular_arithmetic
A professor would probably teach you to use a double-ended queue (which would be far more flexible, and could expand and contract in scope according to dynamic need, but this would also need to be garbage collected, which could prove slow, and why do we even need to bother when we only need to store 12 bullet cavities in 24 storage cells, and leave this static data structure alone at a fixed location in memory and reuse it whenever we need, pairing it with the wall texture so that additional walls can gain their own accumulated signs of damage and shots fired on wall B by one player do not erase the bullet cavities another player sees in front of them on wall A.
The major downside of just simply reserving a pair of cells for storing an X, Y bullet cavity for every bullet that could theoretically be fired in a PvP match, is that this approach breaks down when you have something open ended like a PvE campaign that could be played for four hours at a stretch. So many bullets are fired, on all sides, that this would be a large allocation of static memory to store all of this. Genuinely possible for a single level of a campaign. You could also store all the corpses created and then make the player backtrack at the end to the extraction zone and see the damage they wrought on advancing to the defended objective and blowing it up, but then you look at a game like _No Man's Sky_ with 2^64-1 planets and you realise that there is not enough storage on all the PCs in the world combined to record everything you could do to modify things, so the notion of erasing trivial stuff you did so long ago in the past you can't remember doing it becomes essential. You can also have multiple data structures storing these "memories" and keep the more significant actions around far longer, but balance this by making them less trivial to accomplish in game (such as collectively destroying a space station with your friends and returning to see that the X, Y, Z, T space-time coordinates of that "huge event" had been added to a checklist so that it would regenerate the star system procedurally entirely deterministically and then go "Oh, wait... we don't have that space station as it was destroyed last Tuesday" and get rid of it (then work on having it rebuilt if the local economy has need of another and can afford it, and have it also have features of the affected economy E, C, S, R so it can model the recovery of trade and reconstruction of the Station whilst you are away, as some process that could be procedurally derived from the time it happened T (compared to the time you later return, T2) in which interval you can determine if it has been rebuilt or is still under construction. Alternatively, you can store another four cells (which you would definitely need to do if modelling a background server based economy even based off a probabilistic approximation of all trade taking place in the entire galaxy). However, this is getting into complex territory and may not even be necessary if not a focus of the gameplay experience.
Good morning, Javid! You read my mind in this video, for I have been musing about the very same programming challenge as of late (though for a terrestrial setting, not a stellar one). I can't watch your entire video right now, so I will come back to it in installments.
I recommend to have a look at perlin noise and its derivates. It is usually used to generate terrain and textures. The way I understand it, multiple, randomly generated, smooth curves are overlaid on top of each other to simulate mountains ranges (large scaling factors), single peaks and valleys (medium scaling factors) and the single rocks etc. (small scaling factors).
Such a serene narrative, quite hypnotic actually. No debugging necessary. We are moving quite casually from A to B to Z. Of course, rand is rubbish and the mersenne-twister is slow. That is why everybody chooses Lehmer random numbers ... Keep up the great work :)
Have been for decades now fascinated by randomness... This vid has such great insights! Thanks so much. You're so awesome yet again
I'm completely honest, the first I came on to your channel, I was mostly pissed of, because I searched for things like algorithms and procedural generation.
But I was completely new to programming (which I'm still) and needed those things in Java... :) And your videos "blocked" the RUclips search page, whilst they gave a lot of information about how to do in theories but still not showing how to implement it in Java... (Yeah I'm dumb to judge a channel about C++ by not showing stuff in Java).
Complete misjudgment... Your videos are by far the best about algorithms and so you can find on RUclips. And really want to thank you for your effort!!!!
Finally i can be the master of my own world
@Markus Zeller If you use the same seed you can create alternate timelines
What a happy coincidence, I've been dabbling in my own procedural universe for little over a year now. Your excellent explanations would have saved me a lot of headaches early on as I was learning programming and experimenting with procedural generation.
I love your videos, they keep me motivated and I find them very helpful even though my main focus is Unity w/ C#.
Thanks Zorbaq, I try to show things in a language agnostic way. You could take a technique like that shown and implement it in whichever platform you prefer, I just find C++ simple and convenient.
this is awesome. I've been looking around for something easier to understand and you nailed it. Thanks for the vid
This time rewatching I was paying attention to your system layout and I like it a lot; an animation is kewl, but this is much more efficient
Minecrafts generation is deterministic. The chunks don’t have to be stored, they just are so player interaction with the world is not lost.
ideally there should be a function to check if there had been player interaction with the world in order to avoid bloating up memory, since a portion of playing minecraft comes down to crossing massive oceans or roving across reaches of land that often provide no unique reason for players to interact with them
@@Gogglesofkrome But just being in a chunk in minecraft will change it since there are mobs moving and plants growing and as soon as a chunk is created that process is started and the state of it is changed from before. So yes some chunks might not be changed in a visual way, but still there often are changes.
This was discussed in detail in a video regarding one anarchy server where hacked clients are used to find player bases by identifying how much each chunk had changed from the original creation, thereby allowing the searcher to see how long the player had been there.
So, in theory you might save a bit of space but that was not the primary priority.
@@davidmartensson273 Most biomes don't have anything growing while you pass through them, and mobs aren't dedicated to memory so long as they haven't been fed or tagged, with the only exception of the enderman, which is the only mob that changes the environment without user interaction. If you're running through the landscape and not touching so much as a thing on your way through it, then it would be effectively identical to a fresh map gen, and as such if the developers were more storage optimization focused, this generated data wouldn't be saved. The reason it is saved is to spare the processors the repeated effort of regenerating the same areas over and over again.
@@Gogglesofkrome the problem is speed. Generation causes lag in Minecraft because procedural generation takes time. So if chunks weren’t saved to memory, every time you cross over a chunk you’d have to generate it again. A lot of this is due to the fact that Minecraft is not multithreaded. If chunk generation were on a separate thread you could do it this way.
@@fpsoftdev this issue of speed is generally what I was referring to when I was talking about the generation being used to spare the processors the repeated effort of regenerating the same areas over and over again. It's too bad minecraft came into existence within that time period that multithreading had only just become widely available; otherwise a lot of the issues of performance on a general level wouldn't exist.
Can't believe that Elite was programmed an a speccy 48. Pretty amazing. Lots of respect to the game developers from back in the 80's.
Never seen a video so simply well detailed, instructive and interesting. Thanks for sharing your knowledge with the world❣
Great topic! I was thinking about just this sort of thing recently. I think the biggest problem for me was how do you know what you are selecting and I love your solution and how simple it is. That was also a great example of the default random generator. I honestly never really cared about the whole random number problem, but that demonstration really opened my eyes.
...
Although Minecraft does store the world, it does add to it as you play, it generates a larger and larger world as you explore, but then saves it. It uses a fixed seed to create the same world, which I have tested from seeds I have seen online. I am not sure if you could get away from saving something in a game like Minecraft where the world is altered by the player so drastically. Perhaps you could just save what you alter, so it is procedurally generated, then the changes are loaded in? Could be a solution. You would still be saving something, but only what has been altered. Great topic anyhow, if you have a solution where nothing would need to be saved (except perhaps a user defined seed) I would like to see it. I suppose it depends on the game itself. Certainly SOMETHING has to be saved in a persistent universe where the player is changing, building etc.
Yeah I think that is the only feasible way to store a universe this large quickly enough, difference maps are definitely the way forward if anyone were to continue this idea.
Cheers Javid for another great video.
Can't wait to give up real life so I can spend all day playing with code. One day. There's another channel that does a series called coding adventures that does game related programming exploration and mathematical modelling. Between the two of you I plan to build a library of skills and techniques and begin my own journey to make dumb programs and games. That's my dream, and it's enabled thanks to you Javid. Thank you.
Minecraft is procedural in the data generated for a given seed, but once that level data is put in motion it needs to be saved. Fire, water, and NPC's can alter the generated data. If your universe had a Deathstar that destroyed planets you'd need to store that information somewhere as well. No Man Sky works this way as well.
Modern processors do have a "real" random number generator, but it's "slow" and should probably only be used for seeding a quality PRNG.
Thank you for the wonderful videos!
[just finished the video - you mentioned the above at the end] :P
I just subscribed to your channel. Your voice is calm, your explanations are clear, your videos make me want to code even more
Thank you 👍
lol thanks Esu!
What you want is a hash function, or even a set of hash functions, not an RNG. The technique is to hash the "key" value (your coordinates, for example) and use the bits of the hashed result for your "randomness." You don't need a crypto-strength hash either.
After learning the generation method, i'm really interested in the storing process of interactions with procedural entities, glad you'll make a video about it :)
Just store the changes in a hash table with the sector as the key. Then retrieve that entry when you need the data. Store the hash table along with the seed to disk to get a save file. Tada!
Cryptography actually requires both real random numbers (which are generated in hardware) and pseudorandom numbers.
Using your star system as a parallel: It is important that if two people determine the information about a star system at the same coordinates, they get the same results. However it is also important that given the properties of a star system (but not its position in the grid) it very hard to deduce the original seed (or grid position) used.
Thanks for sharing your ideas, this is great example. One could also generate names of stars and planet with same idea.
Another excellent video. Very concise, and lends a very practical description. I have an entire book on procedural generation that might make more sense now. Thank you!
Short, sharp, funny, and to the point…a bit like impaling really 🤣
I always look forward to your videos and I even manage to understand some of it still. Thank you!
lol, thanks as always Phil XD
I watched this video while on a fair amount of LSD, and it changed my life
I've always had sort of a vague idea of how this works, but seeing is really cleanly (and simply!) laid out has inspired me to open up a code editor for the first time since new-year!
Also, not sure if I'm wrong or if this is just a nitpick, but I'm fairly sure Minecrafts world is procedurally generated, since the game does have the concept of seeds that will re-create an identical world every time it's input (even on another machine etc). It does also generate new chunks on demand. I think the reason it's stored on disk is because it's faster, due to the sheer amount of generation that is done per chunk, it's faster to read-back from disk after creating it once. So, the storing to disk part is not critical to the creation of the world, but rather convenience and speed, and as you alluded to at the end, to store changes to the world. But maybe that's what you meant?
And, I'm really looking forward to seeing how persistent changes can be implemented! I'm imagining it comes down to basically storing the changes to disk, rather than storing universe chunks. That way, you only need to store the changes the user has actually inflicted on the world, which in comparison to the entire universe is obviously tiny... But interested to see the details of that.
As far as I know, Minecraft procedurally generates all the chunks except for the ones which were updated by a player. However, even in this situation, only the changes are stored while the chunk is regenerated on load.
Loading from a disk will always be hundreds of times slower than generating even the biggest of terrains.
@@MrAlaxUA I'm not sure that's true, every chunk that MC generates is stored and compressed to disk in its entirety: minecraft.gamepedia.com/Chunk_format
Including lots of extra data like precomputed light data etc. But this happens regardless of whether the player makes changes to the world or not; it's still loaded and saved to disk after initial generation.
The CPU load from generating chunks is actually really significant, so loading from disk is preferable, because its not resource intensive (each chunk is only about 50MB or so). This frees the CPU to actually be busy drawing and simulating the loaded chunks rather than regenerating them on the fly every time, which when you think about it, would be a colossal waste of processing power - why re-generate every time you load a chunk, when you can just do the work once, and store it? The MC world is incredibly complex, so it makes sense to do it that way.
If the world is trivial though, its faster to do it on the fly. Up to a point, at least.
@@Mythricia1988 Exactly, in some modern games we can even hear about generating terrain/chunks etc on GPU because generating them on CPU would not be fast enough for real time game (for example games with voxel terrain where you can make holes etc in terrain).
The chunks that are modified must be stored to disk otherwise the changes that the player made will be reverted. Procedural generation creates worlds but does not track the changes on them.
You can be smart and just track the changes themselves though. For example block(0,0) is dirt, block(10,12) is air, etc.
I'm guessing that Minecraft stores to disk the chunks you visit; even if you haven't changed anything.
New video - instant upvote.
This is one of the best, if not the best, channel I've ever discovered. It is useful from start to finish... also to improve my English. Thank you to exist sir.
I dont think it was a random number generator which put this video in my recommended feed. No, it was meant to be. I dont code but Ive been wanting to watch people code and talk about what they think while they do, so I really appreciate your video and like your style of guiding it along. New subscriber!!!
Excellent video. You briefly touched on gaussian distributions but I'd like to expand on it. You can actually very easily create gaussian distributions by summing multiple random numbers. For example rand(6)+rand(6) will have a maximum of 10, a minimum of 0, but values will concentrate around the middle. In some cases this can be more realistic, for example heights of humans.
You can also create unbounded distributions. Consider the following code: int nMoons=0; while (rand(2)==0) ++nMoons;
There's a 50% chance of no moon, 25% chance of 1 moon, 12.5% chance of 2, 6.25% chance of 3, and so on to infinity.
As you explore you will find planets with more and more moons, and even the developer won't know what planet has the most moons unless he writes code to search for it.
Thanks Garo! Yeah, Im sure statisticians/probability enthusiasts can have hours of fun tinkering with the constructions XD
Fascinating! Converted the Lehmer routine to C# in a WPF project and did the Stars and Planets as icons. Works brilliantly, thanks javidx9.
This brought back fond memories of Elite:Frontier, which was the first one I played and loved, and how it had a whole frickin' universe to explore in glorious A500 colors while only occupying one single 3.5" disk. That blew my mind back then.
Countless cargo shipments to and from Barnard's Star wasn't that fun, though, haha!
Thank you. You just gave me the idea of adding pixels to my custom vector class. (eg v+px or v+=px)
I've started working on a project which is highly inspired by the first elite game and now you're uploading this... nice timing! xD
They were right...
He _would_ program the entire universe!
We called it!
As others have noted, Minecraft is based upon deterministic seed world generation. That's why Minecraft speedrunners search for seeds with a particular world generation.
I hope you guys are doing well. I have not seen much going on with the channel, but I know you have the baby and work. Thanks!
I disagree with your definition of procedural generation at the start of the video ... or maybe only with the given examples.
Minecraft does procedurally generate it's world, it only needs to store the information to save the changes made in a chunk, it will always generate the exact same initial world state given the same seed and version of the game. It's not just random and needs to be saved to be persistent, if that would be the case then i would agree with you, but neither Minecraft nor most modern rogue likes work this way. Most, if not all of the ones i know, can perfectly recreate the whole world/dungeon based on nothing more then the seed and a location, for every player in the exact same way. Daily runs are a popular thing in modern rogue likes and they stem from the fact that every player will generate the exact same level just by using the same seed, so developers only need to define a daily seed so that every player can run the same level and competing for the daily highscore.
@FichDichInDemArsch Could you please elaborate on that?
Superb content. The idea is quite clever imo, I had only vaguely known about some of the very basic concepts. It is much clearer to me now. Can't wait for more.
Cheers cygnus!
My first thought for changing state in such a system, if change occurs, generate and store changes, check for changes at the coordinates selected as you select.
I am hyped for this video (I will watch it later) and a elite player (1984, Frontier etc and elite dangerous) I am excited by procedural generation.
I love Elite too, always have!
I loved this. It was like watching that show a few years back with a secret magician explaining how a bunch of magic tricks actually work. Thank you :)
One of the best tutorials for procedural generations or as i like to call it (seeded random number generator with rules) starters ...... much luv mate. Keep up the good work. Would love to hear more.
I've learned so much in less than 42 minutes. Thank you!
You should extend this example at some point, I would love to see how you handle seeds for stuff generated on a planet. like give them each a world map of countries, each with information about them, then you can view cities in that country, then buildings in each city, rooms in each building, characters in each room.
I use 480p to save bandwidth and in this video, it was fun to watch how youtube is struggling to compress the video :). super fascinating subject, but still I'm lacking some c++ knowledge to fully understand the code, but every day less and less. Regards everybody
Rand was actually twice slower than the later generators! 0.006 vs 0.003.
Awesome video. If you love Elite - consider trying it with a head tracker (or high res vr)
41:20 that question came to my mind few minutes before you asked it and i gave it a thought. Probably i would use some map, where key would be taken from generation algorithm and value would be difference between generated state and current state. This solution breaks your definition of procedural generation, but quite simple.
Top notch as always. Thanks Jx9.
I always enjoy your videos. I have spent my whole career in IT but from a business programming perspective. Always wanted to code in Graphics, i find it fascinating. This was very refreshing. I will be trying this soon... Thanks.
Thats cool to hear David. I'm specifically not that interested in graphics, but lots of people respond well to visual stuff, especially on videos XD
@@javidx9 thanks for the reply. I too have been a follower of Elite. I have one question, trying to get olcPixelGameEngine working in VS2019. I have the include statement in the code but it cannot seem to find the file. I have included it in the project linker general additional library directories. Any thoughts?
Regards
Dave.
@@davidchapman3228 The easiest way is to just have the .h file in your project folder, and include it as necessary. there is nothing to actually link. This may help: ruclips.net/video/eTGSTTxR-Ss/видео.html
@@javidx9 magic, that did the trick. Thanks
One mistake that many make with procedural generation is to make things completely random. But a screen showing white noise (completely random content) is just as boring as a blank one. What hat allows you to stare at art for hours but not photographs or ingrain wallpaper are new patterns:
1. You don't already understand what's going on (nontrivial/novel)
2. You sense there is something to be understood (structured/tractable)
A few random ideas:
- Procedurally generate short strings of words (extracted from a dictionary), then use those words to search google images, and display the top image as the background of the players position in a game. For consistency, prepend a constant or pre-generated sequence. e.g. "'New York Street' scarf tram baby", "'New York Street' blob accountant time"
- As above, but use a restricted dictionary of things like texture names, or peoples names, or other elements of a game.
- As above, but use those as a prompt into GPT2.
- Use the seed as a lat long, limited to a high population area (e.g. NY, LA, etc...) and then convert that into a street address, and use that as a prompt into GPT2.
The point, in general, is to use apparently random values (but which are actually procedural seeds) as prompts into real world databases.
I once wrote a "less random" random (something like Perlin or Simplex, where a small change between input values facilitates a small change in the output) in Blitz3D by using the seed. It would get the random values at each corner of a cell (by seeding using the X and Y of that cell) and then linearly interpolate inbetween them. It was an interesting approach, and it worked pretty well for the purpose of a game written in Blitz3D. In C++, I'm guessing rand() stores the old seed, randomizes the seed and stores it, and then returns the old seed. It'd probably work after another call to rand(), but that'll essentially halve performance. Of course, half is relative. However, I think at that point, you might as well just copy the random generator code and have the seed be a constant value that's combined with the X and Y bits. That's how I would approach spatially-consistent (if that's even a term) randomness at a low level with pretty good performance. Distribution should be good (if the core RNG routine is also pretty good) but gradient leaves room for imagination, but you can solve it with what I did in Blitz3D.
Just discovered your channel and this was the first video I’ve watched. Awesome stuff, definitely interested in the universe “persistent state” and modifications you alluded to at the end. Now to go back to some of your earlier stuff. I’m not a c++ man so will need to jump a few steps back now
To be clear, for a different universe I could have a seed # which together with position gives me the same Galaxy with the same Galaxy seed every time. I could potentially do a 3D cube of stars and check each cubic light year, then randomly locate a star within that lyr^3. So for Galaxy 731 I could warp to a hundred lyr cube at 5300 by 11300 by -100 lyr and quickly check 5332 by 11321 by -123. If it exists, I can further use randomness generated from the seed for that location to place it at 5333.31 by 11321.53 by -123.02
Actually, the C64 was capable of real random numbers by its analogue part of the SID. This little machines still know to amaze, even today :)
This is awesome, gave me a lot of inspiration for projects!!
Awesome. Now I can understand how No Mans Sky was developed (which is an awesome game by the way). Looking forward to this one.
This is extremely interesting and fascinating content. I enjoy a lot that restrictive definition of procedural generation, it carries elegant design ideas. I wanted to know more about this subject, so, thank your very much for that
My pleasure Galileo!
Yet another interesting video. My initial thought was perlin noise and now just learned about Lehmer as well ;)
Thanks Jakob, there is no "standard" way of approaching procedural generation, you just need to think about construction a little differently
Reminds me of Master of Orion, but I've never played Elite. Nice! Makes me wish to explore that universe. :-)
For my project i had to use random to know where flowers should be, it was the same as with your planets
I used a hash library called xxhash, because it's very fast, and i can hash the seed and the output will be consistant, and looks like random!
I'm currently trying to build a terraforming game. This will help making the various star systems the players will be working in.
Good stuff buddy!
Thanks you for sharing. Your code worked like a charm with the new M1 arm64 processor!
The thumbnail reminded me of Elite Dangerous!
I'm actually making a game with this as a premise. I wanted a huge world, with the player being able to change some things in some places, but creating each effect by hand would be just about impossible. So i implemented a similar'ish' method to calculate the effects each time the vicinity is loaded.
It's still a work in progress, so much that i won't make any part of it public, but maybe someday.
Great video, I believe the screen should move by multiple of the sector size so your not out of allignment.
Thank you for this ! I took what you taught here and translated it to rust. I havent actually used it for anything but it was a fun exercise!
The interest of PRNG is to produce long sequences of random numbers from a seed.
Generating only one seemingly random number from a seed is better done using a hash function.
Well if you wanted to manipulate your universe after it's been generated then you have to save either the changes on disk and load them as the universe is generated. Or you would have to save all of what was generated on disk with your changes and load those parts of the universe from disk to maintain level persistence. But at the core of that system, you still have to generate a level though a procedure rather than manually creating the level by hand.
And yes, I did watch til the end of the video. A procedure is a procedure
i've been a fan of elite since i got hooked on the zx spectrum version in the early 90s. i also spent some time on elite: dangerous in recent years, though not active anymore. and although i always knew what procedural generation was, this is still a very enlightening video.
How am I only just finding your channel?! Many thanks for sharing your knowledge.
That is absolutely amazing, I love Math and ComputerScience exactly because of stuff like that!
Splendid and fascinating.
Linux provides /dev/random which is a virtual device providing truly random numbers. The system uses every random thing it can to generate these numbers and turns out there's not much randomness inside computers. Common sources of randomness are voltage in circuits and user input. These are very slow sources so is the generation of truly random numbers. The funny thing about it is that if you provide enough input, by moving cursor for example, /dev/random becomes noticeably faster.
This is a great video. Thanks for the clear and inspirational content :D
Some people can draw near-perfect circles on chalkboards; but at 19:36, it appears that other people can draw near-perfect Gaussian curves instead. With a little practice, you could be one of them!
Pokerstars has a pretty nice video about their random number generation. It seems pretty much perfect at a quantum physics level.
I'm pretty inspired by this. Great video!
Thanks!
Ha! You just solved my tree placement problem on my procedural world. Thanks!
Awesome job describing the algorithms!
I've travelled to many systems in Elite:Dangerous. The systems in this video actually remind me of that.
That cliffhanger though, really looking forward for the next video on this topic
I think it is wrong to think Minecraft automatic generated because the reason why it store it's chuck because the player interact with those chunk so it need to note down what has changed. With the same seeds, Minecraft can recreate the exact copy of the world just like the one you have here.
I
conway's game of life is cool too, very simple rules, but with very cool results :)
@@dutchdykefinger Yes! I have seen variations of Conway's Life for specific situations, like crime. They, too, are pure coolness.
Any lookup with the random generator should be preceded by a lookup in a table. If the entry in the table isn't found, proceed with the random generator, else use the result in the table and ignore the random generator for that lookup. That way you can have the table represent the state after the player has interacted with the world.