3D World Generation: #3 (Quadtree & LOD)

in this project we're going to be doing infinite terrain generation and we'll be doing that by building on and extending the previous tutorials with a quadtree and level of detail in movies you often see these long dramatic shots showing off huge landscapes and if you want to be able to convey that same sense of scale and your own game scene you need to be able to draw a lot of stuff all the way out to the horizon or even further depending on the game you're making in the past couple tutorials we covered implementation of basic height maps before moving on to understanding how to generate noise and calculate fractional Brownian motion to improve the quality of our 3d world generation now we're adding on infinite procedural terrain and level of detail so that we can draw pretty much as much as we want I'll start with a single piece of terrain from the last tutorial what we need to do is work towards extending this to entire landscapes to begin what we want to do is update the terrain based on where the camera is and I did that by creating this terrain chunk manager that checks the cameras position each frame so that as we move around and outside the bounds of that chunk of terrain we generate a new chunk of terrain and as I do that you can see the new one that's closer to the camera sort of pops into existence the next step to making this more infinite is that instead of just generating a single chunk of terrain around the camera we can generate a whole bunch so we figure out which terrain chunk we're in and then proceed to generate all the surrounding ones as well and once you start moving around it gives you a bit more sense of limitless since it doesn't matter how far you can go in any direction will just generate more and more terrain but this is really limited because I can't keep extending this if I want to just draw a few kilometers to the horizon the number of tiles is squared and I need about a hundred and that's just at eye level if I want a further out shot that I can see about let's say 20 kilometers suddenly I need 1,600 this is getting out of hand really quickly what I ended up doing was implementing a quadtree now if you're not familiar with this data structure it's a way of partitioning two-dimensional space by dividing it recursively into four smaller quadrants hence the quad part now I didn't see that many good tutorials in this so this is how I got it to work what you do is you set up a root node which is the area you want the quadtree to cover and then you insert the camera into the tree beginning at the root node you check the distance from the center of the node to the camera and if it's less than some threshold in my case I use whether the distance from the center of the node was less than the width of the node times sort of a multiplier if it's too close then we go ahead and split the node creating four children and you can see here that the way we create the children is pretty straightforward just bottom left bottom right top left and top right at that point we recurse and do the exact same thing in each of these children so for each child we check whether or not they're close to the camera if they're not we do nothing and if they are we split and create four more children and so on until we decide the nodes are too small at which point we can also stop back to our terrain chunk manager what I do is every frame I create a quad tree and then insert the cameras position into it after that I go and get every single leaf node that is every node that has no children under it then we compare that list of terrain chunks so the ones that we already have everything that already exists great we don't need to generate those ones all the new ones we create new terrain chunks for those which will then build the mesh and color the vertices that needed and once we do that Walla we have terrain stretching out for 32 kilometers in every direction as I move around you can see the terrain is a bit fuzzy and low resolution in the distance but as we move it gets smoother and higher resolution from the top here you've got a bit of a better view the white ball is supposed to be where the camera is and you can see how the terrain gets progressively less detailed as you get further away after the camera of pan slowly over the landscape details closer to the camera come in also note that we don't require that many chunks of trained to render this pretty massive scene dropping a breakpoint in the terrain chunk manager we can see that the quadtree only gives us 70 children that means that there's only 70 chunks of terrain that we needed to generate for this entire scene again looking at this from way above in wireframe mode we can see that there's a lot of resolution closer to the camera but it falls off quickly and when you're on the ground yeah maybe you can see it if you're looking for it but we're putting the resources where they matter where they should be up close to the camera and if we were to tried to do this with a thick sized grid like we started with it will require well each terrain chunk is 500 meters by 500 meters so that's 16,000 terrain chunks this isn't quite done yet at least not for now because you may have noticed how the scene stuttered heavily as we moved and it had to generate the new terrain this is caused by the creation of all those new chunks of terrain even though there aren't that many there are still a few and doing them all at once is causing a slowdown so what I did here was I went ahead and created this terrain junk builder class and what this does is that you give it a list of terrain chunks that you need built and it'll spread the creation of them over multiple frames each of the terrain chunks has a rebuild function and I converted that into a generator and that lets me spread the generation of the terrain over multiple frames doing a little bit at a time so what we do is focus on generating one chunk of terrain at a time and when that's done it gets removed from the list and we start working on the next one eventually when they're all complete we swap the old ones and new ones all at once and the new stuff appears the other thing that helped was keeping a pool of terrain chunks handy so that we didn't have to instantiate new ones all the time but instead we reused old ones you can see here that after we generate the new ones we recycle the old ones and those go into a pool whenever we create a chunk of terrain we simply call create terrain chunk with the parameters that we need and that checks whether or not we already have a pre-built one if it does great he uses it otherwise it instantiates a new one and passes it back now there's a few better ways we could do this that we could work on next maybe in a future project like instead of using generator functions we could thread this work off into workers we could also skip generating any of this on the CPU and move this right into vertex shaders or even compute shaders if they're available there's a lot of options for improvement here and so there we have it a quadtree implementation that gives us effectively an infinite procedural world source code is all available on github so fork it and go ahead and tweak it or do whatever you want with it I'll be continuing this tutorial series in the future so look out for the next one make sure to hit like and subscribe and I'll see you next time Cheers you

Channel: SimonDev

Views: 17,863

Keywords: simondev, game development, programming tutorial, 3d world generation, infinite terrain generation, infinite terrain generation javascript, 3d terrain generation in javascript, terrain generator javascript, 3d terrain generation, procedural terrain generation, procedural terrain generation tutorial, javascript 3d, 3d, javascript, javascript game development, quadtree, quadtree implementation, quadtree lod, object pooling javascript, object pooling

Id: YO_A5w_fxRQ

Length: 7min 12sec (432 seconds)

Published: Tue Apr 14 2020