Assisted navigation in virtual environments

• US 8,832,599 B2
• Filed: 10/03/2008
• Issued: 09/09/2014
• Est. Priority Date: 10/03/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Deb, Soumyajit
• Primary Examiner(s): HAILU, TADESSE
• Application Number:
  US12/245,577
• Publication Number:
  US 20100087257A1
• Time in Patent Office: 2,167 Days
• Field of Search: 715548-851, 463/43, 463/1
• US Class Current: 715/848
• CPC Class Codes: A63F 13/45 Controlling the progress of the video game
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics

Abstract

Navigational data may be collected from experienced users and paths may be extracted from the navigational data. One or more points of interest may be identified in the navigational data and the points of interests may be merged into an interest region. The navigational data may be reviewed for interest paths between the interest regions. The collection of possible interest paths may be reviewed interest paths in view of statistical procedures and criteria to determine if the interest path is a preferred interest path. If the preferred interest path does not satisfy the predefined constraints, additional interest paths may be reviewed by substituting an additional interest path for the interest path and repeating the review the interest path analysis. If the preferred interest path satisfies predefined criteria, a walkthrough of the virtual world may be generated based on the preferred interest path.

Claims

1. A method performed by at least one computing device, the method comprising:

collecting, in a gaming environment, a log of locations previously visited by users;

extracting paths from the log of locations;

identifying a plurality of points of interest along the extracted paths;

merging the plurality of points of interests into interest regions, wherein each interest region includes a collection of points of interest located within a defined distance of each other;

identifying interest paths between the interest regions;

reviewing the interest paths in view of a statistical procedure to determine a preferred interest path according to a statistical measure;

determining whether the preferred interest path satisfies a predefined constraint;

in a first instance where the preferred interest path does not satisfy the predefined constraint, substituting an additional interest path for the preferred interest path and repeating the determining; and

in a second instance where the preferred interest path satisfies the predefined constraint, generating a walkthrough path of the gaming environment based on the preferred interest path.

2. The method of claim 1, wherein an individual point of interest is derived from time-marks that indicate the users lingering or obtaining additional assistance.

3. The method of claim 1, wherein the predefined constraint comprises limitations based on a geographic structure.

4. The method of claim 1, wherein the predefined constraint comprises limitations based on user travel preferences.

5. The method of claim 1, wherein the predefined constraint comprises limitations based on a need of an individual user in an application.

6. The method of claim 1, wherein the statistical procedure further comprises determining the preferred interest path based on a minimum time.

7. The method of claim 1, wherein the statistical procedure further comprises determining the preferred interest path based on a minimum distance.

8. The method of claim 1, wherein the statistical procedure further comprises determining the preferred interest path based on a minimum time and a maximum number of points of interest.

9. The method of claim 1, further comprising displaying a subset of the interest paths to an individual user and permitting the user to select the preferred interest path.

10. The method of claim 9, further comprising displaying relevant data about the subset of the interest paths.

11. The method of claim 1, wherein an individual point of interest includes an individual location about which one of the users gathered additional information.

12. A computer storage volatile or nonvolatile memory comprising computer executable code that, when executed by a computer processing unit, causes the computer processing unit to perform acts comprising:

extracting virtual paths from virtual navigational data associated with a virtual environment, wherein the virtual navigational data identifies various virtual locations in the virtual environment that were visited by previous users of the virtual environment that traveled along the virtual paths within the virtual environment;

identifying virtual points of interest along the virtual paths by determining, based on the virtual locations in the virtual navigational data, that the previous users stopped or paused at the virtual points of interest when travelling along the virtual paths;

merging the virtual points of interest into a plurality of virtual interest regions using a region growing algorithm;

deriving a plurality of virtual interest paths between the plurality of virtual interest regions; and

creating a virtual walkthrough path by selecting one of the plurality of virtual interest paths based on a predefined constraint.

13. The computer storage volatile or nonvolatile memory of claim 12, wherein the predefined constraint comprises limitations based on at least one of:

a geographic structure;

a set of user travel preferences; and

a user need in an application.

14. The computer storage volatile or nonvolatile memory of claim 12, the acts further comprising:

determining that individual previous users gathered additional goods or information at corresponding individual virtual locations identified in the virtual navigation data; and

designating the individual virtual locations where the individual previous users gathered the additional goods or information as individual virtual points of interest.

15. The computer storage volatile or nonvolatile memory of claim 12, wherein the virtual locations are represented in the virtual navigation data as corresponding map tiles.

16. The computer storage volatile or nonvolatile memory of claim 12, the acts further comprising:

deriving an individual virtual interest path that ends in an individual virtual interest region.

17. A computer system comprising:

a processing unit; and

a memory in communication with the processing unit and storing computer executable instructions,

wherein the computer executable instructions cause the processing unit to;

extract a plurality of virtual paths from virtual navigational data, wherein the virtual navigational data identifies various virtual locations in a virtual environment that were visited by previous users of the virtual environment;

identify virtual points of interest along the virtual paths by determining, based on the virtual locations in the navigational data, that the previous users of the virtual environment stopped or paused their movement at the virtual points of interest when travelling along the virtual paths;

merge the virtual points of interest into a plurality of virtual interest regions;

derive a plurality of virtual interest paths between the plurality of virtual interest regions; and

select an individual virtual interest path to guide a new user of the virtual environment.

18. The computer system of claim 17, wherein the computer executable instructions cause the processing unit to:

derive the selected individual virtual interest path by identifying a most commonly traveled path used by the previous users of the virtual environment to travel between two virtual interest regions.

19. The computer system of claim 17, wherein the computer executable instructions cause the processing unit to:

use the selected individual virtual interest path for a walkthrough of the new user through the virtual environment.

20. The computer system of claim 17, wherein the computer executable instructions cause the processing unit to:

determine that individual previous users of the virtual environment gathered additional virtual goods at corresponding individual virtual locations identified in the virtual navigation data; and

designate the individual virtual locations where the individual previous users gathered the additional goods as individual virtual points of interest.

21. The computer system of claim 17, wherein the computer executable instructions cause the processing unit to:

designate at least some of the previous users as expert users of the virtual environment and use corresponding virtual navigational data for the expert users to identify the virtual points of interest.