Introduction

Networked games have gained tremendous popularity in the last decade, with the online gaming market now a multi-billion dollar industry. These games are rapidly evolving from small 4-8 person, one-time play games to large scale games involving thousands of participants [4] and persistent game worlds. However, like most Internet applications, current network games are centralized. Players send control messages to a central server and the server sends (relevant) updates to all other active players. This design suffers from several problems:

• Robustness. It has a central point of failure that reduces robustness. A game should be playable as long as the players' computers are connected.

• Scalability. It has difficulty supporting more than a few hundred players since: 1) the graphics, game-play and AI computation places a significant computation load on the server, and 2) the server bandwidth demand increases linearly (or worse) with the number of players.

• Dedicated infrastructure. It often forces players to rely on infrastructures provided by the game manufacturers. These infrastructures are often not well provisioned or long-lived and, thereby, provide poor performance or prevent users from playing their game long after their purchase.

In this paper, we present the design, implementation and evaluation of Colyseus, a distributed architecture for interactive multi-player games which avoids these shortcomings. Our design can allow large communities to play games without a central dedicated server. Game performance is limited only by the aggregate resources available to the users and the network proximity of the users. We have implemented Colyseus and integrated it with the publicly available Quake II game engine [8] to show the practicality of our architecture.

While making a networked game distributed involves several challenges (some of which we review in Section 2), the most fundamental challenge is distributing the shared game state and logic required for simulating player and AI actions. Managing distributed state has always been a hard problem; but for networked games, the problem is made more difficult by the performance demands of the real-time game-play. Furthermore, since the game-play of an individual player translates to updates to the shared state of the game application, a distributed network game has a much higher amount of write traffic and write sharing between nodes than most other applications. The challenge then is to arrive at a scalable and efficient replication and consistency model which enables reasonably consistent game-play without sacrificing much latency.

In order to better understand the detailed needs of designing realistic distributed multiplayer games, we use Quake II, a first person shooter (FPS) game, as a concrete case study. We chose Quake II because its client-server game model is representative of the architecture of many other online multiplayer games. The shared game-play state of these games is structured as a collection of objects, each representing an individual entity in the games, such as players, weapons, items, etc. Each object is associated with a piece of code called a think function. Typical think functions examine and update the state of both the associated object and other objects in the game. For example, a missile moves by updating its x, y, z coordinate attributes and causes damage by decrementing the health attributes of a player object. The game state and execution is simply composed from the combination of these objects and associated think functions. The server's main loop periodically calls the think functions for every object.

Colyseus realizes an architecture for distributing game objects and associated think functions. The core component in our system is a new distributed object store that is optimized for use in a distributed network game. This distributed object store helps address the issues of ownership, replication and object discovery.

• Ownership. A single node in the distributed system is assigned primary responsibility for an object. This node executes the think function associated with each object, determines which updates are committed, and provides a serialization order to updates. We allow a flexible mapping of objects to nodes to enable locality-aware placement of these primary objects.

• Replication. In order to execute the think function associated with an object, the owner may need to access other objects. We allow any node in the system to create a secondary replica of any object. This node must maintain a connection with the primary owner of the object through which it receives all updates for the object. This direct connection provides the low latency interaction that is often required for real-time game-play.

• Object Discovery. The most challenging aspect of this design is determining, in advance, which objects a think function may need to access during its execution. Otherwise, the node would need to fetch the object upon access, incurring a high latency preventing real-time game-play. In the centralized server implementation, the think function simply iterates over all objects and inspects a subset that are relevant. Based on our inspection of games, we believe that this subset can easily be identified in advance and can be expressed using a limited select-like query over the collection of all objects. However, the results of every think function's select query must be re-evaluated every time an object is updated. We rely on a distributed publish-subscribe system based on Mercury [11] to scalably handle this select processing. Each object generates a subscription that specifies, using range-based predicates over one or more object attributes, the set of objects it is interested in. A primary object's owner periodically generates a publication with the object's metadata (the primary owner's ID and the subset of object attributes that are queriable). When this update is routed to a subscriber, it generates a replica for the object.

With this design, each node ends up replicating objects within the union of interests specified by its primary objects. Minimizing this union also minimizes the amount of communication and storage overhead in our system. The object store monitors the access relationships between objects to create an interest graph of objects within it. Using this interest graph, Colyseus performs automatic clustering and migration of objects in order to minimize communication overheads.

We have implemented a distributed version of the Quake II game server using Colyseus. Quake II clients can connect to any instance of this distributed server and, as a result, the system can be run as a peer-to-peer application (with every client running a copy of the distributed server) or as a distributed infrastructure (with clients connnecting to the closest distributed server). Our measurement of this prototype on an Emulab testbed indicates that Colyseus scales with the number of nodes by distributing game traffic reasonably well across the participants. We also show that Colyseus is able to maintain retrieve relevant objects quickly thereby maintainaining a high consistency of views.

The rest of the paper is organized as follows. In Section 2, we examine the requirements of networked games and the limitations of current architectures in detail. Section 3 provides an overview of the architecture of Colyseus, while Sections 4, 5, and 6 detail the object location, replica management, and object placement and migration components of our system. In Section 7, we present a detailed evaluation of the system. Finally, Section 8 summarizes our work.