U.S. Pat. No. 8,082,245

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

A virtual world is a simulated environment in which users may be represented by avatars. An avatar may be used to “travel” through locations of the virtual world, such as virtual streets, buildings, rooms, etc. While an avatar is in a given location, the user represented by the avatar may be presented with options of other locations that are available to the user, meaning the user may selectively travel to another location by selecting a given option. For example, an avatar present in a hallway may be able to open any one of multiple doors present in the hallway, with each door opening to a different room.

However, a user presented with unfamiliar locations may not know what content of the virtual world is available at each location. Typically, a user would have to determine this information by a process of trial and error. This process may be tedious and time-consuming. Given information describing each location, the user may decide to avoid certain locations, and may only visit other locations.

Embodiments of the invention provide techniques for providing information describing locations to users of an immersive virtual environment. In one embodiment, patterns of locations visited by various users of the virtual environment may be stored in a searchable data structure(s). Further, characteristics of the location visits may be used to determine whether a given location visit was favorable for each user. Subsequently, locations visited by a current user may be matched to one of the stored patterns of locations. The matching pattern may then be used to provide favorability information describing other locations available to the current user. The favorability information may be presented to the user as graphical indications visible within the user's view of the virtual environment.

In the following, reference is made to embodiments of the invention. However, it should be understood that the invention is not limited to specific described embodiments. Instead, any combination of the following features and elements, whether related to different embodiments or not, is contemplated to implement and practice the invention. Furthermore, in various embodiments the invention provides numerous advantages over the prior art. However, although embodiments of the invention may achieve advantages over other possible solutions and/or over the prior art, whether or not a particular advantage is achieved by a given embodiment is not limiting of the invention. Thus, the following aspects, features, embodiments and advantages are merely illustrative and are not considered elements or limitations of the appended claims except where explicitly recited in a claim(s). Likewise, reference to “the invention” shall not be construed as a generalization of any inventive subject matter disclosed herein and shall not be considered to be an element or limitation of the appended claims except where explicitly recited in a claim(s).

One embodiment of the invention is implemented as a program product for use with a computer system. The program(s) of the program product defines functions of the embodiments (including the methods described herein) and can be contained on a variety of computer-readable storage media. Illustrative computer-readable storage media include, but are not limited to: (i) non-writable storage media (e.g., read-only memory devices within a computer such as CD-ROM disks readable by a CD-ROM drive and DVDs readable by a DVD player) on which information is permanently stored; and (ii) writable storage media (e.g., floppy disks within a diskette drive, a hard-disk drive or random-access memory) on which alterable information is stored. Such computer-readable storage media, when carrying computer-readable instructions that direct the functions of the present invention, are embodiments of the present invention. Other media include communications media through which information is conveyed to a computer, such as through a computer or telephone network, including wireless communications networks. The latter embodiment specifically includes transmitting information to/from the Internet and other networks. Such communications media, when carrying computer-readable instructions that direct the functions of the present invention, are embodiments of the present invention. Broadly, computer-readable storage media and communications media may be referred to herein as computer-readable media.

In general, the routines executed to implement the embodiments of the invention, may be part of an operating system or a specific application, component, program, module, object, or sequence of instructions. The computer program of the present invention typically is comprised of a multitude of instructions that will be translated by the native computer into a machine-readable format and hence executable instructions. Also, programs are comprised of variables and data structures that either reside locally to the program or are found in memory or on storage devices. In addition, various programs described hereinafter may be identified based upon the application for which they are implemented in a specific embodiment of the invention. However, it should be appreciated that any particular program nomenclature that follows is used merely for convenience, and thus the invention should not be limited to use solely in any specific application identified and/or implied by such nomenclature.

FIG. 1is a block diagram that illustrates a client server view of computing environment100, according to one embodiment of the invention. As shown, computing environment100includes client computers110, network115and server system120. In one embodiment, the computer systems illustrated in environment100may include existing computer systems, e.g., desktop computers, server computers, laptop computers, tablet computers, and the like. The computing environment100illustrated inFIG. 1, however, is merely an example of one computing environment. Embodiments of the present invention may be implemented using other environments, regardless of whether the computer systems are complex multi-user computing systems, such as a cluster of individual computers connected by a high-speed network, single-user workstations, or network appliances lacking non-volatile storage. Further, the software applications illustrated inFIG. 1and described herein may be implemented using computer software applications executing on existing computer systems, e.g., desktop computers, server computers, laptop computers, tablet computers, and the like. However, the software applications described herein are not limited to any currently existing computing environment or programming language, and may be adapted to take advantage of new computing systems as they become available.

In one embodiment, server system120includes a CPU122, which obtains instructions and data via a bus121from memory126and storage123. The processor122could be any processor adapted to support the methods of the invention. The memory126is any memory sufficiently large to hold the necessary programs and data structures. Memory126could be one or a combination of memory devices, including Random Access Memory, nonvolatile or backup memory, (e.g., programmable or Flash memories, read-only memories, etc.). In addition, memory126and storage123may be considered to include memory physically located elsewhere in a server120, for example, on another computer coupled to the server120via bus121. Server120may be operably connected to the network115, which generally represents any kind of data communications network. Accordingly, the network115may represent both local and wide area networks, including the Internet.

Memory126includes a virtual world130. In one embodiment, virtual world130may be a software application that allows a user to explore and interact with an immersive environment. Illustratively, virtual world130includes virtual locations132, representing simulated locations that the user may inhabit and move through while in the virtual world130.

As shown, each client computer110includes a central processing unit (CPU)102, which obtains instructions and data via a bus111from client memory107and client storage104. CPU102is a programmable logic device that performs all the instruction, logic, and mathematical processing in a computer. Client storage104stores application programs and data for use by client computer110. Client storage104includes hard-disk drives, flash memory devices, optical media and the like. Client computer110is operably connected to the network115.

Client memory107includes an operating system (OS)108and a client application109. Operating system108is the software used for managing the operation of the client computer110. Examples of OS108include UNIX, a version of the Microsoft Windows® operating system, and distributions of the Linux® operating system. (Note, Linux is a trademark of Linus Torvalds in the United States and other countries.)

In one embodiment, client application109provides a software program that allows a user to connect to the virtual world130on server120, and once connected, to perform various user actions. Such actions may include exploring virtual locations132, interacting with other avatars, and interacting with virtual objects. Further, client application109may be configured to generate and display a visual representation of the user within the immersive environment, generally referred to as an avatar. The avatar of the user is generally visible to other users in the virtual world, and the user may view avatars representing the other users. The client application109may also be configured to generate and display the immersive environment to the user and to transmit the user's desired actions to virtual world130. Such a display may include content from the virtual world determined from the user's line of sight at any given time. For the user, the display may include the avatar of that user or may be a camera eye where the user sees the virtual world through the eyes of the avatar representing this user.

The user may view the virtual world using a display device140, such as an LCD or CRT monitor display, and interact with the client application109using input devices150. Further, in one embodiment, the user may interact with client application109and virtual world130using a variety of virtual reality interaction devices160. For example, the user may don a set of virtual reality goggles that have a screen display for each lens. Further, the goggles could be equipped with motion sensors that cause the view of the virtual world presented to the user to move based on the head movements of the individual. As another example, the user could don a pair of gloves configured to translate motion and movement of the user's hands into avatar movements within the virtual reality environment. Of course, embodiments of the invention are not limited to these examples and one of ordinary skill in the art will readily recognize that the invention may be adapted for use with a variety of devices configured to present the virtual world to the user and to translate movement/motion or other actions of the user into actions performed by the avatar representing that user within virtual world130.

In one embodiment, client application109may be configured to capture data describing the virtual locations132visited by a user of the virtual world130(e.g., a user of a particular client110). For example, when the user's avatar visits a virtual location132, the client application109may capture data describing when the visit occurred, the duration of the visit, any actions carried out by the user during the visit, the virtual location132itself, and the like. The virtual location132visited may be described in terms of, e.g., a location identifier, a street address, keywords describing the location, map coordinates, etc. The data captured by the client application109may be stored in a location history105included in the client storage104. Optionally, the data describing the virtual locations132visited by the user may be captured and stored on the server120. That is, such data may be captured by the virtual world130, and the location history105may be included in the storage123.

In one embodiment, memory126in server120may include a pattern analyzer128, representing a software application configured to analyze the movements of users to determine patterns of locations visited within the virtual world130. For example, the pattern analyzer128may analyze the location histories105of multiple users (i.e., location histories105stored in various clients110) to determine common sets of virtual locations132visited by the users. In another example, the pattern analyzer128may continually monitor the virtual world130to detect user visits to virtual locations132. When the pattern analyzer128detects a user visit, data describing the visit may be captured (e.g., an identifier for the virtual location132, when the visit occurred, the duration of the visit, any actions carried out by the user during the visit, etc.), and may be incorporated into data describing multiple locations visits.

In one embodiment, the pattern analyzer128may be configured to determine whether a particular location visit was favorable or unfavorable to the user. More specifically, the pattern analyzer128may analyze characteristics of each visit to determine if the visit was favorable (i.e., interesting, useful, enjoyable, etc.) or unfavorable (i.e., boring, unproductive, etc.) for the user. Further, the pattern analyzer128may determine a favorability rating for the visit, meaning a measure of how favorable the visit was for the user. For example, the pattern analyzer128may determine a positive favorability rating if the user spent at least a specified amount of time at the visited location, or performed at least a specified amount of activity (e.g., interaction with objects or other avatars) at the visited location. Further, the favorability rating may be increased proportionally to any time spent and/or activity performed beyond the required thresholds defining a favorable visit. Conversely, the pattern analyzer128may determine a negative favorability rating (i.e., an unfavorable visit) if the user did not spent at least a specified amount of time at the visited location, or did not perform at least a specified amount of activity at the visited location. Furthermore, in some cases, the pattern analyzer128may determine a neutral favorability rating (i.e., the visit was neither favorable nor unfavorable), or may not determine any favorability rating for the visit. Such cases may occur, e.g., if the duration of the visit is unknown, if the activities performed during the visit are unknown, etc.

In one embodiment, the data determined by the pattern analyzer128(i.e., the particular virtual location132visited, when the visit occurred, the duration of the visit, any actions carried out by the user during the visit, the favorability rating of the visit, etc.) may be stored in the location patterns125included in storage123. The location patterns125may represent a persistent data structure, such as an XML file, a database table, and the like. Optionally, the data describing each visit may be stored as a separate data record included in the location patterns125. Alternatively, the descriptive data may be stored in aggregated form within the location patterns125, for example as statistical data describing a plurality of location visits. Subsequently, location patterns125may be used by pattern analyzer128to provide descriptive information about virtual locations132that a user of virtual world130may wish to visit. More specifically, the pattern analyzer128may be configured to match the user's location history105(i.e., the locations visited by the user) to the location patterns125(i.e., patterns of locations visited by multiple users). Such matching is described in greater detail below with reference toFIG. 5. If a match is found, the pattern analyzer128may use the matching location pattern125to determine favorability information (i.e., whether a location is favorable or unfavorable) about virtual locations132that the user may visit. Such favorability information may then be presented to the user, as described below with reference toFIGS. 2A-2B.

FIG. 5is a conceptual illustration of matching a user's location history510to a location pattern550, according to one embodiment of the invention. As shown, the location history510may be composed in the form of a data table, and may include a “LOCATION ID” column520storing identifiers for virtual locations132that the user has visited, a “DATE VISITED” column521storing dates of the visits, a “VISIT DURATION” column522storing the time durations of the visits, and an “ACTIVITY TYPE” column526storing descriptions of activities performed during the visits. Further, the location pattern550may also be composed in the form of a data table, and may include a “LOCATION ID” column560storing identifiers for virtual locations132that multiple users have visited, a “NUM. OF VISITS” column562storing the number of visits to each location, and an “RATING” column564storing favorability ratings for each location. Assume that the favorability ratings stored in the “RATING” column564are defined on a numeric scale from 0 to 10, with lower numbers (e.g., “1.5”) indicating unfavorable locations, and higher numbers (e.g., “9.5”) indicating favorable locations.

In the example illustrated inFIG. 5, four location identifiers included in the location history510(e.g., location identifier “1201” included in row531) are matched (as indicated by dashed arrows) to location identifiers included in the location pattern550(e.g., location identifier “1201” included in row570). In one embodiment, such matching of locations may be performed by the pattern analyzer128illustrated inFIG. 1. More specifically, the pattern analyzer128may be configured to select one (or more) of a set of the location patterns550by matching locations to the user's location history510. For example, the pattern analyzer128may select one location pattern550that shares more locations with the user's location history510than other location patterns550. Further, the pattern analyzer128may determine that a given location pattern550successfully matches the user's location history510if predefined criteria are met. For example, a successful match may require that at least four locations are shared by the location pattern550and the location history510. Note that the location identifier “1207” included in row533is not matched in the location pattern550. In another example, a successful match may require a majority (i.e., greater than 50%) of the locations included in the location history510to be shared by the location pattern550.

In one embodiment, the pattern analyzer128may consider the age of the user's location history105in matching to a given location pattern125. For example, assume that a first location pattern125(not shown) shares two locations with the user's location history510shown inFIG. 5, namely the locations stored in rows531and533. Assume also that a second location pattern125(also not shown) shares two locations with the user's location history510, namely the locations stored in rows534and535. In order to determine which location pattern125best matches the user's location history510, the pattern analyzer128may be configured to consider the most recent locations visited by the user to be more important than older locations visited by the user. Thus, the pattern analyzer128may select the first location pattern125as the best match to the user's location history510, since the dates (stored in the “DATE VISITED” column521) of the location visits stored in rows531and533are more recent than the location visits stored in rows534and535. Further, the pattern analyzer128may be configured to delete location visits from the user's location history510after some predetermined expiration period has elapsed. For example, the pattern analyzer128may delete any data included in the user's location history510that is more than six moths old.

Once a successful match is determined, any non-matched location identifiers included in the location pattern550(e.g., location identifier “1226” included in row578, location identifier “1228” included in row579, etc.) may be used to provide information on available virtual locations132that the user may visit. For example, assume that the user's avatar is present at a first virtual location132, and from that location, the user's avatar may move to the virtual locations132represented by the location identifiers “1226” and “1228.” Since the location “1226” has a high favorability rating of “9.5,” the user may be presented with an indicator (e.g., a door, a link, a menu selection, etc.) communicating that the user may visit the location “1226,” and also communicating that this virtual location132is likely to be favorable to the user. Further, since the location “1228” has a low favorability rating of “1.2,” the user may be presented with a second indicator communicating that the user may visit the location “1228,” but also communicating that this virtual location132is likely to be unfavorable to the user.

Note that the location pattern550and the location history510shown inFIG. 5are provided for the sake of illustration, and are not intended to limit the scope of the invention. Other embodiments of the invention are also contemplated. For example, the location pattern550and the location history510may be stored together in the client computer110, or may be stored together in the server computer120. In another example, the location pattern550and the location history510may be combined into a single data structure. In yet another example, the location pattern550and/or the location history510may be modified to incorporate other data describing virtual locations132. Such modifications may be made to suit particular situations, and are thus contemplated to be in the scope of the invention.

FIGS. 2A-2Billustrate a user display200for a user participating in a virtual world, according to one embodiment of the invention. As shown inFIG. 2A, the user display200is displaying a view of a virtual plaza included in the virtual world130, with the user represented by an avatar260. The user may interact with elements displayed in user display200. For example, the user may interact with a kiosk280by operating controls built into the kiosk280, requesting information, etc. The user may also interact with other avatars270by voice communication, text messages, etc. In addition, a user may travel to different virtual locations132by moving the avatar260. In one embodiment, such movements may be performed by selecting graphical elements that automatically move the user's avatar to a new location. For example, the user may select door225(e.g., by clicking a pointing device such as a mouse). In response, the avatar260may enter a new virtual location132, namely the interior of the store220. In another example, the user may select door235, thus causing the avatar260to enter the office230.

In one embodiment, the pattern analyzer128may be configured to present indications of the favorability of locations to which the user may travel. Such indications may be presented to the user as graphical indications which may be visible in a user display of the virtual world. For example, referring toFIG. 2A, assume that the pattern analyzer128has matched the user's location history105to a given location pattern125. Assume further that the matching location pattern125includes the library210, and that the library210is described as a favorable location. Thus, the client application109may show the door215as having a highlight effect, indicating to the user that the library210is likely to be a favorable location to visit. Assume further that the matching location pattern125also includes the office230, and that the office230is described as an unfavorable location. Thus, the client application109may show the door235as having a “grayed-out” shading effect, indicating to the user that the office230is likely to be an unfavorable location to visit. Assume further that the matching location pattern125does not include the store220. Thus, the pattern analyzer128may not be able to determine whether the store220is a favorable or unfavorable location to visit. Accordingly, the door225is shown without any graphical indicators of being either a favorable or unfavorable location.

In one embodiment, a movement to a different location may be triggered by a command performed by the user, such as a menu selection, text command, voice command, etc.FIG. 2Billustrates an exemplary embodiment in which the user has performed a command (e.g., right-clicking a mouse cursor within the user display200) to invoke a pop-up menu290. As shown, the pop-up menu290includes three location links that the user may select to change locations, including a “LIBRARY” link291, a “STORE” link292, and an “OFFICE” link293. For example, if the user selects the “LIBRARY” link291, the avatar260(representing the user) may move to an interior location of the library210. Note that the “LIBRARY” link291is displayed with a highlight effect, and the “OFFICE” link293is displayed with a “grayed-out” shading effect. As in the example illustrated inFIG. 2A, such graphical indications are intended to communicate that the pattern analyzer128has determined that the library is likely to be a favorable location to visit, and the office230is likely to be an unfavorable location to visit.

Of course, one of skill in the art will recognize that favorable and unfavorable locations may be represented by a variety of graphical indications. For example, graphical indications may include symbols (e.g., arrows, icons, traffic signs, etc.), text labels, color effects, lighting effects, line or shading effects, and the like. Further, such indications may be configured to convey degrees of favorability, for example by variations, gradations, and the like.

FIG. 3is a flow diagram illustrating a method300for generating a data structure for use in providing information describing locations to a user of a virtual world, according to one embodiment of the invention. For the sake of illustration, the method300is described in conjunction with the system ofFIG. 1. Specifically, the steps of method300may be assumed to be performed by the pattern analyzer128illustrated inFIG. 1. However, persons skilled in the art will understand that any system configured to perform the steps of the method300, in any order, is within the scope of the present invention.

The method300begins at step310by receiving an indication of a user visit to a location within a virtual world (e.g., virtual world130illustrated inFIG. 1). Such indications may include an avatar (representing the user) entering a virtual location132. For example, referring toFIG. 2A, the pattern analyzer128may detect that the avatar260has walked into the library210. At step320, a record of the user's visit to the virtual location132may be created in a location history (e.g., location history105illustrated inFIG. 1). At step330, data describing the visited location may be stored in the visit record. For example, such data may include a location identifier (e.g., a street address, keywords describing the location, map coordinates, etc.). At step340, data describing the time duration of the location visit (e.g., a number of minutes) may be stored in the visit record.

At step350, data describing any activities performed by the user during the location visit may be stored in the visit record. For example, such data may include an action type (e.g., walk, operate, purchase, etc.), a degree of interaction involved in the action, and any elements of the virtual world130involved in the action (e.g., kiosk250, another avatar, etc.). At step360, a favorability rating for the user for the location visit may be determined. More specifically, the pattern analyzer128may be configured to analyze characteristics of the visit (e.g., duration of visit, number or amount of activities performed during the visit, type of activity performed, etc.) to determine a measure of how was favorable or unfavorable the visit was for the user. For example, the pattern analyzer128may determine the favorability rating based on the amount of time spent by the user at the visited location, based on a type or amount of activity performed by the user at the visited location, and the like. Once determined, the favorability rating may be stored in the visit record.

At step370, a location pattern125(i.e., an aggregated data structure describing location visits by multiple users) may be matched to the current user. For example, the pattern analyzer128may identify the location pattern125that shares the most locations in common with the current user's location history105. In another example, the pattern analyzer128may identify a location pattern125that has been previously matched to the current user.

At step380, data describing the location visit (i.e., the data determined at steps330-360) may be incorporated into the matching location pattern125. For example, the pattern analyzer128may update a location pattern125to include the same data added to the location history105. In one embodiment, the location patterns125may store data describing each location visit as a separate record. In another embodiment, the location patterns125may store data in aggregated form, for example as statistical data describing a plurality of location visits.

After step380, the method300terminates. Of course, method300is provided for illustrative purposes only, and is not limiting of the invention. It is contemplated that the steps of method300may be modified to incorporate other data describing location visits into the location history105and/or the location patterns125. Further, it is contemplated that the location history105and the location patterns125may be combined into a single data structure, which may be stored in either the client computer110or the server120. Furthermore, it is contemplated that a location pattern125may be generated by aggregating entire location histories105of multiple users at a time. For example, the pattern analyzer128may generate a new location pattern125by grouping similar location histories105(e.g., location histories105that share at least 50% of the same locations). In other examples, new location patterns125may be generated by grouping visit data for users that are included in a defined group (e.g., a user guild or association), for users that share common interests or activities, and the like. Such modifications may be made to suit particular situations, and are thus contemplated to be in the scope of the invention.

FIG. 4is a flow diagram illustrating a method400for providing information describing locations to users of a virtual world, according to one embodiment of the invention. For the sake of illustration, method400is described in conjunction with the system ofFIG. 1. Specifically, the steps of method400may be assumed to be performed by the client application109and/or the pattern analyzer128illustrated inFIG. 1. However, persons skilled in the art will understand that any system configured to perform the steps of method400, in any order, is within the scope of the present invention.

The method400begins at step410by detecting a triggering event indicating a need to present available virtual locations132to a user of a virtual world130. The triggering event may be an action or movement performed by the user. In one embodiment, a movement into a given virtual location132may trigger the presentation of graphical indications of other virtual locations132that are available for the user to visit. That is, the trigger may be an avatar's movement across a predefined threshold or checkpoint, rather than the performance of a specific action. For example, assume the avatar260(representing the user) enters the town square illustrated inFIG. 2A. This movement may trigger the client application109to present graphical indications of available virtual locations132that the user may move to next, namely doorways to the library220, store220, and office230. In another embodiment, an action or command performed by the user may trigger the presentation of graphical indications of available virtual locations132. For example, as illustrated inFIG. 2B, the user may perform a command (e.g., right-clicking a mouse cursor) to invoke a pop-up menu providing links to available virtual locations132.

At step420, the user's location history105may be matched to a location pattern125. That is, the virtual locations132visited by the user (described by the location history105) may be matched to a predefined set of virtual locations132visited by multiple users (described by a location pattern125). In one embodiment, the location pattern125may be generated by using the method300described above. The pattern analyzer128may determine a successful match if the location pattern125shares at least a predefined number of the virtual locations132included in the location history105. For example, referring toFIG. 5, the pattern analyzer128may determine that the location pattern550matches the location history510because they share four locations. Of course, the pattern analyzer128may also determine a successful match based on other criteria, for example if the location pattern125shares at least a predefined percentage of the virtual locations132included in the location history105, the age of the user visits to the virtual locations132included in the location history105, and the like.

At step430, the pattern analyzer128may determine any virtual locations132included in the location pattern125that are available to the user's avatar (i.e., locations that the avatar can currently travel to). For example, referring toFIG. 5, the pattern analyzer128may determine that the locations “1226” and “1228” are included in the location pattern550, and are also currently available to the user's avatar. In one embodiment, the virtual locations132available to the user's avatar may be limited by access privileges of the user (e.g., security permissions within the virtual world130).

At step440, the pattern analyzer128may determine favorability ratings for the available locations included in the location pattern125. That is, the pattern analyzer128may determine a measure of how favorable each available location is likely to be if the user visits the location. In one embodiment, the favorability ratings may be stored in the location pattern125, and may reflect the favorability of previous visits to a given location by multiple users. For example, referring toFIG. 5, row578of the location pattern550stores a favorability rating of “9.5,” indicating a high favorability rating for the location “1226.” The favorability ratings stored in the location pattern125may be based on, e.g., the amount of time spent by users at each location, the type or amount of activity performed by users at each location, and the like.

At step450, the available locations may be presented along with favorability indicators. For example, referring toFIG. 2A, the client application109may present the user (in the user display200) with the door215, indicating that the user may move the avatar260into the library210. As described, the door215is shown with a highlight effect to indicate to the user that the library210has a high favorability rating, and is thus likely to be a favorable virtual location132for the user to visit. Also, the door235is shown with a “grayed-out” shading effect to indicate to the user that the office230has a low favorability rating, and is thus likely to be a unfavorable virtual location132for the user to visit. After step450, the method400terminates.

While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.