Wednesday, August 15, 2012

Time Management and Synchronization

A key principle of online games is synchronization. Keeping the various players in synch means giving them practically identical and consistent experiences of the virtual world. The reason this is hard is that they are separated by network delays, and worse, those delays are variable.

The ideal situation would be that all players saw exactly the same thing, and that there were no delays. How do we approach that ideal? Consider a use case: there is an observer that is watching two other players (A and B) racing toward a finish line. The observer should see the correct player cross first, and see that happen at the correct time delay from the beginning of the race. To make that sentence make sense, we need a consistent notion of time. I call this Virtual Time, and my views are drawn from computer science theory of the same name, and from the world of Distributed Interactive Simulation.

Let's say the start of the race is time zero. Both racers' clients make the start signal go green at time zero, and they begin accelerating. They send position updates to each other and the observer throughout the race, and try to render the other's position "accurately". What would that look like? Without any adjustment, on A's screen, he would start moving forward. After some network latency, B would start moving forward, and remain behind A all the way to the finish line. But on B's screen, B would start moving forward. After some network latency, B would start receiving updates from A, and would render him back at the start line, then moving forward, always behind. Who won? The Observer would see A's and B's updates arrive at approximately the same time, and pass the finish line at approximately the same time (assuming they accelerate nearly equally). Three different experiences. Unacceptable.

Instead, we add time stamps to every update message. When A starts moving the first update message has a virtual time stamp of zero. Instead of just a position, the update has velocity, and maybe acceleration information as well as the time stamp. When it arrives at B, some time has passed. Let's say it is Virtual Time 5 when it arrives. B will dead reckon A using the initial position, time stamp, and velocity of that time zero update to predict A's position for time 5. B will see himself and A approximately neck and neck. Much better. The Observer would see the same thing. As would A (by dead reckoning B's position).

This approach still has latency artifacts, but they are much reduced. For example, if A veered off from a straightline acceleration to the finish line, B would not know until after a little network delay. In the mean time, B would have rendered A "incorrectly". We expect this. When B gets the post-veering update, it will use it, dead reckon A's position to B's current Virtual Time, and compute the best possible approximation of A's current position. But the previous frame, B would have rendered A as being still on a straight line course. To adjust for this unexpected turn, B will have to start correcting A's rendered position smoothly. The dead reckoned position becomes a Goal or Target position that the consumer incrementally corrects for. If the delta is very large, you may want to "pop" the position to the correct estimate and get it over with. You can use the vehicle physics limits (or a little above) to decide how rapidly to correct its position. In any case, there are lots of ways to believably correct the rendered position to the estimated position.

Note that during the start of the race, at first B would still see A sitting still for a period of time, since it won't get the first update until after a network delay. But after the first delay, it will see that the estimated position should be up near where B has already moved itself. The correction mechanism will quickly match A's rendered position to the dead reckoned one. This may be perceived as impossibly large acceleration for that vehicle. But incorrect acceleration is less easily detected by a person than incorrect position, or teleporting.

Another use case is if A and B are firing at each other. Imagine that B is moving across in front of A, and A fires a missile right when B appears directly in A's path. Let's assume that the client that  owns the target always determines if a missile hits. If we were not using dead reckoning, by the time the missile update arrived back at B, B would have been 2 network delays off to the side, and the missile would surely miss. If we are using dead reckoning, A would be firing when B's estimated position was on target. There might be some discrepancy if B was veering from the predictable path. But there is still one more network latency to be concerned about. By the time the firing message arrives at B, B would be one network latency off to the side. B could apply some dead reckoning for the missile, flying it out a few Virtual Time ticks, but the angle from the firing point might be unacceptable, and would definitely not be the same as what A experienced.

A better, more synchronized, more fair experience would be to delay the firing of the missile on A, while sending the firing message immediately. In other words, when A presses the fire button, schedule the execution of the fire event 5 Virtual Time units in the future. Send that future event to B, and to itself. On both A and B, the fire event will occur simultaneously. I call this a "warm up" animation. The mage winds up, the missile smokes a bit before it fires, or whatever. The player has to learn to account for that little delay if they want the missile to hit.

If you have a game where firing is instantaneous (a rifle, or laser), this is a pretty much impossible problem. You have to put in custom code for this. The shooter decides ahead of time where the bullet will hit, and tells the target. By the time the target is told, both shooter and target have moved, so the rendering of the bullet fly out is not in the same location in space, and will possibly go through a wall. The point of impact is also prone to cheating, of course. I don't like games that have aiming for this reason. They are very difficult to make fair and cheat proof. I prefer target based games. You select a target, then use your weapons on it. The distributed system can then determine whether it worked. Aiming, and determining hits, shooting around corners, etc. is a tough problem. FPS engines are really tough. You should seriously consider whether your game needs to bite off that problem, or if you can make it fun enough using a target based system, and a little randomness. Then add decorative effects that express what the dice said.

The key take away with Time Management, Virtual Time, and synchronization is that whichever client actions are occurring on (A, B, or Observer), they occur in the same time axis. There are nice time synchronization algorithms (look up NTP), that rely on periodically exchanging time stamps using direct messages. And you can solve a lot of problems using events that are scheduled to occur in the future based on Virtual Time timestamps. One challenge though is how to keep the simulation that is being run using Virtual Time in synch with animation and physics that you might be tempted to run using real time. Or what you think is real time. You may have a game that you can pause. How does that work? Do you freeze the animation or not? You are already dealing with different concepts of time. Consider adding Virtual Time. And the notion of Goal positions.