Abstract:
The disclosed massive multi-player on-line gaming environment and method eliminate the coordination and synchronization problems between servers by assigning each game user to a specific client proxy server for game duration and utilizing a space information distribution center to indicate client specific changes in game space. Such configuration eliminates the need to use “grey” areas around partitioning boundaries and servers having to “own” client objects thereby improving massive multi-player on-line gaming scalability.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The present invention is a continuation-in-part of U.S. application Ser. No. 10/821,050, “Method for Distributing and Geographically Load Balancing Location Aware Communication Device Client-Proxy Applications” filed on Apr. 8, 2004. The U.S. application Ser. Nos. 10,821,050, 10/448,949, “Automatically Segmenting and Populating a Distributed Computing Problem” filed on May 29, 2003, and Ser. No. 10/448,625, “System and Method for Balancing a Computing Load Among Computing Resources in a Distributed Computing Problem” filed on May 29, 2003, which are assigned to the same assignee, are herein incorporated by reference in their entireties. 
    
    
     FIELD OF THE INVENTION 
     The present invention generally relates to the field of massive multi-player on-line computer gaming, and more specifically, to a system and method for partitioning work between servers and tracking client interaction with servers in multi-player games running on multiple servers. 
     BACKGROUND OF THE INVENTION 
     With the proliferation of the Internet and technology, massive multi-player on-line games have become increasingly popular. There are a number of common features shared by massive multi-player on-line games which distinguish them from other types of on-line computer games. First, most massive multi-player on-line games host a number of players in a single game world where all those players can interact at one time. For instance, a popular massive multi-player might host thousands of players online at any given time. Second, to support all those players, massive multi-player on-line games employ large-scale game worlds. As such, large areas of the game are interconnected within the game such that players may traverse great distances without having to switch servers manually. Further, multi-player on-line games require updated data for each user location and application that a user may call upon during game play. As the number of players increases, the complexity of calculations and server demand increases. Finally, the game state in massive multi-player on-line games rarely resets. 
     There are two conventional approaches taken to distribute the handling of players and objects in game space. One is to simply partition the game world using special tunnels, small single person passageways, or other contrivances at the boundaries between servers. This approach is limited in that the partitioning is static. Thus, if too many players converge on the same server&#39;s portion of the game world, that server will become overloaded and game performance will suffer. 
     The second approach is the setting of dynamic boundaries. Although the setting of dynamic boundaries limits server overload, with this approach, there are many places in the game space where players can simultaneously see into one or more other servers&#39; area of control. Thus, the servers need to tightly synchronize information with their neighboring servers. Furthermore, in these configurations, a “grey” area is present around the partitioning boundaries where both servers partially “own” the objects, the data is mirrored between the servers, all in an attempt to reduce the work involved in handing off an object to the next server when the object leaves the “grey” area. This mirroring, though, further increases synchronization problems and greatly complicates the server code. These techniques are described in detail in “Massively Multi-player Game Development” edited by Thor Alexander in 2003 (ISBN 1-58450-243-6). As stated in “Massively Multi-player Game Development,” although many limitations are associated with such techniques, implementation is necessary in order to achieve desired massive multi-player on-line game scalability. 
     Therefore, it would be desirable to develop a massive multi-player on-line game with technology designed to overcome the above mentioned difficult coordination and synchronization problems between multiple servers thereby improving on-line gaming. 
     SUMMARY OF THE INVENTION 
     Accordingly, the present invention is a system and a method directed to an improved handling of players and objects in massive multi-player on-line games. The disclosed massive multi-player on-line game system and method may eliminate the coordination and synchronization problems between servers by assigning each game user (client) to a specific client proxy server for game duration and utilizing a space information distribution center to indicate client specific changes in game space. Such configuration eliminates the need to use “grey” areas around partitioning boundaries and servers having to “own” client objects thereby improving massive multi-player on-line gaming scalability. 
     In accordance with a first aspect of the present invention, a massive multi-player on-line gaming environment is disclosed. In an exemplary embodiment, the environment includes a space information distribution system and a game space mapping system connected via an internal network. Further, a plurality of client proxy servers is connected to the internal network. A multiplicity of remote users is connected to the client proxy servers via a worldwide network. Each client proxy server handles one or more users for game duration, wherein the client proxy servers employ the information from the game space mapping system and space information distribution system to distribute only the needed information to each specific user. 
     In accordance with a second aspect of the present invention, a method for partitioning work-load between servers and tracking user interaction with servers in multi-player games running multiple servers is disclosed. In an exemplary embodiment, the method includes the following steps: (1) creating an internal network that includes a space information distribution system and a game space mapping system; (2) assigning each remote game user to a client proxy server, each client proxy server handling one or more users for the duration of the multi-player game and connecting the client proxy servers to the internal network; and (3) employing the space information distribution system to track user status information, the space information distribution system sending the information to the client proxy servers to distribute user specific information to appropriate remote users via a worldwide network. 
     In accordance with a third aspect of the present invention, a method for partitioning work-load between servers and tracking user interaction with servers in massive multi-player online games running multiple servers is disclosed, comprising the steps of: (1) segmenting game space within a multi-player game into a game graph with vertices and edges, the vertices representing game regions and the edges connecting the game regions that can influence each other; (2) assigning each game user to a client proxy server, the client proxy server handling one or more users for the duration of the multi-player game; (3) employing a space information distribution system to track user status information; (4) delegating communications between the client proxy servers and the space information distribution system; and (5) sending the information of the space information distribution system to the client proxy servers, the client proxy servers then employing the information to distribute user specific information to game users connected to the client proxy servers via a worldwide network. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention as claimed. The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate an embodiment of the invention and together with the general description, serve to explain the principles of the invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The numerous advantages of the present invention may be better understood by those skilled in the art by reference to the accompanying figures in which: 
         FIG. 1  is an illustration of a massive multi-player on-line gaming environment in accordance with an exemplary embodiment of the present invention; 
         FIG. 2  is an illustration of a game space mapping system in accordance with an exemplary embodiment of the present invention; 
         FIG. 3A  is an illustration of a cell and collection of cells; 
         FIG. 3B  is an illustration of a collection of cells, core cells and edge cells; 
         FIG. 4  is an example of game scenario when users of a massive multi-player on-line game change position; 
         FIG. 5  is a flow diagram illustrating an additional method for partitioning work between servers and tracking user interaction with servers in multi-player games running multiple servers in accordance with the present invention; and 
         FIG. 6  is a flow diagram illustrating an additional method for partitioning work between servers and tracking user interaction with servers in multi-player games running multiple servers in accordance with the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Reference will now be made in detail to the presently preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. 
       FIG. 1  depicts massive multi-player on-line gaming environment  100 , which is shown by way of example and not by way of limitation. The massive multi-player on-line gaming environment  100  comprises a space information distribution system  104  and a game space mapping system connected via a worldwide network. Further, a plurality of client proxy servers, (i.e. client proxy server  1 ,  108 , and client proxy server  2 ,  110 ) is connected to the internal network  102 . A multiplicity of remote users (i.e. user  1 ,  112 ; user  2 ,  114 ; and user  3 ,  116 ) is connected to the client proxy servers via a worldwide network  118 . One example of a worldwide network is the Internet. Each client proxy server handles one or more users for game duration, wherein the client proxy servers employ the information from the game space mapping system  106  and space information distribution system  104  to distribute only the needed information to each specific user. 
     Referring to  FIG. 2 , the game space mapping system  202  is comprised of a game space mapping program  204 , multiple servers  206  to process the graph of game space, re-mapping game space program  208 , and rules engine  210 . The game space mapping program  204  creates a graph of game space with vertices (nodes) representing specific game regions and edges connecting those game regions capable of being influenced. 
     As illustrated in  FIG. 3A , a cell  310  may represent a node on the game space graph, and may contain data, methods, and pointers to other cells. Cell  310  is grouped within collection  300 . In some situations, a collection could consist of only one cell. Each grid node handles one or more collections at a time whereby the collections are dynamically assigned to a partition for execution on a common grid node. 
       FIG. 3B  shows cells marked with an E or C. Cells marked with an E are edge cells. Cells marked with a C are core cells. The cells within a collection (i.e. the core cells,  314 , and the edge cells,  312 ) communicate with one another directly using in-memory communication such as Java object references. The edge cells will communicate with the edge of neighboring collections using in-memory communication if they are on the same partition. If the collections are not within the same partition, then data is transmitted over the existing network infrastructure. For example, copies of entire objects (i.e. the cells themselves) can be sent from the edge cells of one collection to the edge cells of another collection. Thus, when a cell communicates with a neighboring cell, the cell has access to the code or processes used by the neighboring cell. Since the transmitted objects have data, methods, and pointers to neighboring cells, the communicating cell will also know the neighboring cells of its neighboring cells. The mapping program follows rules to minimize the amount of network communication required. Therefore, the cells, collections, and partitions together form the foundation of the game space mapping system. 
     The rules engine  210  decides whether the game space graph is to be altered. Alteration of the game space graph may be necessary in order to balance server load when activity concentrates in one game space region i.e. an area of a game map where a large number of players have converged. To prevent server over-load, upon receipt of an instruction from the space information distribution system  104  of  FIG. 1 , re-mapping game space program  208  determines the applicable rules engine  210 , and applies such engine to re-calculate the game space graph. Re-mapping game space program  208  configures partitions to remove load from an over-loaded server (or servers) and to adjust data communication requirements accordingly. The re-mapping program  208  adjusts the load by re-assigning cells from a server operating above threshold to a neighboring server that is not above threshold. As such, re-mapping program  208  creates a new game space graph that includes a smaller geographic area being assigned to a specific server thereby reducing the number of game players processed by that server. New communication dependencies, based upon the new assignment, are also reflected in the new game space graph. The reconfiguration of partitions and adjustment of communication requirements is performed according to instructions from rules engine  210 . 
     The game map system  202  assigns partitions to servers  206 , and servers  206  perform the actual computations for the partitions of the game space graph. Multiple servers  206  only send one message to the separate space information distribution system  104  to indicate what is changing in their own part of the game space. The space information distribution system  104  transmits such information to the various client proxy servers, such client proxy server  1 ,  108  and client proxy server  2 ,  110 , which, in turn, only send the needed information to each user. 
     Referring now to  FIG. 4 , a game scenario in which three users converge in one region of game space is provided. As shown, users A, B, and C initially begin in areas where they do not have visual contact with each other in the virtual world map. But after users A, B and C move into the upper right corner of the virtual world map, users A and C are in virtual line of sight with each other and users B and C are in virtual line of sight with each other. Depending on the game type, users A, B and C may call upon the application they are participating in to perform various actions. As the number of users increases in one region of game space, the server demand and number of calculations called upon to be made within that particular region increases. In accordance with the present invention, such scenario is monitored by the space information distribution system and, in turn, by the game space mapping system. If number of users increased above desired threshold, the rules engine within the game space mapping system would re-calculate the game space graph to shift the work-load of the over-burdened server to an un-burdened neighboring server. 
     Referring now to  FIG. 5 , a method for partitioning work between servers and tracking user interaction with servers in massive multi-player games running multiple servers is disclosed. In an exemplary embodiment, the method  500  includes the following steps: (1) creating an internal network  502  that includes a space information distribution system, a game space mapping system, and a plurality of applications and servers; (2) assigning each remote game user to a client proxy server  504 , each client proxy server handling one or more users for the duration of the multi-player game and connecting the client proxy servers to the internal network; and (3) employing the space information distribution system to track user status information  506 , the space information distribution system sending the information to the client proxy servers to distribute user specific information to the remote users via a worldwide network. 
     Additionally, method  500  for partitioning work between servers and tracking user interaction with servers in massive multi-player games running multiple servers disclosed in  FIG. 5 , includes a game space mapping program, multiple servers to process the graph of game space, a re-mapping game space program, and a rules engine to re-calculate the game space graph. In such embodiment, the game space mapping system includes the following steps: (1) creating a game space graph with vertices representing specific game regions and edges connecting the game regions capable of being influenced; (2) assigning partitions to the plurality of servers; (3) the servers performing computations for the partitioning of the game space graph, and then sending one message to the space information distribution system to indicate changes in their own part of the game space; and (4) the space information distribution system transmitting the message from the plurality of servers within the game space mapping system to the various client proxy servers. Additionally, in embodiments of the invention, the re-mapping game space program determines the applicable rule engine and applies such engine to re-calculate the game space graph. 
     Referring now to  FIG. 6 , an additional embodiment of a method  600  for partitioning work between servers and tracking user interaction with servers in massive multi-player online games running multiple servers is disclosed. The method  600  is comprised of the following steps: (1) segmenting game space within a multi-player game into a game graph with vertices and edges  602 , the vertices representing game regions and the edges connecting the game regions that can influence each other; (2) assigning each game user to a client proxy server  604 , the client proxy server handling one or more users for the duration of the multi-player game; (3) employing a space information distribution system to track user status information  606 ; (4) delegating communications between the client proxy servers and the space information distribution system  608 ; (5) sending the information of the space information distribution system to the client proxy servers  610 ; and the client proxy servers then employing the information to distribute user specific information to game users connected to the client proxy servers via a worldwide network  612 . It is contemplated that such method could be utilized to convert an existing computer game into a massive multi-player on-line game. 
     It is believed that the present invention and many of its attendant advantages will be understood by the foregoing description. It is also believed that it will be apparent that various changes may be made in size, materials, shape, form, function, manner of operation, assembly and use of the components thereof without departing from the scope and spirit of the invention or without sacrificing all of its material advantages. The form herein before described being merely an explanatory embodiment thereof. Further, it is contemplated that the specific order or hierarchy of steps in the method can be rearranged while remaining within the scope and spirit of the present invention. It is the intention of the following claims to encompass and include such changes.