Jump to content

  • Log In with Google      Sign In   
  • Create Account


Infinite Terrain, howto?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 gnomgrol   Members   -  Reputation: 568

Like
0Likes
Like

Posted 22 June 2012 - 03:46 AM

Hello everyone,
Im currently working on my terrainengine. I would like to have a very large, fully explorable world.
My Terrain is splitted into chunks already, and its a regular Index/Vertexgrid.
I know that I need to keep just the visible chunks in memory, but im quite unsure how to put this in code.
It sounds to me like I have to compute atleast the normals and heights again(indices are fix and vertices x+z can be done in Vertexshader) as soon as a new chunk has to be loaded. But that takes way to long!

If I have lets say 9 chunks around the player, and then update the heights and normals of them when the player moves over in a new chunk, as well as the x and z value offset for eachs chunk position I pass into the vertexshader . . . would that do any good? Seems a little uggly to me.

Are my chunks to huge for this? 256*256 vertices currently.

If anyone knows about a better method, or can tell me how (MMO)RPGs handle their terrain, please answer.


-gnomgrol

Sponsor:

#2 Ashaman73   Crossbones+   -  Reputation: 6763

Like
0Likes
Like

Posted 22 June 2012 - 05:35 AM

I've a similar approach, but with more chunks (50-100) which are smaller (32x32). Chunks are loaded/created asynchroniously and uploaded synchronioulsy.

#3 samoth   Crossbones+   -  Reputation: 4533

Like
0Likes
Like

Posted 22 June 2012 - 05:57 AM

Generally, I think power-of-two is not such an awesome choice, power-of-two-plus-1 is better. This allows you to do LOD much more easily. A grid of 257*257 vertices very nicely splits into two grids 129*129 vertices each, with one vertex shared at the edge. You want to share the vertices at the edge, or you must do extra work to avoid "holes".

If you make the chunks smaller, the time to compute them and the memory requirement will decrease quadratically. For example, 64*64 only takes 1/16 the memory (and time) compared to your choice of 256*256. Of course when chunks are smaller, you will need a larger number of them, but you have a better granularity.

As already stated in your other thread, you will want to have a "cache". You will need the surrounding 9 tiles in any case, but it is better to start off with e.g. 25 (the surrounding 5x5 instead of 3x3). If you make them 64*64, those 25 tiles will alltogether take less memory than 2 tiles at 256*256. Now don't be too cheap and make your cache capacity somewhat bigger, say, 50 or 100 tiles (decide at program start based on how much memory you have). This will save you from re-computing (or loading from disk, whatever) the same data again and again if the player moves around in a "typical" pattern.

You don't know where the player will move, but no matter where, if you start out with 25 tiles, another one is always immediately available, no matter which direction the player moves. This is nice.
As the player moves, precompute new tiles in the direction the player moves, and add them to the cache. If you are comfortable with threading and synchronization, you can push this work to one or several background threads.

The cache will eventually become full and evict the least fit tile (oldest, farthest away, or some combination, or some other metric) to make room for another one.

Note that everything greatly depends on your requirements. I cannot exactly tell you what resolution your tiles must be, what chunk size they need to be, or how many you need to precompute. For example, assuming 64 meters per tile on 1m/vertex and 0.1s to compute a new tile, a player moving at 230 km/h could outrun your computations. If the player avatar is a sports car, this may be a problem, and you definitively need a bigger set of tiles and/or faster computations. If the avatar is a human, it's not going to happen. You may need more or fewer vertices, depending on what you want and on what you can deliver computation-wise.

Tiles that are more than 1-2 tiles away can eventually be a lower LOD. Again, the exact details depend on your requirements, I cannot give you a precise figure. An ant, a dwarven fighter, an airplane, and a starship have different horizons, and a grid resolution of 1km is not the same as a grid resolution of 1mm.

If (assuming a "kind of normal" setting) you have a 1 meter distance between vertices, the second closest tile will on the average be 96 meters away. It is usually acceptable (and even desirable!) to draw things that far away with less detail. On the other hand, if you have e.g. 16 vertices per meter, then we're only talking about 6 meters. You probably don't want to reduce detail at such a close range.
You probably want to have the higher levels of detail in a cache too, but the lower the level of detail gets, the more you can just as well calculate terrain on the fly. Three levels lower, you only have 81 vertices total (9x9) in a patch.

Edited by samoth, 22 June 2012 - 05:58 AM.


#4 Narf the Mouse   Members   -  Reputation: 318

Like
0Likes
Like

Posted 22 June 2012 - 06:20 AM

http://skytiger.wordpress.com/2010/11/28/xna-large-terrain/ - This one seems rather good.

#5 gnomgrol   Members   -  Reputation: 568

Like
0Likes
Like

Posted 22 June 2012 - 06:22 AM

Thanks for your answer.
I think I got now what to do, atleast the idea of it.
What could the cache look like in code? A std::vector or somewhat?
The biggest problem I saw was the creation of new chunks, but multithreading could really help.

Ingame, the player is gonna be human, so I dont need to compute that much new chunks at once.

And thanks for the tutorial, im gonna read it right now!

Edited by gnomgrol, 22 June 2012 - 06:30 AM.


#6 samoth   Crossbones+   -  Reputation: 4533

Like
0Likes
Like

Posted 22 June 2012 - 07:11 AM

Your cache will need to perform three things:
1. lookup an element based on one key (its identifier, so you can draw a tile)
2. lookup an element based on a different key (the age/cost metric, so you can throw the least needed element away)
3. frequently remove elements from a "random" position in the container (and add a new one in its stead)

2. and 3. could also be done in one sweep over the set once per frame. Again, it depends on what you do, how big, etc. -- std::vector is generally a poor choice, because it does not support any of the required operations well.

Often, one implements such a thing with two std::maps or with a boost::bimap. A single map, a list or priority queue might be concieveable but they're not ideal in one operation each.

On the other hand, depending on the size, it may not matter much. When iterating over e.g. 100 elements once per frame to find the oldest one and mark it for deletion, the fact that it's O(N) does not really make all that much of a difference.

Edited by samoth, 22 June 2012 - 07:12 AM.


#7 gnomgrol   Members   -  Reputation: 568

Like
0Likes
Like

Posted 23 June 2012 - 02:32 AM

Thanks again, but Im affraid I still cant make it.
I cant really get what to put into the two std::maps (I dont want to use an outer lib if possible).
I made the chunks mark themself for deletion as soon as they get out of range and then erease them (works fine).
But I cant get how to compute where a new chunk has to be created and what key to choose to indentifier them, as well as how a second map will help me, sorry.

What I have right now looks like the following:
One std::map which contains all chunks and an int to identifier them.
Every chunk has a startX/startZ coordinate, and its width/height. In their update() function (called every frame) they test if their startpoint (lower left corner) is in range of 500 to the player. If not, they mark themself to get deleted.

But now I cant really deside when to create a new one, and how to store it. The second map you mentioned confuses me =(

Edited by gnomgrol, 23 June 2012 - 02:38 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS