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.

Subversion and feature branches

I've used subversion for a long time (probably around five or six years), but it's only recently I've started to use feature branches actively.

Mostly it was because it was a huge pain to do. You used to have to manually track revisions for all merges for it to work at all. Fortunately that was greatly improved with subversion 1.6, but it was still quite possible to mess it up.

Usual symptoms were crazy conflicts when merging from files not even touched in the branch.

These days, I happily use feature branches, because I finally figured out how to manage them properly. I can't remember exactly who I got this from, it was quite possibly several different people independently from each other.

Basic rules to avoid pain:

• Always stand in the project root (/trunk/ or /branches/branch/) when doing subversion operations.
• Update often.
• Commit often.
• Sync trunk -> branch often.
• Merge branch -> trunk only once, and then delete it.
  

Here are the general operations I use nowadays.

To create a branch:

svn copy TRUNK_URL BRANCH_URL

Start using the branch:

svn switch BRANCH_URL

List existing branches:

svn list BASE_URL/branches

Sync trunk to branch:

svn up
svn merge TRUNK_URL .
svn commit -m "Merged trunk to branch BRANCH"

Reintegrate branch (make sure it's commited and synced recently):

svn switch TRUNK_URL
svn merge --reintegrate BRANCH_URL .
svn commit -m "Reintegrated BRANCH"
svn delete -m "Deleting reintegrated BRANCH" BRANCH_URL

It doesn't look so hard, right?
The trick is that if you do something else at some point, like cherry picking revisions into the branch, subversion tends to get confused. I am not sure if it's subversions fault or the users fault, but in either case, cleaning it up usually gets messy.

An annoying thing is all those URL:s you need to enter.
To simplify things for my most common usage, I wrote a simple bash script:

It mostly just ensures that I don't forget any steps, does some basic error checking, and most importantly, it lets me skip writing the full URL all the time.

Here's what it looks like:

And here is the actual script if anyone is interested.

#!/bin/bash

ERROR='\033[1;31m'
REPO='\033[1;32m'
CBRANCH='\033[1;33m'
COMMAND='\033[1;34m'
EXECUTE='\033[1;35m'
ENDCOL='\033[0m'

FULLURL=`svn info | grep -E "^URL: "| cut -d " " -f 2`
if [ "$FULLURL" == "" ]; then exit 1; fi
TRUNKURL=$(echo $FULLURL | grep -E -o "^.*/trunk")
BRANCHURL=$(echo $FULLURL | grep -E -o "^.*/branches/[^/]+")

set -e

function error() {
echo -e "${ERROR}$1${ENDCOL}"
exit 1
}

function execute() {
echo -e "> ${EXECUTE}$@${ENDCOL}"
$@
}

if [ "$TRUNKURL" != "" ]; then
if [ "$FULLURL" != "$TRUNKURL" ]; then
  error "Please stand in the project root.\n  Expected $TRUNKURL\n   but was $FULLURL"
fi
BRANCH="trunk"
BASEURL=$(echo $TRUNKURL | sed "s/\\/trunk//")
elif [ "$BRANCHURL" != "" ]; then
if [ "$FULLURL" != "$BRANCHURL" ]; then
  error "Please stand in the project root.\n  Expected $BRANCHURL\n   but was $FULLURL"
fi
BRANCH=$(echo $FULLURL | grep -E -o "[^/]+$")
BASEURL=$(echo $BRANCHURL | sed "s/\\/branches\\/$BRANCH//")
else
error "Could not determine trunk or branch from $FULLURL"
fi

function sync() {
if [ "$BRANCH" == "trunk" ]; then error "Must be on a branch to sync or reintegrate!";  fi
CLEAN=`svn status|grep -v "^\\?"`
if [ "$CLEAN" != "" ]; then error "Working copy is not clean. Revert or commit first!"; fi

execute svn up
execute svn merge $BASEURL/trunk .

UPDATED_FILES=`svn status|grep -E -v "^\\?"|cut -b 9-`
if [ "$UPDATED_FILES" == "" ]; then
  echo "Nothing changed, skipping sync."
elif [ "$UPDATED_FILES" == "." ]; then
  echo "Only trivial changes merge - reverting merge"
  execute svn revert -R .
else
  execute svn commit -m "Merged trunk to branch $BRANCH"
fi

}

case $1 in
switch)
if [ "$2" == "" ]; then error "Missing parameter to switch: branch"; fi
execute svn switch $BASEURL/branches/$2
;;
trunk)
execute svn switch $BASEURL/trunk/
;;
list)
echo -e "> ${EXECUTE}svn list $BASEURL/branches${ENDCOL}"
echo "Available branches:"
BRANCHES=`svn list $BASEURL/branches | grep -E -o "^[a-zA-Z]*"`
for b in $BRANCHES; do
  echo -e "  ${CBRANCH}$b${ENDCOL}"
done
;;
reintegrate|reint)
sync
execute svn switch $BASEURL/trunk
execute svn merge --reintegrate $BASEURL/branches/$BRANCH .
execute svn commit -m "Reintegrated $BRANCH"
execute svn delete -m "Deleting reintegrated $BRANCH" $BASEURL/branches/$BRANCH
;;
sync)
sync
;;
create)
if [ "$2" == "" ]; then  error "Missing parameter to create: branch"; fi
execute svn copy $BASEURL/trunk $BASEURL/branches/$2 -m "Creating branch $2 from trunk"
execute svn switch $BASEURL/branches/$2
;;
delete)
if [ "$2" == "" ]; then error "Missing argument to delete: branch"; fi
if [ "$BRANCH" == "$2" ]; then error "Can not delete active branch. Switch first!"; fi
execute svn delete -m "Deleting branch $2" $BASEURL/branches/$2
;;
*)
echo -e "Repository: ${REPO}$BASEURL${ENDCOL}"
echo -e "Active branch: ${CBRANCH}$BRANCH${ENDCOL}"
echo "Usage: ./branch <command> [option]"
echo "Commands:"
echo -e "    ${COMMAND}switch${ENDCOL} ${CBRANCH}<branch>${ENDCOL}       -- switches to the branch"
echo -e "    ${COMMAND}trunk${ENDCOL}                 -- switches to trunk"
echo -e "    ${COMMAND}list${ENDCOL}                  -- list available branches"
echo -e "    ${COMMAND}reintegrate${ENDCOL} or ${COMMAND}reint${ENDCOL}  -- reintegrate active branch to trunk"
echo -e "    ${COMMAND}sync${ENDCOL}                  -- syncs current branch with trunk"
echo -e "    ${COMMAND}create${ENDCOL} ${CBRANCH}<branch>${ENDCOL}       -- creates a new branch from trunk and switches to it"
echo -e "    ${COMMAND}delete${ENDCOL} ${CBRANCH}<branch>${ENDCOL}       -- deletes a branch without reintegrating it"
;;
esac