• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Hawkblood

Terrain generation

20 posts in this topic

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".

0

Share this post


Link to post
Share on other sites

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.

1

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.

0

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.

1

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.)

0

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.
0

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.

0

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.

0

Share this post


Link to post
Share on other sites

@Milcho

That makes sense. I think I understand how to make the quad-tree....cool.png

Basically, I create several planes of varying complexity and adjust the Y-values of the vertices according to the elevation of the spot it is on. I would need to make a routine to render only the ones in view (this will be first person). 

 

BTW, do you have a good quad-tree tutorial?

Edited by Hawkblood
0

Share this post


Link to post
Share on other sites
I kind of second FLeBlanc's recommendation against a quad-tree here. You can get it to work, and it's not really as hard as he makes it out to be, but I'm not sure it's really the right abstraction to use for this. In my experiments in the past, I ended up with a lot more overhead and complexity for the tree management and visibility determination than I felt was really necessary.

If you use a spatial hash, you could even go with something as simple as:
std::map<std::pair<int,int>, TerrainBlock> blocks;
for your map structure. Then if your camera view is centered upon some location, (X,Y) it is a simple matter to find which TerrainBlock (X,Y) resides within, construct a std::pair<int,int>(BlockX,BlockY) from the block coordinates to index into the map and obtain the TerrainBlock, then compute a rectangle of blocks surrounding this central block as the visible area, size of the rectangle decided by your maximum view distance. As the center viewpoint moves, you simply re-calculate this visible area, load TerrainBlocks that need to be loaded for the new area, and discard TerrainBlocks that are no longer within the visible area. I have implemented infinitely sized outdoor areas this way before, and it does work well; plus the coding was far less complex than quad-tree management.
0

Share this post


Link to post
Share on other sites

I kind of second FLeBlanc's recommendation against a quad-tree here. You can get it to work, and it's not really as hard as he makes it out to be, but I'm not sure it's really the right abstraction to use for this. In my experiments in the past, I ended up with a lot more overhead and complexity for the tree management and visibility determination than I felt was really necessary.

[snipped for ease of reading]

The only problem I see with this is that in order to have large viewing distances the number of blocks you'll need to draw will grow quite fast (much faster than a quad tree). From stuff I tested, the limiting factor then becomes not the actual polygon drawing time, but the number of blocks you need to iterate over, plus the number of view frustum tests you need to run on single blocks.

 

True, for a small enough viewing distance this won't be an issue (small enough being again, determined by how large you make your blocks, since the larger your blocks the less of them you'll have for a given view distance), but overall, a quadtree will be able to handle larger viewing distances much better than a block map/array.

 

I definitely agree with you on the complexity of the code though - quad trees can become a slight pain to manage correctly. In my eyes its a tradeoff between simplicity of code and having a really large viewing distance - so if you don't need to have large viewing distances, don't bother with quad trees. If you do want large viewing distance and you don't mind more complex code, quad trees :)

0

Share this post


Link to post
Share on other sites

Isn't it better to use Simplex noise instead of Perlin noise? That is, Simplex noise is faster? I have only used Simplex, so I don't know for sure.

 

I organize blocks into chunks of 32x32x32 blocks. The chunks are then organized in a map<>, just as JTippetts suggested above. The chunks are transformed into a structure better suited for drawing. That is, all faces that may be visible are identified and ordered together with other faces of the same material.

 

I use 3D simplex to create caves and overhang.

 

Sure, there certainly will be quite a lot of data. Even with advanced culling, you may end up with quite a lot of vertices per frame. This is a disadvantage of a voxel based worlds.

 

Terrain_2013-01-25.jpg

 

I am not sure how a quadtree would help you. It is very efficient when you want to find what other objects are near, as the cost doesn't grow quadratically. But if you just need to know what objects are inside the view frustum, the map<> should suffice?

0

Share this post


Link to post
Share on other sites

I feel I need to give everyone a better idea of what I have and what I want.....

My current project is a multi-aspect simulator, if that makes sense.... It has space flight, landing sequences for planets, classic first person, and driving a rover. All views are first person/cockpit view. I am trying to make this game with absolutely NO transitions-- that is to say, the player can fly through a solar system, orbit a planet and then land on it, get out of the ship and walk around. All of this without load screens, pauses, or any other type of transition. The way I would do this is to take the "generation" parts and call them in small chunks instead of all at once. This way, the frame rate suffers as little as possible while still generating what's next.

 

I currently have a large star cluster for the player to explore. Each system will generate as the player is in FTL enroute-- I know. This sounds like a transition, but I want the player to feel as if he is actually on a starship, so it works here. Each planet of the system has a unique texture (hopefuly) and atmosphere generated by perlin noise. Once in a system, the player can go to any planet and orbit it. Once in orbit, the player can select a landing site and begin the landing sequence.

This is what I need to accomplish:

Generate the landing area in a progressive maner.

Split it up in some way to make it managable.

Have high detail up close and low detail far away.

I would like to make it possible for the player to completely traverse the planet and look at every rock and tree without transition...... I have ideas on how to do this, but I don't want to re-invent the wheel.

 

As larspensjo said, perlin noise is slow. So far, it's the only thing I have been able to get to work. If someone has simplex in C++ with no frills and a simple implimentation example, I would love to look at it. I have looked at some simplex code and each time I got a bunch of junk!

 

By the way, is this a good place to post "work in progress" or is there another forum for that?

0

Share this post


Link to post
Share on other sites

If someone has simplex in C++ with no frills and a simple implimentation example, I would love to look at it. I have looked at some simplex code and each time I got a bunch of junk!

I am using simplexnoise1234.h and simplexnoise1234.cpp. I haven't analyzed it much, but I think it is rather efficient.

I would like to make it possible for the player to completely traverse the planet and look at every rock and tree without transition...... I have ideas on how to do this, but I don't want to re-invent the wheel.

It i possible, I am doing it, based on voxel data. The world is infinite (kind of). Instead of planets, though, I have "flying islands". But it would be easy to increase the distances between the islands.

But I have split it up into a server and a client, to allow many players to explore the same universe at the same time.

What I am not using yet, is a LOD functionality. The block resolution is 0.5m, but special objects can have higher resolutions. Edited by larspensjo
0

Share this post


Link to post
Share on other sites

 

I haven't analyzed it much, but I think it is rather efficient.

So, you've used it? How do I generate 3D noise so that it can wrap around a sphere?
Edited by Hawkblood
0

Share this post


Link to post
Share on other sites

I haven't analyzed it much, but I think it is rather efficient.

So, you've used it? How do I generate 3D noise so that it can wrap around a sphere?

There you got me, sorry! I use it, but only on a flat world (though with infinite height).

 

I admit I don't know how to apply the simplex/perlin noise function to spherical objects. I wonder if it would be possible to make transformation from polar coordinates to rectangular, without have singularities at the poles or non constant resolution.

 

One common way to do this is to use a "cube map", which is really just 6 rectangles stitched together into a cube. The height map from these would need to be adjusted by the average radius of the sphere, which should not be hard. There are some disadvantages with this is that there will be a discontinuity between any of the 6 adjacent rectangles. The resolution will also be slightly different at the edges and corners of the cube map (with a factor of sqrt(3)=1.73 in the corners). This non linear resolution should be possible to compensate for, I think?

0

Share this post


Link to post
Share on other sites

I've been trying to upload an image to this post with no luck. Here is a link for it:

https://docs.google.com/file/d/0BySKIgkx3OcbQUNsZkNLSlljcXc/edit

 

As you can see, the top has less quality than the bottom. The top is done with simplex, while the bottom is done with perlin. How do I get better quality with simples?

It is notable that simples is about 2x faster than perlin.....

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0