Patent Publication Number: US-2010113159-A1

Title: Method and apparatus for partitioning virtual worlds using prioritized topic spaces in virtual world systems

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to online applications, and in particular to online gaming applications. 
     2. Background Information 
     Conventional massively multiplayer online games (MMOGs) and virtual worlds (such as Second Life) are unable to scale to support very large numbers of players within a single game/world. This is because such games and virtual worlds are reliant on a single instance of the game, running on a single physical computer system, acting as the authority for all activities within the game. Typically, the limits to scaling in this scenario are the network bandwidth of the single system and, more significantly, the processor capacity of a game server in the system. The game server, functioning as a game engine, is required to provide the simulation capabilities for every object and player in the virtual world. As the number of players (clients) increases the computing resources required increases dramatically. Certain game servers, particularly those providing FPS (First Person Shooter) styles of games, are only capable of supporting tens of users due to the complexity of the simulation and the low latency requirements of the game. 
     In another approach, each of multiple game servers (game engines) runs a map part within the current sphere of interest of the client. The map of the online game can be divided based on the game representation of the map, as a Binary Space Partition (BSP) tree. The tree can then be used to control how game entities are moved between servers running the game engine, such that responsibility for areas of the game map is distributed among a number of servers. A disadvantage of this approach is that said tree is not designed to be used as the basis of a partitioning exercise, being originally designed for the rapid creation of views within the world and for deducing the sphere of influence of any given object within the map. In addition, such approaches require detailed knowledge of, and access to, the map definition. As there are many data formats for the storage of map data, requiring detailed knowledge of the formats makes it more difficult to build a scalable system that can support multiple game/world engines. 
     SUMMARY OF THE INVENTION 
     The invention provides a method and system for hosting an online virtual world system on game engine servers. One embodiment involves obtaining a map representing a virtual world in the game, partitioning the map into multiple partitions, and selecting a game engine server for each partition as responsible for executing the game for detected game entities in that partition, wherein the selection is based on load balancing between the game engine servers. 
     Other aspects and advantages of the present invention will become apparent from the following detailed description, which, when taken in conjunction with the drawings, illustrate by way of example the principles of the invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       For a fuller understanding of the nature and advantages of the invention, as well as a preferred mode of use, reference should be made to the following detailed description read in conjunction with the accompanying drawings, in which: 
         FIG. 1  shows a functional block diagram of a virtual world system embodying aspects of the present invention. 
         FIG. 2  shows a flowchart of a process for partitioning virtual worlds using prioritized topic spaces in a virtual world system, according to an embodiment of the invention. 
         FIG. 3  shows a space map for a game. 
         FIG. 4  shows a grid superimposed on the map. 
         FIG. 5  illustrates partitioning virtual worlds using prioritized topic spaces in a virtual world system, according to an embodiment of the invention. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The following description is made for the purpose of illustrating the general principles of the invention and is not meant to limit the inventive concepts claimed herein. Further, particular features described herein can be used in combination with other described features in each of the various possible combinations and permutations. Unless otherwise specifically defined herein, all terms are to be given their broadest possible interpretation including meanings implied from the specification as well as meanings understood by those skilled in the art and/or as defined in dictionaries, treatises, etc. 
     The invention provides a method and apparatus for partitioning virtual worlds using prioritized topic spaces in a virtual world system. This allows reliably partitioning a virtual world to increase scalability and permit dynamic load balancing. One embodiment of the invention involves using an externally computed management grid, based on key factors of the map (such as the bounding box data), and a prioritized topic space approach to implement a highly scalable virtual world solution that can be dynamically load balanced across a grid of servers. 
     The prioritized topics space approach distributes the workload of running a virtual world or game simulation across a cluster of network connected servers. The responsibility for running the simulation is divided up amongst the servers such that each takes responsibility for one or more areas of the virtual world and the objects and avatars within those areas. 
     The virtual world map is divided into individual grid squares (for a 2 dimensional division) or cubes (for a 3 dimensional division), such that the computing resources for running the simulation of any grid element, when fully populated with the maximum possible number of objects and/or avatars, does not exceed the capabilities of the least capable server in the system. 
     Clients connect to the system via a client proxy element which takes incoming data packets and publishes them to topics that represent the area of the map in which the client&#39;s avatar is currently resident. The simulation engine responsible for the area of the map containing the players avatar subscribes to the topic representing that map area and thus receives the inbound data packets from the client. 
     As the simulation runs, the simulation engines periodically output update data reflecting changes in the state of objects and avatars within the areas of the map they are responsible for. These data updates are published to topics representing the map area within which the object to which the state change corresponds is situated. The client proxy processes subscribe to the topics for the area of the map the avatar of the client is in and the neighboring areas that are visible to the client and thus receive all relevant outbound update packets from the simulation engines that are then formatted into a packet understandable by the client. 
     In a typical conventional game system, the simulation engine outputs a complete data update packet for each and every client within its map and each packet is tailored for the client so that it receives only data that is relevant to it and for objects and avatars within sight. This leads the game engine to potentially send the same data multiple times once for each client to which the object is visible. This is an expensive operation. By contrast, according to an embodiment of the invention each state change for an object is published to the pub/sub framework once and is delivered to each client proxy that needs it by the pub/sub framework, thus reducing the work of the simulation engine. 
     In a virtual world and game engine, prioritization of state change data is used to reduce the network bandwidth used. A normal priority state change may be the movement of the avatar of a player, a high priority change may be the movement of a projectile towards the player or the playing of a sound effect, and a low priority state change may be the movement of another player that is some distance from the avatar of the client. When computing resources or when network bandwidth is scarce, the lower priority data can be discarded or transmitted later without undue loss of fidelity to the players gaming experience. 
     According to the invention, by using prioritized topic spaces, such techniques are extended to further reduce the computing resources required. The invention reduces the amount of time any quantity of state change data is sent by the simulation from potentially hundreds to just once. When the state change data is published, a priority is assigned with the publication in just the same way as the current systems associate a priority, high for a projectile or immediate sound effect, medium for movement of objects close by, and low for movement of distant objects. This prioritization provides guidance to the pub/sub framework as to the order data that should be sent across the network to subscribers. Different pieces of data published to the same topic may be assigned different priorities and thus the order of receipt of data may be different from the order of sending. 
     On the subscriber side, a separate priority can be assigned to a topic. Thus the client proxy will set up subscriptions on behalf of its client for the topics that represent the grid areas surrounding the avatar of the client. The grid square that the client is in will have the highest priority and the priorities of topics for the squares surrounding will have decreasing priority the further they are away from the avatar of the client. 
     The combination of the priorities associated with the data packets by the publisher, effectively based on the category of the state change, combined with the priorities associated with the topics by the subscriber based on geospatial relevance, provide an efficient method to ensure the most relevant data is delivered to and thus processed by the client proxy, and therefore client, first. 
       FIG. 1  shows an example system  10  embodying aspects of the invention. The system  10  provides a virtual world hosting architecture, including a topology where world/game clients  12  connect to one of a number m of client proxy servers  14  which in turn communicate with a grid of n game engine servers  16  over which the world map is spread. Each game engine server  16  is interfaced to a publication and subscription (pub/sub) framework  18  and managed by a corresponding engine agent  19  that isolates the game engine from the details of the pub/sub mechanism. The clients  12  communicate with the proxies  14  using the UDP protocol over a network  15 . The proxies  14  communicate with the game engines  16  using the pub/sub framework  18  which may operate e.g., using a very high performance network mechanism, such as UDP multicasting, a reliable transport such as TCP (transport control protocol), or a very specialized system such as a high speed processor interconnection mechanism. 
     The pub/sub framework  18  services game and world clients (players)  12 , and connects them to a grid of game and world servers (game engines)  16 . Data is published to topics, which may represent logical server identities or roles, and is delivered by the pub/sub framework  18  to those processes that expressed an interest (subscribed) to the topic. Using a subscription service process of the pub/sub framework  18 , the proxy servers  14  subscribe to topics relevant for their clients  12 . Using a publication service process of the framework  18 , a game engine  16  publishes data changes for each object or player it is managing once per game cycle (i.e., publishing data to named topics). The subscribing proxies then aggregate the received data from the framework  18  and forward the aggregated data to their clients  12 . 
     The system uses a 2-dimensional or 3-dimensional management grid that is logically overlaid on the game world map. This grid is defined using a computational method based on the coordinate system of the game engine, and arranged so as to encompass the whole of the virtual world map. Individual grid square cells (or cubes in the 3-dimensional grid), are defined such that the number of player avatars that can be contained within the area/volume of a grid cell can be supported by the least capable computer system. 
     Responsibility for executing the game/world simulation associated with each cell of the management grid is assigned to one or more game engine servers. Each game engine server within the solution may have responsibility for one or more cells. In practice, each engine is likely to have responsibility for a large number of cells (e.g., in the thousands). Each game engine server in the solution executes the simulation and outputs data concerning state changes to entities within its area of the game. The game server also receives state change data from game clients that are represented by avatars within the cells the server is responsible for. 
     Each cell within the management grid is assigned a unique topic name within the topic space of the framework  18 . The topics name is used to publish data relevant to the cell and interested proxies may subscribe to the topics in order to receive such data. 
     Using the framework  18 , the game servers publish state change data for objects within any particular cell to the topic assigned to that cell. The proxies  14  subscribe to the topics associated with the cells which lie within the sphere of interest of each of the player avatars representing the players that are connected to them. Thus, each proxy receives all data relevant to corresponding clients  12  and can aggregate this information into a normal outbound game protocol message on the client connection. 
     Similarly, state change data from game clients  12  is received by the client proxies  14  through the normal game network protocol and is then published via the framework  18  to the cell topic that represents the cell that the player&#39;s avatar is currently in. Each game engine server  16  subscribes to the cell topic and thus receives the state change data. The routing of inbound state change data to the proper engine server  16  is entirely managed by the pub/sub framework  18 . 
       FIG. 2  shows a flowchart of a process  40  for partitioning virtual worlds using prioritized topic spaces in a virtual world system, according to an embodiment of the invention. The process blocks in  FIG. 2  are described below. 
     Block  41 : Determination of the Management Grid and Topic Names 
     The system is controlled by applying an arbitrarily sized grid to the coordinate space of the map.  FIG. 3  shows an example virtual world map  20  which represents a number of interlinked rooms  21 , shown on a 2-dimensional coordinate system centered on (0, 0). The map may be defined to the game/virtual world engine and client as a BSP (Binary Space Partitioning) tree, or other data format. Binary Space Partition (BSP) trees, a common form of expressing a virtual world or game map, are well known within the art of computer gaming. Generally, the map is constructed around a description, wherein an example herein is based on a top-down, or ground view, 2-dimensions (the techniques described herein can easily by extended to 3 dimensions). The example map  20  extends from −500 to +500 in the x-axis and from −400 to +400 in the y-axis. 
     A world management system  17  ( FIG. 1 ) includes a partitioner module  17   a  for partitioning the map, and a load balancer  17   b  for balancing the load between servers. The load balancing function  17   b  can also be distributed among the servers, as discussed in the example herein. 
     The system  17  superimposes a logical grid  22  on the map coordinate space.  FIG. 4  shows an example logical grid  22  superimposed on the map  20 , wherein the example grid  22  includes twenty cells  23 . The grid  22  is not directly related to the original map data except to ensure the grid encompasses the total coordinate space and that the size of the individual grid cells  23  is such that all servers within the cluster are capable of supporting at least one grid cell when the activity within the cell is at a maximum. In a preferred embodiment, the smallest grid cell size is defined such that each cell is capable of containing 100 avatars (10×10), and in certain game engines this relates to a map floor area of e.g., 10 meters by 10 meters. 
     The cells  23  in the grid  22  can be considered to have an identity based on their x and y positions. In the example above, the grid  22  extends to five cells  23  in the x-axis and four cells  23  in the y-axis. In overlaying the grid  22  on the map coordinate space the size of the grid cell has been selected in terms of the map coordinate system. In the example above, where the map coordinate space is effectively 1000 units (−500 to +500) in the x-axis and 800 units in the y-axis, the selected grid square size is 200×200 units. Other number of grid cells and of different sizes may be selected. 
     Since the grid spans the entire map coordinate space, a grid cell containing any point within the map can be expressed as a (x, y) coordinate. Knowing the cell size in map coordinate units, the minimum x coordinate (min_x_coord) and the minimum y coordinate (min_y_coord) of the map bounding box, and assuming integer arithmetic, then the cell identifiers gx and gy for each cell can be determined as: 
         gx =( x _cord−min —   x _coord)/cell_size, 
         gy =( y _cord−min —   y _coord)/cell_size. 
     These x and y cell identifiers gx, gy are then mapped to a unique topic name by simple concatenation of the text representation of the gx and gy values with a separator. Thus, for the example grid  22 , the twenty individual cells  23  would be mapped to twenty unique topic names “1-1”, “1-2”, “1-3”, “1-4”, “2-1”, “2-2”, etc. 
     Block  42 : World Partitioning and Load Balancing 
     Using the calculated management grid identifiers grid (i.e., gx, gy), responsibility for running the world simulation can be divided up between a number of game engine servers  16 . The selection of which management cells  23  are associated with which servers  16  can be computed by different algorithms, typically may be based on the computational capacity of the servers and also the geospatial relationships of the grid cells  23 , to provide an essentially balanced computational load on the involved servers  17 .  FIG. 5  graphically illustrates an example distribution  30  for cells  23  to game engines. In this case the world map has been partitioned between 9 game servers (e.g., Engine  1 -Engine  9 ). Specifically: cells “1-2”, “1-1”, “2-1” and “2-2” are assigned to Engine  1 ; cells “1-4” and “1-3” are assigned to Engine  2 ; cells “4-4” and “4-3” are assigned to Engine  3 ; cells “3-1” and “3-2” are assigned to Engine  4 ; cells “4-1”, “4-2”, “5-1” and “5-2” are assigned to Engine  5 ; cell “3-4” is assigned to Engine  6 ; cell “2-4” is assigned to Engine  7 ; cells “2-3” and “3-3” are assigned to Engine  8 ; and, cells “5-4” and “5-3” are assigned to Engine  9 . This partitioning is preferably performed initially on system start-up based upon externally provided information, automated map analysis, or historical usage information. 
     During execution of the world simulation, the load on individual servers may change. For example, if a number of players (clients) move into a single small area (e.g., moving from a lobby area into an auditorium or meeting room), the load on a single server may start to increase. In this situation, the partitioning of the system may be changed dynamically by publishing requests with the framework  18  to the different servers within the cluster to move responsibility for one or more cells between them. If in the example shown in  FIG. 5 , several players move into the room in the right-hand lower corner of the map, then sever Engine  5  may become too heavily loaded. In this case, server Engine  4  may be instructed to take responsibility for cells “4-1” and “4-2” thus dividing up the work required to support activity within the room. To achieve this, entities “transition” between the servers as described further below. 
     Block  43 : Game Client and Server Data Flow Control 
     Each client proxy  14  handles inbound client connection requests, forwards client state change data to the appropriate game server  16 , and outputs server state change data to the client  12 . The establishment of new connections is known to those skilled in the art. The game servers  16  execute (run) the simulation, and output state changes for the entities within the game. 
     Block  44 : Data Flow Control from the Game Client 
     Each game client  12  delivers state change packets across a connection to the corresponding client proxy  14  e.g., via UDP, using a game or virtual world specific protocol per game cycle (e.g., 10 times per second). The client proxy has sufficiently detailed information about the game protocol to extract the player&#39;s current position information from the inbound messages. The proxy  14  calculates the management grid cell  23  that a player is currently in, and the associated topic name using the steps described above. The proxy  14  then publishes the inbound data packet unchanged to the topic name computed, using the framework  18 . 
     Block  45 : Data Flow Control to the Game Client 
     The proxy  14  tracks a management grid cell  23  that each of corresponding client  12  is currently in. Whenever the proxy  14  detects a new client in a cell or that the client has moved from one cell to another, the proxy  14  determines which management grid cells  23  are currently relevant to that client. In the grid  22  of  FIG. 5 , consider the x-axis from left to right, and the y-axis from bottom to top. If the current position of a client defines that it is in cell x=2, y=3, and if the game defines that a client can only see twenty meters in any direction, and the management grid  22  is based on 10-meter by 10-meter cells  23 , then there are eight neighboring cells  23  that may contain entities that are relevant to the client (i.e., cells “1-2”, “2-2”, “2-3”, “1-3”, “3-3”, “1-4”, “2-4”, and “3-4”) as well as the cell the client resides in (i.e., cell “2-3”). Using the framework  18 , the proxy  14  subscribes to the topics for these cells, so that it can receive game engine update data relevant to said client (i.e., reflecting any state changes of entities, such as other player avatars, within the neighboring cells). 
     When each game server  16  executes its part of the simulation, using the framework  18 , the server  16  publishes state change data for each entity under its control, to the topic for the grid cell in which the entity resides. State changes are delivered by the framework  18  to relevant client proxies  14  based on the topics each proxy subscribed to. Thus, each proxy  14  only receives state changes needed for its corresponding clients  12 . Each proxy  14  then aggregates the individual state change data into a protocol message for each of its clients, based on their individual areas of interest. 
     Block  46 : Entity Transition Control 
     As players move around the virtual world, their avatars come under the control of different game engine servers. As noted, each game server  16  is responsible for an area of the world map  20  as determined by the aforementioned partitioning (e.g.,  FIG. 5 ). As the avatar moves around the map  20 , responsibility for the avatar must be transitioned between game servers  16 . To facilitate this, game data is again published via the framework  18 . 
     When a game engine server  16  determines that an entity (player/client) is moving out of its area (cell) of control, that server packages up the state of the entity (e.g., state data, current script execution state, etc.) and publishes the state information to the topic for the management grid cell the entity is moving into. As the new game engine server that now owns the cell into which the entity is moving has subscribed to the topics of all the cells it controls, that game engine server receives from the framework  18  the state of the moving entity as published by the previous owner game engine server. As such, the new game engine server of the transitioned (moved) entity resurrects the entity from the packaged state information and takes responsibility for publishing future outbound state change data for the transitioned entity. 
     As is known to those skilled in the art, the aforementioned example embodiments described above, according to the present invention, can be implemented in many ways, such as program instructions for execution by a processor, as software modules, as computer program product on computer readable media, as logic circuits, as silicon wafers, as integrated circuits, as application specific integrated circuits, as firmware, etc. Though the present invention has been described with reference to certain versions thereof; however, other versions are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the preferred versions contained herein. 
     Those skilled in the art will appreciate that various adaptations and modifications of the just-described preferred embodiments can be configured without departing from the scope and spirit of the invention. Therefore, it is to be understood that, within the scope of the appended claims, the invention may be practiced other than as specifically described herein.