Object Placement:

Since the model does not restrict where primary objects are placed on the system, we must determine which objects each node should maintain.

図 2: Architecture Overview: The components of Colyseus. The labeled steps are described in Section 3.2.

Since game state and object interests are continually changing, mechanisms meeting these challenges must be able to cope with a highly dynamic environment. We address these challenges with Colyseus's three components, shown in Figure 2.

To locate relevant remote objects, we use a robust, distributed object location component based on a publish-subscribe system called Mercury (described in Section 4). Mercury allows nodes to register interests using range queries over multiple object attributes. Our implementation shows that this is sufficient for Quake II and we believe this is rich enough to support most games. For example, a player may be interested in all objects in the visible area around its avatar, along with some information about her teammates; these interests can be expressed as ( red) in Mercury (steps (1) and (2) in Figure 2).

Once discovered, replicas are maintained by a object management component (described in Section 5) which synchronizes replicas with the primary using mechanisms similar those used by servers to synchronize state with clients (i.e., keep client views up-to-date) in the client-server architecture (steps (3) and (4) in Figure 2).

Finally, we use an object placement component to determine where to place primary objects in the system and where to migrate them as a game progresses (described in Section 6). Section 2 demonstrated that bandwidth requirements of dedicated servers have a steep linear scaling factor with the number of players. Hence, the limiting factor in a distributed game is almost certainly communication cost (i.e., bandwidth). We make the observation that the number of remote object interests is directly related to the cost of communication that must be expended, and our object placement component optimizes object placement using clustering heuristics on an inferred interest graph (steps (5) and (6) in Figure 2). We note that distributing responsibility for state also helps alleviate the computation bottleneck.

Colyseus allows nodes to join the system in a fully self-organizing fashion, so there is no centralized coordination required. In addition, we believe it places few requirements on game developers. The only major additions to the centralized object store programming model are: (1) each object specifies its area-of-interest with range queries (i.e., a declaritive variant of how area-of-interest is currently computed); and (2) each object publishes a small number of attributes (such as their location) that others use to look it up. These can be thought of as naming attributes. For example, Figure 3 shows the object interface that game developers would implement in an application running on Colyseus. Colyseus maintains the actual object store.⁵ Each object in the system is identitified by a globally unique identifer which we call a GUID (e.g., a large pseudo-random number; our implementation uses 80-bit GUIDs) and each node is uniquely identified by an routable SID (i.e., an IP address; our implementation uses 48-bit (IP address, port) pairs as SIDs).

図 3: Application Interface: The interface that game objects implement in applications running on Colyseus.

The following sections describe each component of Colyseus in detail and show how each component affects the implementation of a distributed version of Quake II.