Better Mountain Generators That Aren't Perlin Noise or Erosion

many people have dreamed of summiting the highest mountains but there exists a strange sort of person that dreams of generating them instead one technique for doing so called fractal pein noise has remained popular to this day despite being invented all the way way back in 1983 back then it was really only practical to use when making elaborate CGI for movies nowadays though computers are so fast that it's become the algorithm of choice for generating mountain-like shapes on the Fly famously Minecraft uses several layers of practial pein noise combined and modified in creative ways to get its elaborate looking terrain but this is one of the problems if you just use fractal plin Noise by itself it doesn't look good it looks distinctly artificial contrast this with the rendering of data taken from an actual mountain and the difference is immediately obvious you can tell the real mountain has been intricately crafted over billions of years by the delicately powerful forces of nature while our artificial mountain is the result of a math equation to try and improve on Pearland noise a lot of people have been investigating an alternative algorithm based on erosion the idea is that you start with some mountains generated with pein's algorithm then simulate water raining down and moving sediment around to give the terrain a more natural look while this gives much better results it has a number of drawbacks that make it infusible for most use cases it's much slower than pein's technique it has a number of independent parameters that must be precariously tuned to get the precise look you're after if you mess up even just a little bit the algorithm breaks down and produces useless garbage finally games like Minecraft rely on a very special property of plin noise pein noise can be generated one chunk at a time in any order you like at any time you like without even needing to know anything about what the chunks you've already generated look like in contrast erosion only works right if you generate the entire map all at once if you generate it in chunks it's possible that the water from other chunks might come in and affect the chunk you're currently making so you need to simulate erosion on those chunks at the same time to accurately simulate the current chunk but then you just have the same problem all over again considering that storing an entire Minecraft world at once would require a $100 million of memory sticks I don't think Mojang's using erosion anytime soon but is that really it do you really have to pick between mediocre results and subpar flexibility no of course not being the strange sort of person that dreams about generating mountains I've researched not three but two techniques for generating better-looking mountains that you can use right now in that open world game you're making the first technique we'll look at is in addition to the fractal pein noise algorithm that significantly improves the quality of its results I learned about it from this blog post by the Fantastic Inigo kees since he doesn't give it a name I'll refer to it as the Great trick for reasons that will become evident later to understand how this trick works we don't need to know too much about the inner workings of pein noise but we do need to know what this fractal term means see if we just use pein noise to generate mountains we get something like this we do this by taking the X and y-coordinates of each point on a plane and feeding them into perlin's algorithm which will tell us how high each point should be this looks like the general shape of some mountains but it lacks detail if we just use pearlin Noise by itself all the details are the same size so we can either choose to have a few big details or have a lot of small details but we can't have a mixture like real mountains do this is what the fractal trick aims to emulate instead of just using pein's algorithm and calling it a day we use pein's algorithm multiple times at multiple different scales then layer the results on top of each other the result is much more natural with a pleasing mix of details we use the word fractal to describe this technique because zooming in on the result reveals more detail than was previously visible now as mentioned before this technique by itself doesn't look that great we could do a complicated erosion simulation at this point to help improve the result but we've gone over why that's not the best either instead the gradient trick is something inspired by erosion that still keeps the speed and flexibility of the fractal approach it also works on any kind of fractal noise not just plins the idea is that one of the effects of erosion is to smooth out finer details on steep surfaces because water runs faster there we can replicate this effect byal calculating how steep the point we're currently generating is and use that value to proportionately reduce the effect of smaller layers the steeper point is the weaker the smaller details will be the way we figure out how steep a point is is with a math tool called the gradient the gradient at a point has a very technical definition but it's effectively a vector that tells you which direction will take you uphill from that point its magnitude also tells you how steep the point is it's effectively the higher dimensional cousin of the derivative which is also something that tells you how fast and in what direction a function is increasing in fact the way you calculate the gradient is by finding multiple different derivatives recall that vectors have multiple components telling you how far the vector points in a particular direction to find the gradient we just have to find the derivative in each of these directions and collect those values into a vector the resulting Vector will then point in the direction that increases the fastest since if a particular direction increases faster than another the Cor responding derivative will be higher making the gradient Point more strongly in that direction now there are two main ways to calculate derivatives in computer Graphics one is a universal method that works well enough on just about any kind of input it's called the finite difference approximation it basically takes the definition of the derivative that you would learn in a Calculus class and turns it into code specifically to find the derivative of this function using this approximation we find its value at the current point and then find its value at a point slightly to the right the derivative is then calculated as the slope of the line passing through these two points which is the difference between the values over the distance between them we Define it this way because the slope gets higher as the point gets steeper in ideal math land we can use the limit to find what happens as this distance gets closer and closer to zero but computers don't have infinite resolution so we pick a small but finite number for the distance instead hence the term finite difference approximation we pick it small enough to not skip over important details of the function but big enough so that the limited resolution of computer numbers doesn't become a problem when we use this technique to compute a gradient we find a value at the point we want the gradient of as well as two other points extending a small amount along the X and Y AIS after some simple arithmetic we have our gradient the downside of this method is that you have to calculate the value of the noise function at three different inputs which is a lot to ask if your noise function is expensive or if your performance budget is small it's often harder but sometimes more performant to use an analytical approach instead rather than approximating the derivative at a point we find an exact mathematical equation for the derivative then simply evaluate that equation as needed often times the equation for the derivative shares similarities with the original equation meaning that if we happen to be calculating the original function anyway we already have most of what we need to calculate the derivative the blog post I mention gets into a lot more detail about how exactly to find this equation for a couple different types of noise so if you want more detail about that I'll leave a link suffice to say this version involves more work up front to figure out these equations but pays off in performance allowing your program to run faster or use more layers of noise for a higher quality result now that we have a tool to tell us how steep a point is we can go ahead and implement this fake erosion trick we start by generating the first layer then finding the gradient at all the points we generated the steeper the gradient is the more we reduce the influence of this base layer specifically we use this formula to give us 100% influence when the gradient tells us the layer is perfectly flat but increasingly less influence as the gradient gets steeper one of the parameters you can control here is how fast the gradient decreases the influence making this stronger makes this first layer pointier you can also play around with different functions to adjust the shape of the influence giving different shapes to the slopes of the terrain now that we've done this first layer we can consider the next layer we compute it and its gradients like before but instead of just using that layer's gradients to that layer we use the sum of that layer's gradients and the previous layer's gradients this makes it so that areas that will become steeper when combined will be eroded more strongly than areas that will be flatter when combined we continue adding additional layers keeping a running sum of the gradients at each point and using them to decide how much of the new layer to add in at each point the final result looks like this while we can agree it doesn't exactly look like erosion it does look much more interesting than the plain fractal pein terrain and that's ultimately what matters here in computer Graphics we're in the business of making things look pretty and I think this counts even if it's not perfectly accurate the algorithm We've Ended up with makes the individual layers have more interesting mountainy shapes and also breaks up the monotony of the plane approach by producing different mixtures of the available layers at different points on the terrain and since it's just a simple modification of the basic fractal pearlin algorithm it retains all its desirable qualities namely its speed and its tile ability the other algorithm we're going to look at is completely different and it'll take a number of weird hacks to get working favorably the idea it's based on was discovered when scientists were trying to figure out why certain dissolved compounds would form these sorts of shapes over time conveniently for us these shapes kind of look like The Ridges of mountains the process these scientists discovered is called diffusion limited aggregation abbreviated as D the way you generate these shapes with a computer goes like this first start with an empty image place a single Pixel at the center then add another pixel at a random location randomly move this pixel around until it hits the pixel in the center once it's done so freeze it in place and add another pixel move that one around until it hits one of the existing pixels and then freeze that in place too continue adding and moving pixels to grow an organic sprawling shape and stop adding pixels once you're happy with the density and now we have our ridges adding some image processing magic gives us a texture we can use as a height map indicating higher elevations with brighter points however I'm not going to get into how that works just yet because we already have a problem this technique it's monumentally slow these pixels take their sweet sweet time sticking to each other it takes so long for even just the second pixel to find the first pixel because there's literally a million other places it could visit in the image without hitting the first pixel not to mention that the image processing afterwards involves massive gausian blurs which are famously expensive and really only worth it for highquality applications luckily though we can solve both of these problems by using a gradually increasing level of detail see if the image is small or already filled with a bunch of pixels it doesn't take long at all for a new pixel to find an existing one so what we can do is start with a small image and run da on it until it fills up a bit then we upscale it and run da again on this now fairly populated image to fill in more details we continue increasing the size and running da again until we reach a resolution we're happy with this approach also happens to solve our blur problems while this was always an option the technique we're using now lends itself particularly well to something called a dual filter blur the idea of the Dual filter blur is that you start with a crisp image and gradually make it smaller while applying a slight blur at each step the small image is then repeatedly upscaled again applying a slight blur at each step until the size of the original image is reached the end result looks incredibly blurry for the small amount of processing we did due to the fact that the blurs on the smaller levels acted over larger percentages of the image all at once to use this in our multi-resolution da Technique we can just throw out the the first half of this algorithm and use its upscaling process every time we upscale our image we first generate our starting low resolution image we then make a larger version that's blurry and a larger version that's crisp using the crisp version to add more detail once we have more detail we can add that back to the blurry version and do another blurry upscale while doing a crisp upscale on the broad detail again we add more detail to the crisp image and add the new detail back to the blurry image chain by doing it this way the course detail gets blurred a lot while the fine detail only gets blurred a bit this is effectively another fractal technique and it also performs quite fast now that we have a general overview of how this algorithm works we can dive into the details namely how does this crisp upscaling work how do we ensure that the peaks of the mountains are higher than the base and what exactly do I mean by a small blur first upscaling how do we turn this into this what we want to do here is keep track of which pixels each pixel get stuck to while we're adding detail this one got stuck to that one that one got stuck to this other one and so on once we have this we can upscale this as much as we want by just redrawing these connections as lines on as large of an image as we need this gives us a general structure to start with plus plenty of room to add more detail it helps here to preemptively break up each line into two smaller lines and jiggle each intermediate point a bit to ensure the result doesn't contain lots of straight lines second we want to ensure that when we get around to blurring this whole thing the points towards the center of the web get a higher elevation while the points towards the edges get a lower elevation if we just blurred an image where every pixel was the same value we'd end up with all the ridges existing at the same elevation instead what we can do is assign a different value to every pixel indicating how high it should be we start by assigning the outermost pixels a weight of one then we repeatedly assign to the weight of each pixel the maximum of Weights of pixels that are Downstream from it plus one so these pixels each get a weight of two continuing to climb up we assign a weight of three to these ones but we now have another problem layers with finer detail will add a ton of height towards the top of the mountain really what we want is to just give a gradual transition to the newer details while clamping the higher values to avoid adding too much height there we can reuse the smooth fallof formula from the gradient trick here to ensure that the higher input values approach a maximum value increasingly slowly and now we're ready for the last step blurring the whole thing to turn these ridges into a full height map I mentioned that the blurring algorithm we want to use involves repeatedly upscaling an image and applying a small blur after each upscaling first we need to look at how to do the upscaling itself whenever we upscale an image we need a technique for adding in more data to fill in the now bigger image the simplest kind of upscaling uses something called nearest neighbor interpolation to do this for every pixel in the new image it looks at what the nearest pixel is in the old image and copies its value it has a distinctly blocky look due to the fact that entire blocks of pixels in the new image will be close to single pixels in the old image a slightly better technique is to use linear interpolation for every pixel in the new image we find an equivalent position on the old image for most new pixels this position will lie in between old pixels the previous technique would go on to pick the color of whichever is closest but linear interpolation instead mixes together all the surrounding pixels with proportions given by how close we are to each pixel so if we're right on top of an old pixel we just pick that color but if we're in between two then we get an even mix of their colors and if we're in between four we get an even mix of all the those this results in a much smoother picture but it's not ideal it still doesn't look like a blurry version of the original picture it still retains a distinctly blocky look due to the mathematical properties of this technique this is where the small blur I mention comes in we take our upscale image and create a new image of equal size then we give each pixel in the new image a weighted average of colors from pixels on the original image this pattern is roughly circular turning our ugly upscale into something softer this this is an instance of a general technique called convolution and there are many good videos about it if you want to learn more by repeating this upscaling and blurring process we end up with a nice fuzzy image of whatever size we want and that wraps up the inner workings of the D algorithm by starting with a few pixels and gradually adding more while repeatedly upscaling and blurring we get an interesting sort of terrain that just isn't possible with regular pearlin noise one of the things I like about this algorithm is how much room there is to experiment you can mess with the Reg that pixels are allowed to spawn in and which pixels are set to start with to make different shapes and also the way they randomly move around to get different textures you can even get it generating in chunks if you work at it a bit since you can make a custom area for the pixels to spawn in you can limit the area this algorithm influences if you divide your world into a number of mountainous regions using something like cell noise you can check which region the chunk you're generating lives in and generate all the terrain in that region at once without having to worry about it influencing neighboring regions this is basically how Minecraft is able to generate structures like Dungeons and Villages that span many chunks lastly I'll point out that this algorithm does have one major limitation being that it can't really be ported to run on a GPU the da algorithm is inherently suited to the CPU since it's possible for each new pixel to bump into the pixel deposited right before it on a GPU we would have to make a way to add many pixels to the image all at once without those pixels knowing about each other which goes against the way da works and with the inner workings of Da concluded that wraps it up for these two mountainous algorithms today we saw how the gradient trick can be used to add character to any kind of fractal Technique we saw how the trick retained all the favorable qualities of fractal noise allowing it to be used in all the same situations we also covered an algorithm based on diffusion limited aggregation by generating a pattern of ridg lines and applying some image processing we get a scraggly hype map that more closely resembles the character of actual mountains I hope you found these algorithms interesting and possibly even useful let me know if you make anything cool with them and I'll see you in the next next [Music] one

Channel: Josh's Channel

Views: 256,345

Keywords:

Id: gsJHzBTPG0Y

Length: 18min 8sec (1088 seconds)

Published: Mon Apr 01 2024