A new method for path prediction in network games

ABSTRACT

In almost all multiplayer network games, dead-reckoning (DR) is used to predict the movements of game players, who can then predict the future movements of other players via the DR vectors they received. DR vectors, referred to as network packages, generally contain the position and velocity of game roles controlled by a sender at sending time. To achieve more accurate prediction, some games include the timestamp and acceleration of game roles in DR vectors. However, DR does not work well under bad network conditions. In our previous work [Li and Chen 2006] we proposed a solution called the interest scheme (IS), which proved to be efficient when network latency was unsteady and package loss frequent. Thus, in order to achieve much more accurate prediction, we proposed a hybrid solution. IS assumes that the path prediction for a given player is related to nearby objects or players. That is, that the players' surroundings can affect their movements, and different players may behave differently under the same conditions. In IS, a given player's surroundings are taken into account, and in order to achieve more accuracy, his habitual preferences are also taken into consideration. Experience with network games indicates that the same player will almost always behave in the same way under the same circumstances---for example, use the same fighting style. Moreover, we consider that different prediction methods should be used for different network latencies. So we introduce a hybrid method, which is a combination of IS, DR, and personal preferences. We use a 2D tank game to experiment, and compare the results of our solution with those of traditional methods. To obtain information on the players' habitual movements, we observed each participant for 30 minutes of play. Simulation shows that our method achieves significant improvements in path prediction.

REFERENCES

• 1: Sudhir Aggarwal , Hemant Banavar , Sarit Mukherjee , Sampath Rangarajan, Fairness in dead-reckoning based distributed multi-player games, Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games, October 10-11, 2005, Hawthorne, NY [doi>10.1145/1103599.1103608]
• 2: Sudhir Aggarwal , Hemant Banavar , Amit Khandelwal , Sarit Mukherjee , Sampath Rangarajan, Accuracy in dead-reckoning based distributed multi-player games, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016559]
• 3: Baughman, N. E. and Levine, B. N. 2001. Cheat-proof playout for centralized and distributed online games. In Proceedings of the INFOCOM 01Conference.
• 4: Bernier, Y. W. 2001. Latency compensation methods in client server in-game protocol design and optimization. In Proceedings of the Game Developers Conference '01.
• 5: Diot, C. and Gautier, L. 1999. A distributed architecture for multiplayer interactive applications on the Internet. IEEE Network Mag. 13, 6--15.
• 6: L. Gautier , C. Diot, Design and Evaluation of MiMaze, a Multi-Player Game on the Internet, Proceedings of the IEEE International Conference on Multimedia Computing and Systems, p.233, June 28-July 01, 1998 [doi>10.1109/MMCS.1998.693647]
• 7: Yousuke Hashimoto , Yutaka Ishibashi, Influences of network latency on interactivity in networked rock-paper-scissors, Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, October 30-31, 2006, Singapore [doi>10.1145/1230040.1230091]
• 8: Shaolong Li , Changja Chen, Interest scheme: a new method for path prediction, Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, p.41-es, October 30-31, 2006, Singapore [doi>10.1145/1230040.1230051]
• 9: Yow-Jian Lin , Katherine Guo , Sanjoy Paul, Sync-MS: Synchronized Messaging Service for Real-Time Multi-Player Distributed Games, Proceedings of the 10th IEEE International Conference on Network Protocols, p.155-164, November 12-15, 2002
• 10: Martin Mauve, Consistency in replicated continuous interactive media, Proceedings of the 2000 ACM conference on Computer supported cooperative work, p.181-190, December 2000, Philadelphia, Pennsylvania, United States [doi>10.1145/358916.358989]
• 11: Lothar Pantel , Lars C. Wolf, On the impact of delay on real-time multiplayer games, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507674]
• 12: Lothar Pantel , Lars C. Wolf, On the suitability of dead reckoning schemes for games, Proceedings of the 1st workshop on Network and system support for games, p.79-84, April 16-17, 2002, Bruanschweig, Germany [doi>10.1145/566500.566512]
• 13: Nathan Sheldon , Eric Girard , Seth Borg , Mark Claypool , Emmanuel Agu, The effect of latency on user performance in Warcraft III, Proceedings of the 2nd workshop on Network and system support for games, p.3-14, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963901]
• 14: Simpson, Z. B. 2004 A stream based time synchronization technique for networked computer games. http://www.mine-control.com/zack/timesync/timesync.html.
• 15: Singhal, S. K. and Cheriton, D. R. 1995. Exploiting position history for efficient remote rendering in networked virtual reality. Presence:Teleoperators and Virtual Environments 4, 2, 169--193.
• 16: URL:http://p24.bakadigital.com/p24bb/viewtopic.php?t=14
• 17: Katherine Guo , Sarit Mukherjee , Sampath Rangarajan , Sanjoy Paul, A fair message exchange framework for distributed multi-player games, Proceedings of the 2nd workshop on Network and system support for games, p.29-41, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963903]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Experimentation

Keywords:
dead-reckoning, dead-reckoning vectors, hybrid method, interest scheme (IS), network delay