Archived

This topic is now archived and is closed to further replies.

blahpers

Massive terrain/landscape management

Recommended Posts

blahpers    122
This goes out to anyone who''s actually written code for a massive landscape/terrain engine--not just small landscapes like in most tutorials. Okay, so I''ve done the landscape thing for a relatively-small landscape using a heightmap, and I''d like to generate a nice big one--say, an entire game world. To do this, I couldn''t possibly make one giant mesh--it would never fit into memory. So this weekend I tried a system of dividing the landscape up into chunks (I''ve heard others call them "patches", whatever). I made my own binary file format for a giant landscape file with a header followed by a series of blocks containing the data for each chunk. I could load a chunk with a simple seekg()/read() combo. This seems to be too slow; it takes about 1/10th of a second to allocate, read in, and deallocate a chunk in system memory. That doesn''t even count (de-)allocating the video memory resources (e.g., vertex/index buffers). I''ll frequently have to load and free many chunks in a single frame whenever the player walks the character toward the boundary of a chunk. This wouldn''t happen every frame, of course, so the result would be smooth walking at 60+ fps with the occasional 1-second-or-more pause for loading/freeing. That''s pretty jerky, and pretty bad; I''d like to do better. I''ve started wondering if there''s a better way to do this and I''m missing it. I need a system where I have the freedom to travel all over the world without really long pauses to load and free resources. If you''ve ever flown the airship over the world in FF7 or 8, that''s the kind of freedom I need. That map uses a _lot_ of vertices (FF even deforms the map to simulate curvature of the globe), but there are no noticeable pauses when passing over boundaries even in the PC version of FF7. The floor is open. --- blahpers

Share this post


Link to post
Share on other sites
DanG    122
I have not implemented a terrain engine on the scale that you speak of, however i have some ideas. Firstly, if your generating your mesh using heightmaps for each patch, i don''t see why you can''t use an algorythm like ROAM to dynamically create an optimized mesh using the heightmap values.

If that doesn''t work in your model the other thing you could do is to slowly load in the nearest patches as you play, perhaps in another thread. This way the time to load a patch is strached over a longer period. You could also optimize which patch to work on loading. Say, if the players in on patch 3 and running in the direction of patch 7, work primarily on loading 7. As the player leaves the patch do the oppisite. Say, if the player crossed over to patch 7 two seconds ago and is running away from patch 3, start kicking some of patch 3''s data out of memory, if the player turns around, work harder on bringing patch 3 back into RAM.

Just one more thing. At the end of your post you mentioned curveature of the earth. If your high enough to see that than the ground probably doesn''t need to be very detailed.

Anyway, thats my two bits.

He who said money was the root of all evil knew little of the nature of money and less about the nature of man.

Share this post


Link to post
Share on other sites
_SHO_NUFF    122
You''ll also have a problem with the guy heading towards corners, in which case you''re have to load 3 chunks at a time. If you want, you could help this by making your chunks hexagonal.

Share this post


Link to post
Share on other sites
_SHO_NUFF    122
Another things is, since the problem is memory size, you could use a common compression technique. If you''re holding your height values as ints, you could to this:

for the first hieght in a row, you hold the hieght as an int. Then for each other value, you hold in a char the difference in height from the previous one. Of course there are some limitations but it would make load times shorter, and chunk sizes smaller, so you could maybe have a lot of nearby chunks compressed in memory like this, and uncompress them when it looks like yuo''ll have to display them

let me know how it turns out, I''m starting the same thing.

duvenaud@escape.ca

Share this post


Link to post
Share on other sites
blahpers    122
Thanks for the replies!

I''d never heard of ROAM, so I did a search and . . . wow. This looks very interesting (read: very hard ). But, what the heck, I''m game for anything.

I''ve only scanned the original ROAM abstract, so I''m curious as to how they resolved the "caveat" that all of the terrain data had to be in memory. I could always just read it all in O_o but I don''t think I''ll trust Windows'' virtual memory manager that much.

Switching to research mode,


---
blahpers

Share this post


Link to post
Share on other sites
CheeseGrater    122
There are functions available that can map a file into memory space (consult the MSDN under windows or the man pages under unix), so you can store the terrain in one big file and let the OS page the necessary portions in and out of memory as you need them. You''d probably want some sort of quadtree or other frustrum cull with this method to avoid accessing data you don''t need.

The OS is usually pretty good at paging memory, so there''s no need to reinvent the wheel.

Share this post


Link to post
Share on other sites
Eric    138
As an alternative to what _SHO_NUFF mentioned about heightmap compression...

I use two heightmaps. One is small with higher precision, say 1k x 1k and 16-bit. The other is large with lower precision, say 4k x 4k and 8-bit. Each 16-bit value serves as a common "base" height and the 8-bit values serve as offsets. Basically, I''m relying on the fact that nearby heightmap cells will be "within 8 bits" of each other. The result is 16-24 bits of precision everywhere, with an overall cost of 18 MB for the 4k x 4k grid (9 bits/cell).

If you still think you''ll need to stream in heightmap data, here is my suggestion (your platform is Windows, right?):

(1) Load your entire terrain into virtual memory (hopefully it can all fit!). You may have to memory-map the data file rather than actually read it into memory, just to avoid ridiculous load times.
(2) Divide your terrain into a grid of chunks as you''ve described. Suppose the only chunk you need in memory is the one which the camera is in.
(3) Have a second thread always running. Its only job is to regularly touch the memory of the nearby chunks that the camera might move to soon. When a page fault occurs, this thread will pause for a second, but your main game thread won''t. Windows will automatically page out the least-recently-used chunks as necessary.
(4) Don''t allocate and free vertex/index buffers on the fly. Allocate everything during initialization and find a way to reuse buffers.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
This may not be aplicable, but if you use a function to create your terrain then access to disk shouldn''t be a problem.
The main drawback is that you can''t directly control how the terrain will look. Using Perlin Noise(google) or something similar, one can "generate" points as needed. If you use pseudo-random number generators with a high enough period, you can create virtually endless terrains.
You could still have "cells" that you load in, but do it dynamically by generating the new points. You could also use it to only figure some of the points for those far away, or figure them to a lesser presion. You can find the height at arbitrary points as you need them. You could even map a whole globe this way by using two angles instead of an x and y.

I haven''t really done that great of a job at explaining myself, but if you check out google, you should be able to find some better explainations of this(especially the first two links). If anyone has tried something similar to this, I would like to hear how it worked out.

Karg

Share this post


Link to post
Share on other sites
DanG    122
From my point of view i see the best two possibilities as ROAM or a similar on fly LOD algorythm or a procedural generated terrain. The ROAM algorithm has the advantage that only a currently optimized mesh and the origonal height map are necesary to be in memory. It also sends triangles to the graphics processor in a very even manner. The problem is that on really large maps, the mesh and height map can be too big for memory. Certain culling techniques can be implementeded that keep mesh size down, but it can still be a problem. The other possibility is a procedurally generated turrain with prebuilt tiles. What this means is that you design a heightmap only for the specific areas where it effects gameplay. These are skattered around the map. Then at runtime using some algorithm to randomly genereate what is between the all the tiles (or the ones that are currently seen) this can greatly reduce the memory rewuirment, but it doesn''t work for all things. Often you will come back to the same procdurally generated area and see something new that has been genereated. This gets very confusing to a player sometimes, so be weary. Still its a good choice on really large maps.




He who said money was the root of all evil knew little of the nature of money and less about the nature of man.

Share this post


Link to post
Share on other sites