Targeting - A variation of dead reckoning

Disclaimer: I am writing this article under the assumption that no one else has written one like it; I certainly have not found one. With all the people writing games today, I'm certain the wheel has been re-invented many times over, so please e-mail me if you find another article exactly like this.

Anyone who develops real-time network games understands the importance of keeping them in apparent synchronization without sacrificing game play. I knew this even before starting my own, at which time I looked around programming forums on the 'net for ways to do this. I was not satisfied with any existing methods. I sat down and stared at the screen for a few hours, on and off, until I came up with a method which I call Targeting.

Targeting is a variation of dead reckoning where a remote player moves about a local player's game instance through persistent interpolation toward an uninterpolating and dynamic position.

In English, this means that another player on your screen will constantly move closer and closer to where that player really claims to be at all times. We don't keep any historic information about where the player has been; nonetheless, the remote player and any projectile he launches can appear to travel in a smooth, unbroken path.

Before we go any further, let's put a picture on the blackboard so you understand why we're doing this. There are three entities in client/server based network games: You, the server, and other players.

Figure 1: The reality of network games; what everyone sees (click for animation)

In this example, you are moving your ship back and forth, left to right. If you watch closely enough, you'll see that the server is a bit lagged behind you, and that the other player is lagged behind the server. If this isn't the case, then you need to refresh the page and/or upgrade your browser . This is the current reality of network games. The lag is caused by latency, which is the time it takes game data to get from your computer to everyone elses. The server won't know you moved until a short period of time after you really did move. I tend to think of the game as existing in three different "time zones."

Big deal you say? Well, not when you're trying to shoot the alien!

Figure 2: Latency causes the game to go in different directions for each player (click for animation)

According to your instance of the game, you shot the alien right when you were directly in front of it. The thing is, the server can be a thousand miles away, so he won't know you fired until up to several milliseconds later. In some cases, it could be hundreds of milliseconds! By then, the alien will have moved past your ship on his computer! Look above and see what happens.

Ok, so let's force your laser to appear in front of the alien on the server's machine by magically telling him that is where the laser should be. Thats fine, but now look at the game:

Figure 3: Overly compensating for latency makes the game look bad. (click for animation)

The player on the server is thinking: "Uhhhh, where did that laser come from!?," and will then proceed to throw your game away and go play Half-Life Counterstrike.

Now, let's take this from the approach of Targeting. A target is a structure of information that describes the state, and change of state, of an object that exists in a remote person's instance of a game. When you fire your laser, you send a packet of data to the server saying that A. You shot the laser, B. It was shot at some position in space (ox,oy) and C that it's moving straight up. Here's a graphical representation of that:

Figure 4: The target (the blue thing) has two elements: A position, and a velocity.

In this case, the Target is at (x,y) and the Target is moving straight up because the laser is moving straight up. The Target is determined by steps B and C, and one additional factor: The measure of latency, in milliseconds, between you and the server (I will discuss how to calculate that in a moment). However, to keep the game real, the laser has to come from your ship at the position we will call (ox,oy). We want the laser to converge from (ox,oy) to (x,y) every "frame" (that is, once every time your game runs a complete cycle). Because the target is moving up, both (ox,oy) and (x,y) will change at every frame. Here is some pseudocode:

for each frame {
  target.x_velocity = target.x_velocity + target.x_acceleration;
  target.y_velocity = target.y_velocity + target.y_acceleration;
  target.z_velocity = target.z_velocity + target.z_acceleration;

  target.x_position = target.x_position + target.x_velocity;
  target.y_position = target.y_position + target.y_velocity;
  target.z_position = target.z_position + target.z_velocity;

  laser.x = (laser.x + target.x_position) / 2;
  laser.y = (laser.y + target.y_position) / 2;
  laser.z = (laser.z + target.z_position) / 2;
}

And here's how it looks:

Figure 5: The server and other clients can calculate where the laser is on your screen (the target), but rather than just placing it there, it makes the laser quickly converge to that target. This makes the game run more smoothly for everybody. (click for animation)

The animation is particularly slow because I want you to study this very closely and carefully. Notice in the frame after you fired your laser, the target appeared for the server in the place that the laser is on your screen...yet, the laser on the server itself appeared at (ox,oy), which is the same placed it appeared for you when you shot it. In the following frame, the target is in approximately the same place on all three machines. Remember, we account for the position, velocity, and latency between you and another machine to figure out where the target should be on that other machine. Because of targeting, the laser on the server moves faster toward the alien than it does on player 1, and faster still on other client machines. The animation that shows targeting at work isn't the best example to explain targeting, but it certainly does a better job keeping the game reasonable than the two animations before it.

Now, you might think that interpolating by half in that pseudocode I gave you makes the laser move too quick to be natural. Well, this doesn't have to be the case. You can also try other ways, like this:

laser.x = (laser.x * 99 + target.x_position) / 100;
laser.y = (laser.y * 99 + target.y_position) / 100;
laser.z = (laser.z * 99 + target.z_position) / 100;

So, how do you figure out the measure of latency, and where the target should be as a result of latency? Every PC you will probably ever buy comes with an internal timer that counts the number of milliseconds since your computer booted up. The Windows API function to get this number, in units of milliseconds, is called GetTickCount(). Other OS's have other related functions. To calculate latency from computer A to computer B, computer A should send computer B a special packet that, in effect, means "Send me this packet back immediately after you get it." Just before sending it, computer A should call GetTickCount, and store that return value locally. When computer B gets the packet, it will send it right back to computer A. When computer A gets it back, it should call GetTickCount again, subtract the return value by the locally stored return value, and divide the result by 2. This will give computer A the approximate number of milliseconds it takes to get data to computer B. In this example, computer A is the server, and computer A does this latency measuring every couple of seconds, regardless of when or how often you send packets to him. Back to the immediate case study: Since the laser will move a certain distance over a certain amount of time, he can calculate the approximate distance the laser has travelled between the time you fired it, and the time he got it. Since he will then know the distance travelled, he can figure out where the target should be by displacing it by that distance.

Well this is all nice and neat, but there's one little problem: What if the laser is still too slow, and the alien does not explode for the server or the other players? Worse yet, what if there's another alien between the player and the first alien? The player thinks he can wipe out both with the same travelling laser, but the server doesn't, because the laser travels too quickly on his end. There are two ways of dealing with this:

1: Tell the server you took out that other alien.

If you tell the server which aliens you take out. The server will dismiss the disappearing aliens as something done "because of latency," or the laser apparently grazing the alien ship. The only problem with that is if a no-good-nik figures out how you do this, that person can cheat all the way up to the grand high score!!!

2: Do nothing and dismiss the problem as caused by lag.

With this thinking, the server is the dictator of what's really going on in everyone's game. Clients won't be able to cheat, but the game will seem less realistic and more frustrating, because you could have sworn you blasted those pesky aliens!

I really hope this puts Targeting in perspective for you. I did a quick implementation of it in one of my projects; and in testing, it has proven to work better than I had hoped, even on a 28.8 connection! If you use this technique in your game, drop me a line. I'd like to know how it turns out.