[size="5"] Foreword

When Quake World was released by idsoftware back in 1996, introducing the networking technique "Client Prediction" I kept wondering: "How the heck can they predict where I'm going?" I later read about the subject, or Dead Reckoning, as it's also called, and soon discovered that it had nothing to do with chaos theory or destiny. There has already been written articles on this technique (best one is probably at gamasutra.com), so I presume that you are well-informed of it.


[size="5"]What's your next move?

The technique I am about to explain does exactly what I initially spoke of, that is it guesses your next move. How can it guess? Statistics! Before I go into details with the technical part, let's begin with an example. Say we have a multiplayer football game. Now, it's most likely that you are running towards the ball right? Unless of course your own team has the ball. Then perhaps it was more likely that you ran into position or something. If we make up a ruleset of what is most likely for you to do in a given situation and store it in some kind of statistical database, and then distribute this database out to all playing clients (and perhaps the server), then everyone has the same perception of "common sense". It is now possible for a client to predict the other players most likely move/action, and as long as the other players do things "logically", then there is no need to send out packets are there?


[size="5"]What are these statistical data?

There are two ways to gather statistical data. You can either make up a set of rules of what you think is the most likely action in a given situation. A situation is a composite value of all players position/direction/speed/action at a given time. Or, you can record patterns of actions contra situations during gameplay. As some may have guessed this involves the usage of neural networks. Both options are usable. A neural network will definitely be able to see a lot more patterns than the human mind can manage, while a ruleset is much easier to implement and probably requires much less CPU overhead. No matter what, the statistical model has to be distributed to all clients, so they have the same frame of reference.

[size="5"]
How does it work in practice ?

For each frame (or network tick) you do a for loop through all the other players, and then you (based on the statistical model) predict their next move. You are always presuming that this prediction is what they are really doing, so you set their new position based on it. (Note: you can STILL use the old dead reckoning algorithm, and just put these predictions on top of, as an extra layer.) You also predict your own movement and takes this data and look up against your ACTUAL movement. If these two doesn't match, and if the difference is high enough (perhaps outside a given threshold) you send out a correction packet to all other clients, with your actual position/direction/etc. The other clients will now begin their reckoning on scratch based on your last packet. The benefit is that you don't have to tell the others of your actions as long as you move around logically (as predicted), and with a well trained statistical model you should be able to save a lot of bandwidth usage! Which must be considered the ultimate goal of this technique. The technique is not restricted to human players only, in fact it would be excellent to use with AI players as well, since they already build on some pre-defined set of rules.


[size="5"]Why hasn't it been implemented yet?

Perhaps it has, but it is unlikely. I hope you have an idea as how much CPU time the predictions will require from each client. You have to predict each players likely move in each frame on each client. Recording the statistical data can be a complex task as well. I think CPU's eventually will become powerful enough to calculate these amounts of data. Any comments on this article are appreciated!

(C)Jakob Ramskov 1999
http://www.ramosa.dk/