U.S. Pat. No. 9,630,104

DETAILED DESCRIPTION OF THE ILLUSTRATED EMBODIMENT

This application discloses systems, apparatus, and methods for predictively transferring content from a server system to a client computer where it is maintained in a content cache. Generally, the client computer's content cache can be implemented using techniques well known in the art along with the improvements disclosed herein. In one embodiment of the disclosed invention, the client computer's content cache is implemented using a least recently used (LRU) scheme, as modified herein. The disclosed prediction methods rely on the past and present behavior of an avatar associated with the client computer to determine what content the client computer is most likely to require next.

Referring to the Figures, and in particular toFIG. 1, a virtual world content streaming system100is shown. A server system110comprises a world server112, a content server114, and an account server116. The account server116maintains a list of all persons who have an account with the particular server system110. In addition, the account server116tracks which users are presently using (i.e.; “logged on”) the system, and billing or subscription information related to each user, as well as any information required to reconstruct the user's particular representation of the virtual world. Such information could comprise an inventory of items possessed by the user's avatar, a list of “real” (i.e.; houses, shops, etc.) property or vehicles owned by the user's avatar, which areas the user has explored, the avatar's position and facing within the virtual world when last “saved,” etc. These functions of the account server116are well known in the art. In addition, the account server116can maintain a list of content a particular user is authorized to enter. For instance, in a MMORPG, a user may be authorized to enter into the “starting area” (usually a large city) and all outdoor areas, but not to enter into any structures outside of the starting area unless the user pays a higher subscription fee, or pays an additional fee for all or part of the extra content.

The content server114maintains a database of all content within the particular virtual world implemented by the virtual world streaming system100using techniques well known in the art.

The world server112maintains an individualized world representation for each active user. Utilizing a content requirement prediction technique, the world server112generates content requests for the content server114from which it receives content, and then forwards the content onto the appropriate client.FIG. 1depicts four clients connected to the server system110. However, real world applications of the disclosed invention would likely, but not necessarily, support hundreds, thousands, or even tens of thousands of simultaneous clients.

The world server112is connected to a network120, such as the Internet, via a communication link. Desktop computer client121and notebook computer client122are connected to the network120through a wired connection, while cellular telephone client123and mobile gaming device client124are connected to the network120via wireless links.

Note that whileFIG. 1depicts one possible implementation of a virtual world content streaming system utilizing the disclosed invention, many other systems could utilize the disclosed invention. For instance, the server110could be implemented in a single computer (instead of three as drawn), or even within a single program, or alternatively, the world server112could be implemented as a group of servers, each maintaining a particular area of the virtual world.

FIG. 2visually depicts one possible algorithm using the principles of the disclosed invention to predictively transmit content from a server system110to at least one client121-124. This algorithm is referred to later in the application as the “Location-Velocity Content Transfer,” or LVCT for short. A simple virtual world map200is shown with an avatar204located at the center. Using virtual sight, hearing, and possibly other senses (via force feedback for instance), the avatar has a maximum perception radius208. In addition, a geometrical shape212, such as a two or three dimensional arced surface or a frustrum, is projected from the avatar in the direction that the avatar is looking. All virtual world content unknown to the avatar's204client121-124which is within either the avatar's maximum perception radius208or the boundaries of the geometrical shape212are transmitted to the avatar's204client121-124. Some possible examples of transmitted content are height maps, terrain, objects, moveable objects, equippable objects, actor definitions, artificial intelligence objects, and sounds. As drawn, structure216is within the boundaries of geometrical shape212. In one embodiment of this invention, all information regarding structure216is queued for transmission to the client121-124as soon as the structure216comes within the boundaries of the geometrical shape212. However, given that structures can comprise enormous amounts of content, transmitting all content associated with the structure at once could overload the content cache maintained on the client121-124depending on the type of client (i.e.; desktop computer vs. cellular phone). A more refined method for selectively transmitting structure content is detailed later in this application.

A further refinement of the algorithm detailed inFIG. 2involves the use of the avatar's204confirmed heading. Using this algorithm, all content within the avatar's maximum perception radius208would be transmitted to the client. In addition, a further distance, perhaps out to 1.1 times the maximum perception radius208would also be queued for transmission to the client. However, until the client moved in a particular direction for a predetermined time period, such as 2 seconds, further content (i.e.; out to two times the avatar's204maximum perception distance208) would not be streamed. Yet another refinement of the algorithm depicted inFIG. 2would be to use the avatar's204velocity vector224to determine how far to extend the content transmission radius220beyond the avatar's maximum perception radius208, with the content transmission radius being directly proportional to the magnitude of the velocity vector.

Instead of transmitting all content associated with a structure, a more refined algorithm could be used instead. One example of such an algorithm is illustrated inFIG. 2A. As illustrated,FIG. 2Autilizes a portal structure to progressively transmit visual content. However, the principles of this invention can easily be extended to non-visual content (i.e.; sounds, object definitions, etc.) as well as to other spatial data structures, such as bounding volume hierarchies, binary space partitioning (BSP) trees, or octrees.

InFIG. 2A, the avatar204stands outside a structure240. Depending on where the avatar is disposed, and the avatar's facing, from outside the structure240, the avatar can see through portal250to area260, through portal251to area261, and through portal252to area262. This is shown in content list270, which indicates that areas260-262should be transmitted to the avatar when the avatar is positioned outside the structure240. If the avatar should move into area260, then the avatar will be able to see through portal251into area261, through portal252to area262, and through portal255to area265. Accordingly, content list271is associated with area260. Content lists272-277show which areas are potentially visible to the avatar for other areas within the structure240. Using this information, which can be predetermined using simple raycasting algorithms well known to those skilled in the art, the world server112can selectively transmit only the content required by a particular client121-124. However, for the goal of seamless presentation of the virtual world on the client computer system to be met, the content associated with a particular area must be transmitted to the client computer system before the avatar actually breaches a portal leading into a particular area. This can be accomplished by defining a portal transmission radius280centered at the center of the portal and transmitting the content associated with the area whenever the avatar breaches that area.

A further refinement of the algorithm depicted inFIG. 2Ainvolves the use of the avatar's velocity vector to determine where the avatar appears headed, and to transmit content appropriately. Therefore, if based on the avatar's velocity vector and facing, the server system predicts that the avatar will breach a particular portal's portal transmission radius280within a predetermined period of time, such as two seconds, the server system can queue the content list associated with the area in question for transmission. This allows the server to less frequently update a particular client computer system with content.

FIG. 3Ais a flowchart showing one possible set of steps executed on a client computer implementing the disclosed invention. In step304the client computer notes the position of the avatar. Next, in step308, the avatar's facing is determined. In step312, the avatar's heading, which could be different from the avatar's facing (i.e.; the avatar is looking in a different direction that it is moving), and correspondingly the avatar's velocity vector is determined. In step316, the client transmits the information required by the server, such as the avatar's position, facing vector, and velocity vector. The server system will then execute steps, such as those illustrated inFIG. 3B, to retrieve the correct content and transmit it to the client. In step320, the client receives the content from the server, and in step324, the client updates its content cache. Finally, in step328, the client utilizes the new content as required within its virtual world engine to render a scene.

FIG. 3Bis a flowchart showing one possible set of steps executed on a server system implementing the disclosed invention. In step340, the server system receives a particular avatar's location, facing vector, and/or velocity vector from a particular client. Optionally, in step341, the server determines the appropriate content transmission radius for the particular avatar based on the avatar's velocity vector and/or the time the avatar has maintained a particular heading. In step342, the server system determines the content within the particular avatar's maximum transmission radius. The server then queues that content in step343and transmits it to the particular client in step344.

The algorithm executed by the client computer implement the structure based selective content transmission algorithm illustrated inFIG. 2Ais identical to the algorithm disclosed inFIG. 3A. However, the server system algorithm will differ somewhat for structures as opposed to the general server system algorithm disclosed inFIG. 3B.FIG. 3Cillustrates a server system algorithm tailored to structural content. In step350, the server system receives a particular avatar's location, facing vector, and/or the avatar's velocity vector from a client computer system. In step351, the server system generates content requests for the content server based on the avatar's position and optionally the avatar's velocity vector, as well as the content lists associated with the particular area the avatar presently occupies or appears headed towards as discussed earlier. In step352, the server system queues content corresponding to the requests generated in step351, and transmits that content to the appropriate client computer system in step353.

It should be noted that the steps shown inFIG. 3AandFIG. 3Bare only one possible embodiment of the disclosed invention, and, in particular, the shown steps may be executed on either the client or server as required by the particular implementation.

FIG. 4visually depicts a second algorithm using the principles of the disclosed invention to predictively transmit content from a server system110to at least one client121-124. This algorithm requires at least one structured story line be integrated within the virtual world, and is henceforth referred to as “Storyline Content Transfer” or SCT. Each structured story line can be comprised of multiple story elements. For the purposes of this application, a story element comprises a story event, such as finding an object or solving a puzzle, associated with a particular location. Similar structures are also envisioned as falling within the definition of story element.

As depicted, avatar204is involved in multiple story lines,404,408, and412. While only three story lines are shown, the avatar204may be involved in any number of story lines. Story line404comprises multiple sequential story elements. As shown there is a central story line, comprised of element A, element C, final element, and other elements not shown. In addition, there are other “sub-plots,” which branch off of the main story line. Element B comprises one such sub-plot, and elements D and E comprise another. As depicted, avatar204has completed all story line requirements of element A and element B of story line204. As these elements have already been completed, it is less likely that avatar204will revisit any areas associated with the completed story elements, or require content associated with the completed story elements. On the contrary, as avatar204has not completed the story line requirements of element C, element D, element E, and other elements including the final element, it is more likely that avatar204will visit areas associated with those elements and therefore require the corresponding content. As avatar204is not likely to visit locations associated with elements A and B, content associated with elements A and B is less likely to be required by the client computer121-124hosting avatar204. When purging content from the client computer121-124content cache, the system can account for this, and correspondingly eliminate content associated with elements A and B earlier than would otherwise occur.

While SCT can be used alone, SCT is especially useful when used to enhance LVCT or another primary content transfer prediction algorithm. When used in this way, SCT effectively becomes a secondary decision making factor, which can be used to increase the likelihood that certain content, such as the next element in a particular storyline; i.e.; element C of story line404; will be transferred to the client or maintained in the client cache. For instance, referring toFIG. 2, structure A217is shown as outside of the content transmission radius220as established by the LVCT algorithm. However, if structure A217is associated with story line element C ofFIG. 4, SCT will examine the avatar's heading/velocity vector224and as avatar204appears headed towards structure A217, will give content associated with structure A217a higher weight than that associated with structure216.

FIG. 5Aillustrates one possible set of steps that can be executed by a client computer implementing the disclosed invention. In step504, the client computer121-124transmits certain information associated with an avatar204to the server system110. The transmitted information could be LVCT information, information associated with some other predictive content transfer scheme, or information stored on the client computer121-124indicating story line elements completed by the avatar. Note that story line element information may also be stored on the server system110. In step508, the client computer121-124receives content from the server system110. The client computer updates its content cache in512, and executes its virtual world algorithm on the updated content cache in step516. Note that the content cache can be the same as the virtual world database.

FIG. 5Billustrates one possible set of steps that can be executed by a server system implementing the disclosed invention. In step554, the server system110receives information associated with an avatar204from the client computer121-124. In step558, the server system110determines what story lines the avatar204is involved in. The server system110determines which story line elements the avatar204has completed within the identified story lines in step562. In step566, the server system examines all story line elements in all story lines and determines the story line element the avatar will most likely attempt next. In step570the content associated with the identified story line element is queued for transmission, and that content is transmitted to the client computer121-124in step574.

In a further refinement of the disclosed algorithms, the server could contain a representation of content within the client's content cache. The server could then transmit only that content not already present within the client's content cache. In addition, the server could directly control the client's content cache.

It should be noted that the steps shown inFIG. 5AandFIG. 5Bare only one possible embodiment of the disclosed invention, and, in particular, the shown steps may be executed on either the client or server as required by the particular implementation.

As discussed earlier in association with the account server116, the principles of this invention may also be used to distribute virtual content for a fee. For instance, in many MMORPGs, avatars increase in power as they explore more areas of the virtual world. Content areas may be segregated by the avatar power, so that the most powerful adversaries, treasure, etc. can be concentrated within one content area, and correspondingly less powerful adversaries, treasures, etc. can be concentrated in other content areas. One way that content may be distributed for a fee would be to charge different subscription levels, wherein an introductory subscription could include content associated with a “starting area” as well as content areas associated with the least powerful adversaries, treasures, etc. The first subscription level could be free or a fee could be charged. When the user first created an account with the server system110, billing information, such as a credit card, would be collected. If the initial subscription was free, the credit card would not be charged.

Additional subscription levels, at correspondingly higher fees, could include more power adversaries, treasures, etc. As a user's avatar approached a content area not covered by the avatar's subscription level, the server system110could cause the user's client computer121-124to prompt the user to authorize the higher subscription fee. The server system110could then use billing information gathered from the user when the user first created an account and validate that the additional fee would be acceptable with a creditor associated with the billing information provided by the user. After validating the user's billing information for the additional fee, the user's avatar would be allowed to proceed into the content areas associated with the user's new subscription level.

An additional embodiment of the disclosed invention may allow access to specific content areas for a fee. Using this embodiment, the user could pay a subscription fee for “basic” access to the virtual world, or basic access could be free. Premium content areas, which could be associated with more powerful adversaries, could only be accessed if the user's account indicated that the user had paid for them. As a user's avatar approached a content area that the user had not yet paid for, the server system110could cause the user's client computer121-124to prompt the user to authorize the payment for the premium content area. The server system110could then use the billing information provided by the user when the user first created an account as explained earlier.

Note that this application uses the terms client and server. Within this application, the term client means a consumer of content, and the term server means a provider of content. Using the definitions within this application, web browsers, among other client programs, would fall within the definition of client, and web servers, among other server programs, would fall within the definition of server.

The foregoing description of the invention has been presented for purposes of illustration and description, and is not intended to be exhaustive or to limit the invention to the precise form disclosed. The description was selected to best explain the principles of the invention and practical application of these principles to enable others skilled in the art to best utilize the invention in various embodiments and various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention not be limited by the specification, but be defined by the claims set forth below.