Movement "algorithm" in client-server Multiplayer (MMO) Games?

Question

I've been writing a 2D flash multiplayer game and a socket server. My original plan for the movement algorithm between the client and server was the following:

• The client informs the server about the player's movement mode (moving forward or not moving) and the player's turning mode (not turning, turning left or turning right) whenever these change.
  • The server loops all players every few milliseconds and calculates the angle turned and distance moved, based on the difference in time. The same calculation is done by the client.

My current calculation for the client (same math is used in server) ==>

Turning

var newTimeStamp:uint = UtilLib.getTimeStamp(); //set current timeStamp
                var rot:uint = Math.round((newTimeStamp - turningTimeStamp) / 1000 * 90); //speed = x degrees turning every 1 second
                turningTimeStamp = newTimeStamp; //update timeStamp
                if (turningMode == 1) //left
                {
                    movementAngle = fixAngle(movementAngle - rot);
                }
                else if (turningMode == 2) //right
                {
                    movementAngle = fixAngle(movementAngle + rot);
                }

private function fixAngle(angle:int):uint //fixes an angle in degrees (365 -> 5, -5 -> 355, etc.)
        {
            if (angle > 360)
            {
                angle -= (Math.round(angle / 360) * 360);
            }
            else if (angle < 0)
            {
                angle += (Math.round(Math.abs(angle) / 360) + 1) * 360;
            }
            return angle;
        }

Movement

var newTimeStamp:uint = UtilLib.getTimeStamp(); //set current timeStamp
                var distance:uint = Math.round((newTimeStamp - movementTimeStamp) / 1000 * 300); //speed = x pixels forward every 1 second
                movementTimeStamp = newTimeStamp; //update old timeStamp
                var diagonalChange:Array = getDiagonalChange(movementAngle, distance); //with the current angle, howmuch is dX and dY?
                x += diagonalChange[0];
                y += diagonalChange[1];

private function getDiagonalChange(angle:uint, distance:uint):Array
        {
            var rAngle:Number = angle * Math.PI/180;
            return [Math.round(Math.sin(rAngle) * distance), Math.round((Math.cos(rAngle) * distance) * -1)];
        }

This seems to work great. In order to take lag into account, the server corrects the client's info every now and then by sending this data.

With this system very little bandwidth is used to handle movement. However, the differences between my server and the client's coordinates and angles are too big. Should I maybe extend my "algorithm", to also take into account the latency a user has? Or are there better ways of handling movement in client<>server multiplayer games with great performance?

Anting

Answer 1

My initial design would be similar to yours, but if that's not working, perhaps you could allow the client to do ALL the movement and just have the server do some range checking.

So if your last reported position was X, the next one must be within a radius from X where the radius is based on the difference in timestamps sent from the client with the x,y data.

Mostly this is just needed to detect cheating.

Stopping, fighting, etc would require a position be sent along with the attack, and actions triggered by positions would only be triggered after the client sent the update for that position but would be server-based.

Not sure this would help too much, but it might stop the jolting resyncs you would see from your initial algorithm.

Comment response:

No, the clients would still inform the server of their position, but the server wouldn't try to calculate the next position. This would mean that the server (and all other clients) would be at least one send/receive cycle behind in position.

I guess I'm saying just let the client do all the work, figure out where the character is and tell the server, but include enough info that the server can optionally check validity to ensure nobody's cheating.

The cheat detection could even be turned off for performance or set to randomly check.

Note: All collision/position info on objects within traveling range would need to be sent to the client for this to work.

Grobe

Wouldn't the server have to continueousely receive and re-send tons of messages if all clients had to inform all other clients about their current location? – Anting

+1 I was actually going to suggest the same thing. This is what a lot of popular multiplayer video games do. The server just makes sure everyone is in sync periodically. (I believe the Quake games do this.) – Multifoliate

Well, my first question still applies. Wouldn't the clients have to send thousands of messages all the time to keep the server up to date with every step? Followed by the server sending this data one again out to all nearby players. – Anting

'Thousands of messages all the time' is a bit of an exaggeration, but it's not uncommon for a client to notify the server of its position 10 times a second or so, and for the server to broadcast much of that back out on a similarly frequent basis. – Wilhelmina

Also if you are sending 10 updates a second to the server, you could ignore/miss a few here and there with little or no adverse effect. – Grobe

Answer 2

There are 2 ways I can think of doing this - have the client issue commands to the server & the server will be the ultimate map keeper.

Or, keep the maps in the clients, & the clients will have to establish connections with other clients they're "near" in order to do movement, with recordkeeping being done by the server & checked by a few peers (hacker police).

Interesting to me is the possibility to monitor peer connections, and peers that have a latency above a certain threshold just won't show up in the game.

Masturbate

Interesting, but this kind of limits big fights as P2P can't handle that many connections at the same time - you are now also relying on the client's connection for other clients. I'm still looking for the best server <> client system. – Anting

Why can't P2P handle many connections? Every time someone does something, you either need a rebroadcast from the server, or a message from the peer. I thought the traffic was close to the same (I could be wrong). – Masturbate

Answer 3

Is your server so slow that it cannot handle all of the movement? Especially in a 2-d game? Typically when I make little 2d games the server gives me back all of my movements, so no calculation is required on the client. If the server begins to lag, I simply freeze up a bit, which is what one would typically expect anyway (although this almost never happens).

In any case, I would definitely see how the performance is without the client making any actual calculations itself. If the performance isn't good enough, see if looping through player movements on the server is causing the delay (and start using a different thread for each client).

If there is indeed a real restriction in bandwidth (movements themselves pass very little data), then certainly you need to find the average delay of that particular user and calculate that into the algorithm. However, to continuously keep finding the average (for precision), you'll have to continue to ping the server to find the round-trip time, which shouldn't be all that costly.

Sande

It's not a little 2D game. It's supposed to handle hundreds of players simultaneousely. I need to most optimized system possible. – Anting

hmm, in that case tweaking the server so that it sends out data in small enough intervals will have to do. Of course all servers would need some sort of player cap, but at the very least add a 10-20ms lag on the client movement side. It's barely noticable and should in most instances correspond to the players' actual position. – Sande