How does procedural generation work? | Bitwise

Pikul let's talk about randomness [Music] computers and randomness don't really match after all a computer can only follow very precise instructions so if computers need structure and logical sequences how can they do random operations and on top of that how can we use these random operations to generate worlds that seem to make sense in the world of computers we have two kinds of random numbers true random numbers and pseudo random numbers true random numbers lie an actual randomness occurring in a physical world such as cosmic background radiation whether that truly is random or not is an entirely different question about the predictability of the universe but this is not a physics Channel and I'm not a physicist so for our purposes let's just call it truly random this is pretty much as random as we could possibly get using a computer but it is quite impractical and actually way overkill for most purposes which is why the most common way to get these random numbers is to use pseudo-random number generators they are des of pseudo-random number generators is to use some kind of formula which will generate a sequence of seemingly random numbers for us for example let's take something that seems to generate random numbers such as pi this will spit out a long sequence of random numbers the only problem is the sequence it generates is always the same so to introduce some more randomness we usually use some kind of seed for our random number generators the seed is simply a number we feed into a generator which would change something about the sequence of the numbers we get so for a little PI generator let's say our seed determines where we start in the sequence this means that if we use the same seed we will get the exact same sequence of numbers every time so if we want random numbers every time we use our generator we will need to use a different seed usually the current system time is used as a seed to get a different sequence every time we run our generator of course in reality more complex and unpredictable formulas are used to get these random numbers but the basic principle is the same get a seed feed the seed into the formula and generate the sequence of nom using the formula with this we have our most important ingredient for procedural generation random numbers let's get some terminology out of the way because there is a difference between random generation and procedural generation you'll find that random generation and procedural generation are often used interchangeably but for our purposes we'll go with the definitions defined by Gamasutra we have randomly generated gains where the content is built from predefined elements and we have procedurally generated content where the game builds entirely original content now that we know what we're talking about how can we actually use our random numbers to generate elements in our games let's start with a game that mainly uses randomly generated elements binding of issac in the binding of issac a dungeon is generated consisting of connected rooms through which the player can reverse dungeon generation in the binding of issac works by stitching randomly picked rooms together for example we start with a default starting room next we randomly select one of our four sides to place a room and then we pick one random room from our collection of predefined layouts and place it down we repeat this process until we have placed enough rooms and then finish up by placing a boss room somewhere finally the game could do one extra states where random elements are placed inside the rooms such as chests items or special objects this is all randomly generated which means that the rooms themselves are all designed beforehand the game just decides where and how to place this predefined content this means that the game developers need to create a lot of content beforehand to make sure the game feels different every time you play this system however is vastly different from procedurally generated content for some games making out of this content beforehand is either too much work or just plain impossible this is why games like Minecraft and Terraria use an entirely different system to generate content so now it's finally time to talk about procedural generation where the game itself creates original content for the player to explore but if we want to talk about procedural generation we have to talk about noise no not that kind of noise I'm talking about computer-generated noise distortion patterns and most notably Perlin noise what is Perlin noise well it looks like this now you don't need to understand exactly how it's generated the important bit is that is randomly generated using some math formula and some specific rules which determine its characteristics okay digits sure that's a nice picture you show up with some random cloudy blobs so what well noise like this is often the basis for procedurally generated terrain so how do we use it to understand how to reign generation works and how noise plays into it let's start with a 2d example similar to how to roar eeeh would generate its terrain we'll start simple let's say that white pixels represent a filled space such as dirt or grass and black pixels represent an empty space the first step in our terrain generation is to define the horizon lovely nice and flat terrain make me feel variety but of course this is not an interesting world to explore we need hills valleys and mountains in our landscape so it's time to introduce some offs as not terrain let's just pick a number at random for each of our pixels and move them up or down by that amount this should make a terrain a bit more interesting hmm well that certainly looks more interesting but it doesn't look like a realistic terrain at all so how do we improve this what could we possibly do to get more realistic terrain what could possibly help us solve this problem of course our good old friends Perlin noise instead of shifting our terrain around randomly we use pearling noise to determine our offset similar to how the cloudy texture from before was generated we can also use the same rules to generate a single one-dimensional slice of noise this slice can be used to transform a terrain with a color a pixel in this slice determines how much we move a point up or down for example a white pixel moves a point 25% up and a black pixel moves a point 25% down and everything in between this may the slice of Perlin noise we have describes our 2d height map and because Perlin noise generates much smoother continuous patterns our terrain actually starts looking realistic now however using this method points can only move up or down so this means that we will never get any overhangs or cliffs so the fix this issue we can do another pass with Berlin noise but now instead of shifting points up or down we can shift them left and right and this causes our terrain to deform a little bit creating these nice cliffs and overhangs the generation for these mountains and Hills can be tweaked for instance we can choose how much our values in the Perlin noise move the points around if we choose to move our points less we get lower Hills and if we choose to move our points more we get a more rough mountain area but we can do more we can play around with a generation of the purlins noise itself for instance we can make it transitions between extreme values smoother to give us a more gradual Hills in short we could tweak all kinds of things which would change the kind of terrain that is generated we can even do more passes with different noise maps to make the terrain rougher this can be used to define all kinds of areas and biomes to make our world more interesting and varied imagine placing multiple different biomes next to each other and already you're beginning to see the varied worlds we can create so that generates a terrain above ground but what about all the caves we can explore underground well luckily we can reuse a lot of the same principles once again we're going to need some kind of noise function to carve out our caves unfortunately Perlin noise doesn't really give us the results we need for generating caves different noise generators use different rules and have different characteristics so we've picked a different noise generator which gives us more cave like patterns to make these patterns into caves once again look at the colors in our noise pattern we can set a threshold value which determines when a part of our pattern is a cave for instance if we set a threshold of 80% then anything above 80% whiteness will be considered a cave the lower we set this threshold the wider our caves will be so to make our caves more interesting to explore and to make sure they don't carve these huge portions of our landscape we can play with this threshold value remember that the lower this threshold the wider our caves are so if we decrease this threshold to deeper we go Caves will get progressively wider and wider defer do we go down that's the basics of how a game like terraria would procedurally generate its terrain in 2d but how would this work in three dimensions for a game like Minecraft well luckily pretty much the same principles apply to the 3d world for instance our pearly noise from earlier can now be used in two dimensions and just like in 2d it simply describes the height of her map but now in two dimensions instead of one brighter areas represent taller peaks and darker areas represent the valleys now if we would add some rules to this say adding snow above a certain height or water below a certain height you can already see how this would define our world if you've ever seen one of those augmented reality sand boxes this should feel familiar except in this case the sand is our Perlin noise map once again if you want to add more details or make our terrain more rough we could do multiple passes with this Perlin noise each with a different weight affecting the final result differently for generating our caves we can once again use the same noise generators as our 2d example however to get a nice looking 3d cave system we need to use two noise maps along two axes to determine where the caves are we'll look at where these two noise maps intersect by overlaying them like this we get a nice complex cave system with realistic looking tunnels in open areas with the surface world and the caves done we should have a fairly interesting world to explore already but there wouldn't be much to do without objects in this world so the last pass of our world generation is placing objects all over a world such as plants animals enemies treasure villages etc to give you a general idea of how this work imagine that the placement of an object is always determined by its surroundings we can go through our generated world and place objects based on certain rules for instance was a trees and grass always grow on the surface fonts and flowers only grow in grass and bunnies can only spawn in areas with grass and flowers imagine a similar system for the caves where he would only spawned bats in caves with certain width have lava at a certain depth or have blocks become different ores at different depths these systems can become quite complex as designs want to tweak the player experience and make the environment feel more realistic because of this we won't go too in depth but this should give you a general feel of how such systems could be constructed not a great thing about procedural generation is you can create gigantic worlds without the need to handcrafted all if you recall the way randomness works and our computers means that with the same seed we always get the exact same sequence of random numbers like the sequence of Pi that never changes because of this predictability of the random numbers you can create near infinite worlds even an entire universe without the need to store it all in your system's memory you can see this in games like no man's kind as long as you use the same system to generate your random numbers you can be certain you get the same random numbers with the same input this means that you can construct a system where the content that is generated is determined by its position in space for example even if you leave and come back the rules of your procedural generation never changed which means it will generate the exact same content as the last time you visited since everything is generated on the fly you can't really store the state of the world in a game like that so if you want players to change or add things to the universe you would need to save the changes that player made in the world and reapply them when necessary this allows players to change the world without the need to store an entire universe on your system and that's the beauty of procedural generation you write certain rules and procedures around the computers random number generator which gives you an infinite amount of unique worlds in accordance with your specifications you don't even need to be able to store such a large world as long as the rules don't change I'll be a 2d 3d in space on earth or on the water the possibilities are endless and isn't that wonderful all of that through the magic of programming I know it's been a lot to take in and if you have specific questions I'll try and answer them in the comments and I promise I won't disappear for two years I hope you have learned something new today or at the very least that you're a bit wiser [Music]

Channel: DigiDigger

Views: 293,546

Keywords: Procedural, Generation, Bitwise, Terraria, Binding of Isaac, No man's sky, Minecraft, World, Creation, How, Explanation, Games, Game, Gaming, Analysis, Technical, Teaching

Id: -POwgollFeY

Length: 13min 47sec (827 seconds)

Published: Wed Jan 29 2020