Comparing interest management algorithms for massively multiplayer games

ABSTRACT

Broadcasting all state changes to every player of a massively multiplayer game is not a viable solution. To successfully overcome the challenge of scale, massively multiplayer games have to employ sophisticated interest management techniques that only send relevant state changes to each player. This paper compares the performance of different interest management algorithms based on measurements obtained in a real massively multiplayer game using human and computer-generated player actions. We show that interest management algorithms that take into account obstacles in the world reduce the number of update messages between players by up to a factor of 6, and that some computationally inexpensive tile-based interest management algorithms can approximate ideal visibility-based interest management at very low cost. The experiments also show that measurements obtained with computer-controlled players performing random actions can approximate measurements of games played by real humans, provided that the starting positions of the random players are chosen adequately. As the size of the world and the number of players of massively multiplayer games increases, adaptive interest management techniques such as the ones studied in this paper will become increasingly important.

REFERENCES

• 1: JSysmon. http://jsysmon.sourceforge.net.
• 2: Mammoth: The massively multiplayer prototype. http://mammoth.cs.mcgill.ca, 2006.
• 3: Howard Abrams , Kent Watsen , Michael Zyda, Three-tiered interest management for large-scale virtual environments, Proceedings of the ACM symposium on Virtual reality software and technology, p.125-129, November 02-05, 1998, Taipei, Taiwan [doi>10.1145/293701.293717]
• 4: John W. Barrus , Richard C. Waters , David B. Anderson, Locales and Beacons: Efficient and Precise Support for Large Multi-User Virtual Environments, Proceedings of the 1996 Virtual Reality Annual International Symposium (VRAIS 96), p.204, March 30-April 03, 1996
• 5: S. Benford and L. E. Fahlen. A spatial model of interaction in large virtual environments. In Third European Conference on Computer Supported Cooperative Work, pages 107--123, 1993.
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: Stefan Fiedler , Michael Wallner , Michael Weber, A communication architecture for massive multiplayer games, Proceedings of the 1st workshop on Network and system support for games, p.14-22, April 16-17, 2002, Bruanschweig, Germany [doi>10.1145/566500.566503]
• 8: Thomas A. Funkhouser, RING: a client-server system for multi-user virtual environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.85-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199418]
• 9: C. Greenhalgh. Awareness-based communication management in the MASSIVE systems. Distributed Systems Engineering, vol. 5, no. 3:129--137, 1998.
• 10: Seunghyun Han , Mingyu Lim , Dongman Lee, Scalable interest management using interest group based filtering for large networked virtual environments, Proceedings of the ACM symposium on Virtual reality software and technology, October 22-25, 2000, Seoul, Korea [doi>10.1145/502390.502410]
• 11: Mojtaba Hosseini , Steve Pettifer , Nicolas D. Georganas, Visibility-based interest management in collaborative virtual environments, Proceedings of the 4th international conference on Collaborative virtual environments, September 30-October 02, 2002, Bonn, Germany [doi>10.1145/571878.571901]
• 12: Michael R. Macedonia , Michael J. Zyda , David R. Pratt , Donald P. Brutzman , Paul T. Barham, Exploiting Reality with Multicast Groups, IEEE Computer Graphics and Applications, v.15 n.5, p.38-45, September 1995 [doi>10.1109/38.403826]
• 13: Michal Masa , Jiří Žára, Generalized interest management in virtual environments, Proceedings of the 4th international conference on Collaborative virtual environments, September 30-October 02, 2002, Bonn, Germany [doi>10.1145/571878.571904]
• 14: R. D. P. McFarlane. Network software architecture for real-time massively-multiplayer online games. Master's thesis, McGill University, 2005.
• 15: Graham Morgan , Fengyun Lu , Kier Storey, Interest management middleware for networked games, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053436]
• 16: K. L. Morse. Interest management in large-scale distributed simulations. Technical report, Department of Information & Computer Science, University of California, Irvine, 1996.
• 17: Quazal. Duplication Spaces#8482; Quazal Multiplayer Connectivity White Paper, January 2002. http://www.quazal.com.
• 18: S. J. Rak and D. J. V. Hook. Evaluation of grid-based relevance filtering for multicast group assignment, 1996.
• 19: Sandeep Singhal , Michael Zyda, Networked virtual environments: design and implementation, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1999
• 20: Li Zou , Mostafa H. Ammar , Christophe Diot, An Evaluation of Grouping Techniques for State Dissemination in Networked Multi-User Games, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.33, August 15-18, 2001

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
computer games, distributed games, interest management