Hey,

I am implementing height field water simulation in my multiplayer game engine. The system I am using is roughly the one described in this paper:

http://www.matthiasmueller.info/talks/GDC2008.pdf

In a nutshell, you have a height field where each element in the field represents a vertex on the water surface mesh. The water surface interacts with the rigid bodies of the physics engine, and they in turn affect the water. The server runs the physics at 10 FPS with the clients at 60 FPS. To cope with small differences in the physics engine on every machine, the server sends the updated transforms to the clients every so often and the clients correct themselves accordingly (with some smoothing and prediction added so all looks nice and smooth).

My question is, how should I propagate the water surface height values from the server to the clients? We are talking about something along the lines of 128x128 floats, so sending them all every tick is not an option. I was thinking I might put every element in a randomly selected "update bucket". Every tick (the server is normally ticking at 10 FPS) a bucket would be sent across the network to the clients. Since the vertices would be randomly selected you would never see an "area" of the water suddenly get updated.

The water tends to affect other objects slowly so the update does not have to be immediate, but somehow I have to prevent the whole sea from going out of sync with the server over time. What do you think of my proposed solution? Any other ideas?

Cheers!

Sending a randomly selected subset of samples each frame would work to make sure everybody will, over time, see similar-ish things.
Given the chaotic nature of fluid dynamics, I expect there to be some "minimum threshold" of send data below which you will not see much benefit in sync.
Also, you probably want to make sure that the updates are volume preserving -- when you get an update that you're off, that volume has to come from/go to the neighboring cells.

Another option is to use compression. The state of the sea is likely to compress very well (be locally smooth.) You could look into something like sending a grayscale JPG of the entire sea every once in a while. This will quantize the update somewhat, but also get everybody on the same page.
Another trick when using lossy compression for updates is to re-initialize the master simulation with the output of the compressed data, to make sure everyone starts from the same state.

Good suggestions, cheers!

Yes, the volume preservation might indeed be a problem with my solution. I have had a little bit of water loss in the past.

Some sort of lossy compression will likely be enough for this, and reinitting the server with the data to send sounds like a good idea. I have been avoiding JPG ever since PNG came into the picture (I take it you suggested it because it might compress better than PNG?). Are there any open source libraries that I can use for the creation of the JPG data? They would have to be unencumbered by licenses, etc...

Thank you again!

The surface wave properties are almost surely predictable so any of the advance video codecs can encode the surface waves ( converted into topological grayscale ) and their motion into a very small streams. Even then that's probably not necessary as you can use any compression algorithm and achieve acceptable results. Using either diff against previous frame or baseline frame then compressing that you can probably send lossless snapshot of the entire grid in real time ( 10ups ) and be within a reasonable bandwidth budget. If you want to throw out some data u can compress it even further.

Good Luck!

Also, if users don't affect the water, only water affects users, OR if you can accept a time delay between "user action" and "water being affected" (so that the commands can make it to all players) then you can use a deterministic simulation for the water. No updates needed at all.

Actually I have a version which is driven by a bunch of sine waves and the server time. This way only the time has to be kept in sync over the network. With this approach the floating objects obviously cannot affect the surface, which was the biggest problem and the one that made me look into the height field simulation.

Anyway, I think I'll try converting the height field values to half floats and running them through LZ4 or something and then sending them to all clients every know and then. Maybe the data wont be too big.

Personally, I think quantized 16-bit values (0 == bottom allowed position, 65535 == top allowed position) would compress better. And even better if you first do one level of lifting.
Lifting is when you encode the first value, and then encode the delta to the next value. This will typically compress much better because you'll get a lot of small values as long as you have smooth changes.

Looking forward to hearing how it goes!

Allright, so I had some time to try this out, and since you wanted to know how it went, here we go.

I had to store two values per vertex (the position and velocity of the height map point). My test level has a water height field of 128x128. That adds up to (128 * 128 * 8 bytes = 131072 bytes.

I quantized the values into 2 byte unsigned shorts and ran the resulting data through LZ4. That gives me data that is around 38000 bytes. Applying the lifting you mentioned gets it down to around 32000. However, I had some problems with that so I turned it off for now. I wonder if the resolution of my quantizing range is too small when quantizing the deltas or something.

Anyway, thanks for your help. This seems like a step in the right direction. And the packing and unpacking code is so fast that it does not even show up in my profiler currently (shows how fast LZ4 really is).

How are you quantizing the values? Also what is the breakdown of the position and velocity values (byte wise) per vertex. Is that a 3D vector + float? For floating point data ( which I assume is what you're working with, even thought u quantize it ), some people do a wavelet transform on the data and then quantize it (by throwing away some of the wavelet data ) before compressing. See

http://en.wikipedia.org/wiki/Discrete_wavelet_transform

there is an implementation of DWT in java which u can use. This is essentially what the newer JPG and PNG formats do for their lossy compression.

Good Luck!

-ddn

The position and velocity are just two floats. Since I am using a height map I don't need to send the X and Z values as they never change. The wavelet transform looks interesting, I'll take a look. Cheers!