Multiplayer Online GamesOutlineTypes of MOG: Categorization by GenreFirst-Person Shooter (FPS)FPS (cont.)Role-Playing Game (RPG)Another RPG (Sort of)RPG (cont.)Real-Time Strategy (RTS)RTS (cont.)Types of MOG: Categorization by PersistencyNo PersistencyPersistent Player InformationPersistent Game WorldScales of MOGInteresting CombinationsPLATO Computer SystemInnovationsHardwarePLATO V TerminalPLATO IV TerminalMultiplayer GamesEmpireSlide 24AvatarSlide 26Research Issues (1)Research Issues (2)Research Issues (3)Recent PapersServer Discovery for FPSServer Discovery for FPS (2)Slide 331500 Archers on a 28.81500 Archers on a 28.8 (2)1500 Archers on a 28.8 (3)Slide 37Latency Compensation in Half-LifePredicting Where I AmPredicting Where You AreLag CompensationEffect of Latency in Warcraft 3Slide 43Fair Message ExchangeFair Message Exchange (2)Fair Message Exchange (3)Cheat-Proof PlayoutSlide 48Cheat-Proof Playout (2)Slide 50SecuritySecurity (2)Casual & Wireless GamesMultiplayer Online GamesAn-Cheng HuangBruce MaggsOutline•Overview of multiplayer online games (MOGs)•Research issues•Sample of recent papers•A few observationsTypes of MOG: Categorization by Genre•First-Person Shooter (FPS)•Role-Playing Game (RPG)•Real-Time Strategy (RTS)First-Person Shooter (FPS)Game worldPlayer characterWeaponsAim + shootCall of Duty, Activision / Infinity WardFPS (cont.)GameworldRole-Playing Game (RPG)Game worldPlayer character“Weapons”Accomplish task,Improve (virtual)ability, accomplishharder task, etc.Diablo II, Blizzard Entertainment / Blizzard North (?)Another RPG (Sort of)Game worldPlayer characterAccomplish task,Improve (virtual)ability, accomplishharder task, etc.RPG (cont.)GameworldReal-Time Strategy (RTS)Game world“Units”Explore, build,combatRise of Nations, MicrosoftRTS (cont.)GameworldTypes of MOG: Categorization by Persistency•No persistency•Persistent player information•Persistent game world•Persistency–Local: e.g., run a persistent server for a few friends–Global: e.g., game company hosts servers for allNo PersistencyBeforegamingsessionDuringAfterPersistent Player InformationBeforegamingsessionDuringAfter Persistent Game WorldBeforegamingsessionDuringAfterScales of MOG•n: Number of players in a game world•n<=8•n<=64•n>1000  Massively Multiplayer (MMOG)Interesting Combinations•n<=64 (16-32 mostly), no persistency, FPS: e.g., CoD•n<=8 (2-4 mostly), no persistency, RTS: RoN•n<=8, persistent player information, RPG: Diablo II•n>1000, persistent game world, RPG: EverQuest•n>1000, persistent game world, FPS: PlanetSidePLATO Computer System•PLATO IV Developed by the University of Illinois and the Control Data Corporation•1961 timesharing PLATO II begins•1964 invention of plasma panel•1968 PLATO IV begins•Spun off as “NovaNET” late 1980’s•Revived at www.cyber1.orgInnovations•first LARGE on-line community•invention of the plasma panel•multimedia•“personal notes” – email•“group notes” – newsgroups•“consulting mode” – like PC anywhere•widely used “term talk” (like Unix talk)•multiplayer graphical games•IBM correctly attributes Lotus Notes to PLATOHardware•Control Data mainframes designed by Seymour Cray•Cyber 70, 176, CDC 6600, 7600•Magnetic core memory•60-bit words, 6-bit characters•One’s-complement arithmetic•Up to 1000 simultaneous users•(NovaNET runs on Alpha today?)PLATO V Terminal•Plasma panel and CRT versions•Same 512 x 512 display•8080 processor implemented all graphicsPLATO IV TerminalFrom http://plato.filmteknik.com/Multiplayer Games•Dungeons and Dragons–orthanc, avatar•Space–empireEmpireEmpireAvatarAvatarResearch Issues (1)•n=16-32, no persistency, FPS–Most sensitive to latency, jitter, and relative latency–Client/server architecture (anyone can run a server)left button clickedrender a rocket at (x1,y1) flying toward (x2,y2)•How to find a (good) server?•How to meet the performance requirements?•Security (fairness/anti-cheating)?Research Issues (2)•n=2-4, no persistency, RTS–Each user control many units (e.g., >100s)•Too many units!•Security?Player1Player2left button clicked on(xd,yd)next renderu1: (x1,y1)u2: (x2,y2)…un: (xn,yn)next renderu1: (x1,y1)u2: (x2,y2)…un: (xn,yn)next renderu1: (x1,y1)u2: (x2,y2)…un: (xn,yn)next renderu1: (x1,y1)u2: (x2,y2)…un: (xn,yn)Research Issues (3)•n<=8, persistent player information, RPG•n>1000, persistent game world, RPG & FPS•Persistency  EconomyVirtual:•Performance/Scalability•Security, Security, SecurityReal life:84 listings,$12Subscription-basedRecent Papers•Server discovery for FPS–[Bernier GDC00], [Henderson NG02]•Too many units in RTS–[Bettner & Terrano GDC01]•Performance requirements of FPS & RTS–[Bernier GDC01], [Pantel & Wolf NG02], [Sheldon et al. NG03] •Security–[Guo et al. NG03], [Baughman & Levine INFOCOM01]•Traffic modeling•ArchitectureServer Discovery for FPS•~50000 servers for Counter Strike [Feng NG03]•[Bernier GDC00] How it’s done in Half-Life–“Master server” (server directory)•Game servers send periodic keepalive messages to master•Handle IP-spoofing DoS attacks with challenge/response•Reduce bandwidth usage with batched requests–Client gets list from directory and polls each serverServer Discovery for FPS (2)•[Henderson NG02] –Problems with centralized: single point of failure, stale/redundant info, client polling servers, etc.–A peer-to-peer approach•Clientserverclientserver…•Stop when a suitable server found–Potential problems•Stale/inconsistent info•Lack of scalable queryingRecent Papers•Server discovery for FPS–[Bernier GDC00], [Henderson NG02]•Too many units in RTS–[Bettner & Terrano GDC01]•Performance requirements of FPS & RTS–[Bernier GDC01], [Pantel & Wolf NG02], [Sheldon et al. NG03] •Security–[Guo et al. NG03], [Baughman & Levine INFOCOM01]•Traffic modeling•Architecture1500 Archers on a 28.8•[Bettner & Terrano GDC01] Age of Empires•Too many units to update individually! Simultaneous simulations (tricky!)Player1Player2left button clicked on(xd,yd)left button clicked on(xd,yd)next renderu1: (x1,y1)u2: (x2,y2)…un: (xn,yn)next renderu1: