CS4344

Venue: LT19
Date: 6 Oct 2010 (Wednesday)
Time: 6:30pm

Research Assistant Position Available

A research assistant position is currently available in the Multimedia Systems Lab at School of Computing, National University of Singapore to work on a research project related to 3D rendering on mobile phones. We are seeking candidates with the following skills to fill this position:

• Familiarity with OpenGL and GPU programming.
• Good communication skills in English.
• Ability to work in a team.
• Independent and critical thinking skills.

A bachelor degree in Computer Science or related discipline is required. Fresh graduates are welcome to apply.   If you are interested, please email me at weitsang@comp.nus.edu.sg

Game Server Administrator (Windows/Unix):

1. Be responsible of maintaining and monitoring game servers (on either windows or Unix platform).

a. Good knowledge in shells and administration tools

b. Good knowledge in networking

c. Good knowledge in operating systems

2. Have strong interest in gaming industry and general knowledge of online computer games

3. Be a fast learner and able to collaborate in a team environment.

If you are interested to work at this startup, let me know and I will put you in touch with the person In charge

03/05/2010 (Mon)
9:00 AM - 11:00 AM
SR2

The final exam is an OPEN BOOK exam and covers materials from Lecture 1 to 11. The style of the exam is similar to that of the quizzes. There are no programming question.

Here are your grades for your assignment. Let me know if your assignment grade is a surprise to you.

        A1              A2

025J    A-              A-
390U    A-              A-
030X    A-              A-

350J    A               A-
400B    A               A-
406W    A               A-
033H    A               A-

324A    B               B
325N    B               B
333M    B               B

233N    A-              A
237L    A-              A
265B    A-              A       

947M    A-              A-
016L    A-              A-
372L    A-              A-

417N    A               A
178X    A               A
182M    A               A

960Y    A-              A-
961L    A-              A-
967E    A-              A-

158E    A               A
101M    A               A

713N    TBD             TBD
991Y    TBD             TBD
171R    TBD             TBD
436J    TBD             TBD

Please verify if the following marks are consistent with what you get.   Please let me know before 5th May if you find any inconsistency.

        Q1  Q2  Q3
016L    5   3   7
025J    2   6   7.5
030X    6   6   8.5
033H    10  5   7
101M    7   5   7.5
158E    0   3   7
171R    -   5   -
178X    5   10  8
182M    6   5   7
233N    0   0   8
237L    8   5   9
265B    7   5   6.5
324A    3   5   7.5
325N    4   0   5
333M    3   0   5
350J    1   0   6
372L    0   5   8
390U    1   6   8
400B    7   3   4.5
406W    4   8   8
417N    9   10  7
436J    2   -   5
713N    -   -   -
947M    0   7   8
960Y    7   6   7
961L    8   6   8
967E    -   5   -
991Y    0   3   8

1.

An issue that needs to be addressed when using dead reckoning is the value of the distance error threshold T, i.e., the threshold of the distance between actual position and predicted position above which an update needs to be sent. When two players are close to each other in the game world, accuracy is important and therefore the threshold should be small. For two players that are further apart, the threshold can be larger.

Now consider how such adaptive dead reckoning scheme can be used in the following scenario. We have a centralized client/server architecture, with a server S, and clients (i.e., players) p₀, p₁, …, p_n. We may assume that the latency between the clients and the server is negligible. Let d(i,j) be the distance between player p_i and p_j in the game world, and T(i,j) be the error threshold between p_i and p_j. The game designers have determined that the following relationship between error threshold and players distance is suitable for their game.

T(i,j) = 0.2*d(i,j)

A player always updates the server S whenever its velocity changes. When S receives an update from a player p_i, S uses adaptive dead reckoning to decide whether to forward this update to another player p_j (i != j) based on T(p_i,p_j) and the current prediction error of p_i‘s position at p_j.

(a) Explain how the adaptive dead reckoning approach above can lead to huge computational overhead at S.

(b) Suggest how the computation of error threshold can be modified to reduce the computational overhead at S, while still being adaptive to distance between players.

(c) In the scenario above, should a player use dead reckoning between itself and the server? Justify your answer.

2.

According to the Voronoi Overlay Network (VON) scheme proposed by Hu et al., a peer maintains direct connections with its AoI neighbors (all peers within its AoI). When a peer generates an update, it unicasts the updates to all its AoI neighbors. This method is not scalable when the number of AoI neighbors becomes large. To improve scalability, we want to explore the use of application-level multicast to disseminate updates to AoI neighbors.

One of the fundamental questions in application-level multicast is how to organize the receivers into a tree. By using the existing Voronoi structure, describe how the AoI neighbors of a peer can be organized into a multicast tree. In your description, include what messages are being exchanged, and how you ensure that the resulting structure is a tree (depending on your solution, the latter can be either trivial or tricky).

Assume that the players stay static (i.e., no one moves, joins, or leaves) when the tree is constructed, and assume that the tree can be reconstructed from scratch every time the Voronoi structure changes.

Just a gentle reminder that we are going to have our last quiz, Quiz 3, this coming Monday, 5 April 2010.

I will allow 10 more minutes to complete the quiz than usual.

5 April 2010

This lecture will consider a problem unique to mobile gaming. We will review two techniques to reduce power consumption of games on mobile devices, through suspending wireless interface card and scaling CPU frequency.

We will have Quiz 3 this week.

References

• [Shi03] describes a scheme for power-aware dead reckoning. Focus on the problem when reading the paper, rather than the solution.
• [Gu06] describes the problem and setup on DVFS for games. The detail solutions to estimating the number of cycles are described in other papers.

  [Shi03]

  Shi, W., Perumalla, K., and Fujimoto, R.. Power-aware State Dissemination in Mobile Distributed Virtual Environments. In Proceedings of the Seventeenth Workshop on Parallel and Distributed Simulation, 2003. [ACM DL | Google Scholar ]

  [Gu06]

  Gu, Y., Chakraborty, S., and Ooi, W. T. Games are up for DVFS. In Proceedings of the 43rd Annual Conference on Design Automation, 2006 [ Google Scholar ].

  Slides

  Download slides as PDF.

1.

A game map in a first person shooting game consists of two areas: (i)  an outdoor area that is wide open with little occlusion, and (ii), an indoor area consisting of many rooms and corridors.  A mobility trace of the players reveal that players tend to move around at high speed indoor.  Further, each player tends to visit almost all the rooms indoor within a short time (perhaps to search for enemies or items).  On the other hand, the players tend to be less mobile outdoor (perhaps hiding and waiting to ambush other players).  The game uses visibility-based interest management.

(a) Consider implementing this game using a peer-to-peer architecture.  Would such mobility pattern support the use of frontier sets to reduce the number of messages exchanged between players?  Justify your answer.

(b) Suppose we want to implement this game using a zoned server architecture.  We are interested in dividing the game map into zones and assigning each zone to a server for state management.  Players can still move between zones seamlessly.

(I) Based on the mobility pattern observed above, give an argument against sub-dividing the outdoor area into zones.

(ii) Based on the mobility pattern observed above, give an argument against sub-dividing the indoor area into zones.

2.

Consider a client/server implementation of two player Pong game similar to your Assignment 1.

(a) Someone suggested that we apply redundant data bundling (RDB) for TCP to packets exchanged between the clients and the server.

Is this useful?  If yes, describe the type of packets (its content and purposes) for which RDB is useful.  Otherwise, argue why RDB is not
necessary for your implementation of Pong.

(b) The networking library ENet provides optional reliability — when sending a packet, the application can indicate with a boolean flag whether the
packet should be delivered reliably or not.

Someone suggested that we always turn the reliability flag off (i.e., send unreliably) when sending paddle position updates in Pong.  Explain why this can lead to undesirable result and suggest how can you use the reliability flag wisely to avoid it.

(Note that sending all paddle position updates reliably is not a good solution).

29 March 2010

Abstract

In this lecture, we will look at transport protocols for games. We will discuss the pros and cons of using TCP and UDP for games, some tweaks to TCP that makes it more suitable for games, and briefly discuss SCTP, a relatively new transport protocol, that seems to fit the requirements of games nicely.

References

[Chen06]

Kuan-Ta Chen, Chun-Ying Huang, Polly Huang, Chin-Laung Lei, “An empirical evaluation of TCP performance in online games,” in Proc. of ACE 2006 [from Kuan-Ta Chen (aka Chun-Yang Chen) Homepage]

[Griw06]

C Griwodz, P. Halvorsen, “The Fun of using TCP for an MMORPG”“, NOSSDAV 2006 [Available from Simula Research Lab]

[Harc07]

S. Harcsik, A Petlund, C Griwodz, P. Halvorsen, “Latency Evaluation of Networking Mechanisms for Game Traffic“, NetGames 2007 [Available on NetGames 2007 Website]

Slides

Download as PDF.

Read the rest of this entry »

Lecture time: 22 March 2010, 1000

Abstract

First, we will finish off the unfinished section on fair message exchange using proxies from last week.  Then, we will discuss two studies on networked game traffic, which give insights on the characteristics of packets generated by a typical game.

References

• [Feng05] is the main reference for the discussion on game traffic characteristics of Counter Strike, while [Chen05] discussed the analysis of game traffic of Shen Zhou Online.

[Feng05]

W. Feng, F. Chang, W. Feng, and J. Walpole, “A Traffic Characterization of Popular Online Games”, in IEEE/ACM Transactions on Networking 13(3), June 2005. [Google Scholar]

[Chen05]

K. Chen, P. Huang, C. Lei, “Game Traffic Analysis: An MMORPG Perspective”, ACM NOSSDAV 2005. [PDF From NTU (Taiwan)]

Slides

Download as PDF

Read the rest of this entry »

Introduction

In this assignment, you will implement a 2-player pong game with peer-to-peer architecture, running on iPod Touch.  You can either modify the naive implementation given in Assignment 1 or modify your Assignment 1 solution.

Due Date
22 March, 2010 (Design Document)
12 April, 2010 (Final Submission)

Deliverables
For design document:

• A 10-page design document (11-pt, single spacing) (softcopy to IVLE workbin, hardcopy to me)

For final submission:

• Source code, to be submitted to IVLE workbin.
• A 10-page final report (11-pt, single spacing) (softcopy to IVLE workbin, hardcopy to me)
• A demo/presentation.

Team

You should do this assignment in a team of three.

Grading Criteria

• Design Document (30%)
  • Writing (5%) — well structured, logically written.
  • Correctness (25%) — choosing the right technique, proper justification given.
• Final Submission (70%)
  • Correctness (25%) — correct implementation of what you claimed, use the right choice of properly justified techniques.
  • Achievement (20%) — amount of work done, novel techniques used, effort in UI improvements etc.
  • Source code (5%) — well structured, properly formatted and documented
  • Report (10%) — well structured, well written, explains our solution clearly and correctly
  • Demo/Presentation (10%) — explain clearly, able to answer questions etc.

Your Task

Your task is to implement a peer-to-peer version of the iPong game with the following

• Responsiveness : The game should be playable in the presence of non-zero network delay.
• Consistency: The player should see smooth display of the game states, with minimal visual disruptions and consistent with the game rules. Further, the game states of the clients should be consistent (e.g. velocity of the ball).
• Efficiency: The communication overhead between the players should be reduced to minimal.
• Fairness: In the presence of network delays, no players should be at a disadvantage because of network lag.
• Robustness: When a player quits/fails unexpectedly, the game should be able to continue with minimal disruption (with the quit player replaced by a bot).

An important advantage for P2P game is robustness, and thus it is a new requirement for this assignment (although this only really matters if there are more than two players). Note that you should deal with players that fails unexpectedly (e.g., network failure).

Even though cheating is an issue in P2P game, preventing/detecting cheat is NOT a requirement for this assignment.

Some trade offs between these criteria are necessary. You should justify all your decisions in your assignment report.

If you attempted different combination of techniques, and found some works better than the other, document that in your report as well. (e.g., “I also implemented X and Y, but found that they do not work as well because ….”)

Note that this is an open ended project. As such I do not have a “model” answer of what should be implemented. You are also free to try out your own techniques, even if it is something that is specific to Pong only, as long as it helps improve the game according to the above four criteria. You are free to make the assignment more interesting (e.g., by adding random perturbation to the simulated network delay to simulate jitter).

The Server

Despite this being an assignment on peer-to-peer architecture, you can use a server in this assignment to avoid complications arising from interconnecting the peers.

The players still connect to the server and send messages to each other through the server.  However, the server is not allowed to store any states, simulate any game logic, or modify any messages exchanged between the players.  The role of the server is strictly restricted to forwarding messages between players and simulating the network delay.  (“Relay node” is a more appropriate name for the server in this case.)

In other words, you should design the solution as if the players are sending messages directly to each other without the server.

Design Document

You should submit a design document, detailing how your team plan to approach the problem. You should explain your design choices and how you plan to implement the design. Give as much detail as possible (e.g., draw diagrams of the communications between the peers, UML diagrams, pseudocode etc.) on your implementation.

The goal is to make make sure that your team starts thinking about the assignment early, design and plan properly before coding, and to allow me to give feedback to your design choices early. Note that you are free to change your design after you submitted the design document (i.e., your final submission need not follow the design if you come up with better ideas later).

You should at least answer the following questions explicitly.

• What messages are exchanged between the peers? When do the message exchange occur?
• Who is in charge of making what decisions in the game? In the case of conflicts or inconsistencies, how are the conflicts or inconsistencies resolved?
• What steps are you taking to reduce visual disruptions in the game?
• How do you make sure the ball velocity is consistent (the ball hits the paddle in the same region (R1/R2/R3)) in the peers?
• How do you improve fairness between the players?
• What happen when a peer quits? How do you ensure that the game continues with minimal disruption?

Final Report

Your final report should document your solution as implemented in your code submission. It will be an update of your design document. You should also document (i) any changes from the design document, (ii) solutions that you tried but did not work, (iii) any limitations of your solution.

Besides describing your solution, you should also evaluate your solution and report it in the final report.  You should at least answer the following questions in the evaluation section:

• how well does your solution work when network delay increases?
• how much delay can your solution tolerate while keeping the game playable?

Discussion

Discussion among teams, either online or offline, is encouraged. However, each team needs to code up the solution and write the report separately.

Advice

As always, start really early and have fun!

Lecture time: 15 March 2010

Abstract

In this lecture, we will introduce hybrid architecture for network games. We will look at a variety of different architectures at a very high level, and consider how to improve fairness using proxies in great details.

References

• P2P with Central Arbiter is mentioned in [Pell03].
• Section 2.1 of [Cron04] has a good introduction on mirror server architecture.
• [Guo05] is the main reference for the fair message exchange protocol.

[Pell03]

Pellegrino, J. D. & Dovrolis, C. “Bandwidth requirement and state consistency in three multiplayer game architectures,”, in Proc. NetGames ’03, pp. 52-59. [Google Scholar]

[Cron04]

E. Cronin, A. Kurc, B. Filstrup, S. Jamin, “An Efficient Synchronization Mechanism for Mirrored Game Architectures,” Multimedia Tools and Applications, 23(1), May 2004. [Google Scholar]

[Guo05]

K. Guo et. al, “A Fair Message Exchange Framework for Distributed Multi-Player Games,” in Proc. NetGames 2003. [Google Scholar]

Slides:

Download as PDF

Read the rest of this entry »

Just a gentle reminder that we will be having Quiz 2 this coming Monday, 15 March 2010. The quiz covers Lecture 5, 6, and 7.

1.

Does the following visibility-based interest management scheme for client/server architecture work? Explain.

When a player P becomes not visible to all other players in a game (i.e., no other players is interested in the updates from P), P stops sending updates to the server. P starts updating the server again only after P discovers that it becomes visible to at least one other player again.

2.

In lockstep protocol, a player does not reveal his action to all other players until he has received commitments from all other players.

Someone modifies lockstep protocol slightly to improve its performance: if a player A has already sent his commitment to player B, and he
has received commitment to B, then A can reveal his action to B, even though A has not received commitments from some other players yet.

Is look-ahead cheat possible in this modified version? Explain.

3.

Let C be the set of all cells in a game map and PVS(c) for a cell c be the set of all cells in C that are visible from c.

A scheme is proposed to reduced the number of location update exchanges between two player A and B and it works as follows. Let c(A) and c(B) be the cells that A and B are in respectively. A computes PVS(c(B)) and B computes PVS(c(A)). Then as long as A is moving in a cell that belongs to C – PVS(c(B)), A needs not update B. Similarly, as long as B is moving in a cell that belongs to C – PVS(c(A)), B needs not update A.

Is there anything wrong in this scheme? Explain.

Most students seem to have not in-depth understanding of the basic concepts taught in Lecture 2 and 3. Several students mainly throw in whatever techniques taught in class with vague statements, like “if we use X, we can improve consistency” without considering the specific scenario outlined in the questions (I see similar things in the design document of Assignment 1).

Read the rest of this entry »

Lecture time: 8 March 2010

Abstract

In this lecture, we will see two ways interest management is used in a peer-to-peer architecture to reduce the number of message exchanges.

References

• [Stee05] is the main reference for Frontier Sets.
• [Hu06] is the main reference for VON.
• The VAST homepage provides many resources (papers, slides, demo, source code) related to VON.

[Stee05]

A. Steed and C. Angus, “Supporting Scalable Peer to Peer Virtual Environments using Frontier Sets,” IEEE Virtual Reality 2005 (VR2005), Bonn, Germany, March 2005. [Google Scholar]

[Hu06]

Shun-Yun Hu, Jui-Fa Chen and Tsu-Han Chen, “VON: A Scalable Peer-to-Peer Network for Virtual Environments,” IEEE Network, vol. 20, no. 4, Jul./Aug. 2006, pp. 22-31 Available on VAST publication page

Slides

Download as PDF

Read the rest of this entry »

Dear class,

The deadline for Assignment 1 has been extended to 15 March, 2010 (by a week).  I hope you can make full use of this extended period to produce a nice solution/implementation of iPong.

Cheers,
Wei Tsang

Lecture time: 1 March 2010, 1000

Abstract This is the first of several lectures on peer-to-peer architecture. We will look at point-to-point communication model first in this lecture, discussing how to order events. Without an authorative and trusted server, players can cheat. We will examine different proposals to prevent and detect cheating, as well as their limitations.

References

• Bucket synchronization is used in MiMaze [Gaut98].
• [Bret01] provides a good account on how synchornized simulation are implemented from the view of AoE.
• [Baug01] introduces lockstep protocol and asynchrornous synchronization. Pipeline Lockstep and Adaptive Pipeline Lockstep are introduced in [Cron03]
• Section 10.1.2 of [Smed06] gives a very brief overview of three lockstep protocols. Section 9.5 of [Smed06] introduces synchronized simulation.

[Gaut98]

L. Gautier and C. Diot, “Design and evaluation of MiMaze, a multi-player game on the internet,” in Proc. IEEE Multimedia Systems Conference, June 1998. [CiteSeer]

[Bret01]

P. Breetner, and M. Terrano “1500 Archers on a 28.8: Networking Programming in Age of Empires and Beyond”. In Game Developers Conference ’01. [Google Scholar]

[Baug01]

N. E. Baughman and B. N. Levine. “Cheat-proof playout for centralized and distributed online games.“, In INFOCOM 2001, [CiteSeer]

[Cron03]

E. Cronin, B. Filstrup, and S. Jamin, “Cheat-Proofing Dead Reckoned Multiplayer Games”, In ADCOG 2003, [U.Mich's Project Site]

Slides Download as PDF

Read the rest of this entry »

Lecture time: 22 February 2010, 1000 

Abstract

In this lecture, we will review different approaches to interest management, and study a few algorithms in details.

References

• An overview of AOI mechanism is presented in [Smed06].
• A good overview of different interest management schemes can be found in [Boul06].
• Cell-to-cell visibility algorithm is described in the context of interactive walkthrough in a classic paper by Teller [Tell91].
• The generalized interest management scheme used in Lucid Platform 1.0 is described in a paper by Liu et al [Liu05], while the sort-based region matching algorithm is described in [Racz05].

[Smed06]

J. Smed and H Hakonen, “Algorithms and Networking for Computer Games”, Wiley, July 2006. [NUS LINC]

[Boul06]

J. Boulanger, J. Kienzle, and C. Verbrugge. “Comparing interest management algorithms for massively multiplayer games,” In NetGames ’06. [ACM DL | Google Scholar]

[Tell91]

S. Teller, and C. Sequin, Visibility preprocessing for interactive walkthroughs. In SIGGRAPH ’91. [ACM DL | Google Scholar]

[Liu05]

Liu E. S., Yip M. K., and Yu G. Scalable interest management for multidimensional routing space. In VRST ’05. [ACM DL | Google Scholar]

[Racz05]

C. Raczy, G. Tan, and J. Yu, A sort-based DDM matching algorithm for HLA. ACM Transactions on Modeling and Computer Simulations 15(1) (Jan. 2005), 14-38. [ACM DL]

Slides

Download as PDF

Read the rest of this entry »

Here are some sample questions from past quizzes.  Feel free to discuss them by posting comments to this post.

1.

Network latency is not constant, but instead, it fluctuates depending on the congestion level in the network. The degree of fluctuation is known as delay jitter. Explain what are the effects (if any) of high delay jitter to the game play when the following techniques are used. Explain if you answer would be different if clocks between the clients and the server are synchonized/not synchronized.

(a) permissible client/server architecture: a client always waits for acknowledgment from the server before updating its local state.

(b) artificial lag: server postpones processing of client messages to improve fairness among the clients.

(c) lag compensation: server rewind to a previous state to determine if a player has hit another player.

(d) local perception filter: rendering of passive objects are time-shifted to create consistent view among the players.

2.

Multi-player games often include characters that are not controlled by a human player known as non-player characters. A non-player character, or NPC, moves and behaves based on some algorithms, which takes the other states in the games, such as position of players, as input. They may also interact with the players.

Who should be in charge of simulating (i.e., computing the states of) the NPCs? The clients, the server, or both? Justify your answer from the perspective of responsiveness, efficiency, and consistency of the game.

Introduction

In this assignment, you are given an implementation of a 2-player pong game, implemented with permissive client/server architecture, running on iPod Touch. The given implementation ensures consistency by letting the server decide the states at all time. But it is neither fair, responsive, nor efficient. Your task is to appropriately apply techniques you learnt in the class (or any other techniques you think are suitable) to improve responsiveness, fairness, efficiency, while at the same time maintain the consistency of the game states as much as possible to keep the game playable .

Due Date
22 February, 2010 (Design Document)
8 March, 2010 (Final Submission)
Read the rest of this entry »

Lecture time: 8 February 2010, 1000

Abstract In this lecture, I will give a very short introduction to the Objective-C language and X-Code. I will also discuss Assignment 1 in detail.

References

• [Apple] provides a good reference for Cocoa and Objective-C programming.
• [Chatelier09] is an introductory article to Objective-C for C++ programmers.

  [Chatelier09]

  P. Chatelier , ”From C++ to Objective C” [PDF Online]

  [Apple]

  iPhone Dev Center

  Slides Download as PDF

Dear class,

Due to the passing of my father, I will be away on Monday 1 February, 2010. Thus, there will be no lecture on this coming Monday.

Assignment 1 will be released one week later.

Lecture time: 25 January 2010, 1000

Abstract In this lecture, we will continue our discussion on consistency techniques in multiplayer games. We will discuss dead reckoning, a technique used to reduce the number of message exchange, and local perception filter, a technique used to improve interactivity in the games. We will also explore two models of time synchronization in the game.

References

• Predictions, both local and opponent prediction, is discussed in [Armi06] Section 6.2.
• Dead reckoning is discussed in Section 9.3 of [Smed06]. A classic article by Jesse Aronson can be found online [Aron97].
• A more complicated version of Local perception filter, where passive entities accelerates and decelerates, is described in details in [Smed06]. The same chapter also discusses extension of local perception filter to implementing “bullet time” in multiplayer games.
• MMD, a simulator for local perception filter and bullet time can be found on Smed’s web site.

[Smed06]

J. Smed and H Hakonen, “Algorithms and Networking for Computer Games”, Wiley, July 2006. [NUS LINC]

[Armi06]

G. Armitage, M. Claypool and P. Branch, “Networking and Online Games: Understanding and Engineering Multiplayer Internet Games,” Wiley, June 2006. [NUS LINC]

[Aron97]

J. Aronson, “Dead Reckoning: Latency Hiding for Networked Games”, Gamasutra, September 1997. [Gamasutra]

Slides Download as PDF

Read the rest of this entry »

Please form a team of three for your Assignment 1 and email me the team members information (names, emails) and how many Macs and iPod Touches/iPhones you have among the team members, before Friday 22 January.

If you are looking to join a team or if your team needs one more member, you may post an “ad” as a comment under this post.

Lecture time: 18 January 2010, 1000

Abstract: In this lecture, we will look at consistency issue in client/server architecture and several different techniques to synchronize states among the players, including the method used in Valve’s Source game engine (used in Unreal Tournament and various other games). We will see how these techniques trade-off between responsiveness, fairness, and consistency.

To make proper trade-off decision, we need to know the requirements of games (how much inconsistency/lagginess can user tolerate?) We will also discuss two papers which study user tolerance in Unreal Tournament and Warcraft III.

References:

• Permissible client-server architecture is used in Unreal Tournament, and is described by [McCo03]. The article also mentions the responsiveness issue and describes how a client can use short-circuiting for movement command to improve responsiveness in Unreal Tournament.
• Local lag is introduced by [Diot99] in the form of bucket synchronization and in the context of peer-to-peer architecture (we will cover this later in class). The term local lag and the idea to adapt the lag is introduced by [Mauv04].
• Short circuiting with immediate feedback is mentioned in [Smed06], Section 9.1.1.
• Time delay is mentioned in [Armi06], Section 6.3.1.
• See [Armi06], Section 7.1 for a summary of user studies and results.
• Papers on the user studies can be found on the WPI project web sites for Unreal Tournament and Warcraft III. Screenshot of Unreal Tournament is taken from the same site.
• Unreal Tournament’s networking component is described here on the Epic Games website.
• Convergence is described by [Smed06] in Section 9.3.2 in the context of dead reckoning.
• The “dead man that shoots” example was mentioned by [Mauv00] in the context of fully distributed games.
• Lag Compensation techniques used in Half Life in [Armi06] Section 6.3.2 and also in great details online at Valve’s Wiki.

[McCo03]

A. McCoy, D. Delaney, and T. Ward, “Game-State Fidelity Across Distributed Interactive Games”, Crossroads vol. 9, no. 4 (Jun. 2003), 4-9 [ACM Crossroads]

[Diot99]

C. Diot and L. Gautier, “A distributed architecture for multiplayer interactive applications on the internet,” IEEE Networks magazine, vol. 13, no. 4, July/August 1999. [Google Scholar]

[Mauv04]

M. Mauve, J. Vogel, V. Hilt, and W. Eelsberg, “Local-lag and Timewarp: Providing Consistency for Replicated Continuous Applications,” IEEE Transactions on Multimedia, vol. 6, no. 1, pp. 45-57, 2004. [Google Scholar]

[Smed06]

J. Smed and H Hakonen, “Algorithms and Networking for Computer Games”, Wiley, July 2006. [NUS LINC]

[Armi06]

G. Armitage, M. Claypool and P. Branch, “Networking and Online Games: Understanding and Engineering Multiplayer Internet Games,” Wiley, June 2006. [NUS LINC]

[Mauv00]

M. Mauve, “How to Keep a Dead Man from Shooting.” In Proc of the 7th intl Workshop on interactive Distributed Multimedia Systems and Telecommunication Services, 2000. [Google Scholar]

Slides: Download

Read the rest of this entry »

Lecture time: 11 January 2010, 0900

Abstract: This is the introductory lecture for CS4344. In this lecture, I define the scope of the class, introduces an abstract model for networked games, describes two basic communication architectures, and detailed the design requirements for networked games.

Slides: Download
Read the rest of this entry »

Welcome to a new semester of CS4344. This is the main website for the class, where you will find information, announcements, slides, quizzes and discussions for CS4344. I will post the first set of slides soon, but in the meantime, please feel free to wander around the websites for the past offerings of CS4344.