Jump to content
  • Advertisement
Sign in to follow this  
Hawkblood

Terrain generation

This topic is 1969 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

First, I'm new to this forum, but not new to C++ or DirectX9. I've tried searching the topic of how to generate terrain, but didn't find anything I thought was useful for these specific parameters:

 

-fast generation

-contenuous (moves with the player so there is no spacial limit)

-detailed up close, low-poly at distance, and smooth transition between.

 

I've come up with some ideas, but I would like to know if there is anyone here that knows how the experts do it.....

I think my ideas would be slower than methods used by "the industry".

Share this post


Link to post
Share on other sites
Advertisement

perlin Noise (and associated fractals) is the canonical way of doing this.  Basially, it generates a continous (i.e. smooth) surface at whatever coordinate you give the algorithm.  Zooming in and out is just a matter of giving it more accurate coordinates, say... 1.25 between 1.0 and 1.5.  The point will be exactly between the neighbors on the contour of the surface.

 

Perlin noise itself isn't very interesting.

 

http://upload.wikimedia.org/wikipedia/commons/d/da/Perlin_noise.jpg

 

As you can see, it kinda looks like the noise you get off a TV, but blurry.  More interesting is when you use the output of Perlin Noise as a basis function for various fractals, e.g.:

 

FBM:  https://sites.google.com/site/jicenospam/hill_fbm.png (this is what libnoise samples usually show, note that it is NOT perlin noise, but a derivative of such)

 

Hybrid Multifractal:  http://www.dragonheadstudio.com/htc/tutorial9.jpg

 

Ridged Multifractal:  http://www.neilblevins.com/cg_education/procedural_noise/musgrave_ridged_turbulent3.jpg

 

Once you have these constituent fractals, you can mix and match them with basic math functions as you please.  There's a wealth of other things you can do too, but this is just a topical overview.

Share this post


Link to post
Share on other sites

Thank you both for replying. The method for generating the "heights" for the mesh/meshes is one issue. I think I'll use perlin noise, but I have tried to use it without success. I have a method for generating the height values already, but it's slow. The quad-tree method is what is more pressing at the moment. I don't even know how it's done.... I understand the concept, but how to impliment it eludes me. Is it a single mesh or is it multiple meshes that are placed together? I'll look at the libnoise article, but I need to know how the quad-tree is done.

 

Thank you.

Share this post


Link to post
Share on other sites

You will probably want to use multiple meshes placed adjacent to one another. For lower LOD chunks, you can use a lower res block of samples plus a skirt to hide the cracks between seams.

 

Perlin noise fractals are ideally suited for this kind of on-the-fly generation, because in order to get a lower detail terrain (and incidentally one that will generate more quickly) you simply reduce the octave count of the fractal. So for example, if the largest block size is MxM, and the next LOD level down is a block M/2xMx2, then you can generate the first one using, say, 8 octaves and the second LOD level using 4 octaves.

 

If you are going with a large or practically infinite terrain, then I would recommend against using a quadtree. The basic quadtree takes a finite, bounded volume and splits it recursively into 2x2 sections, which doesn't extend well to an infinite sized volume. Instead, I would use something like a spatial hash where blocks are indexed using a BlockX, BlockY pair that is hashed to find the "bucket" in which that terrain block lives. Block coordinates can be negative and practically infinite (if a large enough precision type is used for the coordinate pair) and you can easily draw a "chunk" of blocks centered at some given coordinate to implement your moving window into the world. You can also easily implement streaming and discarding of blocks as they come into or go out of a larger "active" window on the world.

Share this post


Link to post
Share on other sites

Thank you FLeBlanc. I've used that method before, but I thought a better method was out there. Are you sure the quad-tree method has those limitations you described?

Share this post


Link to post
Share on other sites
Thank you FLeBlanc. I've used that method before, but I thought a better method was out there. Are you sure the quad-tree method has those limitations you described?

 

Yes. In order to represent an infinite terrain your quadtree needs to be infinitely sized; that means, the top-level node has to be infinite. Let's say you go with just "really large" For example, say your standard terrain chunk is 16x16 meters, and you want to represent an area 1km x 1km in size. That equates to a tree 7 levels deep; ie, the root node would be a node 1024x1024 meters in size, the next level down would be 4 nodes each sized 512x512 meters, next would be 16 nodes sized 256x256, and so on until the leaf level would comprise 4096 nodes each sized 16x16. That is for a mere square kilometer.

 

To represent an area the size of, say, Nebraska you would be looking at an area that is 512km on a side, or 524288 meters to a side on the root node, and the tree would be 16 levels deep. That's getting into crazy territory if you are doing recursive culling and such.

 

Additionally, this assumes that you do bound the player to some finite area, that area being the size of the root node. If you are not bounding the player, then you have no way of calculating the size of the root node, so your only recourse is to hack some sort of collection of quadtrees. You can always grow a tree downward from the root, but growing upward from the root is trickier. And if you do manage to figure out a scheme for growing your quadtree infinitely upward, you then face the problem that any search of the tree (for culling or other purposes) is going to increase in overall complexity the further the player explores. If the player stays close to spawn, searches will be fast since the tree won't have grown very deep. But if he hops on a horse and tears ass across the country to the other side, your tree is going to grow quickly and search complexity will correspondingly grow as well.

 

On the other hand, if you use a spatial hash then it doesn't matter how large the area is. There is no requirement for setting bounds, and search complexity will not grow with explored area size. Complexity will be exactly the same for a small world as for a huge one (minus some basically trivial bookkeeping depending on the spatial hash implementation.)

Share this post


Link to post
Share on other sites
You can use a quadtree by:
-Add a new root node when you need more area (or just make it 32 layers to start with to match integer positions range)
-Never traverse the whole tree (well youll need to do that sometimes but not for every access). You should know what branch(es) you are currently working in.
-You could use a tree with a higher branching rate. lets say 4*4 children per node. That would make it not so deep.

Share this post


Link to post
Share on other sites

Here is what I have done before:

-had a HUGE, low-poly, scaled mesh of the entire terrain (the absolute maximum the player could explore).

-had 25x25 "blocks" of 100mX100m each placed over the huge terrain.

-as the player moved from one block to another, the blocks would shift in the opposite direction. The blocks at the far edge opposite the direction of travel would be repositioned to the front and reused as the new terrain blocks.

 

Of course I will have an absolute max distance of where the player can go, but I don't want it to be practical or desirable for the player to go there. So, I want the area to be huge.

Share this post


Link to post
Share on other sites

Of course I will have an absolute max distance of where the player can go, but I don't want it to be practical or desirable for the player to go there. So, I want the area to be huge.

Why do you limit your area like that?

Infinite terrain doesn't have to be displayed all at once - see how the video I posted originally handles it.

 

You can have a 3x3 grid of big blocks (you can make the grid 5x5 or 7x7 etc). Each time the player changes which one of these 'big blocks' he's in, the blocks are re-organized such that the new block the player is in, is the center one again. I thought this was pretty well illustrated from the video, so I can't really give a better illustration.

 

Then, for getting more fine detail, you basically subdivide each big block depending on how close the player is to it. Once you subdivide, you no longer draw the low-res terrain, but instead draw the resulting 4 smaller blocks.

 

After that you run the same sub-division on the resulting smaller blocks, until:

a) either the player is too far away from the block so it doesn't need to be subdivided (this 'too far' should be a function of the block size - i.e. if the block is 32x32m, then 'too far' could be more than 32m away from the block's side, but if the block is 8x8m, then 'too far' is going to be 8m away from the block's side),

b) or your block's resolution is small enough that you don't need to subdivide anymore. By that I mean that if your block size becomes 8x8m and you're doing 8x8 samples, your resolution will be 1m. If that's good enough for you, then stop there. if it isn't, then subdivide the 8x8 block again, so now you have a 4x4m block that has 8x8 sampls, so your resolution will be 0.5m, giving you even more fine terrain. 

 

Of course, your terrain function must be specifying fine enough details for smaller resolutions, because if its not, your 0.5m resolution block will look exactly the same as your 1m resolution block, only use up more triangles. If using perlin noise, you just have to make sure you add noise with small enough frequency to give some definition at 0.5m.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!