Movement prediction for non-shooters

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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)

Answer 4

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.