• home
• research
• resumé
• schedule
• about me
• Et Cetera
• bookmarks

Colyseus: Making distributed FPS games possible

Networked games are rapidly evolving from small 4-8 person, one-time play games to large-scale games involving thousands of participants and persistent game worlds. However, like most Internet applications, current networked games are centralized. Players send control messages to a central server and the server sends (relevant) state updates to all active players. This design suffers from the well known robustness and scalability problems of single server designs. For example, high update rates prevent even well provisioned servers from supporting more than several tens of players for first person shooter (FPS) games. Further, client-server game designs often force players to rely on infrastructure provided by the game manufacturers. These infrastructures are sometimes not well provisioned or long-lived; thus, they either provide poor performance or prevent users from playing their game long after their purchase.

Although several "platforms" and "middleware layers" have emerged to try to tackle the burden of partitioning game state across a servers (such as Big World, Open Skies, and Zona), all of these efforts have targeted centrally controlled, tightly administered server clusters, addressing none of the afore mentioned problems (in addition, most have been designed for non-latency sensitive games such as RPGs). IBM and Sun are betting that utility computing and economies of scale will be the solutions, but so far few game publishers have signed on. However, a third possibility exists. There is significant evidence that given appropriate incentives, players themselves are willing to provide resources for multiplayer games. For example, in most FPS games, public servers are run by third parties (such as clans or guilds), and number in the hundreds to thousands for individual games. Moreover, the majority of these servers are underutilized. Given the rapid growth of broadband and even faster access links, even the casual gamer may have excess resources available in the near future.

A truly distributed game architecture could potentially address the shortcomings of centralized designs leveraging public server resources for free. In addition, it could permit a truly peer-to-peer deployment with little or no central control, somewhat like existing file-sharing applications. However, architecting any distributed application is difficult due to the challenges of partitioning application state (e.g., the game world state) and execution (e.g., the logic to simulate player and game AI actions) among the participating hosts. Distributing a networked game is made even more difficult by the performance demands of real-time game-play. In addition, since the game-play of an individual player translates to updates to the shared state of the game application, there is much more write traffic and write-sharing than traditional distributed applications like file systems and content distribution.

Colyseus

Fortunately, there are two fundamental properties of games that we can take advantage of in addressing these challenges. First, games tolerate weak consistency in the application state. For example, even current client-server implementations minimize interactive response time by presenting a weakly consistent view of the game world to players. Second, game-play is usually governed by a strict set of rules that make the reads and writes of shared state highly predictable. For example, most reads and writes caused by a player occur on objects which are physically close to them in the game world. The challenge, then, is to arrive at a scalable and efficient state and logic partitioning that enables reasonably consistent, low-latency game-play. We have designed and implemented Colyseus, a novel distributed architecture for interactive multiplayer games designed to achieve the above goals in a widely distributed environment with no centralized management.

In particular, Colyseus showcases the following features:

• Efficient Partitioning: Colyseus partitions game state and execution among participating servers, though any node may create read-only secondary replicas of any game object. A good paritioning reduces interactive response times for players and efficiently utilizes the computational and bandwidth resources on all the servers to execute a single seamless game world, while secondary replicas enable the low-latency read access needed to keep the game execution timely.
• Efficient Object Location: Colyseus enables efficient and robust object discovery using either a traditional Distributed Hash Table (DHT) or a dyamically load-balanced, range-queriable DHT called Mercury. Moreover, these substrates automatically repair themselves and integrate new resources, allowing Colyseus' object discovery layer to tolerate server additions, removals, and failures gracefully without an administrator in the loop.
• Speculative Prefetching: Colyseus leverages the locality and predictability in game data access patterns to identify objects each server will need to replicate in the near future, enabling it to speculatively pre-fetch required objects before they are needed without incurring substantial overhead.

Colyseus enables games to efficiently use widely distributed servers to support a large community of users. We have integrated our implementation of Colyseus with Quake II (a popular server-based FPS game), and have also used real measurements of Quake III game-play to develop our own Colyseus-based game that mimics the Quake III workload. Moreover, Colyseus exports a simple but flexible API for game developers that is similar to existing game networking engines such as the Torque Networking Library. Our prototypes can be run either on a community of servers or in a completely peer-to-peer setting, and our initial evaluation shows that it can support at least hundreds of servers and players. See our publications for more details.

People

Current:

• Ashwin Bharambe
• Jeffrey Pang
• Srinivasan Seshan

Past affiliations:

• Mukesh Agrawal
• Justin Weisz

Publications

Last modified: Thu Nov 02 09:32:34 EST 2006