Thursday, January 27, 2011

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.

10 comments:

MrCoder said...

Is "first player shooter" the hip 2011 version of a first-person shooter?

Kristofer said...

Fine, I'll add a dash!

sathya shri said...
This comment has been removed by the author.
Unknown said...

Nice tips. Very innovative... Your post shows all your effort and great experience towards your work Your Information is Great if mastered very well.
python training in velachery | python training institute in chennai

Anonymous said...

Thanks for such a great article here. I was searching for something like this for quite a long time and at last I’ve found it on your blog. It was definitely interesting for me to read about their market situation nowadays. Well written article Thank You for Sharing with Us project management courses in chennai | pmp training class in chennai | pmp training fee | project management training certification | project management training in chennai | project management certification online |

kani said...

nice..
inplant training in chennai
inplant training in chennai
inplant training in chennai for it
hosting
india hosting
india web hosting
iran web hosting
technology 11 great image sites like imgur hosting
final year project dotnet server hacking what is web hosting
macao web hosting

shree said...

very nice....
inplant training in chennai
inplant training in chennai
inplant training in chennai for it
namibia web hosting
norway web hosting
rwanda web hosting
spain hosting
turkey web hosting
venezuela hosting
vietnam shared web hosting

shri said...

good...
internship in chennai for ece students
internships in chennai for cse students 2019
Inplant training in chennai
internship for eee students
free internship in chennai
eee internship in chennai
internship for ece students in chennai
inplant training in bangalore for cse
inplant training in bangalore
ccna training in chennai


Finansb said...

Mmorpg oyunlar hakkında detaylı bilgi için: Mmorpg oyunlar

suresh said...

Well done! Your explanation way is very attractive for me and I like more tips from your great post. Surely I will share your great post for my friends and this is very useful for freshers. Keeping the great work!
DevOps Training in Chennai

DevOps Course in Chennai

Post a Comment