I began work on my terrain part of my MMO/Persistant World game, and considered what I wanted the terrain to be able to do.

Preface: this is just kinda a think out loud situation.

The gist of it is, I want players to be able to alter the terrain. Because the game is going to support player structures, it might be required to terrace a hill, dig a hole, flatten the ground. I also intended for them to eventually dig a mine made out of voxels polygonized by an inside out marching cubes method, but thats a whole other topic.(Sounds minecrafty to me)

I understand that if someone alters the terrain you send a simple "delta" packet to alter the client's representation of the terrain. But my issues lie in simply transversing the world's large terrain. The issues are this.

1) If a player is moving through the world I need to update the client on what terrain is around him. If I use chunks of terrain at different LOD's I can reduce the height points needed in the area. Reducing the amount to be sent. At a terrain resolution of 1 point per meter (2 bytes per point), and a sight "radius" of 4 kM I would need almost 50kb of data for a single 32 meter shift in position. Seems like hefty chunk of data.

2) The client request for map data should be kept at a minimum size as well. Supposing the client cached some of the terrain data it would reduce the need for data from the server when a client hung around a single place. It wouldn't be great if the client asked for each chunk individually. Perhaps a rectangle request?

3) If a client caches a chunk, walks out of range, someone digs a hole, and the client walks back. How does the client know that it needs an update and can't use its cache anymore?

Any thoughts would be helpful.

As a point of reference, if terrain is comprised out of heightmaps, then just streaming images works. A dual core server is handling a GIS system of hundreds concurrent users, serving IIRC 2m or 1m resolution images at various resolutions, encoded and clipped on the fly into JPEG chunks. Obviously modifiable by users, backed by some enterprise DB. All over HTTP obviously, displayed by browser. Almost certainly not as optimized as Google Maps or such. Same system is used to serve height data (PNG I think) at about the same resolution, 3D scenery is generated client-side on-the-fly. There are about ~5000 triangles active at any given time.

The rest is just a matter of relative scale, but streaming is really the least of the problems.

Quote:At a terrain resolution of 1 point per meter (2 bytes per point), and a sight "radius" of 4 kM I would need almost 50kb of data for a single 32 meter shift in position. Seems like hefty chunk of data.

If it becomes an issue, mip-map streaming solves most of problems. Stream chunks at different resolutions, perhaps use a noise generator or such.

Keep in mind that rendering is not free either - 4096x4096 terrain is a lot of vertices and triangles. Instead, consider 128x128 at 1m resolution, 256 at 4, 512 at 16 (numbers might be way off). Half a kilometer is quite far. And anything beyond will likely need billboarding anyway. Adding some procedural or fractal noise can also mask the low resolution if needed.

There are also lighting and post-processing problems with terrain modifications, generation of pathing and collision, clipping, culling, ....

The big problem is concurrent modification. Free-form concurrent modeling is likely not possible, too many issues with latency and similar stuff. Instead, mask these problems by making the actions somehow abstract. Rather than digging a hole, spawn a bulldozer that has one of those progress bars and then takes 15 seconds to dig a moat by itself. Or if explosion occurs, compute the impact when grenade is launched and apply a few seconds later.

That is the practical solution - it's obviously possible to have full free form, but only with decent budget and a user use case.

There is likely a reason why terrain isn't modifiable in any of mainstream titles.

Hmm

Rendering currently is not an issue I am able to render a LOD controlled map of the size I want. The points being rendered certainly isn't close to 4096x4096, thats just an indication of how far I want the person to be able to see.

That 50kb calculation was actually with different resolution blocks



Is a general picture of how I'd handle LOD levels, the blue lines are what I thought should already be buffered and the red lines are what would need to be requested if the player moved to the right.

Each subsequent red line contains twice as many chunks but the chunks have half the resolution so the number of bytes per stay the same.

EDIT: ^^^ Is incorrect, If I skip every other vertex, it is not half the vertex data. Making the numbers below totally incorrect. However it works out well for the solution because there is less and less data being sent. I just look stupid.

If there are 5 rings at 16x16 chunks I would have to load 21504 bytes of data at 2 bytes a point. If there are 5 rings of 32x32 I need to load 73728 bytes (I screwed up my 50kb calculation) of data. What I took out of your thing about images is I should compress my height data like an image. I know PNG uses DEFLATE, would it be any advantage to combine a lossless compression for inner rings and a lossy compression for outer rings?

As for concurrent terrain modification, it wouldn't be a smooth transition unless the client interpolates it. Most actions would be slow anyway, like shovel work. Aside from like you said, explosions which would have a precomputed terrain patch.

Despite most main titles not including modifiable terrain, however I would still like to find some sort of perhaps compromise in size or map complexity to accomplish my goal. Perhaps lowering my view distance and height map resolution. But I would like to avoid that.


[Edited by - Tocs1001 on August 21, 2010 10:32:10 PM]

A few observations;

Half a kilometer (500m) isn't really that far away when it comes to terrain. A crestline at that distance needs a fair amount of samples per meter to look decent.

Digging/craters also needs really high resolution to look good unless you're creating large moats. Texturing etc can help you alot here of course, especially procedurally generated.

If you're already doing multiple data resolutions, I'd recommend a quad tree instead of some origin-centered approach. It makes for more complicated tools, but is really flexible and dynamic. The non-leaf nodes can be used when streaming lower resolution for rendering.

Terrain modifications in multiplayer games is problematic because of the potentially large amount of data that needs to be sent to joining clients; especially in an MMO. It can be alleviated by predefining "brushes" tho; when a player digs a hole a particular brush is applied and when another clients needs to see the modifications it is only sent what brush and where - not the resulting heightfield samples affected. In an MMO you might also get away with just sending modifications within a certain radius, unless you're adding or removing entire mountains.

Make sure your physics engine can handle the solution you go with (for example, it might not like lodded data; you'll probably need to keep the entire heightfield in memory).

Quote:Original post by Tocs1001

Rendering currently is not an issue I am able to render a LOD controlled map of the size I want. The points being rendered certainly isn't close to 4096x4096, thats just an indication of how far I want the person to be able to see.

Too granular.

Make each patch 256x256. On server, keep 4 different levels of detail. Perhaps 1, 4, 16 and 64m per pixel. Each patch is then 256m - 16km across. This way, lower level terrain is streamed very rarely. This terrain is fixed or very rarely changed, so it can be efficiently cached.

Quote:What I took out of your thing about images is I should compress my height data like an image. I know PNG uses DEFLATE, would it be any advantage to combine a lossless compression for inner rings and a lossy compression for outer rings?

Lower resolution ones can probably use 8-bit per pixel and scaling factor. Doesn't matter really.

PNG is one way, but I don't recall off-hand if it supports 16-bit channels. Zlib compression would work as well, especially if chunk is swizzled first - write all MSBs first, then next bit, and next, until LSB. Most of these would be either 0 or 1. Implementation detail.

Quote:Despite most main titles not including modifiable terrain, however I would still like to find some sort of perhaps compromise in size or map complexity to accomplish my goal. Perhaps lowering my view distance and height map resolution. But I would like to avoid that.

1m resolution is probably too low. Might as well start with 4m or similar. Then, for detail, send such data separately as set of modifications and let each client compute it themselves.

This gets around the resolution problem, since suddenly a moat can use 10cm resolution - and even get scaled according to user's LOD preferences. A way must be found to deal with complexity - each such feature adds to processing times, so 6000 explosions would require 6000 features to be processed and integrated into map. One of features could be arbitrarily placed heightmap patch.

Quote:A crestline at that distance needs a fair amount of samples per meter to look decent.

Except it will most likely be precalculated and baked into textures or faked with shaders or similar. Fully streamed terrain simply isn't best suited for such features.

We seem to have lost track of the question.

The problem is not rendering, the crestline doesn't need to be detailed. Its a shape in the distance so that if your exploring the world(part of the game) you don't suddenly come face to face with a mountain when haphazardly walking around.

Besides increasing the resolution on my crestline will do nothing but create more problems I already have TOO MUCH data to send.

Modifying my terrain wasn't my main issue, I get how to save bandwidth by sending actions instead of terrain modifications. That is a no brainer. Although limiting to one edit per area would be a significant load off editing and loading (Could predownload the base terrain) I will use this as a last resort, as it isn't really in the spirit of my original intension.

My problem lies in streaming the terrain as you move throughout the world. I can't simply have them download the whole world every time they log in. That would be stupid. They could however download the map once, and download a delta list on login, depending on server activity the size of the delta list could either be large or small. This hardly seems appropriate though...

I don't see any significant advantage to switching to a quad-tree method. I was looking at http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.pdf as my method of rendering. It is one of my favorites because of ease of implementation, uniform buffers and hardware vertex manipulation. And you don't have to deal with stitching. Either way a chunk of terrain is a chunk, or perhaps I'm missing the point?

Quote:1m resolution is probably too low (high?). Might as well start with 4m or similar. Then, for detail, send such data separately as set of modifications and let each client compute it themselves.

This gets around the resolution problem, since suddenly a moat can use 10cm resolution - and even get scaled according to user's LOD preferences. A way must be found to deal with complexity - each such feature adds to processing times, so 6000 explosions would require 6000 features to be processed and integrated into map. One of features could be arbitrarily placed heightmap patch.

I had not thought of this supposing I did a 4m separation. I could have 8x8 chunks and a chunk would only be 128 bytes which fairly cheap. I could put in more points client side and do a bicubic interpolation to smooth things out. Lower rez digging, same resolution look. The initial load size uncompressed would only be 11kb.

Thanks for your help guys :)

Quote:Original post by Tocs1001
I already have TOO MUCH data to send.

Do you?

256x256 chunk is 128kb, let's assume it's 1m resolution, so 256m across.
Person walks/runs at ~10km/hour = 2.7m/s.
It takes them ~95 seconds to cross that chunk.

Required worst-case bandwidth is then 1.3kb/sec.

Regardless of how many lower resolution maps are used, each is half the resolution and they add a grand total of 33% (mip-map overhead formula), so worst-case bandwidth (without compression) is well under 2kb/sec sustained. That is dial-up rate.

Quote:I can't simply have them download the whole world every time they log in. That would be stupid.

You do realize that Google actively combats and even forbids any kind of caching of YouTube videos - they must be downloaded on each play and only persist until that browser session is closed. And they make up ~80% of internet traffic (or similarily silly figure). Each video is ~30-70MB.

Just to point out that very few users have problems with this much content, so it comes more to server-side bandwidth costs.