Prediction techiques in computer games
Author: Joakim Bech
Supervisor: Lennart Ohlsson
Date of completion: 2005-05-27
Abstract
In this master's thesis we discuss how to solve or reduce the problems that occur when synchronizing clients in a networked environment. Irregular latency and jitter make it hard to predict where a game object will be in the nearest future. The problem is interesting because even though the bandwidth to the internet has increased for people all over the world, we still have latency and jitter in the network. Networked multiplayer games have grown in popularity, and from being played only against neighbours in a directly connected network we have started to play over the internet with our friends within the same geographical location. But there is still a problem when players want to play across continents. Too big latency and jitter will make existing games unplayable. A solution to these kinds of problems would benefit both the game developers and all the players that are playing against each other.
The main purpose of this thesis is to find out how these kinds of problems could be reduced, or in the best case be solved. The overarching theme of the solution is prediction, where prediction is based on two parts. The first part of it is extrapolation, i.e. how to make a good guess where an object will be located in the future. Extrapolation methods that are discussed are basic linear and quadratic expressions, based on the laws of Newtonian physics, Richardson extrapolation and Catmull-Rom splines. The other part of the prediction problem is to decide how an object should move from one place to another. Linear paths make objects go in straight paths between positions and this could look strange in some applications. By using some areas from mathematics behind the splines (like cubic splines, hermites and Catmull-Rom splines) we can make the movement smoother. This removes problems like objects suddenly teleporting from a place to another. To get a generic extrapolation algorithm we have discretizised mathematical expressions to get FIR-filter coefficients. With the FIR-filter coefficients, we can change extrapolation algorithm by just changing the coefficients that the algorithm will use.
To be able to test the ideas and algorithms, we have developed a game called shuffle puck and a simulation utility called Cursorsimulation. In these tools we can tune parameters and simulate a networked environment. Our work has showed that the best method to use in terms of a small deviation error is to use linear extrapolation and linear interpolation. The smoothness that we will get by using other methods like Catmull-Rom is expensive because it will give a greater deviation error. We have evolved a concept of predictors and replicators that are responsible for how a game object will move in an asynchronous networked environment. We have shown that this will work, but will not be as good as the existing methods as client side prediction, that is common in modern games.
Software
Prerequisites
To be able to run the software you have to download following:
Pythton 2.3.0
Twisted 1.3.0
Pygame 1.6
Numarray 1.3.2
Shuffle puck
The files should be available here in both zip and tar.gz.
Cursorsimulation
The files should be available here in both zip and tar.gz.
Report
The report is in PDF format and should be available for download here (high quality, for printing).
