# Movement prediction for non-shooters

I'm working on an isometric 2D game with moderate-scale multiplayer, approximately 20-30 players connected at once to a persistent server. I've had some difficulty getting a good movement prediction implementation in place.

Physics/Movement

The game doesn't have a true physics implementation, but uses the basic principles to implement movement. Rather than continually polling input, state changes (ie/ mouse down/up/move events) are used to change the state of the character entity the player is controlling. The player's direction (ie/ north-east) is combined with a constant speed and turned into a true 3D vector - the entity's velocity.

In the main game loop, "Update" is called before "Draw". The update logic triggers a "physics update task" that tracks all entities with a non-zero velocity uses very basic integration to change the entities position. For example: entity.Position += entity.Velocity.Scale(ElapsedTime.Seconds) (where "Seconds" is a floating point value, but the same approach would work for millisecond integer values).

The key point is that no interpolation is used for movement - the rudimentary physics engine has no concept of a "previous state" or "current state", only a position and velocity.

State Change and Update Packets

When the velocity of the character entity the player is controlling changes, a "move avatar" packet is sent to the server containing the entity's action type (stand, walk, run), direction (north-east), and current position. This is different from how 3D first person games work. In a 3D game the velocity (direction) can change frame to frame as the player moves around. Sending every state change would effectively transmit a packet per frame, which would be too expensive. Instead, 3D games seem to ignore state changes and send "state update" packets on a fixed interval - say, every 80-150ms.

Since speed and direction updates occur much less frequently in my game, I can get away with sending every state change. Although all of the physics simulations occur at the same speed and are deterministic, latency is still an issue. For that reason, I send out routine position update packets (similar to a 3D game) but much less frequently - right now every 250ms, but I suspect with good prediction I can easily boost it towards 500ms. The biggest problem is that I've now deviated from the norm - all other documentation, guides, and samples online send routine updates and interpolate between the two states. It seems incompatible with my architecture, and I need to come up with a better movement prediction algorithm that is closer to a (very basic) "networked physics" architecture.

The server then receives the packet and determines the players speed from it's movement type based on a script (Is the player able to run? Get the player's running speed). Once it has the speed, it combines it with the direction to get a vector - the entity's velocity. Some cheat detection and basic validation occurs, and the entity on the server side is updated with the current velocity, direction, and position. Basic throttling is also performed to prevent players from flooding the server with movement requests.

After updating its own entity, the server broadcasts an "avatar position update" packet to all other players within range. The position update packet is used to update the client side physics simulations (world state) of the remote clients and perform prediction and lag compensation.

Prediction and Lag Compensation

As mentioned above, clients are authoritative for their own position. Except in cases of cheating or anomalies, the client's avatar will never be repositioned by the server. No extrapolation ("move now and correct later") is required for the client's avatar - what the player sees is correct. However, some sort of extrapolation or interpolation is required for all remote entities that are moving. Some sort of prediction and/or lag-compensation is clearly required within the client's local simulation / physics engine.

Problems

I've been struggling with various algorithms, and have a number of questions and problems:

1. Should I be extrapolating, interpolating, or both? My "gut feeling" is that I should be using pure extrapolation based on velocity. State change is received by the client, client computes a "predicted" velocity that compensates for lag, and the regular physics system does the rest. However, it feels at odds to all other sample code and articles - they all seem to store a number of states and perform interpolation without a physics engine.

2. When a packet arrives, I've tried interpolating the packet's position with the packet's velocity over a fixed time period (say, 200ms). I then take the difference between the interpolated position and the current "error" position to compute a new vector and place that on the entity instead of the velocity that was sent. However, the assumption is that another packet will arrive in that time interval, and it's incredibly difficult to "guess" when the next packet will arrive - especially since they don't all arrive on fixed intervals (ie/ state changes as well). Is the concept fundamentally flawed, or is it correct but needs some fixes / adjustments?

3. What happens when a remote player stops? I can immediately stop the entity, but it will be positioned in the "wrong" spot until it moves again. If I estimate a vector or try to interpolate, I have an issue because I don't store the previous state - the physics engine has no way to say "you need to stop after you reach position X". It simply understands a velocity, nothing more complex. I'm reluctant to add the "packet movement state" information to the entities or physics engine, since it violates basic design principles and bleeds network code across the rest of the game engine.

4. What should happen when entities collide? There are three scenarios - the controlling player collides locally, two entities collide on the server during a position update, or a remote entity update collides on the local client. In all cases I'm uncertain how to handle the collision - aside from cheating, both states are "correct" but at different time periods. In the case of a remote entity it doesn't make sense to draw it walking through a wall, so I perform collision detection on the local client and cause it to "stop". Based on point #2 above, I might compute a "corrected vector" that continually tries to move the entity "through the wall" which will never succeed - the remote avatar is stuck there until the error gets too high and it "snaps" into position. How do games work around this?

-
What does a game being 3D or 2D have to do with what kind of server you use? and why won't an athoritive server work for your game? – AttackingHobo Jun 28 '11 at 5:57
@Roy T. bandwidth tradeoffs. The bandwidth is the most valuable resource in today's computer systems. – FxIII Jun 28 '11 at 7:08
That's just untrue, online games are largely dominated by response time, for example on a 10Mbit line (1.25MB/s) the latency between server-client is 20ms, sending a 1.25kb packet will take 20ms+1ms. Sending a 12.5kb packet will take 30ms. On a twice as fast line, a 1.25kb packet will still take 20ms+0.5ms, and 20ms+5ms for the 12.kb packet. Latency is the limiting factor, not bandwidth. Anyway, I don't know how much data there is, but sending 50 vector3's (25x position + 25x rotation) is only 600 bytes, sending this every 20ms will cost 30kb/s. (+ packet overhead). – Roy T. Jun 28 '11 at 9:32
Quake engine has prediction since first version. Quake prediction is described there and on some other places. Check it out. – user712092 Sep 12 '11 at 5:12
Do You do this position+=velocity*deltatime for each entity in parallel (imperatively: in code You have 2 arrays of physical parameters of entities, one frame apart, You update the older one to be newer and swap them)? There are some problems with iterating by Sean Barret, who made base of Thief 1 engine. – user712092 Sep 12 '11 at 5:21

The only thing to say is that 2D, isometric, 3D, they're all the same when it comes to this problem. Because you see many examples of 3D and you're only using a 2D octant-limited input system with instantaneous velocity doesn't mean that you can throw out networking principles that have evolved over the last 20+ years.

Design principles be damned when game play is compromised!

By throwing out previous and current you're discarding the few pieces of information that could solve your problem. To those data I would add time-stamps and calculated lag so the extrapolation can better predict where that player will be and the interpolation can better smooth out velocity changes over time.

The above is a big reason why servers seem to send out a lot of state information and not control inputs. Another big reason is based on what protocol you're using. UDP with accepted packet loss and out of order delivery? TCP with assured delivery and retries? With any protocol you're going to get packets at weird times, delayed or piled on top of each other in a flurry of activity. All of those weird packets need to fit into a context so the client can figure out what's going on.

Finally, even though your inputs are very limited to 8 directions the actual change can happen at any time - enforcing a 250ms cycle will just frustrate quick players. 30 players is nothing big for any server to handle. If you're talking about thousands... even then groups of them are split across multiple boxen so individual servers are only carrying a reasonable load.

Have you ever profiled a physics engine like Havok or Bullet running? They're really quite optimized and very, very fast. You may be falling into the trap of assuming operation ABC will be slow and optimizing something that doesn't need it.

-
Definite sage-advice here! It's easy to loose sight of the big picture. I'm using TCP in this case. The "8-directions" issue isn't as much of a problem in terms of inputs - it's more of a problem with interpolation and extrapolation. The graphics are limited to those angles and use animated sprites - the gameplay "looks weird" if the player moves in a different angle or velocity that's too far off the norm. – ShadowChaser Jan 9 '12 at 6:15

So your server is essentially a "referee"? In this case, I believe that everything in your client has to be deterministic; you need to make sure that everything on each client will always give the same result.

For your first question, once the local player recieves the other players' direction, apart from being able to decellerate his movement over time and apply collisions, I don't see how you could predict which direction the player will next turn, especially in an 8 direction environment.

When you recieve the "real position" update of each player (that maybe you could try staggering on the server) yes you will need to interpolate the position and direction of the player. If the "guessed" position is very wrong (i.e. the player completely changed direction just after the last direction packet was sent) you will have a huge gap. This means that either the player jumps position, or you can interpolate to the next guessed position. This will provide smoother interpolation over time.

When entities collide, if you can create a determinist system, each player can simulate the collision locally, and they results shouldn't be too far from the reality. Each local machine should simulate the collision for both players, in which case making sure that the final state will be non-blocking and acceptable.

For the server side of things, a referee server can still do simple calculations to check for example to speed of a player over short times to use as a simple anti-cheat mechanism. If you loop through monitoring each player over 1s at a time, your cheat detection will be scalable, only it will take longer to find cheaters.

-
Thanks - that sounds pretty close to what I need, especially on the server side. One interesting point is that although players are locked into 8 directions, internally movement is a 3D vector. I thought about this a bit more in the past day, and I think I'm struggling the fact that I don't have interpolation implemented at all - I simply use a very basic integration, setting the velocity and updating the position based on the vector each update. – ShadowChaser Jun 28 '11 at 15:49
I'm not sure how to combine that with interpolation or prediction. I tried taking the updated position sent in the packet, integrating it over a fixed time period (say, 200ms) and then determining the vector (velocity) needed to reach that point in 200ms. In other words, regardless of the player's current incorrect position on the client side, they should still reach the same "estimated correct position" in 200ms. It ended up sending my character off in crazy directions - I assume because the 200ms really should be the time to the next packet, which I can't estimate. – ShadowChaser Jun 28 '11 at 15:50
Did you make sure to first integrate the right position at t to t+1 before integrating the wrong position to the guessed right position at t+1? – Jonathan Connell Jun 28 '11 at 16:23
Yes - I double checked that I was using the correct position for the original integration. Originally that was a bug, but fixing it still didn't seem to create a noticeable improvement. My suspicion is the "+1" - it needs to be very dependent on the time between packets. There are two problems: send state changes in addition to regular (250ms) updates and I can't predict when those will occur. Also, I'm reluctant to lock in a specific interval since it makes sense for the server to send fewer updates for entities that are further away from the player. Time between packets can change. – ShadowChaser Jun 28 '11 at 18:04
Yeah including a fixed kind of timestep is probably not a good idea. I'm worried though that the erraticness of 8-direction movement will be very difficult (if not impossible?) to predict. Even so, you may be able to try to use the average latency of the client to predict t+1, and have a threshold above which you always "teleport" the other players to their new positions. – Jonathan Connell Jun 29 '11 at 7:45

Can you not include velocity in your state change messages and use that to predict movement? e.g. assume velocity doesn't change until you get a message saying it changed? I think you are already sending positions, so if something "overshoots" because of this you have the correct position from the next update anyway. Then you can step positions during updates as you already do using the velocity from the last message, and overwriting the position whenever a message is received with a new position. This also means that if position doesn't change, but velocity does you need to send a message (if that is even a valid case in your game), but that won't impact your bandwidth usage much, if at all.

Interpolation should not matter here, that is for e.g when you know where something will be in future, whether you have it, what method you are using etc. Are you confused with extrapolation perhaps? (for which what I describe is one, simple, approach)

-

My first questions would be: What is wrong with using a model where the server has authority? Why does it matter whether the environment is 2D or 3D? It would make your cheat protection a lot easier if your server was authoritative.

Most of the samples I saw tightly couple movement prediction right into the entities themselves. For example, storing the previous state along with the current state. I'd like to avoid that and keep entities with their "current state" only. Is there a better way to handle this?

When performing prediction, it is necessary to maintain several states (or at least deltas) on the client so that the when the authoritative state/delta is received from the server, it can be compared with those of the client and you can make the necessary corrections. The idea is to keep as much as possible deterministic to minimize the amount of corrections required. If you don't maintain the previous states, you can't know if something different happened on the server.

What should happen when the player stops? I can't interpolate to the correct position, since they might need to walk backwards or another strange direction if their position is too far ahead.

Why do you need to interpolate? The authoritative server should override any erroneous movements.

What should happen when entities collide? If the current player collides with something, the answer is simple - just stop the player from moving. But what happens if two entities take up the same space on the server? What if the local prediction causes a remote entity to collide with the player or another entity - do I stop them as well? If the prediction had the misfortune of sticking them in front of a wall that the player has gone around, the prediction will never be able to compensate and once the error gets to high the entity will snap to the new position.

These are the situations where there would be a conflict between the server and client and is why you need to maintain states on the client so that the server can correct any errors.

Sorry for the quick answers, I've gotta head off. Read this article, it does mention shooters but should work for any game requiring real-time networking.

-
A few answers: * If the server has authority, it would be responsible for tracking all moving entities and updating their positions on a regular interval. In other words, it needs to run the physics engine - which could get expensive. Scalability is a major design goal of mine. * I need to interpolate on the client side, other wise every server update sent to the clients will cause the entities to jump. Right now my interpolation is done in the physics engine - it just sets the velocity. There are no states or deltas. – ShadowChaser Jun 28 '11 at 6:02
I've read through all of Glenn's articles, but he states in the comments that they're only geared towards shooters (ie/ high update frequencies). A few of his articles talk about authoritative clients, which is the implementation I'm striving for. I don't want to do any interpolation/physics on the server, but I'm willing to change my mind if that's truly the only way :) – ShadowChaser Jun 28 '11 at 6:04
-1. What you wrote only vaguely touches on the topic; feels ambiguous. Answers feel sub-par when they are essentially "read this long article", while not containing useful information from the article at hand. – AttackingHobo Jun 28 '11 at 6:07
@AttackingHobo I'd have to agree with you. I mentioned I was in a hurry but that's no excuse. If I didn't have time it would have been better to leave it alone. Lesson learned. – Gary Buyn Jun 28 '11 at 8:42