CSIS FYP 2003-2004

Multiplayer Internet Game using Multi-Server Architecture

 

Supervisors:

  • Dr. C.L. Wang (Networking and Multi-server solutions)
  • Dr. Wenping Wang (Computer Graphic and VR)

Project Students:

  • Ivy Tang Pui Ying,
  • Ng Wing See
  • Lau Chi Lik
  • Ng Ying Fan
  • Li Hoi Ling

Description: 

This project will develop a scalable, real-time, and flexible 3-D online game using a multi-server architecture. This project includes 3 key areas:
(1) Client-side rendering (Computer Graphics) (2) Client-server communication protocols (3) Efficient game partitioning and synchronization
(4) Flexible 3D object model creation. Several 3D and virtual reality techniques will be employed to enhance the rendering quality. We also emphasize the network infrastructure to make the game more scalable and can achieve real-time response.

Project Webpage: http://www.csis.hku.hk/~wow

Figure 1: Design of Game Engine based on A Multi-Server Architecture

 

 

Figure 2: A Classical Internet Game System (Bottleneck in the Centralized Game Server)

 

Our goal is to develop an scalable Internet Game with the following features :

Game Engine  We expect the system can accommodate hundreds of users to play at the same time. The servers need to collect client state information and maintain a global game state. Some computation-intensive tasks, such as collision detection, will be performed. How to achieve load balancing is a study issue. Some dynamic load balancing scheme is required.
Game Partitioning  The partitioning mechanism is the core of every Internet game design. Without an efficient partitioning scheme, intensive control or player movement messages will be propagated in the network, which consequentially lengthens the game response time. Special game partitioning mechanisms are required to distributed workload among multiple game servers. 
Synchronization  Synchronization mechanism deals with the details of maintaining consistent state revolving from the latency delay or loss of computer network communication. It is a challenging issue in many fast-paced multiplayer Internet games. You may consider to adopt some well-known synchronization algorithms, including Lockstep, Chandy-Misra, Time-Warp, Breathing, and Bucket synchronization.
Real-time 3D Rendering  This part will be done in the client side. Several 3D and virtual reality techniques will be employed to enhance the rendering quality. . 
Open 3D Modeling  allow users to add scene or more roles into the game. We hope this part can be downloaded from any location and be executed at any device thru a Web browser.
Game Workload Generator  A client-site load generator program will be developed to simulate the actual runtime player action and movement. We assume there will be hundreds of players in the system. Multiple client machines will be used to perform the test.

 

Some Useful Links

Java in Games

  1. Jake Simpson. Game Engine Anatomy. http://www.extremetech.com/article2/0,3973,594,00.asp
  2. GL4Java: OpenGL for Java, http://www.jausoft.com/ and (applications) http://www.jausoft.com/products/gl4java/gl4java_apps.html
  3. Java Gaming - http://www.javagaming.org
  4. Michael Morrison, “Teach Yourself Internet Game Programming with Java in 21 Days”, ch.17.
  5. Gaming tutorial http://www.flipcode.com/network/ and http://www.gamedev.net/
  6. Frustum Culling in OpenGL by By Mark Morley, December 2000, http://www.markmorley.com/opengl/frustumculling.html
  7. Marler J., Evaluating Java for Game Development, 2002, http://www.rolemaker.dk/articles/evaljava/
  8. Sun Microsystems, Inc., Java3D, http://java.sun.com/products/java-media/3D/
  9. Java gaming procedure http://www.njnet.edu.cn/info/ebook/java/javagame/
  10. Sound engine reference http://www.jsresources.org/

Collision Detection

  1. Photon, ColDet – Free 3D Collision Detection Library, 2002, http://www.photoneffect.com/coldet
  2. Melax S., Gamasutra - Features – “BSP Collision Detection As Used In MDK2 and NeverWinter Nights”, 2001, http://www.gamasutra.com/features/20010324/melax_01.htm
  3. UNC Gamma Research Group, Gamma: Geometric Algorithms for Modeling,
  4. Motion and Animation, 2002, http://www.cs.unc.edu/~geom/
  5. UNC Gamma Research Group, RAPID -- Robust and Accurate Polygon Interference Detection, 1997, http://www.cs.unc.edu/~geom/OBB/OBBT.html
  6. Ehmann S., SWIFT++ Speedy Walking via Improved Feature Testing for Non-Convex Objects, 2001, http://www.cs.unc.edu/~geom/SWIFT++/

Useful VR Softwares and Systems

  • VRML: web-based VR applications.
  • Adebe Atmosphere : commercial product, multi-user VR and chat room applications, including scene building tool.
  • Blaxxun :commercial product, multi-user VR and chat room applications based on VRML. (Sample: http://vr.jrc.it/papers/mu/bxxcli.html)
  • Active Worlds : commercial product, multi-user VR and chat room applications.
  • Meme: Memetm was designed from the ground up for multi-user networked virtual worlds. Available for free, with all source code. Meme comes with Metatopia, a multi-user virtual universe. Metatopia features multiple virtual spaces, distributed virtual objects, and fully-articulated avatars with multiple facial expressions.
  • HIVE : Large Scale Real Time Multi-User Virtual Reality Research project.
  • 3DSite: VirtualReality  : You can find some applications or VR source codes here.
  • WireGL : http://graphics.stanford.edu/software/wiregl/:
    • WireGL is a research project at the Stanford University Computer Graphics Lab to explore cluster rendering systems. The software package available on this web site allows graphics applications to render to a cluster of workstations outputting to a tiled display.

Previous Year's Project:

Research Papers:

General graphics resources
  • Book: Computer Graphics: Principles and Practice in C (2nd Edition)
    James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes
    Addison-Wesley (The computer graphics bible).
  • Book: Mathematics for 3D Game Programming & Computer Graphics
    Eric Lengyel, Charles River Media, 2001

Graphics library resources

  • OpenGL
    • Book: OpenGL Programming Guide: The Official Guide to Learning OpenGL
      Mason Woo, Jackie Neider, Tom Davis, Dave Shreiner...
      Addison-Wesley, 3rd Edition, 1999
    • Book: OpenGL Game Programming
      Dave Astle, Kevin Hawkins, Andre LaMothe, Premier Press, 2001
    • Link: http://www.opengl.org
      The official OpenGL site
      Many samples, advanced techniques and hardware specific info.

3D Modeling resources

 

General:

  1. Smed, Kaukoranta, and Hakonen, "A Review on Networking and Multiplayer Computer Games", Technical Report 454, Turku Centre for Computer Science, 2002. http://staff.cs.utu.fi/~jounsmed/papers/TR454.pdf (Must Read)
  2. Smed, Kaukoranta, and Hakonen, "Aspects of Networking in Multiplayer Computer Games", The Electronic Library, 20(2):87-97, 2002.
  3. J. M. Pullen, D. C. Wood, “Networking technology and DIS,” Proceedings of the IEEE, Vol. 83 8, Page(s): 1156 -1167.
  4. R. Reddy, R. Garrett, “Future technology challenges in distributed interactive simulation,” Proceedings of the IEEE, Vol. 83 8, Page(s): 1188-1195.
  5. J. E. Shiflett, W. H. Lunceford, R. Willis, “Application of distributed interactive simulation technology within the Department of Defense,” Proceedings of the IEEE, Vol. 83 8, Page(s): 1168-1178.
  6. M. R. Macedonia, “A Taxonomy for Networked Virtual Environments,” IEEE Multimedia vol. 4, no. 1, 1997.
  7. Fullford, “Distributed Interactive Simulation: It’s Past, Present, and Future,” Proc. Of ACM Simulation ‘96.
  8. Inria’s MiMaze project (a real-time multiplayer game on the Internet): http://www-sop.inria.fr/rodeo/MiMaze/
    • Design and Evaluation of MiMaze, a Multi-player Game on the Internet; authors: Laurent Gautier, Christophe Diot. IEEE Multimedia Systems Conference. Austin. June 28 - July 1, 1998.
    • MiMaze, a 3D Multi-Player Game on the Internet; authors: Emmanuel Lety, Laurent Gautier, Christophe Diot. In the Proceedings of the 4th International Conference on Virtual System and MultiMedia, Nov 98, Gifu, Japan.
  9. A Distributed Multiplayer Game Server System
    http://warriors.eecs.umich.edu/games/papers/quakefinal.pdf
  10. An Overview of Multiplayer Architectures. www.cs.umd.edu/Honors/reports/Semion/MethodsXforXMultiplayerXGameWorldXSynchronization.doc
  11. Why Peer-to-Peer Architectures Should Replace Client/Server in MMOGs
    http://www.gignews.com/spotlight0901_hoyt.htm
  12. L. Gautier and C. Diot, “A Distributed Architecture for Multiplayer Interactive Applications on the Internet,” IEEE Network, Vol.13, pp.6-15, 1999.
  13. CittaTron: a Multiple-server Networked Game with Load Adjustment Mechanism on the Internet. http://www.nal.ics.es.osaka-u.ac.jp/mm/document/H_12/m-hori/m-hori_euromedia01.pdf
  14. SpaceFusion : A Multi-Server Architecture For Shared Virtual Environments
  15. NetEffect: a network architecture for large-scale multi-user virtual worlds ??
  16. A multi-server architecture for distributed virtual walkthrough ??
  17. Design of the Server Cluster to Support Avatar Migration ??
  18. Performance Characterization of Distributed Virtual-Reality Applications: A Case Study. http://www.cs.tufts.edu/~jacob/papers/ic02.deligiannidis.pdf
  19. A Scalable, Multi-user VRML Server ??
  20. Network topologies for scalable multi-user virtual environments ??
  21. An Efficient Partitioning Algorithm for Distributed Virtual Environment Systems ??
  22. Design of the Server Cluster for the Scalable Networked Virtual Environment. http://www.bohr.idv.tw/pdf/D016.pdf
  23. An Open Middleware for Large-scale Networked Virtual Environments
  24. RING: A Client-Server System for Multi-User Virtual Environments. http://www.cs.princeton.edu/~funk/symp95.ps.gz
  25. T.A. Funkhouser. RING: A client-server system for multiuser virtual environments. In Proc. 1995 Symposium on Interactive 3D Graphics, pages 85{92. ACM SIGGRAPH, April 1995.

Synchronization

  1. (Synchronization, TSS algorithm, must read) An Efficient Synchronization Mechanism for Mirrored Game Architectures
  2. P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. IDMaps: A global Internet host distance estimation service. IEEE/ACM Transactions on Networking, 9(5):525{540, October 2001.
  3. L. Gautier, C. Diot, and J. Kurose. End-to-end transmission control mechanisms for multiparty interactive applications on the Internet. In Proc. Of IEEE Infocom 1999, volume 3, March 1999.
  4. Cheat-Proof Playout for Centralized and Distributed Online Games
    http://signl.cs.umass.edu/pubs/baughman.infocom01.ps.gz
  5. M. Ahamad and R. Kordale, “Scalable Consistency Protocols for Distributed Services,” IEEE Transactions on Parallel and Distributed Systems, Vol.10, pp.888-903, 1999.
  6. L. Vaghi, C. Greenhalgh, and S. Benford, “Coping with Inconsistency due to Network Delays in Collaborative Virtual Environments,” In Proceedings of the ACM Symposium on Virtual Reality Software and Technology, pp.42-49,London, 1999.

 

Other papers:

§         http://www.cs.princeton.edu/gfx/papers/samanta00sketch.pdf

§         http://www-classes.usc.edu/engr/ee-s/657h/Render911.pdf

§         http://www.cs.ucdavis.edu/~ma/papers/icase_tr9737.pdf

 

 

 

Last Update: July 8, 2002