## CS4344

### Networked and Mobile Gaming, 2014/15

#### Author: Ooi Wei Tsang

Here is the final assessment paper for your reference.

In Question 1, we explore a taxonomy of in-game actions and try to discover why some actions are more sensitive to delay and consistency, while some are not. Here, we introduce two new notions, precision and deadline, or an action. In Part (a) and (b), you are asked to give two examples, one for high-precision, loose-deadline (HP-LD) action, and the other for low-precision, tight-deadline (LP-TD) action. Most of you got these questions correct. My favorite example for LP-TD: player is on-fire and need to jump into the river.

Next, you are asked to explain the relationship between precision and tolerable response time, and between deadline and tolerable response time. Many of you answered that there is no relationship between precision needed for the action and the tolerable response time. In fact, the higher the precision needed, the lower the tolerable response time is. Case in point: have you tried clicking on a few target pixels on screen when your mouse cursor movement is delayed after you move the mouse? It is really annoying. Most of you got the relationship between deadline and tolerable response time correct though (loose deadline means higher tolerable response time).

Finally, in Question 1, you are asked to explain what type of actions is good for short-circuiting, which reduces response time and increases inconsistency. About half got this correct: LP-TD. Since low precision is needed, inconsistency is tolerated, but low response time is good for tight-deadline action.

For Question 2, if you understand the question and DDM, the first two parts are giveaways. SL will never overlap with UR, and SR will never overlap with UL. On the other hand, SLR will always overlap with ULR.

Next, you are asked to sketch a recursive algorithm. The idea is basically, to call split() on S and U to partition the input into six partitions. The pairs in SLR will always overlap with ULR. For the rest, we recursively call DDM on the following pairs: SL and (UL union ULR), SR and (UR union ULR), and SLR and (UL union UR). There is no need to consider those that never overlaps. Some of you got partial credits because you only recusrively call DDM on SL and UL, and SR and UR.

Now, for Question 3, Part (a) is mostly a give away: delayed ack is implemented in the receiver only; fast retransmission and exponential backoff on the sender only; and redundant data bundle needs to be implemented on both sides (since receiver needs to make sense of the bundled data from the sender). Part (b) is also quite straightforward. If the NIC sleeps for too long, it could cause the connection to idle for more than RTO, and the connections’ congestion window resets. If it sleeps even longer, the TCP connection might time out and three way handshake is needed to reestablish the connection. Either way, the connection restarts from slow-start phase again.

Question 4 receives several answers that do not use virtual network coordinates and got 0. For the rest, as long as you explain how players can establish its network virtual coordinate (by obtaining a few landmarks from the server, measuring RTT to them, then reporting the RTT or coordinate back to the server) and how the server does matchmaking (by clustering the players using distance computed from the coordinate), you get 15.

Finally, Question 5 is the one that stumped most of you. The answer can be summarized in two words: frontier region. If two players have no chance of entering each other AOI, there is no need to exchange position update, and this can be achieved through frontier region.

It is disappointing that many of you answered: if two players are not in each other’s AOI, then there is no need to exchange position update. The problem is that, if two nodes do not know the latest position of each other, how do they know that they are in each other’s AOI or not? A similar answer is that two players are very far apart, then they do not have to exchange position update. But did not explain “how far”, nor did the answers explain how can a node know if the other node is far, without know its latest position!

The other popular answer that received a small partial credit is that, if two players (say, A and B) have a common neighbor (C), then they need not exchange position update, since C can tell A and B when A and B enters each others’ AOI. This is correct but incomplete. If A, B, and C are mutually enclosing neighbor of each other, then by this rule, they would not exchange position update so C would not know A and B’s latest positions!

I am, however, quite delighted that a few of you came up with an unexpected answer that is correct: if A is moving away from the last know position of B, it need not update B (and vice versa). The rational is that if A and B are not in each other AOI’s to begin with, then this movement would never cause A and B to enter each other’s AOI.

I hope you had fun answering the paper, which ties up quite a few disparate ideas together, and learn something new in the process. Cheers.

I have finished grading the projects, and am very happy with what you have achieved. Compared to previous years, I have seen more creative games, more thoughtful decisions into what algorithms to implement (and equally important — what not to implement), and more cohesive teamwork. Some of the games not only meet the academic expectation for CS4344 but also is polished enough to be unleashed on real users. Bravo and please pat yourself on your back.

I would like to make all your repo public. If you have any concern about me doing so (e.g., you committed some embarassing code, you included some commercial library/asset), let me know before May 15.

Considering only the academic expectation of CS4344, here are your grades. Most teams that made good decisions about how to deal with network delay and synchronize the game states receive A-/A/A+ range. A few team is lacking in this respect and receives B/B+. A few students received one grade lower than the rest of the teammates, as their contributions are significantly less as reflected in git’s commit log.

```024U      B
063M      A+
075E      A
076N      A
103N      B-
217A      A-
234N      A
422A      A
441B      A
454U      A
498A      A+
541L      A-
557Y      B
656X      A-
676R      A-
683X      B+
695H      B+
718U      B+
726B      A-
734A      B+
742W      B+
747W      A-
751U      A
758E      A-
812X      A+
829B      A+
856J      B+
860W      B
909Y      A
924M      A-
924R      A+
934R      A+
988U      B
998R      A+
```

This is an open ended assignment and many different solutions are submitted. The best (and closest to the solution I came up with) is the one by Yang Shun and Hieu (read their report here). Basically, the idea is to find the set of ships that could possibly collide with a rocket, and only send the “fire” commands to these ships. Two other teams have similar solutions. This turned out to be tricky to compute, but with some thoughts, it is doable.

Another popular solution that does not work as well is to use cell-based, distance IM (either a fixed distance or a “cross” ala Problem Set 2). If “turn” or “fire” are sent only when the ship/rocket enters into the AOI, the player will see sudden appearance / teleportation of ships/rockets. Depending on the implementation, this could be either subtle or annoying. Another tricky part is to compute the cell a ship/rocket is in efficiently. If you compute the cell every gameLoop(), it is going to be slow. So you need to predict when a rocket/ship will cross the boundary and update the cell the rocket/ship belongs to only then.

Most of you got the efficiency part right, by considering only rockets and ships in each other’s AOI. But, note that if you recompute the AOI of every rocket and every ship in a loop before checking hasHit(), it does not actually make it more efficient! It would be more efficient only if hasHit() is more expensive to compute than the AOI, which is not the case here.

Several teams tried the multiple server solutions, but none got it perfectly right.

Congratulations to all the teams for the great demos on display tonight. The guests are very impressed with the quality of the games that you have developed! Well done everyone.

The three projects identified as particularly outstanding by the judges are Elemetal Frenzy, Fighting Arena, and Nutty Ninja X. Here are their trailers!

• Please remember to merge your code into the master branch at github.  I will pull a copy after submission deadline.

Here is a video explaining Assignment 2.

By now, you should have received an email with comments on your specific assignment. Do let me know if there are any surprises or bug in my marking.

You did not do as well as expected. Specific comments will be emailed to you. I will post a video with a solution.

```024U    6
063M    11
075E    10
076N    7
103N    7
217A    6
234N    7
422A    10
441B    5
454U    5
498A    11
541L    6
557Y    7
613L    3
656X    10
676R    10
683X    7
695H    7
718U    7
726B    6
734A    7
742W    6
747W    6
751U    8
758E    7
812X    7
829B    7
856J    6
860W    7
909Y    8
924M    8
924R    7
934R    7
988U    6
998R    7
```

I hacked this poster template up quickly after class today. I hope this is helpful for those preparing poster.

Remember to check out the STePS FAQ and tips for making good posters.

1. Final examination is now known as final assessment in NUS.
2. The final assessment for CS4344 will be on:
• Date: 29/04/2015 (Wed)
• Time: 9:00 AM
• Venue: SR2
3. There will be 5 long questions, a total of 100 marks.
4. Roughly, you should spend X minutes on questions worth X marks.
5. The final assessment is an open book assessment. You may bring in any analog material that you like.
6. No Javascript coding is required during the final assessment. But you may be asked to sketch one or more algorithms to solve a problem.

Get your last problem set here.

If you don’t receive anything, or can’t see any annotation after trying very hard, or is surprised by your grade, feel free to contact me.

Most of you are able to obtain the basic traffic traces and characterize the traffic in terms of throughput, packet load, and packet size properly. Well done! There are, however, many of you who did not plot a histogram properly. Most common mistakes are (i) use non-uniform bucket size, (ii) use non-integer bucket, (iii) plot packet size versus time.

The analysis of traffic patterns, especially the periodic pattern, is missing in many submissions.

```024U	B+
063M	A
075E	B-
076N	B+
103N	B+
217A	A
234N	A-
422A	A-
441B	B
454U	A-
498A	A+
541L	B+
557Y	A
613L	B
656X	A-
676R	B
683X	B+
695H	A
718U	A
726B	B+
734A	B
742W	A
747W	A-
751U	B+
758E	A-
812X	B
829B	A-
856J	A
860W	B
909Y	A
924M	C+
924R	-
934R	A
988U	A
998R	B

```

The last lecture for CS4344 explores two advanced, but important, topics for multiplayer games: cheating and cloud gaming. The topics do not quite have proper solutions yet, and are currently being actively developed and studied by both the academia and the industry.

## Introduction

You have been shown a naive implementation of a massively multi-player Space Battle game. In this assignment, your task is to improve the implementation so as to improve the efficiency of the server and to reduce the number of messages sent using interest management. For extra bonus, you can improve the scalability of the server by using multiple servers while maintaining a seamless world.

Please doodle a time to meet here as a team.

I expect to see something that runs by this milestone, so please come into the meeting prepared, with server, client, etc. set up.

In this lecture, we will look at the characteristics of networked game traffic and its impact on the design of 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.

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 [Google Scholar]
[Griw06]
C Griwodz, P. Halvorsen, “The Fun of using TCP for an MMORPG”“, NOSSDAV 2006 [Google Scholar]
[Harc07]
S. Harcsik, A Petlund, C Griwodz, P. Halvorsen, “Latency Evaluation of Networking Mechanisms for Game Traffic“, NetGames 2007 [Google Scholar]

Here is your next problem set for discussion starting this week.

In this lecture, we will look at the current protocol for discovering game servers and how to improve the protocol.  We will also look at ways we can group players with low latency to each other together in the same game session.

References

The REED server discovery algorithm is discussed in detail in [Armitage12].  [Manweller11] provides a highly detailed description of a study in latency measurement and estimation in mobile networks, with application to player matchmaking in mobile games.  The use of hierarchical clustering and QT clustering to match players are discussed in this context in the section on Grouping Agent.

[Manweller11]
Justin Manweiler, Sharad Agarwal, Ming Zhang, Romit Roy Choudhury, and Paramvir Bahl. “Switchboard: a matchmaking system for multiplayer mobile games.” In Proceedings of the 9th international conference on Mobile systems, applications, and services, pp. 71-84. ACM, 2011. [Google Scholar]
[Armitage12]
Grenville Armitage and Amiel Heyde. “REED: Optimizing first person shooter game server discovery using network coordinates.” ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP) 8, no. 2 (2012): 20. [Google Scholar]

Dr. Bhojan Anand will give a guest lecture this week and share with you his PhD research work on energy-aware mobile gaming.  He will present two of his work on:

• K Thirugnanam, Bhojan Anand, J Sebastian, PG Kannan, AL Ananda, RK Balan, and MC Chan, “Dynamic Lookahead Mechanism for Conserving Power in Multi-Player Mobile Games,”  IEEE INFOCOM 2012, Orlando, Florida, Mar 2012. [PDF]
• Bhojan Anand, Akhihebbal L. Ananda, Mun Choon Chan and Rajesh Krishna Balan, “ARIVU: Making Networked Mobile Games Green – A Scalable Power-Aware Middleware”, MOBILE NETWORKS AND APPLICATIONS, Springer Netherlands, Feb 2012. [PDF]

As you may know, Wei Tsang is out of town for a conference trip during Week 9. Dr. Anand Bhojan will be your guest lecture for Week 9, where he will share with you his research work on energy efficient gaming.

There is no tutorial for Week 9.

Despite missing two weeks of tutorials, we should be able to catch up on the questions before the end of the semester.

This eLearning lecture consists of two parts. The first introduces you to mirrored server architecture and zoned server architecture. The second, which is prerecorded and given by the co-founder of ImonCloud, Dr. Shun-Yun HU, introduces you to the ImonCloud and the back-end architecture (which is a hybrid architecture and uses a type of VON).

Here are the videos. Note that the ImonCloud presentation video is password protected. The password is posted in IVLE announcement.

Here is the reference to ImonCloud:
Shun-Yun Hu, Matthew Lien, “ImonCloud: Easing Development and Deployment
for Scalable Networked Games”, IEEE CCNC 2014. [PDF]

There are no suitable references to the lecture on hybrid architecture. You can download the slides here.

Update: IT Care has not resolved the issue wrt creating IVLE chat room. I will have to cancel the tutorial sessions for today.

The plan is to conduct our tutorial via IVLE chat, during our regular tutorial time.

But I have failed to create IVLE chat rooms for our tutorial tomorrow. IVLE refused and told me no slot is available and insists that I choose another date/time, even though the list of taken time slot shows otherwise. I have asked for help from IT care.

Please watch out this post for the latest update. Hopefully I will get the link to the chat room up here tomorrow.

http://doodle.com/hd69bdz347dinawm

Abstract

In this lecture, we will discuss how interest management is used in a point-to-point architecture to reduce the number of message exchanges. In particular, we will look at two different methods, one that uses cell-to-cell visibility and the other that uses distance-based visibility.

References

• [Stee05] is the main reference for Frontier Sets.
• [Hu06] is the main reference for 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 Google Scholar
A demo of Voronoi Diagram can be found in University of Bonn’s VoroGlide site.

Slides

Preview the slides here.

Here is Problem Set 2 on interest management.

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. [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 | Google Scholar]

Here is the preview of the slides.

## Introduction

You have been shown a naive implementation of a two-player Pong game in class. In this assignment, your task is to improve the implementation so as to improve the consistency and responsiveness of the game, while at the same time reduce the visual disruption and jerkiness of the entity movement in the game.

This week, let’s discuss about the design of multiplayer games, focusing on usability and balanced/fun game mechanics, as a preparation for your project. I do not play games (anymore) so I will rely on the class to augment the content with your own game playing experience.

• Pinelle, D., Wong, N., Stach, T., and Gutwin, C. (2009). Usability heuristics for networked multiplayer games. In Proceedings of the ACM 2009 International Conference on Supporting Group Work, GROUP ’09, pages 169-178, New York, NY, USA. ACM. [Google Scholar]

Additional references that might be useful include:

Here are some videos of CS4344’s projects from AY13/14. I showed the trailer in the first lecture, here are the longer ones.

Abstract In this lecture, we will continue our discussion on consistency techniques in multiplayer games. We will discuss local perception filter, a technique used to improve interactivity in the games, and bucket synchronization, a technique used in point-to-point games without a server.

References

• A more complicated version of local perception filter, where passive entities accelerates and decelerates, is described in details in [Smed06].
• Bucket synchronization is used in MiMaze [Gaut98].
• [Bret01] provides a good account on how synchronized simulation is implemented from the view of AoE.
[Smed06]
J. Smed and H Hakonen, Algorithms and Networking for Computer Games, Wiley, July 2006. [NUS LINC]
[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. [Google Scholar]
[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]

You can preview the slides for this lecture.

Please don’t use your NUS email since the update notifications from NUS blogs are considered as spam by NUS own spam filter.

Problem Set 1 has been released. This will be used for the 2-3 tutorials, so not all topics in this problem set will be covered in lectures by the time of the first tutorial next week.

Abstract We have seen that we can get into inconsistent states in multiplayer games.  In this lecture, we will see how players and servers can predict what the “right” states are, and how they can compensate for incorrect states in making decisions.

References

• The 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.
• Lag Compensation techniques used in Half Life in [Armi06] Section 6.3.2 and also in great details online at Valve’s Wiki.
• Predictions, both local and opponent predictions, are 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].
[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]

You can preview the slides for this lecture here.

Here are the videos for HTML5/Javascript. Note: It won’t cover everything on HTML5/Javascript, but enough for you to understand and start Assignment 2. Also, this is recorded for eLearning Week last AY. Some comments might be out of context.

And here is the last part on Pong, partially repeat what I covered in class.

For those having trouble running npm and node on Windows, see

http://stackoverflow.com/questions/25093276/node-js-windows-error-enoent-stat-c-users-rt-appdata-roaming-npm

This is due to a bug in node’s installation (https://github.com/joyent/node/issues/8141)

For each team member,

• Name, Student ID, Github ID
• For each team,

• A group selfie
• In this lecture, we will try to achieve two things.

First, I will show you a simple two-player Pong game and walk you through the key parts of the code.  This game will serve as the basis for your Assignment 2 and help to explain some concepts in this lecture.

Second, we will see how lags (or latency, or delay) on the Internet lead us to a solution that causes inconsistency and unfairness, and how we can introduce lags ourselves to mitigate these two issues.  We will end with a discussion on a set of experiments conducted to study the acceptable lags in two popular games, Unreal Tournament and Warcraft III.

Although not necessary, those of you with a laptop can bring it to class to follow along the Pong game.  Watching demos is useful, but there is nothing compared to playing with the demos yourself in class :)

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.
• The “dead man that shoots” example was mentioned by [Mauv00] in the context of fully distributed games.
[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]