|
...multiserver engine running grid. Other approaches require that a game be specifically designed to scale to MMOG player levels. Our approach, using IBM OptimalGrid middleware (which provides an abstracted underlying grid infrastructure to an application) allowed us to reuse an existing game engine without the need to make any significant changes to it. In this paper we examine the design elements needed by an MMOG and provide a practical implementation example-the extension of the id Software Quake II [R] game engine using OptimalGrid middleware. A key feature of this work is the ability to programmatically partition a game world onto a dynamically chosen and sized set of servers, each serving one or more regions of the map, followed by the reintegration of the distributed game world into a seamless presentation for game clients. We explore novel features developed in this work and present results of our initial performance validation experiments with the resulting system.
INTRODUCTION
The computer game industry is deploying a new genre known as the massively multiplayer online game (MMOG), characterized by large numbers of clients--ranging from several hundred to hundreds of thousands--playing simultaneously. Until now, the creation of such a scalable game has been done primarily by custom-designing game engines unique to the specific MMOG. Efforts to create reusable MMOG game development and game engines have been underway, Butterfly.net (1) being an example of a commercial game development environment for MMOGs. In its work, Butterfly.net obtained patents related to the development of games and games using grids. Subsequently, it has updated its business plan and renamed itself Emergent Game Technologies. At the time of the writing of this paper, details about this new entity's game architecture were not available. The issues surrounding the building of MMOGs and large-scale virtual environments (2) have become an area of interest and study, with academia publishing studies on general architecture, intelligent on demand provisioning, (3) server selection, (4) distributed communications models, (5) distributed server location schemes, (6) game artificial intelligence, and agent-based testing frameworks for game developers. Additionally, the application of MMOG technology to building large-scale agent-based simulations (7) for research on non-game-related commercial customer relationship management systems is also underway. The complexities of large-scale group interactions (8) within online games, that is, exploring the communities that come about within the virtual worlds of the games, has also become a topic of research.
Many techniques have been developed to distribute both massively parallel applications and connected parallel applications, such as cellular automata and finite element modeling. (9) MMOGs--like other applications that stress the resource limitations of a single system--are excellent candidates to which the scalable computing power of grids can be applied, such as the approach taken by Emergent Technologies (1) and that presented in this paper.
MMOGs are especially demanding in their low communication-latency requirements. In computing, as in other systems, increasing the number of parts, in this case the number of computers, increases the likelihood of failure of a part. To provide a stable and long-lasting game for players, MMOGs running on a grid require fault tolerance and dynamic load balancing, just like scientific grid applications. However, unlike scientific applications that tolerate interruption for checkpoint and logging, online games do not permit interruption or latency degradation during load balancing or system maintenance.
Because considerable performance optimization and game-play balancing have been done to single-server multiplayer engines such as id Software Quake ** and Valve Half-Life **, (10,11) it would be desirable if the effort put into such engines could be reused to run MMOGs. Instead of designing new engines specifically for MMOGs, the reuse of existing optimized engines would allow many of today's games to be scaled up to MMOG level and allow game developers to continue using game engines with which they are familiar. Many popular engines apply similar architectures, offering the hope that techniques for scaling up of game engines to MMOG levels for one engine can be reapplied to other engines. Ideally, such scaling techniques would be done in a generalized manner, rather than specifically enhancing any one particular engine, helping to broaden the applicability of the techniques.
In this paper we report the results and lessons learned in enhancing an existing single-server multiplayer game engine to scale to the MMOG level. We chose the popular open-source Quake II ** (12) game engine from id Software for this work, but have attempted to develop reusable generalized techniques in performing the enhancement. This enhancement was accomplished by using the OptimalGrid (13) autonomic grid middleware from IBM Research. This middleware was originally designed with scientific and engineering applications in mind; however, the OptimalGrid object model and dynamic load-balancing features were easily adapted to asynchronous online games.
In this paper, we examine the key issues in extending a game engine to running in a multiserver environment; we introduce the Quake II game engine and OptimalGrid middleware. We then provide an overview of the resulting system, outlining its major components, followed by an exploration of the details of the design. We introduce the runtime environment developed to manage the execution of the MMOG game engine and discuss the additional debugging challenges inherent in a large distributed system, along with the solutions we used. We then present the results of the performance experiments we performed on the system, and lastly, our conclusions and a brief outline of future work.
MASSIVELY MULTIPLAYER ONLINE GAMES
Many types of parallel computational problems have been considered in research and implemented in mature systems. They range from problems with moderate connectivity, such as the simulation of finite element models, to massively parallel tasks, such as the search for optimal Golomb rulers. (14,15) MMOGs however, present a set of unique constraints. Like many scientific simulations, the game worlds found in MMOGs are often well-suited to division into spatial regions that may be run in parallel, albeit connected regions.
Game-world partitioning
Game worlds typically are continuous like the real world. This means that each spatial division has strong connectivity to the regions that neighbor (touch) it; actions and events in one region affect objects in neighboring regions. For example, a gun fired in one region of the world may cause damage to a player in another region that lies along a line-of-sight path from the first. Long-range interactions between regions can exist, meaning in the example that there may be multiple regions along the line-of-sight path, with each region possibly being hosted on a different server. Thus connectivity between regions is not limited to those that are "physically'" adjacent, but instead, connectivity exists between any region and all the regions that are visible to it. For example, in long hallways and large open areas, a player's local actions must be observable to players in any other visible region, regardless of which server is controlling that region. Any implementation of spatial partitioning of the game world into discrete regions assigned to different servers must provide a mechanism to propagate events to servers holding adjacent regions, and it must also have a mechanism to propagate such events along the full path of connected regions, and events must be propagated in a timely manner so that no cause-and-effect delay is introduced that exceeds that intended by the game designer or would be experienced if the game regions were all hosted on a single server.
The dependencies between spatial regions of the world are mitigated somewhat by the presence of barriers such as walls, but some long-distance connections typically remain. This situation complicates the problem of dividing the world into regions. How can a parallel system take advantage of the near-neighbor connectivity of regions with multiple obstacles while still allowing distantly connected regions to correctly influence one another? An intelligent algorithm for positioning region boundaries should take into account the underlying mechanics of the game that may or may not allow one point to influence another.
Data exchange
One way to help address the problems of strong connectivity is to introduce a global, shared message space, or whiteboard, for communication between portions of the parallel system. In the most extreme case, if every one of n servers was responsible for a region of the world connected to some region on every other server, connecting the servers directly to one another would result in O([n.sup.2]) connections across the network, or n - 1 per server. Introducing a single whiteboard as an intermediary, however, reduces the total connections to O(n), or one per server. Of course, this improvement comes at the cost of increasing latency in sending messages and limiting the collective bandwidth of all communication channels in the system to that of the whiteboard. A more scalable approach is to use a number of whiteboards, each responsible for forwarding messages between a set of servers that are nearby (in the sense of game-world regions). Each server then needs to connect only to several whiteboards.
Partition granularity
A key problem involved in the partitioning of the game world is choosing the degree to which the world is subdivided. For a one-time or static partitioning of the game world, a significant tradeoff must be made. If too few regions are used, then fewer servers may be used, but regions can become overloaded with players and other active entities. If too many regions are chosen, the area of the game world covered by a region becomes quite small. While this allows for more servers to be used, it can result in excessive data exchange among servers due to the number of regions connected to each region; player movement between servers will be very frequent, and other game entities, such as weapons fire, will be required to cross numerous servers. A practical strategy for choosing a partitioning granularity takes into consideration the maximum number of servers upon which the game will be hosted, the complexity of the interconnectedness of regions, and features specific to the game that affect event propagation and generation.
Although some effort at selecting an optimal allocation of servers and assignment of regions can be made before launching the game, such choices become outdated and invalid quickly as the result of game play. Thus, to achieve and maintain an optimal use of servers requires adaptive reassignment of regions and reallocation of servers (adding and removing) during game play. This is because server load arises primarily from the players active on a server and the players moving within the game world--and thus moving between servers. These activities can continuously change the optimal assignment of regions and use of servers.
Latency
Apart from the issues arising from the topology of the game world, MMOGs have another set of distinct challenges. These derive from the interactive nature of games. One would like the solution of a scientific problem to be completed as soon as possible, but the precise time taken by each successive step is not typically a concern. Games, however, have stringent constraints on the time taken to compute successive states of the world and the latency in client/server communications. This is especially true because it is normally necessary to perform all game "physics"" (evaluation of the rules of the game world) on servers to prevent players from cheating by altering their client software. Consider the sequence of events triggered in a typical game when a player moves forward. After the user chooses to move and presses the corresponding key, the command is sent to the server, which computes the movement, and the new position of the player is then sent back to the client. Players do not get any visual feedback that they have moved until this round-trip communication has taken place. Players are sensitive to delays in this feedback loop as small as tens of milliseconds. To address this sensitivity during periods of unusually high latency, the Quake II client attempts to predict the server response to provide feedback to the user sooner. However, this prediction is error-prone and considered a last resort.
These latency requirements significantly constrain parallel architectures for MMOGs. If a distributed architecture requires switching of network connections between clients and servers or transmission of game objects such as players or projectiles between servers, those transitions must take place in a time frame sufficiently short to allow a seamless user experience.
One strategy to reduce critical latencies is to treat aspects of the system as asynchronous. Rather than having every server act in lockstep, exchanging messages at regular intervals, as is essential in scientific simulations, it can be advantageous to allow different components of the system to run freely, sending each other events as soon as the need arises. In a system for running MMOGs on multiple servers, this may mean allowing the servers to generate states of their portion of the world out of sync with each other and to send each other messages as soon as it is useful to do so.
QUAKE II
Quake II is a popular multiplayer (but not massively multiplayer) game developed by id Software. Released in late 1997, it is representative of the genre of games known as first person shooters--games in which the player is presented with a three-dimensional (3D) view rendered from the perspective of the game character and whose action is centered on the player firing weapons at adversaries. Like most other first person shooters (FPSes), multiplayer games in Quake II take the form of death matches, in which players run around a level composed of rooms, tunnels, and outdoor areas attempting to shoot and kill their opponents. Although almost seven years old, Quake II is particularly representative of many online...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IBM Systems Journal
A marketing maturity model for IT: building a customer-centric IT orga..., March 01, 2006
Online games and e-business: architecture for integrating business mod..., March 01, 2006
A context-aware smart-call-center solution: improving customer service..., March 01, 2006
Content protection for games., March 01, 2006
High-performance server systems and the next generation of online game..., March 01, 2006
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
