Streaming Terrain

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.

You do not need 1m resolution 4 km out.

Also, if you can pre-load the base terrain, and send edits as separate chunks rather than send the data baked, you may get away with sending less for most areas -- especially if you limit how densely the users can edit the terrain!

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.

Quote:

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

Let's assume we tolerate only a 2 pixel error (there's at most 2 pixels distance from any given pixel to a pixel derived directly from a sample).
Let's assume the screen is 1200 pixels wide.
Let's assume a 90 degree horizontal FOV (45 out in each direction).

This means we need a sample every 4 pixels, or 300 samples across the 90 degree FOV. Which, at 500 meters, means 300 samples over 500 meters, or one sample every 1.6 meters, so I think "fair amount of samples per meter" is overstating the problem a bit.

I also know that most MMO games where you are ground based wouldn't get you more than 500 meter view distance total; they'd hide the further in fog and level design. Looking at WoW, for example, you don't have very far views, even when flying between continents. Most MMO games would probably be OK with a 10 pixel error, too (so, one sample every 20 pixels, or ~60 samples over 500 meters).

Still, there are many things you can do in game design. For example, if building structures is the main reason to sculpt terrain, you can make the structures auto-conform the terrain, so no explicit sculpting is needed.
You could also only allow users to sculpt terrain coarsely -- "flatten a square of size 20x20 meters" or "build a 50 meter wide moat at this location." Then don't let multiple terrain edits overlap in area, and send only the terrain edits, not the outcome. That ends up being a much smaller amount of data, even at the highest edit density -- mostly because you limit the allowable edit density this way.

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.

Quote:

We seem to have lost track of the question. The problem is not rendering

I think it is intricately tied into rendering, but perhaps we didn't explain ourselves well enough.

The basic assumption here is that you don't need to download "just in time" more data than needed to render the current view. Thus, what you actually want to render does matter, and drives how much data you need to download. If you can get away with rendering less data, then you need to download less data.

Also, if there is a downloadable/installable part, then the user can download/install the "base terrain" once. This means that there is zero data send needed when moving. If players then edit the terrain, you only need to send the deltas edited by players, as you move around. There are many ways to make the data for user edits be smaller than the base terrain mesh.

If players can't edit terrain "too much" (say, build a mountain where there was a lake before), then you may even be able to get away with not downloading user edits for the further-out terrain blocks, and only download edits for the close-by terrain blocks.

I now feel incompetent.

Quote:

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.

I guess thats why earlier you said

Quote:

Too granular.

Sorry I didn't understand earlier. I also didn't have the appropriate visualization of how "hardy" an internet connection is, thanks for the youtube bit.

Quote:

The basic assumption here is that you don't need to download "just in time" more data than needed to render the current view. Thus, what you actually want to render does matter, and drives how much data you need to download. If you can get away with rendering less data, then you need to download less data

That is the basic premise of what I was starting under, unfortunately I didn't directly tie it to rendering, I just assumed any rendering type would put the LOD data to good use. Obviously, bad assumption.

I think I have enough info here to create a working solution. Thankyou both, so much, for your help.

Almost all IO today has very high bandwidth, but relatively high latency, especially for real-time use.

Storage also tends to not be a problem. Having client cache 500MB is not really a problem. And 50MB is quite plenty for terrain, especially if one byte = one vertex.

Compression tends to work better with large samples, so sending more will result in sub-linear bandwidth requirement.

If one wanted to go really computer sciensy on all this stuff, there are various wavelet techniques where detail is sent in frequency domain or something like MPEG's SDCT which allows composition of individual patches in transform independent way. But IMHO it's not worth it.

There is also the problem of server load. With 16x16 patches, server would need to send a new patch every 5 seconds or so. But with 500 users that means once every 10ms, and that is a lot of disk IO. Without compression, sending 256x256x2 patches means 76 patches can be sent each second over 100MBit line. Over 700 on gigabit. Multiply by some integer factor if compressed.

Computers have gotten faster, but they still prefer trivial tasks, such as simple additions or multiplications. Accuracy with above schemes might also be a problem for deterministic algorithms. It turns out that sending large patches can be done surprisingly efficiently, especially when not constrained to some standard such as HTTP + HTML.

Another comparison - cnn.com's home page is 510kb. gzip is probably used, so transferred data is likely less.

So the best way for this would be to simply have server stream chunks based on client's position. This allows prioritization and bandwidth control based on server workload.


The two much more important problems that remain are:
- how are terrain modifications handled (what if client must apply tens of thousands of grenade shells). What if terrain change requires client to load 500MB of additional textures (besides 400MB already in memory)?
- how much does bandwidth on server cost? Is it unlimited or metered? What is the CPU cost break-even point when it might (not) be worth compressing or processing more?

One method I found to reduce the server load for sending terrain patches to clients was to use a combination of where the same player had been before and where on average most other players were also going in the game.

For this I used the statistics server from RNLobby to keep track of all player's movements through the game. Since the statistics server is basically a big programmable number cruncher with database back-end it doesn't matter if it crunches positions or kills.

This means for each game map it was possible to build up a hot-spot map of where players were likely to go next based on where they were and had been previously. If the player had not been to the map before then the average accumulated results based on other players was used.

Since the statistics server could store each individual player it could build up over time a preferred route for players. People are creature of habit, especially when they work out their routes around the map.

This information allowed the server to work out ahead of time where the player is going to be going based on past performance and send terrain data before the client is going to need it.

Of course if the player went too far away from their previously chosen route the system would revert back to sending terrain that is close or use other player data as a basis to guess where they might go. The next time this different route would have some weight and over time if the player changed their habit the system would accommodate that different route.

This proved to be more efficient than just sending what is near the player at the current time.

The other advantage of such a system using the statistics server was that the games designers could use this system to see how their levels were being used by many players. It had history tracked over time as well so they could see how players slowly found new areas of maps which suddenly got very popular.

Hi there!

How about sending an update to all nearby (affected) players with "dig a 50x50 hole at x,y" and let the clients perform the changes as needed? Meanwhile - the same command is sent to the server that does the necessary changes on its map (which will be streamed by any other player coming afterwards).

That way you offload the server and traffic and rely on the clients to change their approximation of the game world.

EDIT:

I realized you've thought this through yourself already.
What I would do is simply to store each change in a list.
Upon login that list (hash nr etc) would be compared to the clientside version and recreated appropriately.
At a certain point the list would be to time consuming to recreate and the remote copy of the mapfile is downloaded and replaces the old one.

Quote:

Original post by Martin Piper This proved to be more efficient than just sending what is near the player at the current time.

That's interesting! What specific game was this for?

Quote:

The other advantage of such a system using the statistics server was that the games designers could use this system to see how their levels were being used by many players. It had history tracked over time as well so they could see how players slowly found new areas of maps which suddenly got very popular.

Each year at GDC, some new studio gives a presentation that boils down to "and then we started plotting X against a map of our levels, and the designers went gaga."
I've come to the conclusion that you should just plot everything as a separate (controllable) overlay, and let the designers turn them on/off as appropriate.

Quote:

Original post by hplus0603 That's interesting! What specific game was this for?

Unfortunately I cannot say yet.

I have also given thought of mutable terrain in my own game Abydos Online.
Right now I will go for a pretty simple solution.

An area has a size of 10000x10000 meters. This is divided in a quad tree of lets say 16x16 (resulting in quads of size 625 meter).
Each quad can keep an hash of all computed from all its vertices, each change the hash is re-computed. This allows a player to cache the terrain and easily find out if any changes has been made by comparing the hash.

If you go advanced you can even keep track of let say the 100 latest changes (hash and vertices that changed) per chunk and check if the players hash matches any of those, just download the changes. In worst case the player has to download the complete chunk of terrain again.

You still have the problem of managing large changes that would affect views of people far away. This could be solved by actually having some value of how much the terrain is altered, for example if Y has changed more than Amount (perhaps during a short period of time) make some global event of it that will spread the changes throughout the whole area or something.

In the far future I want to have something voxel-based.

Quote:

Each quad can keep an hash of all computed from all its vertices, each change the hash is re-computed

I would store a version number, and increment it each time a change is saved/applied/published. A hash has some (smallish) chance of collision. A version number doesn't. And, more importantly, a version number may make it easier to decide whether to send a delta or a full update.

Also, another data representation is to represent the large-scale stuff as a block of, say, 64x64 cells. Smaller cells that divide off of that are represented as the delta from the interpolated value of the higher layer. That makes progressive download be a lot easier, it may help compression, and it makes rough outlines of profiles/ridgelines available earlier for far-away places. The draw-back is that, when you change one block, all the parent blocks change a bit, too.

Correct me if I am wrong but is it not impossible for the hash to collide if you base it on the content of the quad?

Each quad has its own hash, therefore it no problem that many quads have the same hash.

Incrementing a value is probably going to fail at some point in the future (Probably not a big issue unless your game is running for a couple of hundred years, but who knows). Of course you can avoid this by programming careful, but really think a constant 32 byte md5 checksum is in theory a more elegant solution and incrementing a value which may increase in size.

And unsigned integer will not run out until about a value of 4 billion. If you have an md5 you can probably treat it as a hex value to spare bandwidth plus have future safe solution.

Quote:

Each quad has its own hash, therefore it no problem that many quads have the same hash.

Hashes are done over changes above base state. A hash of change long of sorts.

Quote:

Incrementing a value is probably going to fail at some point in the future

It will, but one can precisely determine when.

A quick napkin calculation gives a good estimate. 2^32 / 3600 / 24 / (500 changes per second) results in almost 100 days. And 500 changes per second per quad is absurd.

Another reasoning is that each change needs to be persisted. If each change is just one byte, then there will be 4 gigabytes of changes per quad that user will need to download to come up to speed. So at some point, or even quite frequently, these changes will somehow need to be either permanently merged into baseline, or the current snapshot will need to be cached and treated as baseline, thereby resetting the counter.

Biggest advantage of a counter is determinism. It's possible to determine precisely when collision/overflow will occur.


With hashes and probabilities same issues as with MTBF rating occur. Hard drives have MTBF at around 5 years. Build a data center, put 5000 disks into it, watch three of them fail every day.