Movement in MMORPG games

Typical for MMORPG games is that there are a lot of players running around, and they usually want to interact with each other in some way - to the very least extent they want to see that other people are there.

This can of course be a potential problem, due to the massive amount of data that needs to be sent over the internet. The amount of character data to send grows quadratically with the number of players in crowded locations.

There are some tricks you can use to at the very least reduce the constant factor in order to increase the number of players supported.

First, it is important to note that not all online games have the same requirements when it comes to character movement:

• In first-player shooters, it is important that all other players are always displayed in the correct locations, in order to be able to aim and fire accurately. This is not true for most MMORPG games.
• MMORPG:s need to handle hundreds of players in the same location, first-player shooters tend to support much fewer.
• Smooth movement and high fidelity of small movements is important in MMORPGs for the social interactions to feel more natural, whereas in first-player shooters it's much more important to fast forward movements to always be up to date - it's also preferable to do dead reckoning in order to account for latency.

This leads me to the conclusion that we should design the movement system to be more like a VCR (if anyone still remembers those). Clients record their movements and sends compiled packages to other players for playback. This makes it easy to support smooth movement. It also makes it easier to compress the data sent. The tradeoff is course slightly more cpu and memory usage for reduced network traffic.

Here come some of the tricks we currently use for Spaced.

Path compaction

Path compaction is the first step in reducing network traffic.
Basically we compact movement paths to a straight line if the distance from the start to the end is close enough to the sum of the distance of each path segment. This can easily be done in constant time for each added path segment, so it's a simple choice.

Same state

Send a bitfield with one bit for each type of movement data (position, rotation, animation state). Then simply don't send the actual data if it hasn't changed since last frame. This by itself reduces our network usage to about 40 bytes per second and character, with sending frames at least ten times per second, when the character is idling.

Compressed positions

Position vectors are stored clientside with very high precision (64 bits per component), which is useful for local calculations, but is probably a bit silly for sending it over the network, so we just convert it to floats instead.

Compressed rotations

Character rotations (the facing) are represented as quaternions, with four double components in the range [-1, 1].
Since we don't really need that high resolution for the rotation for movement playback, we simply encode each component as a signed byte, with -127 mapping to -1 and 127 mapping to 1.

Movement deltas

I think this the most interesting trick of the ones described.
Instead of sending the position each frame, we can just send the delta compared to previous frame!

With a naive encoding, this will be as expensive to send as the actual position, but we can take advantage of the fact that most movements will be very small vectors.

Start with size = ceil(log_2(max(x, y, z)))
size will hopefulle be an int in the range [-128, 127] because then we can store it in a byte (otherwise we'll just revert to sending a full position instead)

Now we know that x / 2^size must be in the range [-1, 1] which is great, since we can store it in a byte with some (a lot!) lost precision.

Calculate the actual bytes to send as x_send = x * 127 / 2^size (and the same for y and z)

By sending size along with these three bytes, we can send a compressed vector in just four bytes. It can be decompressed as: (x * 2^size / 127, y * 2^size / 127, z * 2^size / 127).

But wait a second...

You're probably thinking that this won't work, because you lose to much data when you compress it, and when you add up all those delta vectors, you'll get more and more value drift!

That's true, but the solution is quite simple.
Instead of calculating the deltas as Delta(n) = compress(P(n) - P(n - 1)), we calculate it as Delta(n) = compress(P(n) - Q(n-1)), where Q(n) is defined as Q(n-1) + Delta(n).
This means that all the drift errors that we generate at P(n) will be accounted for when we generate P(n+1). The total drift error at P(n) will thus never be greater than 1/127 of the size of the movement at P(n).

This has been stress tested by a scenario test which measures the actual drift for millions of updates, and it never increases more than 0.1.